Unclear on std allocator usage

[mfeemster]

In the documentation, under "Design decisions", you state that the standard allocator is used. I've been testing with map, and it appears this is the case. So when I run the benchmark, the performance of the default allocator and this one is the same.

So I am a bit unclear on why you chose to do this? It seems you are not even using the allocator you wrote and are instead just defaulting to the std one?

Does the decision have anything to do with this?

#2

Also, what is the reasoning behind this:

template <class U>
Allocator(const Allocator<U, growSize>& other)
{
	if (!std::is_same<T, U>::value)
		defaultAllocator = new std::allocator<T>();
}

Why do you use the standard allocator if U and T are different? This appears to be called from rebind. Perhaps I'm a bit clueless on this since I'm new to allocators.

I am building on MSVC 2017 as well.

I would really like to get this working as it seems like a very elegant and simple way to boost map performance.

Thanks.

[moya-mmoczala]

Thank you for your hint! I'll add it to the ReadMe. so before I explain purpose of this workaround lets analyse how the MSVC behaves....

For some reason MS decided to implement STL allocator support very oddly. When you create a container with own allocator specified, the container will do the following:

• create an instance X of allocator
• create an instance Y of the allocator using the constructor you mentioned
• allocate some memory for internal purpose using Y
• destroy the Y instance (without releasing the allocated memory)

Then, when you use container the X instance used for alloc/free.
Finally, when your container is destroyed it does following:

• create an instance Z of the allocator using the constructor you mentioned
• using Z release memory previously allocated with Y
• destroy the Z instance
• destroy X

Therefore, to workaround it, when the constructor you mentioned is used I replace allocation with defaultAllocator which allows to do the above without any consequences.

The allocator I proposed cleans up all the block you forgot to release on destroy, so you cannot do it the way MS proposed.

This "issue" appeared in some release of MSVC and previously it was working as good as GCC. When I reported it to MS they claimed it is not a bug - sure, a feature haha!

Anyways, regarding your question, the container should use defaultAllocator only once - remember to build your project in release mode. I am using MSVC Community 2017 version 15.6.5

[moya-mmoczala]

I have updated both - ReadMe and the code. I would be more than happy if you could check it. Thanks!

[mfeemster]

I spent a few days looking into this, as well as the short_alloc by howard hinnant:

https://howardhinnant.github.io/short_alloc.h

and comparing it with yours. I ran a bunch of tests and saw what you describe where creating an unorered_map in MSVC does all sorts of crazy things.

I think howard's approach is good, where the allocator itself carries no state other than a reference to a memory pool called an arena. Of course, his arena is fairly limited because of his use case of trying to make one with static allocation.

I've created a hybrid of both where the arena can grow, and ends up containing a linked list of memory chunks. But also allows for returned items to the pool to be a linked list of available memory like yours.

My use case is specifically with map and unordered_map. I don't really care about any others, so mine ended up being pretty limited and specific.

In the course of making it, I realized that all of my allocation sizes must be the same, otherwise the linked list of returned items wouldn't really work (how can you have a linked list of pointers without knowing how big the memory they point to actually is).

So when creating a map, I noticed the map will internally call for some large contiguous blocks of memory when doing its internal housekeeping. For those cases, I just default to the system new and delete. For all other calls which are actually allocating nodes, the requested memory size will be the same, so those come from the pool. When I create an allocator, I specify the size it should be expecting for each alloc request.

Using the design that howard did, where the allocator just keeps a reference to an arena has a few shortcomings.

-All containers using that arena must be on the same thread, and must all have an object lifetime SHORTER than the arena itself.

-All containers using single arena instance must request the same memory size for their allocations. Containers needing different size objects each need to create their own arena.

I tried taking a different approach where you could copy memory from one arena to another and no matter how hard I tried, I could not get it to work. After doing some searching, I found others who ran into this problem. There is no good way to transfer memory and the allocators between objects, either with copying or with std::move(). So I just went with howard's approach of an arena which can NEVER be copied or moved.

So that is what I settled on. Possibly a different use case than yours, but it works for me.

My 2 cents is that the authors of the C++ containers provided the facility to use a custom allocator, but never actually thought through how it would work. As a result, the usage of custom allocators is impossible for even trivial cases, which is sad. Maybe they'll fix it some day.

[moya-mmoczala]

Thank you so much for your time and all insights. I will left this issue open for others as a guide. Thanks once again!