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

Subject: Re: [Boost-users] Query regarding interest in my submitting plf::colony to Boost
From: Gonzalo BG (gonzalobg88_at_[hidden])
Date: 2015-07-13 18:47:23

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..._at_[hidden] <javascript:> 
> http://lists.boost.org/mailman/listinfo.cgi/boost-users 
>