Proposal: Vector-like container, which takes O(log(N)) for insert/erase, feedback
Date: Thu, 3 Apr 2014 16:39:29 -0700 From: Glen Fernandes <glen.fernandes@gmail.com> I wasn't sure at first why my name was in parenthesis in the e-mail subject. :-) Glen It's my fault, sorry about it. Date: Fri, 04 Apr 2014 13:41:04 +0200 From: Adam Wulkiewicz <adam.wulkiewicz@gmail.com> Subject: Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase AFAIU just like a B-tree can be seen as a generalization of a binary search tree in that a node can have more than two children, your container can be seen as a similar generalization of a Rope. Or it can be seen as an augumented B-tree (not really because the values are no longer stored in internal nodes and the tree isn't sorted, correct me if I'm wrong). Your You understood right. proposal is very similar to Counted B-tree (http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html), which is a B-tree with random access. The difference is that your container can't be used to search for a stored value in O(logN) without sorting and binary search. This may be ok if someone require only random access, the size of a node is smaller which probably improves the cacheing. Again, right. There are a lot of situations when only random access is necessary. You probably will not sort characters in string.
In general, B-tree was introduced to improve the performance of the access to data stored in persistent memory (lower performance). In this case it was better to load the whole page into memory (and cache it) than load many small, scatered parts. But in the case of RAM-only-access, a binary search tree should be faster. As far as we don't consider spatial indexing, interval trees, etc. where values/nodes may "overlap" somehow and we must search in more than one subtree. Therefore I'm wondering if a classic Rope would be faster than your container in the use-case you're testing - simple insert and random It outperformed Rope 10 times. It's expected result. Please visit my
Hi, everybody! The most important feature of my container is performance. However, other features will appear later. https://github.com/alexkupri/array/blob/master/description/description.txt Today I compared my container with rope. My container outperformed it 10 times. link, I added verbose explanation under "ROPE TEST" section. Shortly speaking, four reasons exist: cache, pages, balancing and malloc/free.
access to a in-memory container. Have you test it? I'd perform 2 tests: 1. Very big number of values + truly random insert/access to prevent cacheing 2. insert/access in the same area I've tested with truly random tests. Please see results and code of SingleOperationPerformanceCheck and MultipleOperationsTest functions. Tell me, if I'm wrong.
IMHO the benefits related to the use of this container should be more noticable if the persistent storage were used. In memory/cache there are the same relationship as in HD/memory.
As for the name, it's definietly not an array. I'd call it B-rope. Thanks, your option is accepted. I'll collect more options and we'll vote. I like brope.
Regards, Adam
Message: 9 From: Lars Viklund <zao@acc.umu.se> Date: Fri, 4 Apr 2014 14:10:06 +0200 If it doesn't have contiguous storage, it's not a replacement for vector, however much you want it to be the universal container that everyone uses for everything. It may be a better general-purpose container compared to the usual default containers, deque and vector, but it isn't a replacement for either of them. Well, I would see it as first choise container for non-sorted data. It's comparable with vector/deque on small arrays and outperforms them on large sizes. It's more preferrable than list at least in terms of malloc/free calls. And it's probably better for strings. So one should use it by default in all cases with unsorted data and use list, vector, deque and string only if he/she really understands what he/she does. You use the term 'intrusive' in the documentation, but it doesn't seem to carry the usual meaning that it requires the types involved to participate in the container structure. You are right. I've corrected the documentation. Now I call "fat leaves" leaves which contain elements, and "thin leaves" leaves which contain pointers to elements. Your tests doesn't seem to exercise much else than container<int> either. Suggest your tests. I'm not quite sure I like the explicit L/M non-type template parameters either, considering that it leaks implementation detail into every single user of the type. Well, you are right in principle. It must have default parameters. But it's platform dependent, they should be chosen so that branch and leaf would take roughly 1 cache line, minus information required for malloc overhead. As for the Copy-on-Write semantics, isn't the general consensus that CoW is a horrible horrible thing and is very hard to get right+fast in the modern world with concurrency? I disagree with your estimation. There are different situations, different machines. Embedded and mobile machines want to save memory. Large machines can also want to save memory, if they amount of data is large. Finally, they can even speed-up by avoiding copying the whole array. Imagine you are writing text editor. (DNA editor, sound editor, etc.) You make backup copy and continue editing, again backup copy and continue editing. And you keep only forward commands (without undo). You can easily rollback to any state you need. Ofcourse, user should decide, whether CoW option is necessary for him/her, because it wastes resources when enabled and not used.
Message: 11 Date: Fri, 4 Apr 2014 23:23:09 +1000 From: Vadim Stadnik <vadimstdk@gmail.com> Could you please provide a figure that shows data association with nodes in your data structure? I updated the doc, follow the link above.
Hi Alexander, Please respond one email at a time, otherwise it's hard to follow the discussion. See http://www.boost.org/community/policy.html. Alexander Kuprijanov wrote:
Hi, everybody! The most important feature of my container is performance. However, other features will appear later. https://github.com/alexkupri/array/blob/master/description/description.txt
Today I compared my container with rope. My container outperformed it 10 times.
Again, the times you measure are too small to reasonably tell which one is faster. You could perform each test 10k more times to keep the results around 1s. Instead of comparing it with a different implementation I guess it would be sufficient to contain only 2 children in the internal nodes. <snip>
Message: 9 From: Lars Viklund <zao@acc.umu.se> Date: Fri, 4 Apr 2014 14:10:06 +0200 If it doesn't have contiguous storage, it's not a replacement for vector, however much you want it to be the universal container that everyone uses for everything. It may be a better general-purpose container compared to the usual default containers, deque and vector, but it isn't a replacement for either of them. Well, I would see it as first choise container for non-sorted data. It's comparable with vector/deque on small arrays and outperforms them on large sizes. It's more preferrable than list at least in terms of malloc/free calls. And it's probably better for strings. So one should use it by default in all cases with unsorted data and use list, vector, deque and string only if he/she really understands what he/she does.
I agree with Lars. Your container shouldn't be seen as a replacement. It has different properties, hence it may be useful in some situations but not all of them. And I strongly dissagree with the statement that your container should be the first choice. std::vector<> will outperform it in most of the real-life use-cases. Also, IMHO the most important feature of std::list<> is insert() and erase() not invalidating other iterators. AFAIU in your container iterators may be invalid after insert()? Regards, Adam
On Apr 5, 2014, at 4:59 PM, Adam Wulkiewicz <adam.wulkiewicz@gmail.com> wrote:
I agree with Lars. Your container shouldn't be seen as a replacement. It has different properties, hence it may be useful in some situations but not all of them.
..
AFAIU in your container iterators may be invalid after insert...
I think it would benefit the discussion if we would lists it's properties about access and O() and compare it with STL containers. If it a class on its own then one can expect more variant in the future like the hash_map version of a map.
On 6 April 2014 00:45, Alexander Kuprijanov <alexkupri@gmail.com> wrote:
Hi, everybody! The most important feature of my container is performance. However, other features will appear later. https://github.com/alexkupri/array/blob/master/description/description.txt Today I compared my container with rope. My container outperformed it 10 times.
Hi Alex, could you include a build file (I recommend CMake)? My cursory attempt to compile main.cpp spewed lots of errors. Thanks, cheers. Jeremy
On Sun, Apr 6, 2014 at 12:45 AM, Alexander Kuprijanov <alexkupri@gmail.com>wrote:
Message: 11 Date: Fri, 4 Apr 2014 23:23:09 +1000 From: Vadim Stadnik <vadimstdk@gmail.com> Could you please provide a figure that shows data association with nodes in your data structure?
I updated the doc, follow the link above.
Thank you for the figure! IIUC, this data structure is a variant of an augmented B+ tree, since it stores elements of a data set in external nodes only and provides access to the elements through a B-tree, which implements augmenting with the counts of elements. It is a combination of two data structures, which is one of the main features of B+ trees. This data structure is quite similar to augmented B+ trees implemented in the library "STL Extensions" submitted for Boost review https://github.com/vstadnik/stl_ext_adv_review. For comparison, please have a look at Figure 1 in the section "Design and implementation of B+ trees" that shows an example of a string representation. This data structures is a combinations of a segmented array and a dynamically allocated B-tree. The difference is that this data structure is a level-linked B+ trees. It has additional links so that nodes at every internal level of the tree form a linked list. The main advantage of the level-linked variant of B+ trees is that with multiple augmenting they can support not only fast access and update operations on sequences of elements, but also fast sequential summation algorithms, which have logarithmic running time. The first suggestion is to implement a container that provides a union of interfaces of STL sequences and can be used as a replacement for std::vector, std::list and std::deque. In the library "STL extensions" this container is named std_ext_adv::sequence. In addition to this, the data structure that you developed can be used to store sorted elements. Thus, it can support interfaces of STL containers std::set, std::multiset, std::map and std::multimap. Did you consider the development of these associative containers? I would suggest implementing all of these STL containers without fast summation algorithms for the first version. The users will be able to take advantage of interchangeable containers and choose the best one for a specific application. Regards, Vadim Stadnik
Vadim Stadnik <vadimstdk <at> gmail.com> writes:
IIUC, this data structure is a variant of an augmented B+ tree, since it stores elements of a data set in external nodes only and provides access to the elements through a B-tree, which implements augmenting with the counts of elements. It is a combination of two data structures, which is one of the main features of B+ trees. This data structure is quite similar to augmented B+ trees implemented in the library "STL Extensions" submitted for Boost review https://github.com/vstadnik/stl_ext_adv_review.
Hi, Vadim! I've compared current performance of our containers. Mine outperforms yours roughly by 1.5-2 times in random single insert, delete and random access. However, yours outperforms mine up to 3 times on large arrays in iterative access. Additionally, yours keeps additional pointer per each element. This seems me quite unnecessary and ineffective. Yours takes roughly 2 times more memory. I understood for myself, how to implement iterators, so that they will be relatively fast and compatible with std::vector interface. This will be my priority #1, because everybody wants stl compatibility. Best regards, A.K.
On Tue, Apr 8, 2014 at 11:07 PM, Alex Kupriianov <alexkupri@gmail.com>wrote:
Vadim Stadnik <vadimstdk <at> gmail.com> writes:
IIUC, this data structure is a variant of an augmented B+ tree, since it stores elements of a data set in external nodes only and provides access
to
the elements through a B-tree, which implements augmenting with the counts of elements. It is a combination of two data structures, which is one of the main features of B+ trees. This data structure is quite similar to augmented B+ trees implemented in the library "STL Extensions" submitted for Boost review https://github.com/vstadnik/stl_ext_adv_review.
Hi, Vadim! I've compared current performance of our containers. Mine outperforms yours roughly by 1.5-2 times in random single insert, delete and random access. However, yours outperforms mine up to 3 times on large arrays in iterative access. Additionally, yours keeps additional pointer per each element. This seems me quite unnecessary and ineffective. Yours takes roughly 2 times more memory. I understood for myself, how to implement iterators, so that they will be relatively fast and compatible with std::vector interface. This will be my priority #1, because everybody wants stl compatibility.
Thank you for the comparison of performance. The performance of an algorithm is normally better in a native data structure than in its STL variant unless the latter can take advantage of a fast allocator. When you implement STL compliant containers your data structures can be compared with many other data structures: linked lists, red-black trees, arrays, vectors, and other augmented trees. The current implementation of augmented B+ trees that you tested is quite general. At this stage I would like to avoid the problem of premature optimization. The use of space and performance of specific algorithms can be improved in this variant of B+ trees. This task requires specification of priorities. Regards, Vadim Stadnik
Alexander Kuprijanov <alexkupri <at> gmail.com> writes:
Hi, everybody! The most important feature of my container is performance. However, other features will appear later. https://github.com/alexkupri/array/blob/master/description/description.txt Today I compared my container with rope. My container outperformed it 10 times.
Hi again, boost community! After some time of hesitating, I re-implemented the container. Shortly speaking, the container has interface like vector, but performs insertions/deletions much faster (random access, however, a bit slower). It takes O(log(N)) for insertions, deletions, random access, near O(1) for iterative access. It performs random insertions/deletions faster than vector in absolute values (not only in O() terms) on all range of container size. The things I've changed: 1) renamed the container; 2) made its interface compatible with vector; 3) added some useful functions, such as split and concatenate, which do not move all elements and require only O(log(N)) time. I hope the container will be useful extension. Code: https://github.com/alexkupri/array Manual: http://alexkupri.github.com/array/
On Thu, Jul 10, 2014 at 4:44 AM, Aleksandr Kupriianov <alexkupri@gmail.com> wrote:
Hi again, boost community! After some time of hesitating, I re-implemented the container. Shortly speaking, the container has interface like vector, but performs insertions/deletions much faster (random access, however, a bit slower). It takes O(log(N)) for insertions, deletions, random access, near O(1) for iterative access. It performs random insertions/deletions faster than vector in absolute values (not only in O() terms) on all range of container size.
Hi Aleksandr, IMO, the data structure and container that you developed are quite useful. Any data structure or container that outperforms std::vector<T> is important in practice, since std::vector<T> is the default and the most frequently used standard container. Linear computational complexity of its update operations can significantly affect performance of user algorithms. This is why I suggest keep improving your code and project. The first problem is that your files do not include Boost license. If you are planning to submit your project for Boost review please check this list of requirements: http://www.boost.org/development/requirements.html As for documentation, it is necessary to explain benefits of your data structure and container. It would be helpful to provide examples of applications in which the new container can replace std::vector<T> with significant performance gain. You can use already available examples discussed in my and other similar projects, but it would be even more impressive if you add some new examples. It is also highly desirable to include a section that explains the design of your data structure. One or two figures that illustrate the method of augmenting would help every interested programmer to better understand your achievements. Thank you for comparing performance with my containers. A bit later I will test your container and will write more comments. Regards, Vadim Stadnik
participants (7)
-
Adam Wulkiewicz -
Aleksandr Kupriianov -
Alex Kupriianov
-
Alexander Kuprijanov
-
Jeremy Murphy -
Thijs (M.A.) van den Berg -
Vadim Stadnik