- Boost - lists.preview.boost.org

[containers] Vector-like container, which takes O(log(N)) > for insert/erase, question to Adam Wulkiewicz about iterators
by Alexander Kuprijanov 06 Apr '14

06 Apr '14

Hi, again, Adam! > > Date: Sat, 05 Apr 2014 16:59:18 +0200 > From: Adam Wulkiewicz <adam.wulkiewicz(a)gmail.com> > 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. Vector outperforms it only (roughly) 2 times on small arrays (when it contains only one leaf) on all operations, only (roughly) 3 times on iterating access on all sizes and only log(N) times on random access. But it severely (N/log(N)) outperforms vector in all insert/erase cases. See my explained test results. I still believe it's close to first choise. > 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()? That is very interesting question. Currently such sort of persistent iterators (I call them bookmarks) are not implemented. PLEASE PLEASE PLEASE, EVERYBODY, give me an example of the task when such iterators are necessary. Will this feature add feature to my container, if implemented? Best regards, A.K.

1 0

[container] Vector-like container, which takes O(log(N)) for insert/erase, response to Adam Wulkiewicz about performance
by Alexander Kuprijanov 06 Apr '14

06 Apr '14

Hi, Adam! > Date: Sat, 05 Apr 2014 16:59:18 +0200 > From: Adam Wulkiewicz <adam.wulkiewicz(a)gmail.com> > 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. I believe my calculations are reliable. I'm sorry I did not explained it earlier and did not provide clarification on github. Firstly, the output is time per one operations in milliseconds. E.g., if it says 1.00e-4, it means 1e-7 seconds or 0. 000 000 1 seconds per one operation. The operation performed many times and result is divided. Secondly, in each operation there are many calculations, by both repeating and array growing. If the line before array says "averaged on 500 measurements" and in array size is 1024, it meant that it was 500 arrays and each of them growed from 512 elements to 1024 elements, giving 256000 atomic additions. Each of them took 1.17e-04 ms in average, they all took about 30 ms. Granularity of Linux timer (which is used in test) is 1 ms, so tolerance in the case is 3%. > Instead of comparing it with a different implementation I guess it would > be sufficient to contain only 2 children in the internal nodes. > Well, I in fact found that numbers 14/28 are near optimum. (There are several optimums for different operations.) Theory agrees with practice, the best performance is when leaf/branch fits one cache line. (In fact, my container allows minimum L=4 M=4, each branch and leaf may have from 2 to 4 items. It behaves worse generally.) I tried to compare it with rope because I was asked to do so. I'll compare it with other similar containers as well. Rope has other problems such as balancing when critical and so on. Best regards, A.K.

1 0

Proposal: Vector-like container, which takes O(log(N)) for insert/erase, response to Bjorn Reese about copy-on-write
by Alexander Kuprijanov 06 Apr '14

06 Apr '14

> Date: Fri, 04 Apr 2014 19:24:53 +0200 > From: Bjorn Reese <breese(a)mail1.stofanet.dk> > To: boost(a)lists.boost.org > Subject: Re: [boost] Proposal: Vector-like container, which takes > O(log(N)) for insert/erase (Glen Fernandes) > Message-ID: <533EEAE5.2040304(a)mail1.stofanet.dk> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > > On 04/04/2014 02:10 PM, Lars Viklund wrote: > >> 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? > > Yes: > > http://www.gotw.ca/publications/optimizations.htm > Hi, Bjorn, 1) Proposed Copy-on-Write (CoW) optimization will be only option. Developer will chose, which container he or she wants: a) without CoW, b) with CoW with internal locks, c) with CoW without internal locks (very dangerous). Option "a" will be the first choise. Option "c" is used either in single-threaded apps or if he/she knows that all shallow copies are maintained in the single thtread or behind single semaphore which protects all shallow copies. 2) The article states mostly that there are ineffective optimizations of CoW. CoW by itself is not that bad. Citation: Plain 1726ms Plain_FastAlloc 642ms COW_Unsafe 1629ms COW_AtomicInt 1949ms COW_CritSec 10660ms COW_Mutex 33298ms e.g., the AtomicInt is 10-15% slower than plain, while Mutex 33 times. 3) There are situations where it's worth. Firstly, mobile/embedded devices are memory greedy. Secondly, small changes in very large arrays, such as text editors. Thirdly, no need to implement "undo" command in text editors, that reduces development time. But I see that community does not appreciate this feature so I do it in the end of my priority list. Best regards, A.K.

1 0

[git] Near future.. How do we deal with git-native libraries?
by Rene Rivera 05 Apr '14

05 Apr '14

As the owner of the Predef library which exists originally in github and not svn.. I'm wondering about some things for the near future (as in this coming week): 1. Where will the git repo live for a library? Will the repo need to stay in the boostorg organization? Or is it possible/desirable to use the existing repo that's part of my user account? 2. I notice that there's a ".gitattributes" file in the svn imported version of the Predef repo. Will I need to add that file to my actual Predef git repo? And if so, is there a single canonical version of that file I should use? And a followup.. In the future if that file changes, does it need to change for all repos consistently? Rene. -- -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

9 31

[asio] Bug: Handlers execute on the wrong strand.
by Greg Barron 04 Apr '14

04 Apr '14

Hi All, I would like to refer you to this bug report: https://svn.boost.org/trac/boost/ticket/9203 I won't paste the full contents of the bug report into this message. The executive summary is that the allocation algorithm for the implementation of asio::strand can and does allocate the implementation of an existing strand to strands that are subsequently allocated. This can have the effect that handlers wrapped in strand (b) will actually be executed on strand (a). I consider this to be a bug but if there is something that I'm misunderstanding about the operation of strands it would be great if you could help me clear it up. If the consensus is that this is a bug, what are the chances for it to be included in the 1.56 release? It is probably too late to be included in the 1.55 release. I've implemented a work around which could only be described as a hack and would be embarrassed to show it to anybody. But it gets me over my hump :). Thanks! -- Greg

5 4

Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase (Glen Fernandes)
by Alexander Kuprijanov 04 Apr '14

04 Apr '14

Hi, again, I've implemented a container which should replace vector and have O(log(N)) for insert/delete. Please review. https://github.com/alexkupri/array/blob/master/description/description.txt The code is small, the description is verbose. Best regards, A.K.

6 5

Boost.asio avoid the use of pipe
by Thomas Heller 03 Apr '14

03 Apr '14

Hi list, I'm currently trying to get a asio based software to run on CNK (a very lightweight kernel) which only implements a subset of the POSIX functions. One of the functions which is not implement is pipe. However, asio uses this in the epoll and select reactor. Is there any possibility to avoid that pipe is used? What options do I have? Cheers, Thomas

2 3

[typeof] failed to compile under dependent context
by feverzsj 03 Apr '14

03 Apr '14

hi, list here is some code failed to compile with msvc9. Not sure if it is wrong use case or bug. template<class T> struct A { static T apply() { return T(); } }; template<class T> struct B { typedef BOOST_TYPEOF_TPL(A<T>::apply()) type; // error C2064: term does not evaluate to a function taking 0 arguments }; template<class T> BOOST_TYPEOF_TPL(A<T>::apply()) foo2() // error C2064: term does not evaluate to a function taking 0 arguments { } template<class T> void foo1() { BOOST_TYPEOF_TPL(A<T>::apply()) t; // ok } Regards, zsj -- View this message in context: http://boost.2283326.n4.nabble.com/boost-typeof-failed-to-compile-under-dep… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 1

Boost.Geometry selected for MySQL
by Barend Gehrels 03 Apr '14

03 Apr '14

Hi, Recent news which is published this week (actually today): Boost.Geometry will be used for MySQL 's spatial database features. http://mysqlserverteam.com/building-mysql-with-boost/ This also means MySQL (server) will now use Boost libraries from now on. Regards, Barend

4 4

[BGL] Visual Studio 12 finish_edge() failure, general BOOST_TTI_HAS_MEMBER_FUNCTION failure?
by Michael Behrns-Miller 01 Apr '14

01 Apr '14

Hello boost! In the BGL, finish_edge() is a visitor function of DFS, but it is optional. It is made optional via BOOST_TTI_HAS_MEMBER_FUNCTION. Here's how BGL defines it: ------------- BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge) template <bool IsCallable> struct do_call_finish_edge { template <typename E, typename G, typename Vis> static void call_finish_edge(Vis& vis, const E& e, const G& g) { vis.finish_edge(e, g); } }; template <> struct do_call_finish_edge<false> { template <typename E, typename G, typename Vis> static void call_finish_edge(Vis&, const E&, const G&) {} }; template <typename E, typename G, typename Vis> void call_finish_edge(Vis& vis, const E& e, const G& g) { // Only call if method exists do_call_finish_edge<has_member_function_finish_edge<Vis, void>::value>::call_finish_edge(vis, e, g); } ------------- In all my efforts, the Visual Studio 12 compiler fails to call finish_edge(). I've tried templated versions, direct versions, virtual versions, with and without const params, inline and not inline. In every case, VS says "code will not be hit, no executable code is associated with this line. possible causes: preprocessor directives or compiler/linker optimizations". I'm in debug mode with minimal optimizations, and there's no preprocessor wrapper. It's possible there's a problem with the way I'm calling it, but it happens when I use a simple example from another user. This ticket includes very simple sample code that should fire the finish_edge() function. It does not work for me using VS 12: https://svn.boost.org/trac/boost/ticket/9770 https://svn.boost.org/trac/boost/attachment/ticket/9770/test.cc I have a large project depending on the BGL, which has been great otherwise. I've coded a workaround by using the other non-optional visitor functions. But there are edge cases (sorry, no pun intended! ha) that fail with my workaround. The only possible solution is to get finish_edge() to fire. I'd like to do it the intended way, rather than rewrite BGL code to make finish_edge() non-optional. I'll go try this with a recent version of gcc now... Thanks for any input at all! Michael Behrns-Miller

2 6