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" <d...@softplc.com >>> <mailto:d...@softplc.com>> 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 _______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp