Review Wizard Report for November 2012
============================================== Review Wizard Status Report for November 2012 ============================================== News ==== 1. ODEInt Reviewed 2. Boost 1.52.0 Released. No New Libraries. Open Issues =========== The following libraries have review managers, but have not yet been scheduled for review: * Range Extensions - added May 2012; review manager: Neil Groves. The following libraries have been reviewed and await reports from their review managers: * Predef - reviewed February 2012; review manager: Joel Falcou. * Coroutine - reviewed September 2012; review manager: Hartmut Kaiser. The following libraries have been accepted to Boost, but have not yet been submitted to SVN: * Constrained Value - accepted September 2010; author: Robert Kawulak. * GIL.IO - accepted January 2011; author: Christian Henning. * Contract - accepted September 2012; author: Lorenzo Caminiti. The following libraries have been accepted and submitted to SVN, but have not yet appeared in a release: * Atomic - accepted July 2011; author Helge Bahmann. * Type Traits Introspection - accepted August 2011; author: Edward Diener. * Lockfree - accepted August 2011; author: Tim Blechmann. The following libraries have been accepted provisionally to Boost, but have not been submitted for mini-review and full acceptance: * Endian - accepted provisionally November 2011; author: Beman Dawes. * Log - accepted provisionally March 2010; author: Andrey Semashev. General Announcements ===================== As always, we need experienced review managers. Please take a look at the list of libraries in need of managers and check out their descriptions. In general review managers are active boost participants, including library contributors, infrastructure contributors, and other mailing list participants with a substantial track record of constructive participation. If you can serve as review manager for any of them, email Ron Garcia or John Phillips, "rxg at cs dot cmu dot edu" and "phillips at pacific dot mps dot ohio-state dot edu" respectively. We are also suffering from a lack of reviewers. While we all understand time pressures and the need to complete paying work, the strength of Boost is based on the detailed and informed reviews submitted by you. If you are interested in reviewing a library but won't have time during the review period, you can always prepare your review ahead of time. No rule says you can only work on a review during the review period. A link to this report will be posted to www.boost.org. If you would like us to make any modifications or additions to this report, please email Ron or John. The review schedule is an unordered list of the libraries awaiting review. As such, any library on the schedule can be reviewed once the developer is ready, a review manager has been secured, and the manager, developer, and wizards agree on a date to schedule the review. Review Schedule =============== * Join (M) * Pimpl (M) * Sorting (M) * Quaternions, Vectors, Matrices (M) * Variadic Macro Data (M) * Block Pointer (M) * Singularity (M) * Extended Complex Numbers (M) * Metaparse (M) * Polygon: Voronoi Extensions * Coroutine * Range Extensions * Nowide (M) * Array (M) * TypeIndex (M) * STL Extensions (M) ``(M)`` marks libraries that need review managers. -------------------- Join ---- :Author: Yigong Liu :Review Manager: Needed :Download: http://channel.sourceforge.net/ :Description: Join is an asynchronous, message based C++ concurrency library based on join calculus. It is applicable both to multi-threaded applications and to the orchestration of asynchronous, event-based applications. It follows Comega's design and implementation and builds with Boost facilities. It provides a high level concurrency API with asynchronous methods, synchronous methods, and chords which are "join-patterns" defining the synchronization, asynchrony, and concurrency. Pimpl ----- :Author: Vladimir Batov :Review Manager: Needed :Download: https://github.com/boost-vault/Miscellaneous/blob/master/Pimpl.zip :Description: The Pimpl idiom is a simple yet robust technique to minimize coupling via the separation of interface and implementation and then implementation hiding. This library provides a convenient yet flexible and generic deployment technique for the Pimpl idiom. It's seemingly complete and broadly applicable, yet minimal, simple and pleasant to use. Sorting ------- :Author: Steven Ross :Review Manager: Needed :Download: https://github.com/boost-vault/Sorting :Description: A grouping of 3 templated hybrid radix/comparison-based sorting algorithms that provide superior worst-case and average-case performance to std::sort: integer_sort, which sorts fixed-size data types that support a rightshift (default of >>) and a comparison (default of <) operator. float_sort, which sorts standard floating-point numbers by safely casting them to integers. string_sort, which sorts variable-length data types, and is optimized for 8-bit character strings. All 3 algorithms have O(n(k/s + s)) runtime where k is the number of bits in the data type and s is a constant, and limited memory overhead (in the kB for realistic inputs). In testing, integer_sort varies from 35% faster to 2X as fast as std::sort, depending on processor, compiler optimizations, and data distribution. float_sort is roughly 70% faster than std::sort. string_sort is roughly 2X as fast as std::sort. Quaternions, Vectors, Matrices ------------------------------ :Author: Emil Dotchevski :Review Manager: Needed :Download: http://www.revergestudios.com/boost-qvm/ :Description: QVM defines a set of generic functions and operator overloads for working with quaternions, vectors and matrices of static size. The library also defines vector and matrix data types, however it allows users to introduce their own types by specializing the q_traits, v_traits and m_traits templates. Variadic Macro Data ------------------- :Author: Edward Diener :Review Manager: Needed :Download: `Boost Sandbox <http://svn.boost.org/svn/boost/sandbox/variadic_macro_data/>`__ :Description: This library adds support and functionality for variadic macros to Boost as well as integrating variadic macros with the Boost PP library without changing the latter library in any way. Block Pointer ------------- :Author: Phil Bouchard :Review Manager: Needed :Download: https://svn.boost.org/svn/boost/sandbox/block_ptr/ :Description: Deterministic memory manager of constant complexity capable of handling cyclic collections. Singularity ----------- :Author: Ben Robinson :Review Manager: Needed :Download: https://github.com/cppmaven/Singularity :Description: The Singularity Design Pattern allows you to restrict any class to a single instance. Unlike the infamous Singleton, Singularity gives you direct control over the lifetime of the object, does not require you to grant global access to the object, nor does it limit you to the default constructor for that object. Extended Complex Numbers ------------------------ :Author: Matthieu Schaller :Review Manager: Needed :Download: http://code.google.com/p/cpp-imaginary-numbers/ :Description: The library is an extension of the std::complex class addressing two issues: 1. The standard does not guaranty the behaviour of the complex class if instantiated with types other than float/double/long double. 2. Some calculation where pure imaginary numbers (i.e. multiples of sqrt(-1)) appear are unnecessarily slowed down due to the lack of support for these numbers. The code I submit contains two interleaved classes boost::complex and boost::imaginary which can be instantiated with any type T provided T overloads the usual arithmetic operators and some basic (real) mathematical functions depending on which complex function will be used. It is thus an extended version of Thorsten Ottosen's n1869 proposal (http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1869.html) Metaparse --------- :Author: Abel Sinkovics :Review Manager: Needed :Download: http://abel.web.elte.hu/metaparse/metaparse.zip :Description: Metaparse is a library for constructing parsers parsing at compile-time based on template metaprogramming. The parsers built with the library take boost::mpl::strings as input and can produce - types - objects (types with public static members) - callable C++ functions (types with public static method) - template metafunction classes as output (based on the input being parsed). On compilers supporting constexpr the library provides the following syntactic sugar for writing the input of the parsers: BOOST_STRING("this is a string") The library can be used for implementing DSLs in C++, including DSLs making C++ template metaprogramming easier (see examples). Polygon: Voronoi Extensions --------------------------- :Author: Andril Sydorchuk :Review Manager: Lucanus Simonson :Download: http://svn.boost.org/svn/boost/sandbox/gtl/ :Description: This library extends Boost.Polygon with the following features: - Robust and efficient implementation of the sweepline algorithm that allows to construct Voronoi diagram, Delaunay triangulation and medial axis of a set of points and line segments. - Coordinates of the output geometries are computed within the 64 machine epsilon relative error (6 mantissa bits). - Voronoi diagram data structure that allows efficient traversal and data association with the output Voronoi graph. - No 3rd party dependencies (e.g. GMP, MPFR), all the required multiple precision types are implemented as part of the library. - The input and output coordinate type domains are configurable via coordinate type traits, thus allowing to compute coordinates of the Voronoi vertices within any required precision. - The full construction of the Voronoi diagram of 100 000 points takes only 0.27 seconds (see benchmarks). Coroutine --------- :Author: Oliver Kowalke :Review Manager: Hartmut Kaiser :Download: http://gitorious.org/boost-dev/boost-dev/archive-tarball/coroutine :Description: This library is an implementation of coroutines and generators using Boost.Context. Range Extensions ---------------- :Author: Akira Takahashi :Review Manager: Neil Groves :Download: https://github.com/faithandbrave/OvenToBoost :Description: This project adds some features of the Oven Range Library to Boost.Range. Features: - Additional Range Adaptors (taken, taken_while, dropped, dropped_while, elements, elements_key, memoized, outdirected) - Extensions for using Lambda (regular function, regular operator) - Infinite Range (iteration function) - and additional range utilities. Nowide ------ :Author: Artyom Beilis :Review Manager: Needed :Download: http://cppcms.com/files/nowide/ :Description: This library makes cross platform Unicode aware programming easier. It provides an implementation of standard C and C++ library functions, such that their inputs are UTF-8 aware on Windows without requiring to use Wide API. Array ----- :Author: Brian Smith :Review Manager: Needed :Download: https://github.com/BrianJSmith/Array :Description: The array class is a C++11 compatible implementation of static multidimensional arrays. TypeIndex --------- :Author: Antony Polukhin :Review Manager: Needed :Download: https://github.com/apolukhin/type_index :Description: TypeIndex is an extended C++11 type_index library, that * works with disabled RTTI * can store const-volatile-reference info about types (if user requested it) * has all the functionality of std::type_index * has portable across compilers and platforms functionality for getting demangled type names * works across modules/shared libraries * does not require C++11 to work STL Extensions -------------- :Author: Vadim Stadnik :Review Manager: Needed :Download: https://github.com/vstadnik/stl_ext_adv_review :Description: The proposed library [stl_ext_adv] offers augmented array based B+ trees and STL containers that support the interfaces of the C++03 sequences and associative containers. The library offers a number of extensions and performance improvements that are not available in C++03 and C++11 standard containers. Libraries under development =========================== See http://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction for a current listing of libraries under development.
Thank you for catching that Chris. Best, Ron On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
<snip>
The following libraries have been accepted to Boost, but have not yet
been submitted to SVN:
<snip>
There's Multiprecision as well, unless I missed it in the list.
Thank you for the excellent update!
Best regards, Chris.
<snip>
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi Ronald The 3 of October I sent a message requesting the Formal Review of the library Countertree. I don't know if this is sufficient for to request a Formal Review. If not, please, say me, in order to to do it. That message contains a brief description of the project. The code and the documentation are located in my dropbox, because when I had lost the password of the vault. But if it is necessary I will put there. Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip Online documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html I would know if you have any time estimation about the beginning of the review. I ask you because, in the Countertree library the logical expansion is the concurrent version. This is important because many libraries like the Threading Building Blocks have concurrent data structures, but don't have concurrent data structures based on trees ( set, multiset, map and multimap), due to the difficulty of to distribute the elements stored between an arbitrary number of threads. With the countertree is easy because you can use like a vector. Depending of the time estimation, if close, I will do more quietly and I can be a reviewer of some library, if not I will tray to finish the concurrent part for the review. Regards Francisco Tapia 2012/11/12 Ronald Garcia <rxg@cs.cmu.edu>
Thank you for catching that Chris.
Best, Ron
On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
<snip>
The following libraries have been accepted to Boost, but have not yet
been submitted to SVN:
<snip>
There's Multiprecision as well, unless I missed it in the list.
Thank you for the excellent update!
Best regards, Chris.
<snip>
_______________________________________________ Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hello Francisco, Thank you for your note. Could you forward me a copy of the October 3 note, because I do not have a copy. Also, I cannot estimate the time when the review will happen. You will need to find a review manager first and then schedule the review, so the time until the review could vary greatly. Ultimately it is up to you whether you would like to continue working or prepare for review now. Best, Ron On Nov 14, 2012, at 3:02 PM, Francisco José Tapia wrote:
Hi Ronald
The 3 of October I sent a message requesting the Formal Review of the library Countertree. I don't know if this is sufficient for to request a Formal Review. If not, please, say me, in order to to do it.
That message contains a brief description of the project. The code and the documentation are located in my dropbox, because when I had lost the password of the vault. But if it is necessary I will put there.
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Online documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
I would know if you have any time estimation about the beginning of the review. I ask you because, in the Countertree library the logical expansion is the concurrent version. This is important because many libraries like the Threading Building Blocks have concurrent data structures, but don't have concurrent data structures based on trees ( set, multiset, map and multimap), due to the difficulty of to distribute the elements stored between an arbitrary number of threads. With the countertree is easy because you can use like a vector.
Depending of the time estimation, if close, I will do more quietly and I can be a reviewer of some library, if not I will tray to finish the concurrent part for the review.
Regards
Francisco Tapia
2012/11/12 Ronald Garcia <rxg@cs.cmu.edu>
Thank you for catching that Chris.
Best, Ron
On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
<snip>
The following libraries have been accepted to Boost, but have not yet
been submitted to SVN:
<snip>
There's Multiprecision as well, unless I missed it in the list.
Thank you for the excellent update!
Best regards, Chris.
<snip>
_______________________________________________ Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi , Ron I send you a copy of the message. I supouse I will have time for the two thinks and . I will examine the projects for review in order to be reviewer of someone Thanks Francisco Hi all, I would like to request a formal review of the library “Countertree + Suballocator” [countertree] Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip Quick view of documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html For the people who don't know this project, this is a description : *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 . Based on this tree we have : - With unordered information we have vectors (countertree::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 countertree 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) *SUBALLOCATOR* In the allocation of equal size elements ( as in STL list, set, multiset,map and multimap), when the number of elements grows, many allocators begin to have speed problems. For to improve the speed, many allocators request to the Operating System big chucks of memory ( pool allocators). With this, the allocator don't need request memory to the operating system for each allocation. But many allocators don't return well the unused chucks of memory to the Operating System and the memory used by the allocator is the maximum used, never decrease . The *suballocator is a solution to these problems*, and others memory problems described in the suballocator page. The suballocator is a layer between the allocator and the data structures, compatible with any allocator with the STL definition. The suballocator request memory to the allocator, and return to it when unused. The suballocator replace to the allocator in the allocation of equal size elements With the suballocator a) *We have a very fast allocation* *(around 2 times faster than the std::allocator of GCC 4.7, CLANG 3.0 and 3 times than Visual Studio 10 *See details in the *Suballocator Benchmark*)* b) *Return the suballocator return memory to the allocator, this can use in the allocation of others types of data or for return to the *Operating System, decreasing the memory used by the program, *( as you can see in the *Suballocator Benchmark *)* c) *You can use with any allocator if it is according with the STL definition*. The suballocator provides speed and memory management to any allocator. d) Even the time of the allocation is a small part of the time spent in the insertion in a std::set, the suballocator obtain time reductions over over the 30% respect the std::allocator. The secret is the cache performance due to the data locality improvement. *COUNTERTREE + SUBALLOCATOR* The join of the two ideas provide us data structures with a suballocator built-in. They are, in the namespace countertree, the vector_tree_pool, set_pool, multiset_pool,map_pool and multimap_pool, with identical interface than the STL classes but better performance for big number of elements It is fast, useful and easy to understand and use,. They are the like the STL classes with a few additional functions. This library is designed thinking in programmers with a basic knowledge of C++. As I say in the documentation, if you know the STL classes vector, set , multiset, map , multimap and allocator, you know more than 95% needed for to use this library. I showed the library to several friends and colleagues, and one of them said me “If your potential users are not experts, and they need more than 5 minutes to understand what's the goal of the library and what they can do with it, many of them leave the page.... , and the library”. The first page of the documentation explain the library, the reasons and what can do. And in the next pages show the details and how can do in a a easy way. I had checked this code with GCC 4.7 , CLANG/LLVM 3.0 and Visual C++ 10 ( all with 32 and 64bits.). In code of the project is composed by the code of the classes, the test programs, the benchmarks programs used and mentioned in the documentation, and several examples of the code I had checked all the requirements for to request the review. But I am not sure if all is OK. If you miss something or something is wrong , please , mail me and I will correct as soon as possible Sincerely yours Francisco Tapia fjtapia@gmail.com 2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Hello Francisco,
Thank you for your note. Could you forward me a copy of the October 3 note, because I do not have a copy. Also, I cannot estimate the time when the review will happen. You will need to find a review manager first and then schedule the review, so the time until the review could vary greatly. Ultimately it is up to you whether you would like to continue working or prepare for review now.
Best, Ron
On Nov 14, 2012, at 3:02 PM, Francisco José Tapia wrote:
Hi Ronald
The 3 of October I sent a message requesting the Formal Review of the library Countertree. I don't know if this is sufficient for to request a Formal Review. If not, please, say me, in order to to do it.
That message contains a brief description of the project. The code and the documentation are located in my dropbox, because when I had lost the password of the vault. But if it is necessary I will put there.
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Online documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
I would know if you have any time estimation about the beginning of the review. I ask you because, in the Countertree library the logical expansion is the concurrent version. This is important because many libraries like the Threading Building Blocks have concurrent data structures, but don't have concurrent data structures based on trees ( set, multiset, map and multimap), due to the difficulty of to distribute the elements stored between an arbitrary number of threads. With the countertree is easy because you can use like a vector.
Depending of the time estimation, if close, I will do more quietly and I can be a reviewer of some library, if not I will tray to finish the concurrent part for the review.
Regards
Francisco Tapia
2012/11/12 Ronald Garcia <rxg@cs.cmu.edu>
Thank you for catching that Chris.
Best, Ron
On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
<snip>
The following libraries have been accepted to Boost, but have not yet
been submitted to SVN:
<snip>
There's Multiprecision as well, unless I missed it in the list.
Thank you for the excellent update!
Best regards, Chris.
<snip>
_______________________________________________ Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Thanks Francisco. I have added Countertree to the review schedule. Best, Ron On Nov 15, 2012, at 10:59 PM, Francisco José Tapia wrote:
Hi , Ron
I send you a copy of the message.
I supouse I will have time for the two thinks and . I will examine the projects for review in order to be reviewer of someone
Thanks
Francisco
Hi all, I would like to request a formal review of the library “Countertree + Suballocator” [countertree]
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Quick view of documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
For the people who don't know this project, this is a description :
*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 . Based on this tree we have :
- With unordered information we have vectors (countertree::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 countertree 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)
*SUBALLOCATOR*
In the allocation of equal size elements ( as in STL list, set, multiset,map and multimap), when the number of elements grows, many allocators begin to have speed problems. For to improve the speed, many allocators request to the Operating System big chucks of memory ( pool allocators). With this, the allocator don't need request memory to the operating system for each allocation. But many allocators don't return well the unused chucks of memory to the Operating System and the memory used by the allocator is the maximum used, never decrease .
The *suballocator is a solution to these problems*, and others memory problems described in the suballocator page. The suballocator is a layer between the allocator and the data structures, compatible with any allocator with the STL definition. The suballocator request memory to the allocator, and return to it when unused. The suballocator replace to the allocator in the allocation of equal size elements
With the suballocator
a) *We have a very fast allocation* *(around 2 times faster than the std::allocator of GCC 4.7, CLANG 3.0 and 3 times than Visual Studio 10 *See details in the *Suballocator Benchmark*)* b) *Return the suballocator return memory to the allocator, this can use in the allocation of others types of data or for return to the *Operating System, decreasing the memory used by the program, *( as you can see in the *Suballocator Benchmark *)* c) *You can use with any allocator if it is according with the STL definition*. The suballocator provides speed and memory management to any allocator.
d) Even the time of the allocation is a small part of the time spent in the insertion in a std::set, the suballocator obtain time reductions over over the 30% respect the std::allocator. The secret is the cache performance due to the data locality improvement.
*COUNTERTREE + SUBALLOCATOR*
The join of the two ideas provide us data structures with a suballocator built-in. They are, in the namespace countertree, the vector_tree_pool, set_pool, multiset_pool,map_pool and multimap_pool, with identical interface than the STL classes but better performance for big number of elements
It is fast, useful and easy to understand and use,. They are the like the STL classes with a few additional functions.
This library is designed thinking in programmers with a basic knowledge of C++. As I say in the documentation, if you know the STL classes vector, set , multiset, map , multimap and allocator, you know more than 95% needed for to use this library.
I showed the library to several friends and colleagues, and one of them said me “If your potential users are not experts, and they need more than 5 minutes to understand what's the goal of the library and what they can do with it, many of them leave the page.... , and the library”.
The first page of the documentation explain the library, the reasons and what can do. And in the next pages show the details and how can do in a a easy way.
I had checked this code with GCC 4.7 , CLANG/LLVM 3.0 and Visual C++ 10 ( all with 32 and 64bits.). In code of the project is composed by the code of the classes, the test programs, the benchmarks programs used and mentioned in the documentation, and several examples of the code
I had checked all the requirements for to request the review. But I am not sure if all is OK. If you miss something or something is wrong , please , mail me and I will correct as soon as possible
Sincerely yours
Francisco Tapia
fjtapia@gmail.com
2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Hello Francisco,
Thank you for your note. Could you forward me a copy of the October 3 note, because I do not have a copy. Also, I cannot estimate the time when the review will happen. You will need to find a review manager first and then schedule the review, so the time until the review could vary greatly. Ultimately it is up to you whether you would like to continue working or prepare for review now.
Best, Ron
On Nov 14, 2012, at 3:02 PM, Francisco José Tapia wrote:
Hi Ronald
The 3 of October I sent a message requesting the Formal Review of the library Countertree. I don't know if this is sufficient for to request a Formal Review. If not, please, say me, in order to to do it.
That message contains a brief description of the project. The code and the documentation are located in my dropbox, because when I had lost the password of the vault. But if it is necessary I will put there.
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Online documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
I would know if you have any time estimation about the beginning of the review. I ask you because, in the Countertree library the logical expansion is the concurrent version. This is important because many libraries like the Threading Building Blocks have concurrent data structures, but don't have concurrent data structures based on trees ( set, multiset, map and multimap), due to the difficulty of to distribute the elements stored between an arbitrary number of threads. With the countertree is easy because you can use like a vector.
Depending of the time estimation, if close, I will do more quietly and I can be a reviewer of some library, if not I will tray to finish the concurrent part for the review.
Regards
Francisco Tapia
2012/11/12 Ronald Garcia <rxg@cs.cmu.edu>
Thank you for catching that Chris.
Best, Ron
On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
<snip>
The following libraries have been accepted to Boost, but have not yet
been submitted to SVN:
<snip>
There's Multiprecision as well, unless I missed it in the list.
Thank you for the excellent update!
Best regards, Chris.
<snip>
_______________________________________________ Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Thanks Ron. I am sorry because I didn't thought about the resume of the project. It's too long, it's like a novel ! I will write a short description and I will send you in a few days. Thanks Francisco 2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Thanks Francisco. I have added Countertree to the review schedule.
Best, Ron
On Nov 15, 2012, at 10:59 PM, Francisco José Tapia wrote:
Hi , Ron
I send you a copy of the message.
I supouse I will have time for the two thinks and . I will examine the projects for review in order to be reviewer of someone
Thanks
Francisco
Hi all, I would like to request a formal review of the library “Countertree + Suballocator” [countertree]
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Quick view of documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
For the people who don't know this project, this is a description :
*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 . Based on this tree we have :
- With unordered information we have vectors (countertree::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 countertree 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)
*SUBALLOCATOR*
In the allocation of equal size elements ( as in STL list, set, multiset,map and multimap), when the number of elements grows, many allocators begin to have speed problems. For to improve the speed, many allocators request to the Operating System big chucks of memory ( pool allocators). With this, the allocator don't need request memory to the operating system for each allocation. But many allocators don't return well the unused chucks of memory to the Operating System and the memory used by the allocator is the maximum used, never decrease .
The *suballocator is a solution to these problems*, and others memory problems described in the suballocator page. The suballocator is a layer between the allocator and the data structures, compatible with any allocator with the STL definition. The suballocator request memory to the allocator, and return to it when unused. The suballocator replace to the allocator in the allocation of equal size elements
With the suballocator
a) *We have a very fast allocation* *(around 2 times faster than the std::allocator of GCC 4.7, CLANG 3.0 and 3 times than Visual Studio 10 *See details in the *Suballocator Benchmark*)* b) *Return the suballocator return memory to the allocator, this can use in the allocation of others types of data or for return to the *Operating System, decreasing the memory used by the program, *( as you can see in the *Suballocator Benchmark *)* c) *You can use with any allocator if it is according with the STL definition*. The suballocator provides speed and memory management to any allocator.
d) Even the time of the allocation is a small part of the time spent in the insertion in a std::set, the suballocator obtain time reductions over over the 30% respect the std::allocator. The secret is the cache performance due to the data locality improvement.
*COUNTERTREE + SUBALLOCATOR*
The join of the two ideas provide us data structures with a suballocator built-in. They are, in the namespace countertree, the vector_tree_pool, set_pool, multiset_pool,map_pool and multimap_pool, with identical interface than the STL classes but better performance for big number of elements
It is fast, useful and easy to understand and use,. They are the like the STL classes with a few additional functions.
This library is designed thinking in programmers with a basic knowledge of C++. As I say in the documentation, if you know the STL classes vector, set , multiset, map , multimap and allocator, you know more than 95% needed for to use this library.
I showed the library to several friends and colleagues, and one of them said me “If your potential users are not experts, and they need more than 5 minutes to understand what's the goal of the library and what they can do with it, many of them leave the page.... , and the library”.
The first page of the documentation explain the library, the reasons and what can do. And in the next pages show the details and how can do in a a easy way.
I had checked this code with GCC 4.7 , CLANG/LLVM 3.0 and Visual C++ 10 ( all with 32 and 64bits.). In code of the project is composed by the code of the classes, the test programs, the benchmarks programs used and mentioned in the documentation, and several examples of the code
I had checked all the requirements for to request the review. But I am not sure if all is OK. If you miss something or something is wrong , please , mail me and I will correct as soon as possible
Sincerely yours
Francisco Tapia
fjtapia@gmail.com
2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Hello Francisco,
Thank you for your note. Could you forward me a copy of the October 3 note, because I do not have a copy. Also, I cannot estimate the time when the review will happen. You will need to find a review manager first and then schedule the review, so the time until the review could vary greatly. Ultimately it is up to you whether you would like to continue working or prepare for review now.
Best, Ron
On Nov 14, 2012, at 3:02 PM, Francisco José Tapia wrote:
Hi Ronald
The 3 of October I sent a message requesting the Formal Review of the library Countertree. I don't know if this is sufficient for to request a Formal Review. If not, please, say me, in order to to do it.
That message contains a brief description of the project. The code and the documentation are located in my dropbox, because when I had lost the password of the vault. But if it is necessary I will put there.
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Online documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
I would know if you have any time estimation about the beginning of the review. I ask you because, in the Countertree library the logical expansion is the concurrent version. This is important because many libraries like the Threading Building Blocks have concurrent data structures, but don't have concurrent data structures based on trees ( set, multiset, map and multimap), due to the difficulty of to distribute the elements stored between an arbitrary number of threads. With the countertree is easy because you can use like a vector.
Depending of the time estimation, if close, I will do more quietly and I can be a reviewer of some library, if not I will tray to finish the concurrent part for the review.
Regards
Francisco Tapia
2012/11/12 Ronald Garcia <rxg@cs.cmu.edu>
Thank you for catching that Chris.
Best, Ron
On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
<snip>
> The following libraries have been accepted to Boost, but have not
yet
> been submitted to SVN:
<snip>
There's Multiprecision as well, unless I missed it in the list.
Thank you for the excellent update!
Best regards, Chris.
<snip>
_______________________________________________ Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Thank you Francisco. Also, please cc: me directly on it so it doesn't slip past Best, Ron On Nov 17, 2012, at 8:57 AM, Francisco José Tapia wrote:
Thanks Ron.
I am sorry because I didn't thought about the resume of the project. It's too long, it's like a novel !
I will write a short description and I will send you in a few days.
Thanks
Francisco
2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Thanks Francisco. I have added Countertree to the review schedule.
Best, Ron
On Nov 15, 2012, at 10:59 PM, Francisco José Tapia wrote:
Hi , Ron
I send you a copy of the message.
I supouse I will have time for the two thinks and . I will examine the projects for review in order to be reviewer of someone
Thanks
Francisco
Hi all, I would like to request a formal review of the library “Countertree + Suballocator” [countertree]
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Quick view of documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
For the people who don't know this project, this is a description :
*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 . Based on this tree we have :
- With unordered information we have vectors (countertree::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 countertree 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)
*SUBALLOCATOR*
In the allocation of equal size elements ( as in STL list, set, multiset,map and multimap), when the number of elements grows, many allocators begin to have speed problems. For to improve the speed, many allocators request to the Operating System big chucks of memory ( pool allocators). With this, the allocator don't need request memory to the operating system for each allocation. But many allocators don't return well the unused chucks of memory to the Operating System and the memory used by the allocator is the maximum used, never decrease .
The *suballocator is a solution to these problems*, and others memory problems described in the suballocator page. The suballocator is a layer between the allocator and the data structures, compatible with any allocator with the STL definition. The suballocator request memory to the allocator, and return to it when unused. The suballocator replace to the allocator in the allocation of equal size elements
With the suballocator
a) *We have a very fast allocation* *(around 2 times faster than the std::allocator of GCC 4.7, CLANG 3.0 and 3 times than Visual Studio 10 *See details in the *Suballocator Benchmark*)* b) *Return the suballocator return memory to the allocator, this can use in the allocation of others types of data or for return to the *Operating System, decreasing the memory used by the program, *( as you can see in the *Suballocator Benchmark *)* c) *You can use with any allocator if it is according with the STL definition*. The suballocator provides speed and memory management to any allocator.
d) Even the time of the allocation is a small part of the time spent in the insertion in a std::set, the suballocator obtain time reductions over over the 30% respect the std::allocator. The secret is the cache performance due to the data locality improvement.
*COUNTERTREE + SUBALLOCATOR*
The join of the two ideas provide us data structures with a suballocator built-in. They are, in the namespace countertree, the vector_tree_pool, set_pool, multiset_pool,map_pool and multimap_pool, with identical interface than the STL classes but better performance for big number of elements
It is fast, useful and easy to understand and use,. They are the like the STL classes with a few additional functions.
This library is designed thinking in programmers with a basic knowledge of C++. As I say in the documentation, if you know the STL classes vector, set , multiset, map , multimap and allocator, you know more than 95% needed for to use this library.
I showed the library to several friends and colleagues, and one of them said me “If your potential users are not experts, and they need more than 5 minutes to understand what's the goal of the library and what they can do with it, many of them leave the page.... , and the library”.
The first page of the documentation explain the library, the reasons and what can do. And in the next pages show the details and how can do in a a easy way.
I had checked this code with GCC 4.7 , CLANG/LLVM 3.0 and Visual C++ 10 ( all with 32 and 64bits.). In code of the project is composed by the code of the classes, the test programs, the benchmarks programs used and mentioned in the documentation, and several examples of the code
I had checked all the requirements for to request the review. But I am not sure if all is OK. If you miss something or something is wrong , please , mail me and I will correct as soon as possible
Sincerely yours
Francisco Tapia
fjtapia@gmail.com
2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Hello Francisco,
Thank you for your note. Could you forward me a copy of the October 3 note, because I do not have a copy. Also, I cannot estimate the time when the review will happen. You will need to find a review manager first and then schedule the review, so the time until the review could vary greatly. Ultimately it is up to you whether you would like to continue working or prepare for review now.
Best, Ron
On Nov 14, 2012, at 3:02 PM, Francisco José Tapia wrote:
Hi Ronald
The 3 of October I sent a message requesting the Formal Review of the library Countertree. I don't know if this is sufficient for to request a Formal Review. If not, please, say me, in order to to do it.
That message contains a brief description of the project. The code and the documentation are located in my dropbox, because when I had lost the password of the vault. But if it is necessary I will put there.
Project location ( zip file with code and documentation) : https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
Online documentation with code download : https://dl.dropbox.com/u/8437476/works/countertree/index.html
I would know if you have any time estimation about the beginning of the review. I ask you because, in the Countertree library the logical expansion is the concurrent version. This is important because many libraries like the Threading Building Blocks have concurrent data structures, but don't have concurrent data structures based on trees ( set, multiset, map and multimap), due to the difficulty of to distribute the elements stored between an arbitrary number of threads. With the countertree is easy because you can use like a vector.
Depending of the time estimation, if close, I will do more quietly and I can be a reviewer of some library, if not I will tray to finish the concurrent part for the review.
Regards
Francisco Tapia
2012/11/12 Ronald Garcia <rxg@cs.cmu.edu>
Thank you for catching that Chris.
Best, Ron
On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
> > <snip> > >> The following libraries have been accepted to Boost, but have not yet > >> been submitted to SVN: > > <snip> > > There's Multiprecision as well, unless I missed it in the list. > > Thank you for the excellent update! > > Best regards, Chris. > > <snip> > > _______________________________________________ > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Christopher Kormanyos -
Francisco José Tapia -
Ronald Garcia