- Boost - lists.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

Number of tests in boost
by Axel Ismirlian 11 Jul '14

11 Jul '14

Hello, I was wondering whether there is a precise way to count the total number of tests across all libraries? What is the total number of tests in boost? Sincerely, -Axel

2 1

Test build for 1.56 available
by Marshall Clow 11 Jul '14

11 Jul '14

I have made a test build for 1.56 and would appreciate help in finding problems with it. boost.1.56.0.tar.gz: https://dl.dropboxusercontent.com/u/11048326/boost/boost-1.56.0a1c1.tar.gz boost.1.56.0.zip: https://dl.dropboxusercontent.com/u/11048326/boost/boost-1.56.0a1c1.zip The tar.gz file builds w/o errors on my Mac. The zip version contains windows line endings. I’m looking for: * missing files/libraries * files/folders that don’t belong in the release * files/folders in the wrong places * build failures * Anything else that is wrong. One thing I’ve noticed is that these are *significantly* larger than the 1.55.0 archives. A bunch of that is because the Boost.Ublas documentation has exploded in size - but there are probably other reasons as well. Looking forward to feedback… — Marshall

15 33

Re: [boost] Libraries failing across the board.
by Matthew Musto 11 Jul '14

11 Jul '14

David, Thank you, I understand. I guess I will have to wait for 1.57 or try to merge in the development branch to my local 1.56 version as soon as it is working. I realize we do not hold releases until all tests pass but I wonder if we should do something like that for one release a year as a long term support (LTS) version. It just makes relying upon boost very difficult from a end user perspective when major development projects often times rely upon multiple libraries. Would this be worth having a larger discussion about in its own thread? Thanks, -Matt From: David Bellot <david.bellot <at> gmail.com> Subject: Re: Libraries failing across the board. <http://news.gmane.org/find-root.php?message_id=CAOE6ZJGDf%5fwxRhp50KQyEbKE1…> Newsgroups: gmane.comp.lib.boost.devel <http://news.gmane.org/gmane.comp.lib.boost.devel> Date: 2014-07-11 11:36:24 GMT (2 hours and 7 minutes ago) yes, I know it's not ideal but we haven't time to do better this time [image: :-(] I will try to update the devel branch on git if it helps On Thu, Jul 10, 2014 at 12:22 AM, Matthew Musto <matthew.musto <at> gmail.com> wrote: > David, > > Just so I am clear, you are saying that 1.56 cannot be relied upon by users > who need ublas as there is no intention of making it work? > > If that is true, this release is effectively worthless to me or anyone else > who needs any other library in conjunction with ublas? For example, I rely > heavily upon threads, serialization, asio and numeric/ublas. 1.55 did not > compile on VS2013 and there was much hope for this release which now seems > dashed. > > -Matt > > > >Date: Tue, 8 Jul 2014 23:24:15 +0100 > >From: David Bellot <david.bellot <at> gmail.com> > >To: "boost <at> lists.boost.org" <boost <at> lists.boost.org> > >Subject: Re: [boost] Libraries failing across the board. > >Message-ID: > > <CAOE6ZJGEhHEcujgXw4N2r= > >DLsn3vhx9+qSc3eN=jdfPHNSUcJA <at> mail.gmail.com> > >Content-Type: text/plain; charset=UTF-8 > > > >for ublas we decided to skip this release and concentrate on 1.57 as we > >have more patches coming. > >- D > > > > > >On Tue, Jul 8, 2014 at 10:07 PM, Beman Dawes <bdawes <at> acm.org> wrote: > > > >> Marshall is just a few days away from being able to put out a beta > release > >> candidate. (And that is very good news!) > >> > >> But we still have too many libraries failing across the board on master: > >> > >> accumulators > >> interprocess > >> numeric/ublas > >> pool > >> proto > >> spirit/repository > >> spirit/test > >> tr1 > >> wave > >> > >> See > http://www.boost.org/development/tests/master/developer/summary.html > >> > >> What is the hold up with these? Does anyone need help? > >> > >> --Beman > > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost >

1 0

Re: [boost] Interest in a new generic matrix library with specific 3D operations?
by Fabien Picarougne 11 Jul '14

11 Jul '14

Hello, I wanted to see my idea through to the end and I have updated my library to make the data container generic (https://bitbucket.org/fpicarougne/template-matrix-library) I got a little inspired from QVM but with a different implementation as you can see in the code. Now, the matrix library is independent from the storage, you can use predefined storages (see CMat.h for dense storage with SDenseStorage or SProxyArrayStorage in order to use a C array given by the user) but also built your own by derived (CRTP) from SStorage. For example, getting a column or a submatrix of a matrix is very easy. This make all the matrix operations independent from the storage type, and all the methods are usable if you have predefined basic operators (+, * ...). I admit that you can do quite the same thing with QVM, but I my opinion, factorization of methods is very easy with the architecture of my library because of inheritance. See test.cpp for a usage example. What do you think about this? Is it of interest to you? Fabien

1 0

Libraries failing across the board.
by Matthew Musto 11 Jul '14

11 Jul '14

David, Just so I am clear, you are saying that 1.56 cannot be relied upon by users who need ublas as there is no intention of making it work? If that is true, this release is effectively worthless to me or anyone else who needs any other library in conjunction with ublas? For example, I rely heavily upon threads, serialization, asio and numeric/ublas. 1.55 did not compile on VS2013 and there was much hope for this release which now seems dashed. -Matt >Date: Tue, 8 Jul 2014 23:24:15 +0100 >From: David Bellot <david.bellot(a)gmail.com> >To: "boost(a)lists.boost.org" <boost(a)lists.boost.org> >Subject: Re: [boost] Libraries failing across the board. >Message-ID: > <CAOE6ZJGEhHEcujgXw4N2r= >DLsn3vhx9+qSc3eN=jdfPHNSUcJA(a)mail.gmail.com> >Content-Type: text/plain; charset=UTF-8 > >for ublas we decided to skip this release and concentrate on 1.57 as we >have more patches coming. >- D > > >On Tue, Jul 8, 2014 at 10:07 PM, Beman Dawes <bdawes(a)acm.org> wrote: > >> Marshall is just a few days away from being able to put out a beta release >> candidate. (And that is very good news!) >> >> But we still have too many libraries failing across the board on master: >> >> accumulators >> interprocess >> numeric/ublas >> pool >> proto >> spirit/repository >> spirit/test >> tr1 >> wave >> >> See http://www.boost.org/development/tests/master/developer/summary.html >> >> What is the hold up with these? Does anyone need help? >> >> --Beman

2 1

Missing symbols when Compiling Boost on AIX 6.1
by Axel Ismirlian 10 Jul '14

10 Jul '14

Hello everyone, One of the errors that keeps popping up time and time again as I attempt to compile boost on AIX is the following: common.mkdir ../bin.v2/libs/asio/test/basic_datagram_socket_select.test common.mkdir ../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1 common.mkdir ../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug common.mkdir ../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug/threading-multi gcc.compile.c+ + ../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug/threading-multi/basic_datagram_socket.o gcc.link ../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug/threading-multi/basic_datagram_socket_select ld: 0711-224 WARNING: Duplicate symbol: .init_unit_test_suite(int, char**) ld: 0711-345 Use the -bloadmap or -bnoquiet option to obtain more information. ld: 0711-317 ERROR: Undefined symbol: .test_main(int, char**) collect2: error: ld returned 8 exit status "g++" -o "../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug/threading-multi/basic_datagram_socket_select" "../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug/threading-multi/basic_datagram_socket.o" "../bin.v2/libs/test/build/gcc-4.8.1/debug/link-static/threading-multi/libboost_test_exec_monitor.a" "../bin.v2/libs/system/build/gcc-4.8.1/debug/threading-multi/libboost_system.so" "../bin.v2/libs/regex/build/gcc-4.8.1/debug/threading-multi/libboost_regex.so" "../bin.v2/libs/date_time/build/gcc-4.8.1/debug/threading-multi/libboost_date_time.so" -lrt -g -Wl,-brtl -Wl,-bnoipath -pthread ...failed gcc.link ../bin.v2/libs/asio/test/basic_datagram_socket_select.test/gcc-4.8.1/debug/threading-multi/basic_datagram_socket_select... So this particular error happens in every single asio test, but this kind of error also happens across a few other libraries. I tried to set the gcc flag that simply states that these type of linking errors should be ignored, but many tests apparently still reference the symbol on AIX. Additionally while debugging, I realized that the power linux platform also keeps the symbols test_main undefined, but apparently manages to throw them out in the executable. My main question is where in the building framework are those symbols being thrown out? Or is the issue something bigger? Thank you for reading. Sincerely, -Axel

1 0

GSoC: Boost.Pipeline -- scheduling of segments
by Benedek Thaler 10 Jul '14

10 Jul '14

Hi I'm working on the GSoC Pipeline project, which is based on the N3534 [1] proposal. Work in progress can be found on GitHub [2]. A simple example of using the pipeline: pipeline::from(input_container) | transformation1 | t2 | t3 | output_container; When running this pipeline, items will be read from `input_container`, processed by the transformations and written to the `output_container`. Each segment should be applied in a parallel manner, this is the point of the pipeline. However, scheduling of these works is not trivial. Quoting the proposal: "The current pipeline framework uses one thread for each stage of the pipeline. To limit the use of resources, it should be possible to run with fewer threads, using work-stealing or work-sharing techniques." We are wondering if we could improve on this. Lets assume a thread pool of a single thread and the example pipeline above. On run(), the ideal would be that the thread reads *some* items from `input_container`, applies the transformations on them and pushes the results to `output_container`. That is: spending some time on each transformation then yield and pick up the next one. However, doing this would imply the transformations are reentrant. This additional constraint must be considered carefully. This behavior is implemented in the `development` branch [2]. Aside the two solutions above, Vicente J. Botet Escriba coined in the following idea: Let the threads work on a single transformation until the queue gets closed (no more input), then move to the next one. This is easy to implement and scales to as many threads as many segments are present. On the other hand, it kills the performance of the "online usecase": pipeline::from(read_message_from_socket) | process_message | send_message; It's not deterministic when the first segment will end, the pipeline will hang and won't provide any output. Also, in a slightly less strict scenario, when the end of input is specified, the latency could be just too high. To summarize, the following options are on the table: 1. Dedicate a thread to each segment (what to do with a fixed size threadpool?) 2. Constrain the transformations to be reentrant. 3. Run each transformations until there is input to be processed, from beginning to the end. We are kindly asking the recipients to share their ideas or opinions, ideally with a matching usecase. Thanks, Benedek [1]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3534.html [2]: https://github.com/erenon/pipeline/tree/development

8 35

[iterator] Move iterators to a separate namespace
by Andrey Semashev 10 Jul '14

10 Jul '14

Hi, I've created this pull request a few days ago: https://github.com/boostorg/iterator/pull/5 It basically moves all iterators to boost::iterators namespace (while still importing the symbols to boost namespace for backward compatibility). This change is also intended to fix the counting_iterator_test test on older compilers, which was broken by my previous pull request (there appeared a name clash with Boost.TypeTraits). Could it be merged?

1 1

permission to merge odeint to trunk
by Karsten Ahnert 10 Jul '14

10 Jul '14

Can I still merge the develop branch of odeint into the master? The develop branch compiles fine and the tests are running for some time now. I also guess that no other boost libraries depend on odeint, so it should be relatively safe to merge it. Btw. there were no announcements that the master branch closes for the release, so I thought there is still some time to merge develop into master. But it seems that the release of Boost 1.56 has gained momentum and I don't want to silently merge into master.

2 2