Re: [boost] [density] new library

Subject: Re: [boost] [density] new library
From: Giuseppe Campana (giu.campana_at_[hidden])
Date: 2016-06-13 18:14:40

Il 13/06/2016 19:56, Klaim - Joël Lamotte ha scritto:
> You might want to clarify the differences with this library as colony is
> well advanced in it's production.
The main difference is that plf::colony is an homogeneous container 
(elements have all the same type), while density deals with 
heterogeneous containers, in which elements may have a common base class 
(i.e. polymorphic containers like dense_list<Widget>), or may be 
completely type-erased (for example: dense_list<void> or 
dense_function_list<int(float)>). The core idea of colony is avoiding 
element reallocation and moving. The core idea of density is avoiding 
wastes of memory and sparse data structures.

Another difference is in the memory management: plf::colony allocates 
increasingly big memory blocks while the container get filled, while 
density paged containers allocate fixed-size pages. Fixed size 
allocation is extremely fast and straightforward. Furthermore, a page 
allocator may use a thread-local temporary depot of free pages to get a 
new page without having to synchronize with the other threads. This 
optimization is not still implemented, but I believe that it will be 
beneficial for all the paged containers (that is paged_queue, 
paged_function_queue, and all the lifo classes). Anyway density is 
already performing better than the alternatives, especially with queues 
(http://peggysansonetti.it/tech/density/html/func_queue_bench.html).

density deals with lifo allocation as well. This may may at first seem 
unrelated to heterogeneous containers, but actually it's not. For 
example you may need to copy or move on the stack an element from an 
heterogeneous container, but you don't know how big it is, so you use a 
lifo_buffer, like in the producer-consumer sample 
(http://peggysansonetti.it/tech/density/html/producer_consumer_sample.html). 
As explained in the comments, the drawback of using lifo_buffer in this 
way is that the code is not automatically exception safe. Very soon 
density will provide a type-erased lifo_object that will fix this.
I care a lot about exception safeness: the test of density performs an 
exhaustive test on the strong exception guarantee on all the testcases, 
trying to raise an exception in every place in which an exception may 
occur and checking in a catch block that the container has not changed.