kicad-developers team mailing list archive

[Dick Hollenbeck <dick@xxxxxxxxxxx>]

On 10/16/2013 09:32 AM, Maciej Sumiński wrote:
> On 10/16/2013 02:59 PM, Dick Hollenbeck wrote:
>>
>> On Oct 16, 2013 7:53 AM, "Dick Hollenbeck" <dick@xxxxxxxxxxx
>> <mailto:dick@xxxxxxxxxxx>> wrote:
>>  >
>>  > Looks promising, and super job on the presentation.
>>  >
>>  > Once you have it working, give some thought to using a special
>> purpose allocator for the elements of your container.   A memory pool
>> scheme, anchored on the container, might pay dividends if it removes the
>> size test for element allocations.  If you want the pool anchored on the
>> container, then overloading operator new is not best, but rather have a
>> container function do the allocations of its elements (from a pool it
>> owns.)
>>
>> Invariably
>> this means having an "in place" new operator for the element, not a
>> normal new operator overload.
>>
>> Such anchoring of pool in container is a separate decision from deciding
>> to use a fixed block allocator at all.  The fixed block allocator will
>> be worth it regardless of where the pool lives.  If you have to move
>> elements from one container to another, then anchoring the pool on the
>> container is not appropriate.  But you could then have a class that held
>> all your containers and a pool common to those containers.  I bring this
>> up because when instantiating hundreds of thousands of elements, memory
>> heap calls can be the bottleneck.
> 
> Thanks for the suggestion - I like the idea. I have briefly read the 
> boost::pool project page and initially it seems to be an easy solution 
> to the problem.


That is likely to be a *very* fast solution.  But keep in mind that if you are going to
delete the pool, since it is anchored in your ratsnest class, then you really don't need
element deletion, i.e. operator delete () on the container element.

This let's you trancend into *very very* fast, if you use it to your advantage.  The
problem with supporting pool::free( node ) is that it often requires that a pointer to the
big block from which the smaller fixed size block came be saved in the smaller block.
There may be other ways, look into this.  This additional pointer, if present,  is
unnecessary if you don't worry about delete node, since the pool is going to be deleted
anyways.  The pointer is a way to figure out which big block to add the small fixed block
back into upon a free.  It is overhead you don't need.

Just saving that one pointer can be a big deal.  If the boost scheme is doing this, or if
its allocation function uses more than about 3 lines of code, then it may not be optimal.

Also, if your algorithm can work with pointers to the node, where moving nodes from one
container to another is really a matter of moving pointers, you will also pick up some speed.

What I envision is that when the pool would be inclined to return NULL, meaning the
current big block is exhausted, that it allocate another big block and then put that big
block onto a linked list of big blocks, singly linked is good enough.  After that, it puts
each small block within the big block onto another singly linked list, called a freelist.
 Each of the lists are held in the pool anchor.  The anchor destructor frees all the big
blocks.

operator delete () can be a dummy for the node element, I assume you will need one since
the container destructor may be calling it, and this happens before the pool destructor
hopefully.



 Especially that nodes are very likely going to be POD
> structures with fixed size.
> I guess it is already included in C++11 as the emplace() function that 
> is available for many std containers.
> 
> Regards,
> Orson
>