Harry Sintonen wrote: > pagealign code (lib/pagealign_alloc.c) has a mistake whereas USE_MMAP code > uses the linked list to maintain the memory allocations. This is unnessary > as mmap() always returns memory aligned to the page size. Thus the buffer > could be passed as-is, similar to what HAVE_POSIX_MEMALIGN code is doing. > > This suboptimal USE_MMAP code leads to serious performance regressions for > example with CVS 1.12.12 and later (earlier CVS versions did not use > pagealign and are thus unaffected). CVS also uses a list to maintain send > buffers. While pagealign code uses insert-to-head, the buffer list in CVS > are insert-to-tail. This combination leads to extremely expensive buffer > deallocation loops where CVS hogs 100% of the CPU for hours on end. We've > seen checkout of large repository to take over 2 hours.
Looking at the actual code: https://sources.debian.org/src/cvs/2:1.12.13+real-30/src/buffer.c?hl=111#L250 The function buf_free_datas, which is the only function that invokes pagealign_free here, frees them in first-to-last order. And gnulib's linked list - stores the blocks in last-to-first order, - in pagealign_free, searches for a block in the same order. So, yes, this is O(N²) behaviour. As a workaround, I would propose that you change buf_free_datas to call pagealign_free in last-to-first order. Then it will become O(N), without needing any further work in Gnulib. Recall that 'cvs' is the only user of this module currently: https://codesearch.debian.net/search?q=%3D+pagealign_alloc&literal=1 https://codesearch.debian.net/search?q=%3D+pagealign_xalloc&literal=1 Bruno
