7/01/2008

07-01-08 - 1

I have this big MP3 dir. When I do a recursive list on it, it takes literally 60 seconds to grind the disk, and I can hear the disk churning like crazy. Just the first time, of course, after that it's in cache (for a little while anyway, urgh).

Hang on now. We sort of take this for granted that that's reasonable, but it's 100% not reasonable.

I almost never write those files, but I read them often and list the contents often. The layout of those files on disk could be totally optimized for recursive listing. In particular, all the directory descriptors for all the subdirs could be packed on disk immediate contiguously, so that to do a full recursive list it's just one single fast continuous hardware read and blammo I have it all.

Obviously you can't do that for dirs you're changing a lot all the time, but for the vast majority of dirs that are semi-static, the content listing could be laid out far better.

I wrote before about another common case where NTFS is badly broken : the "log file" usage pattern where you're doing lots of appends and flushes. (it frags the hell out of files in that case)

This stuff is designed by smart people, but that doesn't mean it's perfect. I get a feeling a lot of these Smart People are too theoretically rigorous; they look at mean behavior and big O()'s and malicious attack usage patterns. I see the same thing with Google Search, and of course I would see the same thing a lot when reviewing my guy's work at OddWorld or anywhere else. Hey, that algorithm sounds good on paper and all, but look I can see the way we're actually using it and this behavior I'm seeing is not ideal, so let's fix the case that's actually being used.

A lot of Smart People fail the "human in a cage test". With any piece of software I imagine instead of a computer I have a guy inside a box with slots where we can pass data to each other. I ask myself, if I had a human in a box, how would he solve this problem? Would he do better than my software? If so, my software can do better.

There's another point that's actually very important. It that's the usage pattern and the algorithm are not seperable. Smart People, even those who take the good step of studying typical usage patterns and tailoring the algorithm to typical usage, make the mistake of treating the usage as this external force that's constant and not responsive to the algorithm. Of course that's not true. The users are human and will change their behavior to suit the algorithm.

You can see this of course in memory allocators. If you're considering swapping in some different allocator, you might look at your current usage pattern and pick the allocator that gives you the best improvement for your current usage. But your usage need not be held constant. For each allocator choice you should consider what you could win if you changed your usage slightly.

At something like the operating system level, it's usually a win to make typical usage slightly worse if you can provide an easily acheived fast path. If people know there is a certain behavior that will give them a fast path, they will change their workflow slightly to use the fastpath. The {user,algorithm} system is tied and they should respond to each other; the user is not held as constant over changes of algorithm.

For example, with our NTFS file system case, if I knew there was a certain way to use it to avoid fragmentation and have fast dir listings, I could change my usage to do that. In reality, NTFS is just really old and seems semi-broken.

This is extremely obvious of course, but people often miss it. If you provide some new allocator that has a much faster fast path, there will no doubt be objections that it doesn't actually optimize the current usage pattern. Yes, true, but the usage pattern can change!!

BTW, how to get Lie and Lay right.

BTW #2, Hardware designers seem to suffer almost the exact opposite problem, which is they just don't give a damn about usage at all, they just do whatever is good for the hardware and figure people can adapt their software to work in the new way. This of course isn't wise either, you need to optimize the joint {user,algorithm} system.

No comments:

old rants