Re: [TUHS] UUCP Maps

On Mon, Aug 25, 2014 at 06:36:17PM -0400, John Cowan wrote: Good old pathalias. I've got a story for you there, Clem (he's Masscomp right?) might get a grin out of it. I was sys admin for 20 users on a Masscomp machine that had a 40MB disk. We were at the end of a dog leg in UUCP, ...!uwvax!geophys!geowhiz!$user, and could easily see the appeal in user(a)host.whatever. When I ran pathalias it generated a 2MB (or more) sized file. Way too big for our disk. So I walked across the street to talk to my alg prof (Udi Manber, he was A9, ran search at google, he's a smart cookie, I was not). He listened to the problem and quickly said "You've got time best cast and space worst case" and described how you would change the system to do a lookup for each host in turn (the furthest host returns the next closer host and so on). That gets you space best case, time worst case. I got it, I saw how to write that code, and I say thanks and head out the door. "Not so fast" says Udi. "What would be really interesting is if you could approximate both space and time best case". Which lead to about a 6 month (or more) programming effort on my part (it's a graph problem and a dynamic programming problem) and a paper for IEEE. The fun part about that project was that Udi was all theory and I was all practice. I was reading the maps in and building the graph on a microvax with not a lot of ram, might have been 4MB, might have been less. For some reason that escapes me I had to sort them and I used qsort() and it took overnight. I went to Udi and told him about it and he asked what sort I was using and I said qsort(). "Oh, that explains it, you need to use a radix sort". Stupid me slinks out to figure what a radix sort was, did so, implemented it, it got slower! WTF, right? So I poked around, this was my first journey into performance debugging, vmstat was a useful tool then (and now). I eventually discovered that the machine was swapping like crazy and I poked some more. After much poking I decided I was fragmented and it was malloc()s fault. Wrote my own malloc that allocated 400K at a time and did all my strdup()s into there. Sort time, with qsort, when from overnight to 20 minutes. Go practice, eh? I like to think that while Udi taught me all about the theory (and he did, I flunked his class at least twice before I passed), I taught him about practice. VM != real memory for example. He's also the guy who watched me jump every time xclock chimed on the hour and asked why? I told him it sounded exactly the same as the beep on my radar detector (I was a kid, I drove way too fast). After that every time in chimed and I jumped he'd laugh and say "you're hacking too fast" :) --lm P.S. Is Honeyman still around? I haven't seen him in years, we met in person at usenix and he promptly dragged me outside to smoke a spliff. Fun guy, last I heard he was running a research lab in Michigan. Oh, yeah. Googled, he's still there.