[boost] [variant] swap performance (was: Boost.Variant swap performance)

Subject: [boost] [variant] swap performance (was: Boost.Variant swap performance)
From: Dave Abrahams (dave_at_[hidden])
Date: 2012-04-21 05:31:13

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_at_[hidden]> 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_at_[hidden]> 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