Boost C++ Libraries: Ticket #1252: [pool] severe overhead with unaligned sizes.

component changed; owner set

Marshall Clow — Wed, 21 Nov 2007 00:12:00 GMT

owner set to Marshall Clow
component None → pool

cnewbold@… — Thu, 27 Mar 2008 13:14:26 GMT

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 — Tue, 01 Apr 2008 22:16:47 GMT

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? ;-)

status, milestone changed

Marshall Clow — Wed, 17 Sep 2008 03:08:34 GMT

status new → assigned
milestone Boost 1.36.0 → Boost 1.37.0

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.

cc set

Chris Newbold — Mon, 22 Sep 2008 20:18:31 GMT

cc Chris Newbold added

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 — Mon, 22 Sep 2008 20:25:08 GMT

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 — Mon, 22 Sep 2008 20:50:25 GMT

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 — Tue, 23 Sep 2008 14:52:07 GMT

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 — Mon, 29 Sep 2008 20:34:30 GMT

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.

owner, status changed

Marshall Clow — Mon, 29 Sep 2008 21:03:08 GMT

owner changed from Marshall Clow to Chris Newbold
status assigned → new

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

status, milestone changed

Chris Newbold — Wed, 08 Oct 2008 15:59:43 GMT

status new → assigned
milestone Boost 1.37.0 → To Be Determined

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

cc changed

Sat, 02 May 2009 10:03:44 GMT

cc kevin.ic@… added

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.

cc changed

John Maddock — Fri, 07 Jan 2011 11:21:00 GMT

cc boostpool@… added

John Maddock — Tue, 15 Feb 2011 19:03:05 GMT

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

John Maddock — Thu, 24 Feb 2011 10:25:44 GMT

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

status changed; resolution set

John Maddock — Tue, 02 Aug 2011 17:04:12 GMT

status assigned → closed
resolution → fixed

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

cc changed

Wed, 01 Aug 2012 20:05:03 GMT

cc jonathan.jones@… added