[TUHS] UUCP Maps

[A. P. Garcia]

On Aug 25, 2014 7:52 PM, "Larry McVoy" <lm at mcvoy.com> wrote:
>
> On Mon, Aug 25, 2014 at 06:36:17PM -0400, John Cowan wrote:
> > Lyndon Nerenberg scripsit:
> >
> > > Then we should see about getting them to Warren for the archives.
> > > They are a part of "internet" history that should never be lost.
(Along
> > > with the code for pathalias.)
> >
> > Pathalias is distributed as part of Smail 3 in the pd/pathalias
directory.
>
> 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 at 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

but...what was the final size of the file?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20140825/20a57bfe/attachment.html>