Right now ggc has a single free list for multiple sizes. In some cases
the list can get mixed by orders and then the allocator may spend a lot
of time walking the free list to find the right sizes.
This patch splits the free list into multiple free lists by order
which allows O(1) access in most cases.
It also has a fallback list for sizes not in the free lists
(that seems to be needed for now)
For the PR119387 test case it gives a significant speedup,
both with and without debug information.
Potential drawback might be some more fragmentation in the memory
map, so there is a risk that very large compilations may run into
the vma limit on Linux, or have slightly less coverage with
large pages.
For the PR119387 test case which have extra memory overhead with -ggdb:
../obj-fast/gcc/cc1plus-allocpage -std=gnu++20 -O2 pr119387.cc -quiet
ran 1.04 ± 0.01 times faster than ../obj-fast/gcc/cc1plus -std=gnu++20 -O2 pr119387.cc -quiet
2.63 ± 0.01 times faster than ../obj-fast/gcc/cc1plus-allocpage -std=gnu++20 -O2 pr119387.cc -quiet -ggdb
2.78 ± 0.01 times faster than ../obj-fast/gcc/cc1plus -std=gnu++20 -O2 pr119387.cc -quiet -ggdb
It might also help for other test cases creating a lot of garbage.
gcc/ChangeLog:
PR middle-end/114563
PR c++/119387
* ggc-page.cc (struct free_list): New structure.
(struct page_entry): Point to free_list.
(find_free_list): New function.
(find_free_list_order): Dito.
(alloc_page): Use specific free_list.
(release_pages): Dito.
(do_release_pages): Dito.
(init_ggc): Dito.
(ggc_print_statistics): Print overflow stat.
(ggc_pch_read): Use specific free list.