Paul Eggert wrote:
> > A red-black tree, for example, would probably fix the performance
> > of get_memnode.
>
> My thought is to not worry about it. If we head in that direction then
> next thing, we might want it to be thread-safe, and the thing after
> that, we might want it to be high-performance multithreaded, and before
> we know it we have lots more lines of code to maintain. That's overkill
> for this particular problem. Simplicity is good here, so let's just rely
> on the underlying libraries instead. And if that means we gotta use
> malloc and waste a page per allocation then let's do that.
I heavily disagree about all this.
1) When a library offers a memory allocation primitive, it should attempt
not to waste memory. Memory is a limited resource, especially on servers
where 'cvs' is running. Even if the kernel may ultimately swap out the
wasted page out of RAM and use that RAM for more useful things, it still
stresses the machine.
IMO, not wasting memory should be priority #1 here, before simplicity
or multithread-safety. ('cvs' is not a multithreaded program.)
2) No one has asked for an MT-safe implementation of pagealign_alloc.
The current implementation with its linked list is not MT-safe.
No one has asked for "high performance". Only an O(N²) scalability
problem has been reported, and it is still there, on some platforms.
3) The solution to combined requirements (such as, scalability and
MT-safety at the same time) can be done by combining the building
blocks that people learn at university. For scalability, the main
helper are container data structures (instead of linked lists like
in 1960). For MT-safety, the building blocks are the locks (POSIX
calls them mutexes). They have been standardized in ISO C for a reason.
With these building blocks, the solution becomes simple. No one
is asking for a complex solution based immediately on mmap() and futex().
4) What is generally requiring "lots more lines of code to maintain", is
a requirement for async-signal safety, i.e. the ability to use the
facility from a signal handler. But no one has asked for it, regarding
pagealign_alloc.
Bruno
