After going through the code and the benchmarks, I can make sense of the
results now: the benchmarks are for a vector<T>!
One thing comes to mind, it would be interesting to compare your container
agains `boost::stable_vector` and against a vector
Hi all, I've had some expressions of support outside of the Boost community for submission of the plf::colony container and it's associated container plf::stack, mainly from the review judges for my cppcon submission on the same topic (topic didn't make it through to the finals but got a positive response). I'd like to guage reactions here to see whether it is worth spending the time necessary to port it to Boost, with all the associated reviews etc.
plf::colony is a container for unordered data, where erasure and addition do not cause iterator/pointer invalidation, with superior performance characteristics to all std:: containers when either (a) Pointers and iterators which point to container elements must stay valid regardless of container additions and deletions and/or (b) Additions to or deletions from the container will be occurring in performance-critical code.
Erasure performance in particular can be in advance of 6000x of vectors, while still being faster than lists, maps, deques etc for add and iteration. Full details and benchmarks across four compilers are here: http://www.plflib.org/colony.htm#benchmarks
It has been thoroughly tested, including integrating it into the game engine I constructed last year as well as the usual unit tests. It supports both C++0x and C++11, and has been tested on the following compilers so far: Clang 3.4, GCC 4.6, 4.7, 4.8, 4.9 and 5.1 (both 32-bit and 64-bit), MS Visual C++ 2010 & 2013 (2015 supported but untested as yet).
Internally a colony is a combination of a linked-list of increasingly-larger memory blocks combined with boolean erasure fields, combined with a custom memory location recycle stack. The most common comment I get is "that sounds kinda like a deque", so to save some time here are the differences (from the FAQ): "A double-ended queue requires a very different internal framework. It may or may not use a linked-list of memory blocks, dependent on the compiler, and has no comparable performance characteristics. Deque element erasure is very slow, similar to a vector, and it does not free unused memory blocks to the OS once they are empty, unlike a colony. In addition a deque invalidates references to subsequent container elements when erasing elements, which a colony does not. A colony never invalidates pointers/iterators to elements unless the element being referred to is erased."
The rest of the faq is here and I would appreciate it if people read it before casting judgement: http://www.plflib.org/colony.htm
I am aware that it will be a lot of work to port colony to Boost, so I will only undertake this if there is genuine interest. In addition, plf::stack - which colony must use internally - is a std::stack equivalent container but with much better performance characteristics, which can be used outside of plf::colony.
Asides from the performance characteristics, colonies have the following positive and negative properties: Positive: Lack of pointer/iterator invalidation makes interrelating between collections of data easier, without the cache misses associated with vectors of pointers to dynamically-allocated objects. Negative: Due to the additional overhead, performance can be worse for scalar types.
Thanks in advance- Matt B _______________________________________________ Boost-users mailing list Boost...@lists.boost.org javascript: http://lists.boost.org/mailman/listinfo.cgi/boost-users