kicad-developers team mailing list archive

[Dick Hollenbeck <dick@xxxxxxxxxxx>]

On 10/16/2013 03:19 PM, Dick Hollenbeck wrote:
> 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.


Orson,


You reminded me of a couple of things:

a) regardless of whether in place new() is used or not, if the objects have std::string or
wxString, the objects will need destruction to free up their string internals.  The
objects very well may need a ~destructor().


b) emplace() is a modern way of doing old school memory block management with in place
new().  Real time C++ programmers have been using in place new for awhile.  emplace() is
an opportunity to use a stock container, but has been limited to C++11.  But boost, in it
effort to bring early functionality even to *C++03*, has emplace() support on


boost::container::vector

*and*

boost::container::deque


So for a minimal lines of code implementation of what I was talking about above, a person
could simply put a boost::container::deque into your ratsnest class and allocate objects
quickly from there, simply by adding them to the deque with emplace(), and returning a
pointer to the back().  This is minimal lines of code and I doubt there's a faster way,
especically with so few lines of code.


http://www.boost.org/doc/libs/1_48_0/doc/html/container/move_emplace.html#container.move_emplace.emplace