Well, it's not my library, but this looks like a serious problem to me. The only suggestion I can make at this point is to make sure it gets into Trac at http://svn.boost.org/ on Fri Apr 20 2012, David Sankel <camior-AT-gmail.com> wrote:

It looks like someone else ran into this, but there weren't any responses:

http://lists.boost.org/boost-users/2009/06/49263.php

On Fri, Apr 20, 2012 at 4:29 PM, David Sankel <camior@gmail.com> wrote:

...

I tried adding a Boost.Move optimized version and while this helped, I'm still not getting O(1) performance.

void ilPushFront3( IntList & il, int i ) { il = IntList ( std::make_pair ( i , ::boost::move( il ) ) ) ; }

unoptimized ilPushFront: 115 unoptimized ilPushFront w/ larger list: 350 optimized ilPushFront: 217 optimized ilPushFront w/ larger list: 663 move optimized ilPushFront: 121 move optimized ilPushFront w/ larger list: 368

On Fri, Apr 20, 2012 at 3:57 PM, David Sankel <camior@gmail.com> wrote:

...

It seems as though Boost.Variant doesn't take advantage of pointer swaps when it comes to use of recursive variants. In the attached file I declare a simple int list type and include two implementations of a function that adds an int to the front of a list. The first implementation, I would expect to be O(N) on the size of the list and the second implementation to be O(1) on the size of the list.

Unfortunately, the output I get is:

unoptimized ilPushFront: 129 unoptimized ilPushFront w/ larger list: 363 optimized ilPushFront: 211 optimized ilPushFront w/ larger list: 653

Any ideas why this might be happening?

David

-- David Sankel Sankel Software www.sankelsoftware.com 585 617 4748 (Office)

-- David Sankel Sankel Software www.sankelsoftware.com 585 617 4748 (Office)

-- Dave Abrahams BoostPro Computing http://www.boostpro.com