search

microsoft / mimalloc

mimalloc is a compact general purpose allocator with excellent performance.
MIT License
9.74k stars 791 forks source link

oversize allocation in mi_heap_malloc_zero_aligned_at #889

Closed romange closed 1 month ago

romange commented 1 month ago

mi_heap_malloc_aligned(160, 8) returns a block from page with size 192 due to, what seems as suboptimal logic for computing the block size.

Expected - allocation of size=160.

Specifically, in mi_heap_malloc_zero_aligned_at(..., alignment=8) we are checking if mi_likely(page->free != NULL && is_aligned) , so for the first allocation of this size, we fallback to mi_heap_malloc_zero_aligned_at_fallback which unconditionally sets oversize = size + alignment -1=167. This, in turn it forces to allocate the page with bin size on step larger.

It can be trivially fixed for alignment=8 since it should be a noop contstraint but I think it could also be fixed for cases, where size % alignment

romange commented 1 month ago

In fact, mi_heap_malloc_zero_aligned_at always goes through the same route:

  1. tries to allocate 160 bytes page, reaches _mi_page_empty
  2. checks that it's empty and goes through the flow that allocates a 192 block in 192 bytes page.
  3. The next 160 byte allocation will again hit an empty page and will follow the same route.

If we would allocate a 160 bytes page before calling mi_heap_malloc_aligned, it would allocate all these allocations through the existing 160 bytes page.

daanx commented 1 month ago

Thanks! Looking into this now.

daanx commented 1 month ago

Ah, I think you see these results because you build in debug mode, with padding enabled. If you build with -DMI_NO_PADDING=ON you will see it allocates correctly. This is due to the test:

(offset == 0 && alignment <= padsize && padsize <= MI_MEDIUM_OBJ_SIZE_MAX && (padsize & align_mask) == 0)

in mi_heap_malloc_zero_aligned_at_fallback.

daanx commented 1 month ago

I just pushed a refactoring of the aligned allocation code that simplifies things and makes this more apparent. Thanks!

romange commented 1 month ago

Hi @daanx , we already compile mimalloc without padding and I agree padding is one of the reasons but it's not the only one.

I am pretty sure the behavior of mimalloc changes if the page with required size already existed or if it's a new one. I will double check everything tomorrow and will send you the reproducing example.

romange commented 1 month ago

@daanx we used 2.1.4 where the condition was if (offset==0 && alignment<=padsize && padsize<=MI_MAX_ALIGN_GUARANTEE && (padsize&align_mask)==0) note MI_MAX_ALIGN_GUARANTEE and not MI_MEDIUM_OBJ_SIZE_MAX

so for allocations of 160 bytes, this condition does not hold.