Re: [bug-gnulib] valloc()?

[Bruno Haible]

Derek Price wrote:
> Why do you prefer mmap to posix_memalign?

Yes, if posix_memalign exists, it can probably be used instead of mmap.
But since the only known platform having it is glibc, and on glibc it
wastes even more memory than your simple valloc(), I would prefer raw mmap().

This simple program (on x86)

#include <stdlib.h>

int main () {
  void* p;
  posix_memalign(&p, 4096, 2*4096);
  posix_memalign(&p, 4096, 10*4096);
  posix_memalign(&p, 4096, 100*4096);
  return 0;
}

produces this strace:

brk(0)                                  = 0x8049580
brk(0x804a580)                          = 0x804a580
brk(0)                                  = 0x804a580
brk(0x804b000)                          = 0x804b000
brk(0)                                  = 0x804b000
brk(0x804d000)                          = 0x804d000
brk(0)                                  = 0x804d000
brk(0x8058000)                          = 0x8058000
mmap2(NULL, 417792, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 
0x40156000

I.e. when asked for 2 pages, it allocates 2 pages.
     when asked for 10 pages, it allocates 11 pages.
     when asked for 100 pages, it allocates 102 pages.

> it strikes me that my
> bookkeeping for mmap could slow things down if many blocks were
> allocated (I'm storing the ptr->size map in a simple linked list, but
> even something more efficient would eventually slow).

There's a GPLed implementation of red-black trees in the Linux kernel.
Red-black trees, like AVL trees, have an O(log N) worst case runtime for
lookup, insertion, removal. I don't consider this "slow".

Bruno