[pool] severe overhead with unaligned sizes.

[phrosty@…]

Pool will set the size of allocated blocks to the least common multiple of the requested size and LCM(sizeof(void*), sizeof(size_t)).

Request a block size of 1500 on a 32-bit system and you get 1500 byte blocks. Request 1501 bytes and you get 6004 byte blocks - and the extra space isn't ever used. It is obviously even more pronounced on a 64-bit system.

I believe the intent of the author was to align block sizes, not to use LCM. I propose changing pool.hpp:183 from

return details::pool::lcm<size_type>(requested_size, min_size);

to

return requested_size + (min_size - 1) & ~(min_size - 1);

[cnewbold@…]

I see the milestone for this is set to 1.35.0; does that mean that a fix for this problem has been (or will be) included in the upcoming release?

[Marshall Clow]

No - this fix did not make in into 1.35. I need to write a test case to make sure that this does, indeed, fix the problem. Unless you would like to write one? ;-)

[Marshall Clow]

Reading the design documents at http://www.boost.org/doc/libs/1_36_0/libs/pool/doc/implementation/alignment.html, I'm not convinced that you are correct.

Please read that page and tell me what you think.

[Chris Newbold]

Here are my thoughts...

I believe that the design outlined in the linked documents is sound, including the use of LCM to find the chunk size which will satisfy the alignment requirements of the free list pointer and block size.

The problem with the original design is using requested_size in the LCM computation. Just because I asked for chunks of X bytes does not mean that each chunk must be aligned on an X byte boundary.

Predicate 2 of the "Guaranteeing Alignment" document quotes language from 5.3.4/10 of the C++ standard indicating that memory obtained in a 'new' expression must be aligned on a boundary that is a multiple of that required by the type with the most stringent alignment requirement. On most platforms, this is going to be double, or long long, or maybe long double.

The point being that the "worst-case" scenario is that the programmer tries to lay down a structure at the start of a chunk obtained from the pool and that structure has an element of such a type.

This is exactly what malloc() or operator new() does. I do not think that the pool needs to do anything more.

The proposed change in this ticket, however, is not correct. It does not account for the possibility that some type may have a more stringent alignment requirement than the free-list pointer and/or block size value.

[Chris Newbold]

As an aside, a couple of months back I stepped up and volunteered to take owner maintainership of Boost.Pool since it appeared to have been orphaned. If you'd like to wash your hands of this, just assign the ticket to me. :)

[anonymous]

Sorry, I just got around to seeing this. I agree with cnewbold.

I think the alignment should be align(max(min_size, min(requested_size, sizeof(max_type))), 2).

I'm not familiar with other platforms but on x86/x64, sizeof(max_type) is now 32 bytes (for the new AVX instructions from Intel).

[Chris Newbold]

What is max_type?

After some further thought, I think that a clean solution would be to leverage alignment_of from Boost.Typetraits.

Change:

return details::pool::lcm<size_type>(requested_size, min_size);

to:

return details::pool::lcm<size_type>(alignment_of(requested_size), min_size);

[Chris Newbold]

Marshall--

I'm currently in the pool code fixing several other tickets and, if you like and if you think that my suggested fix above is correct, I'd be happy to apply it and write some test cases. Let me know... Thanks.

[Marshall Clow]

Works for me - especially the tests. Pool seems to be lacking in tests. ;-)

[Chris Newbold]

Not going to make 1.37; the changes are somewhat delicate and I'd like to have some bake time before releasing.

[klin <kevin.ic@…>]

Would it be more efficient to simply ignore the alignment requirements for the pointers, and just copy in and out of the memory using aligned addresses before using them?

So we can always allocate in multiples of requested_size (large enough to cover min_size). Then, to access embedded data such as the next pointer, we can do:

void* get_nextof(void const* ptr)
{
 void* p;
 memcpy(&p, ptr, sizeof(void*));
 return p;
}

Seems like the copying penalty would be worth it for a more reasonable overhead.

[John Maddock]

(In [68922]) Add test case for issue #1252. Refs #1252.

[John Maddock]

(In [69235]) Fixes issue #1252. Add test case for #1252. Update docs accordingly. Refs #1252. Correct return value from test_pool_alloc.cpp.

[John Maddock]

(In [73495]) Merge updated Pool lib from trunk. Fixes #1252. Fixes #2696. Fixes #4960. Fixes #5526. Fixes #5568. Fixes #5700.