How to estimate size of static memory block correctly?
kevin-- opened this issue · 13 comments
I'm trying to use a static memory block with a memory_pool to be the allocator for an std::list.
For example:
using DataType = std::shared_ptr<void>;
using MemoryPool =
foonathan::memory::memory_pool<foonathan::memory::node_pool, foonathan::memory::static_block_allocator>;
constexpr size_t pool_capacity = 20;
constexpr size_t node_size_bytes = list_node_size<DataType>::value;
constexpr size_t block_size_bytes = MemoryPool::min_block_size( node_size_bytes, pool_capacity );
INFO( "alignof(DataType) = " << alignof(DataType) );
INFO( "sizeof(DataType) = " << sizeof(DataType) );
INFO( "pool_capacity = " << pool_capacity );
INFO( "node_size_bytes = " << node_size_bytes );
INFO( "block_size_bytes = " << block_size_bytes );
foonathan::memory::static_allocator_storage<block_size_bytes> storage;
MemoryPool memoryPool( node_size_bytes, block_size_bytes, storage );
using Allocator = foonathan::memory::std_allocator<DataType, MemoryPool>;
using Container = std::list<DataType, Allocator>;
Container container{ Allocator{ memoryPool } };
for ( int count = 0; count < static_cast<int>(pool_capacity); ++count ) {
INFO( "adding item " << count );
container.emplace_back( std::make_shared<int>( count ) );
}
CHECK( container.size() == pool_capacity );
So this code on both MSVC x64 and AppleClang x64 reports:
alignof(DataType) = 8
sizeof(DataType) = 16
pool_capacity = 20
node_size_bytes = 32
block_size_bytes = 656
which looks fine. On clang runs with no problems. But on MSVC it runs out of memory trying to add the 16th item, asking to allocate another block of size 656
I was hoping there was some guidance we can use to estimate the required sizes correctly? Using some other diagnostics (a memory counting allocator), it appears the overhead of std::list in MSVCRT is slightly higher than libc++
Thank you
Hm, this should be correct. What is the value of list_node_size<DataType> on clang and MSVC?
it is reporting 32 on both, all the sizing information is consistent
using this example source code, the size of a std::list<std::shared_ptr<void>> node on AppleClang is 32, but on MSVC is 32.0469
https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2016/09/15/stlsizeof.cpp
Wait, so apparently one element of the list is bigger?
I don't have access to MSVC, so can't do it myself. Can you maybe print the allocations out, to figure out which allocation uses more memory? Maybe it's the first proxy object? Does it also happen if you use something other than shared_ptr as element?
good call -- you are correct about the first proxy object. The behavior remains regardless of datatype
Filling data structures with 1024 elements and reporting the per element memory usage.
class MemoryCountingAllocator<struct std::_Container_proxy> * __ptr64
0 16
class MemoryCountingAllocator<struct std::_List_node<class std::shared_ptr<void>,void * __ptr64> > * __ptr64
0 32
1 32
2 32
...
all subsequent elements are the same size
Ohh, and that proxy object is in addition to all others.
Hm, maybe I should just conservatively add one additional node in the calculation of min_block_size() or something like that?
it seems to not be quite as simple as that. I added 1 to the call to min_block_size (aka 20 + 1), but it is failing at 17 instead of 16 now. I will research a bit more and report back. Thanks for the insight so far.
I thought I saw some allocator logging utilities in the library, but now I'm not seeing them? Are there any built in hooks to watch the allocator's alloc/deallocs? Thanks
ok getting a little closer. In the code I posted above, MSVC seems to be allocating 2 things on creation of the std::list.
Creating Container
00000021E78FD910 node allocated: 00000021E78FD668 (16)
00000021E78FD910 node allocated: 00000021E78FD688 (32)
This is then compounded since I'm actually testing a another class which takes Container by rvalue... something like
template<typename Storage>
class OtherThing
{
OtherThing(Storage&& s)
: mStorage(std::move(s)) {}
Storage mStorage;
};
...
OtherThing<Container> thing(std::move(container));
Which then results in 2 more allocations onto my static block:
Creating OtherThing
00000021E78FD910 node allocated: 00000021E78FD6A8 (16)
00000021E78FD910 node allocated: 00000021E78FD6C8 (32)
So somehow move semantics are failing me in this case, perhaps because the std::list takes the allocator by const& and I guess makes a copy...not sure exactly why the original is not being destroyed.
Anyway that accounts for my missing 4 nodes from memory_pool. Not sure what to do about it next.
Will keep going...
well this may not be the answer you want to hear, but I think I will move my implementation to rely on std::vector plus a call to reserve(). That still allocates 1 extra node, but it is seemingly consistent across the contained data types
So to summarize: the underlying issue is that MSVC allocates additional nodes as part of a proxy list, which are not accounted by the min_block_size(). I think the best I can do is to document that you should account for such nodes and add additional memory to your buffer.
Yes @foonathan that seems to be the conclusion. I have made it a type parameter to my static memory pool for the user to indicate what their overhead requirements are
// ... snip ...
namespace container_overhead
{
struct None : std::integral_constant<size_t, 0> {};
#ifdef BOOST_COMP_MSVC_AVAILABLE
struct StlVector : std::integral_constant<size_t, 2> {};
#else
struct StlVector : None {};
#endif
}
template <size_t Capacity,
typename WorstCaseObject,
typename NodeSize = nodesize::SharedPtrAndObj<WorstCaseObject>,
typename ContainerOverhead = container_overhead::None>
struct StaticMemoryPool
{
StaticMemoryPool()
: mStorage()
, mPool( NodeSize::value, storage_size_bytes, mStorage )
{
}
private:
constexpr static size_t storage_size_bytes =
detail::StaticMemoryPoolAllocator::min_block_size( NodeSize::value, Capacity + ContainerOverhead::value );
// ... snip ...
Maybe not the most elegant, but it is working for my needs.
Thank you for all the assistance, and a great library!