Re: Is there in memory tree structure faster than std::map?
Leigh Johnston <leigh@i42.co.uk> wrote:
Three words: custom pool allocator.
It can be difficult to match the compiler's (well, libc's) own allocator,
unless you are willing to make compromises eg. in terms of thread safety.
From my experiments I think that the major reason (or one of the major
reasons) for the slowness of the standard allocator is that it's
thread-safe. If you make a similar allocator that doesn't care about
thread-safety, it can easily be twice as fast, if not even more. (Of
course another option is to try to make a fast lock-free allocator...)
Another major problem is that the standard allocator isn't (and really
can't be) very cache-friendly: As blocks are allocated and deallocated
during the execution of the program, the memory will become more and more
fragmented, and the allocation of subsequent blocks more and more
randomized. This is a cache-killer. If you want to fix this, you'll have
to find some way of defragmenting and compacting the memory once in a
while, which can be really difficult due to how a typical C/C++ program
works.