Note [Allocator sizes]
Our choice of allocator sizes has to balance several considerations: - Allocator sizes should be available for the most commonly request block sizes, in order to avoid excessive waste from rounding up to the next size (internal fragmentation). - It should be possible to efficiently determine which allocator services a certain block size. - The amount of allocators should be kept down to avoid overheads (eg, each capability must have an allocator of each size) and the risk of fragmentation. - It should be possible to efficiently divide by the allocator size. This is necessary to implement marking efficiently. It's trivial to efficiently divide by powers of 2. But to do so efficiently with arbitrary allocator sizes, we need to do some precomputation and make use of the integer division by constants optimisation. We currently try to balance these considerations by adopting the following scheme. We have nonmoving_alloca_dense_cnt "dense" allocators starting with size NONMOVING_ALLOCA0, and incrementing by NONMOVING_ALLOCA_DENSE_INCREMENT. These service the vast majority of allocations. In practice, Haskell programs tend to allocate a lot of small objects. Other allocations are handled by a family of "sparse" allocators, each providing blocks up to a power of 2. This places an upper bound on the waste at half the required block size. See #23340
References 0
This Note does not link to any other.