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<T*> but where the elements are allocated into a Boost.Pool or object pool.

On Monday, July 13, 2015 at 3:08:43 PM UTC+2, Soul Studios wrote:

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
http://lists.boost.org/mailman/listinfo.cgi/boost-users