Saturday, June 03, 2006
Another Random Factoid
Yeah, that's more or less how the LFH works, with one key difference: the LFH is mostly lock-free. It's actually similar to but a bit simpler than the one I was going to implement. They also cheat a little: the list of partially filled reserve blocks is protected by a mutex. The allocator I was going to write didn't use a mutex there, because it used some tricky lock-free voodoo. I'm not sure whether or not the lock-free voodoo is worth the trouble - it will be slower when there's no contention, but faster when multiple threads are trying to access the same list. I'm not sure exactly how common an event that will be, though, since most allocations will come out of the current block, and the partial block list is only used when the current block gets full (essentially two threads would have to try to allocate a block from the same zone at the same time, when the current block is full).