llvm-project.git/libc/src/__support/freelist.cpp, branch users/nico/python-2

[libc][NFC] Remove template arguments from Block (#117386)

2024-11-22T23:33:18+00:00

Reapply "[libc] Use best-fit binary trie to make malloc logarithmic (#117065)"

2024-11-21T23:26:24+00:00

This reverts commit 93b83642ee34d0092b94776728dad0117c2b72a1.

 - Correct riscv32 assumption about alignment (bit of a hack).
 - Fix test case where the largest_small and smallest sizes are the
   same.

Revert "[libc] Use best-fit binary trie to make malloc logarithmic (#117065)"

2024-11-21T19:56:05+00:00

This reverts commit b05600d96f46697e21f6b1b7ad901391326243a8.
riscv32 unit test still broken

Reapply "[libc] Use best-fit binary trie to make malloc logarithmic" (#117065)

2024-11-21T19:30:51+00:00

 - Fix assertion expressions.
 - Fix incorrect small size in freestore_test.
 - There may only be one small size for high alignment and small
   pointers (riscv32).
 - Don't rely on stack alignment in FreeList test.

Revert "[libc] Use best-fit binary trie to make malloc logarithmic" (#117065)

2024-11-20T22:00:07+00:00

Reverts llvm/llvm-project#106259

Unit tests break on AArch64.

[libc] Use best-fit binary trie to make malloc logarithmic (#106259)

2024-11-20T21:54:00+00:00

This reworks the free store implementation in libc's malloc to use a
dlmalloc-style binary trie of circularly linked FIFO free lists. This
data structure can be maintained in logarithmic time, but it still
permits a relatively small implementation compared to other
logarithmic-time ordered maps.

The implementation doesn't do the various bitwise tricks or
optimizations used in actual dlmalloc; it instead optimizes for
(relative) readability and minimum code size. Specific optimization can
be added as necessary given future profiling.