Re: [TUHS] mh/hm, mmh (was: fmt(1): history, POSIX, -t, -c)

On Sun, May 31, 2020 at 12:25:47PM -0400, Richard Salz wrote: My first real research paper was with Udi Manber and it was all about compressing the pathalias maps. I had them on a 40MB disk on a Masscomp that had 20 users. The format was seismo.css.gov geowhiz!geophiz!uwisc!ihnp4!mirror in other words destination path!to!get!there I went to Udi and explained that all of our stuff started with geowhiz!geophiz!uwisc so that string was replicated over and over and it took too much space. Once Udi understood the problem he went "You have time best case, space worst case, you can reverse them like so" seismo -> mirror mirror -> ihnp4 ihnp4 -> uwisc uswisc -> geophiz geophiz -> geowhiz and you'll have time worst case and space best case. I was like "oh, yeah, you are right, cool, thanks" and got up to leave. Not so fast, says Udi, that's not "interesting". What would be interesting is if you could approximate time best case and space best case. With that, I started down the only dynamic programming problem I have ever solved. Udi's idea was to break the graph at what he called pivot points, where the pivot points as much as possible got rid of the replicated strings. He also wanted to limit lookups to just 2. So I had to read in the maps and build a graph from them on my creaky microvax with 4MB of ram. Doing so lead me to the first place I taught Udi about systems. I was fgets() each line and mallocing a copy of it. Then I sorted with qsort() and it took overnight to get the sorted array. Udi asked what sort? Qsort. Oh, that's garbage, use a radix sort, that will be better. WTF is a radix sort, look that up, implemented it, it was worse. So I start poking around and somehow realized we were thrashing VM, we didn't fit, and I have no idea how I figured out that malloc was fragmenting memory but I did. Probably figured out that most of my program was backed by swap, not files, and that's usually malloc or brk. So I wrote my own malloc that grabbed memory in 300KB chunks (why that size, I dunno, seemed right). Then I allocated memory out of those chunks. Got rid of the fragmentation and we fit in 4MB. qsort worked fine, took about 20 minutes (we didn't really fit but we were way closer). Udi was watching as I was doing all this, I think I was working in his office, it was his microvax. The fragmentation thing taught him that when Unix says it has virtual memory and you can just use it, it only works well when you fit. So the programming problem turned out that you calculated the space it work take for every possible pivot point and then at the end, you took the set that gave you the minimum space. We wrote, heh, who am I kidding, Udi wrote, a paper about it. I was still green on writing papers, they were hard for me. I told Udi that and he stared at me blankly and said "Writing papers is easy if you know the content. You just make a good outline and fill it in." He's right, that's how you do it, and it is easy if you know and can make the outline. I went on to do a lot of work with/for him. I wrote a user level thread library that made me write swtch() in assembler for the VAX (I believe I did a 68K version too but the source I have is VAX only). I "cheated" and did 99% of the work in C and popped down the rabbit hole to assembler, did the nasty, and popped back out as a different thread. 112 lines: http://www.mcvoy.com/lm/T/src/Tasm.S Funny Udi story, I was young and wild and drove too fast and got tickets. So I got a radar detector that beeped when it saw the radar gun. Udi upgraded the microvax to some newer release of X10 or X11 and the new xclock beeped on the hour. Every time it beeped, I jumped because it sounded just like the radar detector. Udi asked about it, I explained, he laughed and said "Larry, you're hacking too fast" each time I jumped :) Good times. I almost did a PhD under him but I didn't care for the CS department at Tucson where he went and I liked industry too much.