]> git.ipfire.org Git - thirdparty/gcc.git/commit
Use optimize free lists for alloc_pages
authorAndi Kleen <ak@gcc.gnu.org>
Tue, 1 Apr 2025 22:37:39 +0000 (15:37 -0700)
committerAndi Kleen <ak@gcc.gnu.org>
Fri, 23 May 2025 22:24:09 +0000 (15:24 -0700)
commit725063bc1fda6b0403a8b72fce3b4c9cc6a4ba3a
tree0cc313f0a757525f3fa29076cf112b8ab93cdd4c
parent2f7802783034ad8611e1d25a4aec057d44c96720
Use optimize free lists for alloc_pages

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.
gcc/ggc-page.cc