[Boost-users] Query regarding interest in my submitting plf::colony to Boost

Subject: [Boost-users] Query regarding interest in my submitting plf::colony to Boost
From: Soul Studios (matt_at_[hidden])
Date: 2015-07-13 04:22:01

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