June 2014 - Boost - lists.preview.boost.org

Proposal: Vector-like container, which takes O(log(N)) for insert/erase, feedback
by Alexander Kuprijanov 12 Jul '14

12 Jul '14

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. > Date: Thu, 3 Apr 2014 16:39:29 -0700 > From: Glen Fernandes <glen.fernandes(a)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(a)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 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(a)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(a)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.

7 8

Help with understanding regression test results
by Andrzej Krzemienski 01 Jul '14

01 Jul '14

Hi, Recently I observed lots of test cases showing as failed in regression tests on branch 'develop' in Boost.Optional: http://www.boost.org/development/tests/develop/developer/optional.html When I try to inspect the results they are either empty or refer to the places in the code that do not exist anymore in branch 'develop', as though the test environments were using partial results of GIT commits. But the test dates are after the last commit, so it looks like something is broken with the testing framework. Anyone can help me with figuring out what to do? Regards, &rzej

5 19

[fusion] Definition for FUSION_MAX_MAP_SIZE
by Edward Diener 01 Jul '14

01 Jul '14

The documentation for fusion implies that FUSION_MAX_MAP_SIZE is defined whenever a fusion header is included. is this so ? Testing this out under Wave suggests it is not so. What fusion header needs to be included in order to bring in the definition for FUSION_MAX_MAP_SIZE ?

3 6

[utility] prior(it, n) for n being an unsigned type
by Adam Romanek 30 Jun '14

30 Jun '14

Hi! This is a re-post from boost-users mailing list, as I didn't get any response there. I've just finished investigating an issue in my code which led it to an assert/abort in certain cases. It turned out it was caused by the use of boost::prior(it, n) where n was unsigned int with some non-zero value. I found a question [1] on the mailing list back in 2004 which describes this issue. Additionally a solution to this problem was also posted in one of the replies [2]. My question is - why hasn't it made into the repository yet? The current behavior of boost::prior(it, n) when n is unsigned type is far from the one expected by its potential users so I think it should either be properly documented (warned) or fixed immediately. Am I not seeing something? WBR, Adam Romanek [1] http://lists.boost.org/Archives/boost/2004/02/61556.php [2] http://lists.boost.org/Archives/boost/2004/02/61578.php

4 11

[utility][iterator] generator_iterator tests and documentation.
by Daniel James 30 Jun '14

30 Jun '14

Hi, The generator_iterator tests and documentation are in both the utility and iterator modules. There are also some relevant issues in the inspect report for the iterator module: http://boost.cowic.de/rc/docs-inspect-develop.html#iterator

2 1

[iterator] Make operators conditionally defined
by Andrey Semashev 30 Jun '14

30 Jun '14

Hi, I've made this pull request: https://github.com/boostorg/iterator/pull/4 which makes operators defined for iterator_facade conditionally defined depending on the iterator category. As a side effect this change fixes Boost.Graph tests broken by the recent change to boost::next()/prior() [1]. Could someone take a look and merge it? [1] http://lists.boost.org/Archives/boost/2014/06/214788.php

1 0

[fusion] BOOST_FUSION_ADAPT_TPL_STRUCT
by Greg Rubino 29 Jun '14

29 Jun '14

Hello all, I'm trying to do something like this with fusion: struct exists_tag {}; template <typename A> struct unary { type_a m_name; }; template <> struct unary<exists_tag> { type_b m_name; }; BOOST_FUSION_ADAPT_TPL_STRUCT((A), (unary)(A), (type_a)(m_name)); BOOST_FUSION_ADAPT_TPL_STRUCT((), (unary)(exists_tag), (type_b)(m_name)); I'm not sure if I'm way off here, or if there is some way to accomplish this that I'm just not seeing. Here's the error that I get when I try to compile this code: ./include/query_tree.h:122:1: error: template parameters not used in partial specialization: ./include/query_tree.h:122:1: error: ‘Oper’ Repeated 8 times. Any ideas? Thanks, Greg

2 2

function convert() -- do you find it useful?
by Andrzej Krzemienski 29 Jun '14

29 Jun '14

Hi, This is the second time that I have found the following function useful when playing with variants of Optional library: template <typename T, typename U> typename std::enable_if<std::is_convertible<U, T>::value, T>::type convert(U && u) { return std::forward<U>(u); } It performs an implicit conversion from U to T, but you can call it explicitly. [1st] time I needed it to implement the behavior of value_or (described in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3672.html#optional… ): template <class U> constexpr T optional<T>::value_or(U&& v) const&; Requires: is_copy_constructible<T>::value is true and is_convertible<U&&, T>::value is true. Returns: bool(*this) ? **this : static_cast<T>(std::forward<U>(v)). This needs to be implemented in one expression in C++11, because the function is constexpr, so in the ternary operator, I could either apply no cast and risk unnecessary ambiguity in result type in certain cases, or use a static_cast and bring the explicit conversions in that I didn't want. Function convert() saved the day. [2nd] time was when trying to disable the overload in C++11 using SFINAE, but I didn't want to use enable_if (see a more complete example here: http://akrzemi1.wordpress.com/examples/overloading-enable_if-3/) template <typename U> auto value_or(U const& v) const -> decltype(convert<T>(v)) { if (*this) return this->value(); else return v; } template <typename F> auto value_or(F const& f) const -> decltype(convert<T>(f())) { if (*this) return this->value(); else return f(); } I wanted to check with Boost developers if you find such function convert generally useful (and worth adding somewhere in Boost), or is it just my specific needs. Regards, &rzej

4 6

[regex] [test] Regex auto-link-test problem
by Marcel Raad 29 Jun '14

29 Jun '14

Hi, I'm trying to set up all regression tests on my Windows machine. When I try to execute the test in regex\test\auto-link-test, I get the following error message: ..\..\..\..\b2.exe Jamfile:38: in modules.load ERROR: rule "subproject" unknown in module "Jamfile<[...]\auto-link-test>". [...]/tools/build/src/build\project.jam:311: in load-jamfile [...]/tools/build/src/build\project.jam:64: in load [...]/tools/build/src/build\project.jam:145: in project.find [...]/tools/build/src\build-system.jam:535: in load [...]\tools\build\src/kernel\modules.jam:289: in import [...]\tools\build\src/kernel/bootstrap.jam:139: in boost-build [...]\boost-build.jam:17: in module scope I noticed that the build file is called Jamfile instead of Jamfile.v2, do I have to set Boost.Build to some v1 mode?

3 3

Regression tests broken?
by John Maddock 29 Jun '14

29 Jun '14

For reasons I can't understand, large numbers (almost all actually) of the Math lib tests have just started failing on both master and develop, the error messages all relate to missing object files, for example from a PCH build like this: http://www.boost.org/development/tests/master/developer/output/teeks99-02j-… LINK : fatal error LNK1181: cannot open input file 'C:\local\teeks99-02\j\results\boost\bin.v2\libs\math\test\msvc-12.0\debug\asynch-exceptions-on\link-static\threading-multi\pch_light.obj' Or from common object files that are built with an "obj" rule: http://www.boost.org/development/tests/master/developer/teeks99-02j-win2008… LINK : fatal error LNK1181: cannot open input file 'C:\local\teeks99-02\j\results\boost\bin.v2\libs\math\test\msvc-12.0\debug\asynch-exceptions-on\link-static\threading-multi\compile_test_main.obj' I'm unable to reproduce locally (at least when building in libs/math/test), and strangely not all test runners are showing the issue - though most of them are. Anyone any ideas? Thanks, John.

4 8