Boost logo

Boost Users :

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
>



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net