[Countertree + Suballocator] New Version
Hi this message is to announce the new version of the [countertree + suballocator] library. You can find the zip file with the code and the documentation in https://docs.google.com/file/d/0B9lWJ1Nhb_RhRXVHSS14aGxUZjJjWFdRVC0xZ2czZw/e... or if you want a quick look , you can see in my web page http://fjtapia.webs.com/works/countertree/index.html *COUNTERTREE * This library is an implementation of a binary red-black counter tree. This tree have an additional counter in each leaf. This permit the access to the elements by the position, like in a vector. It is a random access container with random access iterators . With this tree we have vectors (cntree::vector_tree) with identical interface than std::vector. The vector_tree have the same speed inserting and deleting in any position (all the operations are O(log N)).It is slower than std:vector inserting and deleting at end, but much faster for to insert and delete in any other position. With ordered information, we have in the cntree namespace the classes set, multiset, map and multimap, with identical interface than the STL classes, with the plus of access to the elements by position, like in a vector. The iterators are random access , and you can subtract two iterators in a O(log N) time for to know the number of nodes between them (even with the end( ) and rend( ) iterators) For to show the utility of this, imagine a large unordered file with the information about the employees of a big company. You have indexes implemented with multimaps, with pairs [value, position], and use the upper_bound and lower_bound functions. You need to select the employees in a range of age and weight. With the boost:multimap you can know the number of elements of the selection. In the weight query we found 100 elements and in the age query 10000 elements. To travel the elements of the weight query asking for the age, is faster than the opposite. *SUBALLOCATOR * A very hard test for the allocators are the data structures which need a very high number (several millions) of elements of the same size, like the STL list, set, multiset, map or multimap. When the number of elements grow, many allocators begin to have speed problems. The solution proposed for this problem are the custom allocators. These allocators are very fast, but many of them present additional problems related with the memory consumption. And they don't work well when they must manage many types of data. When the allocators receive the request from the program, they request memory to the Operating System, and the memory consumed by the program grows up. When the program return to the allocators the request, many allocators have problems for to return the memory freed to the Operating System (The std::allocator of GCC 4.6 don't return well the memory, and the std::allocator of Visual C++, return, but it is slower than the GCC allocator) If you use only one allocator, you have a bad management or in the speed of equal size elements, or with a wide variety of elements. If you use two allocators, the memory freed by an allocator can't be used by the other, and the memory consumption is very high, and when decrease the number of elements to manage, the memory don't decrease. These problems are specially important in two environments : a) When you have a limited resources, as occurs in the mobile phones, pads ... b) When the programs must run continuously in a multitask environment The solution is the suballocator. It is a mechanism for to manage in a fast way a greater number (hundred millions) of elements with the same size. The suballocator is a layer over the allocator (any allocator with the STL interface). The suballocator receives an allocator as template parameter. When the suballocator needs memory, request memory from the allocator, and when the memory is not used, is returned to the allocator. The suballocator present the same interface than the STL allocator. Form the view point of the data structures, the suballocator is other allocator The suballocator always return the first element free. This improve the cache performance and the speed of the data structures. This simple memory schema permit to the allocators return memory to the Operating System and decrease the memory used by the program, as demonstrate the programs in the benchmarks, and you can see in the benchmark point. With the suballocator a) We have a very *fast allocation* (3 times faster than GCC 4.6 std::allocator, 3.5 times faster than Visual Studio 10 std::allocator ) b) Return memory to the allocator, for to be used by others types of data. Many allocators, return this memory to the Operating System, and *decrease the memory used by the program * c) You *can use with any allocator* if according with the STL definition. The suballocator provides speed and memory management to any allocator. d) In the insertion in a std::set<uint64_t> , the time spent by the allocator is around 1%, but the suballocator save around 35% of time . The suballocator always provide the first position free, This provide us a very compact data are, which *improve the cache performance* All the information showed here is explained and detailed in the point Suballocator. All the information is extracted from the programs in the benchmarks folder. *COUNTERTREE + SUBALLOCATOR* The join of the two ideas provide us data structures with a suballocator built-in. They are, in the namespace cntree, the vector_tree_pool, set_pool, multiset_pool,map_pool and multimap_pool, with identical interface than the STL classes but better performance. Tray it. It fast, useful and easy to understand and use,. They are the STL classes with a few additional functions. I had checked this code with GCC 4.6 (32 and 64) , CLANG/LLVM 3.0 and Visual Studio 1010 (32 and 64). If you find any error or problem in the code , the documentation or in any other part ( as friendly do Mr Rene Rivera in the first version). Please mail me ( fjtapia@gmail.com) or if you mail Boost, please insert [countertree] in the head of the message. Some days I have not time to read all messages arrived to my mail, but if I see that I detect and respond first. If you have some idea, or have any comment, please mail me, always two legs run more than only one in the pursuit of the goal, to be useful to the community of programmers in the same way than our predecessors had been useful to us. Sincerely yours Francisco Tapia fjtapia@gmail.com
on Thu Apr 12 2012, Francisco José Tapia <fjtapia-AT-gmail.com> wrote:
The iterators are random access , and you can subtract two iterators in a O(log N) time for to know the number of nodes between them (even with the end( ) and rend( ) iterators)
If by "are random access" you mean they satisfy the random access iterator requirements, then this is a contradiction. Iterator subtraction is required to be O(1) for random access iterators. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
The iterators don't store the position, because after the creation of an iterator, if you insert or delete elements in the tree, the position of the element pointed bu the iterator can change. The iterators need to travel to the root of the tree for to know their position, with the exception of the iterators end(), and rend(). Normally relate the iterators of vectors with random access iterators O(1), and iterators of a list or set with not random access iterators O(N). These iterators are in the middle O (log N). I don't know other iterators similar. I say random access iterator because you can use the random access algorithms of the STL library as std::sort, std::binary_search wit good results. Obviously they are not so fast as the iterators of a vector, but run well and fast. The std::sort over a counter_tree<int> with 1000000 random elements, spend 2.3 seconds on my computer. If I don't define the iterator as random access I can't use these functions. I examined much information about the iterators, beginning with your Boost library iterators and many other documents and I have not a solution. Perhaps you can help me in order to find a solution which permit to access to the STL library functions without the definition as random access. Sincerely yours Francisco Tapia
Dave Abrahams wrote:
on Thu Apr 12 2012, Francisco José Tapia <fjtapia-AT-gmail.com> wrote:
The iterators are random access , and you can subtract two iterators in a O(log N) time for to know the number of nodes between them (even with the end( ) and rend( ) iterators)
If by "are random access" you mean they satisfy the random access iterator requirements, then this is a contradiction. Iterator subtraction is required to be O(1) for random access iterators.
If the container can store at most 2^64 elements, it can be hard to distinguish O(1) from O(log N). However, if O(log N) implies cache misses and swapping, then O(log N) may really be different from O(1) in practice. Regards, Thomas
Thomas All you say is obviously. The counter_tree can't be so fast as the vectors in algorithms as sort or binary search. I only say that the random algorithms can run with the vector_tree with a good results If you have a hundred million elements and want sort for to search them, obviously the vector_tree is not the best option, even the std::set is slow if you compare with a vector, the sort function and the binary search. But commonly the number of elements used in the majority of the programs are nor so big, and the times with thousands even few millions elements are decent. The main utility of the vector_tree is when you must insert or delete many elements in central positions. It is only an option more, with different features, and if you consider it useful, use .Only that Sincerely yours Francisco Tapia El 12 de abril de 2012 20:30, Thomas Klimpel <Thomas.Klimpel@synopsys.com>escribió:
Dave Abrahams wrote:
on Thu Apr 12 2012, Francisco José Tapia <fjtapia-AT-gmail.com> wrote:
The iterators are random access , and you can subtract two iterators in a O(log N) time for to know the number of nodes between them (even with the end( ) and rend( ) iterators)
If by "are random access" you mean they satisfy the random access iterator requirements, then this is a contradiction. Iterator subtraction is required to be O(1) for random access iterators.
If the container can store at most 2^64 elements, it can be hard to distinguish O(1) from O(log N). However, if O(log N) implies cache misses and swapping, then O(log N) may really be different from O(1) in practice.
Regards, Thomas
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Thu, Apr 12, 2012 at 8:18 PM, Francisco José Tapia <fjtapia@gmail.com>wrote:
Hi
this message is to announce the new version of the [countertree + suballocator] library.
...
This library is an implementation of a binary red-black counter tree. This tree have an additional counter in each leaf. This permit the access to the elements by the position, like in a vector. It is a random access container with random access iterators . ...
Hi all, The trees developed in this project are from class of augmented data structures. Boost library does not have yet such data structures. Some time ago I submitted for discussion of interest three variants of augmented B+ trees. Your project was mentioned in this discussion too. This is why I think the following links might be interesting for you: start of thread, it includes links to documentation and code of augmented B+ trees: http://lists.boost.org/Archives/boost/2011/11/188472.php analysis and comments by Joaquín M López Muñoz: http://lists.boost.org/Archives/boost/2011/12/188591.php my reply: http://lists.boost.org/Archives/boost/2011/12/188746.php One variant of B+ trees with double augmenting supports very efficient summation and calculation of statistical parameters of a data set with logarithmic cost in the worst case. Is it possible to implement similar second augmenting in your RB-trees? This extension will increase the value of your data structures and containers. Regards, Vadim Stadnik
Hi Vadim I didn't know that works. It looks very interesting. About you question if it is possible to implement similar augmenting trees over the counter_tree ? I think yes. It is not very difficult. I suppose it can be done using inheritance of the nodes in the tree. With this, you can add additional information to the nodes, and with the functions you can do all the work of the counter_tree and additional work. I think it is a nice idea Sincerely yours Francisco Tapia El 13 de abril de 2012 12:16, Vadim Stadnik <vadimstdk@gmail.com> escribió:
On Thu, Apr 12, 2012 at 8:18 PM, Francisco José Tapia <fjtapia@gmail.com
wrote:
Hi
this message is to announce the new version of the [countertree + suballocator] library.
...
This library is an implementation of a binary red-black counter tree.
tree have an additional counter in each leaf. This permit the access to
This the
elements by the position, like in a vector. It is a random access container with random access iterators . ...
Hi all,
The trees developed in this project are from class of augmented data structures. Boost library does not have yet such data structures.
Some time ago I submitted for discussion of interest three variants of augmented B+ trees. Your project was mentioned in this discussion too. This is why I think the following links might be interesting for you:
start of thread, it includes links to documentation and code of augmented B+ trees: http://lists.boost.org/Archives/boost/2011/11/188472.php
analysis and comments by Joaquín M López Muñoz: http://lists.boost.org/Archives/boost/2011/12/188591.php
my reply: http://lists.boost.org/Archives/boost/2011/12/188746.php
One variant of B+ trees with double augmenting supports very efficient summation and calculation of statistical parameters of a data set with logarithmic cost in the worst case.
Is it possible to implement similar second augmenting in your RB-trees? This extension will increase the value of your data structures and containers.
Regards, Vadim Stadnik
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sat, Apr 14, 2012 at 4:01 AM, Francisco José Tapia <fjtapia@gmail.com>wrote:
Hi Vadim
I didn't know that works. It looks very interesting.
About you question if it is possible to implement similar augmenting trees over the counter_tree ? I think yes. It is not very difficult. I suppose it can be done using inheritance of the nodes in the tree. With this, you can add additional information to the nodes, and with the functions you can do all the work of the counter_tree and additional work.
Hi Francisco, I am sure that you will enjoy this development and the moment when you first time compare performance of std::accumulate() against augmented_tree.accumulate(). Even though I develop augmented B+ trees, I think that, it is very important to have various augmented RB-trees, since they are basic data structure of many containers in STL. These trees would help understand what useful extensions they can provide for STL containers and algorithms. As for implementation approach, you can use whichever you think is the best one. From my experience, if an approach is correct then development is fast and smooth. Keep in mind that there is an interest in data structures with multiple augmenting (>2). This is certainly possible, but at the moment I do not know if there is a general approach. Your experience with augmented RB-trees will be interesting for me. Regards, Vadim Stadnik
On 12/04/12 12:18, Francisco José Tapia wrote:
*SUBALLOCATOR *
A very hard test for the allocators are the data structures which need a very high number (several millions) of elements of the same size, like the STL list, set, multiset, map or multimap.
When the number of elements grow, many allocators begin to have speed problems. The solution proposed for this problem are the custom allocators. These allocators are very fast, but many of them present additional problems related with the memory consumption. And they don't work well when they must manage many types of data.
When the allocators receive the request from the program, they request memory to the Operating System, and the memory consumed by the program grows up.
When the program return to the allocators the request, many allocators have problems for to return the memory freed to the Operating System (The std::allocator of GCC 4.6 don't return well the memory, and the std::allocator of Visual C++, return, but it is slower than the GCC allocator)
If you use only one allocator, you have a bad management or in the speed of equal size elements, or with a wide variety of elements. If you use two allocators, the memory freed by an allocator can't be used by the other, and the memory consumption is very high, and when decrease the number of elements to manage, the memory don't decrease.
These problems are specially important in two environments : a) When you have a limited resources, as occurs in the mobile phones, pads ... b) When the programs must run continuously in a multitask environment
The solution is the suballocator. It is a mechanism for to manage in a fast way a greater number (hundred millions) of elements with the same size.
The suballocator is a layer over the allocator (any allocator with the STL interface). The suballocator receives an allocator as template parameter. When the suballocator needs memory, request memory from the allocator, and when the memory is not used, is returned to the allocator. The suballocator present the same interface than the STL allocator. Form the view point of the data structures, the suballocator is other allocator
The suballocator always return the first element free. This improve the cache performance and the speed of the data structures. This simple memory schema permit to the allocators return memory to the Operating System and decrease the memory used by the program, as demonstrate the programs in the benchmarks, and you can see in the benchmark point.
With the suballocator
a) We have a very *fast allocation* (3 times faster than GCC 4.6 std::allocator, 3.5 times faster than Visual Studio 10 std::allocator )
b) Return memory to the allocator, for to be used by others types of data. Many allocators, return this memory to the Operating System, and *decrease the memory used by the program *
c) You *can use with any allocator* if according with the STL definition. The suballocator provides speed and memory management to any allocator.
d) In the insertion in a std::set<uint64_t> , the time spent by the allocator is around 1%, but the suballocator save around 35% of time . The suballocator always provide the first position free, This provide us a very compact data are, which *improve the cache performance*
All the information showed here is explained and detailed in the point Suballocator. All the information is extracted from the programs in the benchmarks folder.
From what you're describing, this looks like region-based memory management. In C++, the most common strategy for this kind of thing is arena allocators. How does your allocator differ from the usual arena ones?
On Fri, Apr 13, 2012 at 2:06 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
From what you're describing, this looks like region-based memory management. In C++, the most common strategy for this kind of thing is arena allocators.
How does your allocator differ from the usual arena ones?
Hi Mathias, Is there a need to quote 70 lines just to reply to a few? -- Olaf
On 13/04/12 14:15, Olaf van der Spek wrote:
On Fri, Apr 13, 2012 at 2:06 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
From what you're describing, this looks like region-based memory management. In C++, the most common strategy for this kind of thing is arena allocators.
How does your allocator differ from the usual arena ones?
Hi Mathias,
Is there a need to quote 70 lines just to reply to a few?
My reply was to the description of suballocators, therefore I quoted the full description. I wasn't able to narrow it down more with the little time I give to evaluating the relevant parts; I didn't realize it was so bad.
Hi Mathias The internal structure of the suballocator is like the reversal of the Hanoi Towers game. When the suballocator need memory, request to the allocator a chuck for 1 element. If need more request a chuck of 2, and after 4, and after 8..., always power of 2 elements. The last element always is the biggest. Each chuck has the memory to allocate and a heap of bits for to mark the free elements. This heap is very fast, and shows in an easy way the first position free in the chuck, and if the chuck is full. In every deletion, check the number of elements free. It this is bigger than a value and the last chuck is empty, it is returned to the allocator. It is not a region based allocator but have many similar things. I was surprised when checking the memory used by the program, discover the memory values. The allocators of GCC 4.6 and CLANG/LLVM 3.0 have problems for to return memory to the operating systems. If you create a std::set with 30.000.000 elements, check the memory used by the program, delete all the elements and check the memory. You see the same memory used by the program in the two checks If you do the same in Visual Studio 10, the allocator collect the memory and return to the operating System, and the memory of the program downs a lot. But is a byte slower than the GCC allocator In the benchmarks, the suballocator with the std::allocator with GCC4.6, CLANG 3.0 and VS10, is more than 3 times faster than the std:allocator alone. But with GCC and CLANG, the std::allocator is capable to return the memory returned from the suballocator, to the operating system and the memory used by the program downs. You have graphs showing this in the documentation in the benchmarks of suballocator ( http://fjtapia.webs.com/works/countertree/suballocator.html#benchmark)<http://fjtapia.webs.com/works/countertree/suballocator.html#benchmark> Sincerely yours Francisco Tapia El 13 de abril de 2012 14:06, Mathias Gaunard <mathias.gaunard@ens-lyon.org>escribió:
From what you're describing, this looks like region-based memory management. In C++, the most common strategy for this kind of thing is arena allocators.
How does your allocator differ from the usual arena ones?
______________________________**_________________ Unsubscribe & other changes: http://lists.boost.org/** mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>
On 13/04/12 20:35, Francisco José Tapia wrote:
The allocators of GCC 4.6 and CLANG/LLVM 3.0 have problems for to return memory to the operating systems. If you create a std::set with 30.000.000 elements, check the memory used by the program, delete all the elements and check the memory. You see the same memory used by the program in the two checks
If you do the same in Visual Studio 10, the allocator collect the memory and return to the operating System, and the memory of the program downs a lot. But is a byte slower than the GCC allocator
In the benchmarks, the suballocator with the std::allocator with GCC4.6, CLANG 3.0 and VS10, is more than 3 times faster than the std:allocator alone.
But with GCC and CLANG, the std::allocator is capable to return the memory returned from the suballocator, to the operating system and the memory used by the program downs.
This principle is referred to as a pool allocator, memory is kept rather than given back to the operating system. This results in faster memory management, but of course means that you're not giving the memory for other processes to use. It is well known that GCC uses a pool allocator by default while MSVC does not; note that there is an option in GCC to disable this. I still don't see how your contribution fits into this. Note Boost already has fast pool allocators. This is still different from a region allocator, because in that scenario all memory allocations come from the same pool. The principle of a region allocator is to have a pool for each container.
I am not theoretical. To write code is my hobby , not my work. And after my work and my family, in my free time , I like to think about algorithms and to write them. I would know all the details about the GCC std::allocator ( named new_allocator) examining the code, but I have not time.I don't know what must do a pool allocator and how manage the memory. I like the simple and economical things, and the suballocator is designed according this. When the suballocator don't need a chuck of memory, return it to the allocator for to be used by other data structure or, if the allocator return the memory to the Operating System, to be used by other process. I only know the results as you can see in the benchmark graphs, where all is explained ( http://fjtapia.webs.com/works/countertree/suballocator.html#benchmark)<http://fjtapia.webs.com/works/countertree/suballocator.html#benchmark> According my information ( perhaps I am wrong). In the boost library you have two allocators : boost::pool_allocator and boost::fast_pool_allocator. The first fail when must allocate 50.000.000 elements because the time was excessive. The second is fast, an excelent allocator, but have problems with the memory. If you allocate many elements and check the memory used, deallocate all the elements and check the memory again, you can see it is using the same amount of memory The suballocator have several advantages compared with the boost::fast_pool_allocator : a) It is a byte faster. (This is the less important question) b) The allocator can be used with any allocator. If you have an allocator for share memory , you can't use the fast_pool_allocator c) If in your program you are using a fast_pool_allocator,and in a moment have a peak of work, the memory used by the program grows. But when the work return to low level, the program continues using the same amount of memory. If you use a suballocator, probably the memory used by the program decrease. I don't know the categories where can be included the suballocator. When I study in the Engineer School, They teached me "if somethig run... RUN", this is the important question, not the name. Sincerely yours Francisco Tapia
On 14/04/12 19:43, Francisco José Tapia wrote:
I am not theoretical. To write code is my hobby , not my work. And after my work and my family, in my free time , I like to think about algorithms and to write them.
I would know all the details about the GCC std::allocator ( named new_allocator) examining the code, but I have not time.I don't know what must do a pool allocator and how manage the memory.
I like the simple and economical things, and the suballocator is designed according this.
So you're clearly saying you have little time to commit to this, and do not have the desire to clarify things and employ rigor in your developments. Therefore I do not think your libraries would ever be suitable for inclusion in Boost.
According my information ( perhaps I am wrong). In the boost library you have two allocators : boost::pool_allocator and boost::fast_pool_allocator. The first fail when must allocate 50.000.000 elements because the time was excessive. The second is fast, an excelent allocator, but have problems with the memory. If you allocate many elements and check the memory used, deallocate all the elements and check the memory again, you can see it is using the same amount of memory
As the documentation states, pool_allocator is for vector-like allocation, while fast_pool_allocator is for node-like allocation. The fact the memory is not being freed is by design, this is what a pool allocator is. I would guess that to get what you want, you should use an instance of a pool by container, not the singleton global pool.
The suballocator have several advantages compared with the boost::fast_pool_allocator :
a) It is a byte faster. (This is the less important question)
Being a bit faster is a poor argument. It really depends on the cases, and you can make benchmarks mean whatever you want them to by picking the cases where your approach is the most useful.
b) The allocator can be used with any allocator. If you have an allocator for share memory , you can't use the fast_pool_allocator
Working as an allocator adaptor is indeed a good thing.
c) If in your program you are using a fast_pool_allocator,and in a moment have a peak of work, the memory used by the program grows. But when the work return to low level, the program continues using the same amount of memory. If you use a suballocator, probably the memory used by the program decrease.
Doing this is the conservative choice taken by most malloc/free implementations. It however comes at a great cost in performance, especially when node-like containers are concerned. The solution to this problem is to have several instances of pool allocators working independently, with the ability to free a whole pool and everything inside it at any time. This is region-based memory management.
Hi, In the previous message Mr.Mathias said I have a little time for to attend this project (as I am doing now). I don't have time for to read all the interesting things which I see every day, but to attend the boost community is easy and a pleasure for me It is a stange situation. I am the author, and say “the suballocator is a pool allocator, and when have a chuck of memory free, return it to the allocator”. Mr Mathias respond that according the theory, a pool allocator don't do that and if do, it have a great cost in performance. The suballocator is the empirical demostration that this theory is not correct. If someone want to know anything about the library, the algorithms , the implemention..., ask me, and I will respond you with all my interest. But I can't accept when someone say me that the things I had done in this library , can't be done according a theory. I apologize to the Boost community by the rough style of my previous message. I have no excuse. I am sorry Yours Francisco Tapia
Francisco José Tapia wrote:
In the previous message Mr.Mathias said I have a little time for to attend this project (as I am doing now). I don't have time for to read all the interesting things which I see every day, but to attend the boost community is easy and a pleasure for me
I was going to reply to Mathias (Mr. Gaunard), that his conclusion was unjustified. His perspective appeared to be that those putting work and family ahead of Boost work are unworthy to submit to Boost. That perspective is wrong, and I presume he didn't mean to say that.
It is a stange situation. I am the author, and say "the suballocator is a pool allocator, and when have a chuck of memory free, return it to the allocator". Mr Mathias respond that according the theory, a pool allocator don't do that and if do, it have a great cost in performance. The suballocator is the empirical demostration that this theory is not correct.
I was starting to get a little lost in Mathias's arguments, too. Your allocator adapter, according to your tests, demonstrates high performance and the ability to return memory to the OS, which would seem to be the ideal. I haven't studied your tests, so there may be testing deficiencies that have led to biased conclusions. Your allocator adapter must be tested in numerous contexts to justify its addition into Boost, at least if it's to be used as anything other than a tool for use with your countertree. However, it sounds promising enough to pursue. It may also be possible to follow Mathias' advice regarding a per-container fast_pool_allocator to retain the performance benefits you've described using your allocator adapter. However, it isn't clear that the same benefits would accrue because the container would have to force the pool allocator to return memory to the OS even before destruction to account for use cases in which the number of elements grows large and then drops again while the container continues to exist thereafter. (Actually, looking again, I see that Mathias suggested multiple pools per container so that there was a greater chance of being able to free a given pool, thereby returning memory to the OS. Either way, that puts the onus on the container and isn't as reusable.) _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On 16/04/12 15:41, Stewart, Robert wrote:
Francisco José Tapia wrote:
In the previous message Mr.Mathias said I have a little time for to attend this project (as I am doing now). I don't have time for to read all the interesting things which I see every day, but to attend the boost community is easy and a pleasure for me
I was going to reply to Mathias (Mr. Gaunard), that his conclusion was unjustified. His perspective appeared to be that those putting work and family ahead of Boost work are unworthy to submit to Boost.
I didn't mean this, I was just pointing out that a bit of commitment is necessary to submit a library to Boost. We certainly don't want authors to disappear once they have "given" their library to Boost.
It is a stange situation. I am the author, and say "the suballocator is a pool allocator, and when have a chuck of memory free, return it to the allocator". Mr Mathias respond that according the theory, a pool allocator don't do that and if do, it have a great cost in performance. The suballocator is the empirical demostration that this theory is not correct.
I was starting to get a little lost in Mathias's arguments, too.
There was no real argument, I was just trying to understand a bit more about this library. Francisco's description wasn't very clear on how this new approach compared to those that are already popular in the C++ community. In any case, I'm sorry if I have offended anyone, that wasn't my intention.
Hi, Mr Gaunard , I had forgot all. Smile, and start again. I didn't wrote a description of the algorithm because I didn't know if somebody was interested. Please let me 2 or 3 days, and I will prepare a pdf document with the description of the algorithm. With the explanation and the diagrams, it is very easy understand and see the characteristics of the suballocator described IMPORTANT . About the benchmarks. There are important differences between the times obtained in different processors, depending, mainly of the cache of the processor. The others characteristics as memory allocation don't change. The suballocator shows their utility when you have many elements (several millions). With a small number of elements, the results are similar to the standard allocator. If somebody have any idea or detect a fail, please, contact me, and help me to improve the library and make it useful for the boost community in the same way than others had been useful for us Sincerely yours Francisco Tapia
As promised, I send you the documents with the explanation of the suballocator algorithms. http://fjtapia.webs.com/works/countertree/The_Suballocator_Algorithms.pdf When I was writing the document I had new ideas for to improve the code. Due this, I decided to change the code, and after test the changes, finish the document reflecting the changes. The new code is in http://fjtapia.webs.com/works/countertree/countertree_1.0.zip Thanks by your interest and your patience. If you have any suggestion, want any explanation or any other information, please mail me, and I will send you as soon as possible. Yours
Sincerely yours
Francisco Tapia
participants (7)
-
Dave Abrahams -
Francisco José Tapia -
Mathias Gaunard -
Olaf van der Spek -
Stewart, Robert -
Thomas Klimpel -
Vadim Stadnik