Re: [boost] Regression in Multi-index, 1.35?

From: joaquin_at_[hidden]
Date: 2008-04-03 08:45:19

Amit escribió:
> Joaquin M Lopez Munoz <joaquin <at> tid.es> writes:
>
>   
>> Steven is right on spot: boost::fast_pool_allocator is not correctly
>> specialized for void, as it should. I'll file a bug report about this.
>> In the meantime, you can simply replace fast_pool_allocator with
>> the following fixed_fast_pool_allocator class:
>>     
>
> Many thanks. Your specialization makes the code compile OK - have to make other
> changes  (for new thread interface) before I can run it, will report on the
> outcome.
>
> I think whole of pool needs a review - I think it hasn't been updated for a
> while. Maybe I'll volunteer once I have shipped my current project :)
>   

That'd be great! Something must be done with the handful of abandoned 
libs in Boost.

> By the way, the release notes for 1.35 state that equal_range is now more
> efficient - are we talking better computational complexity here, or less
> overhead?  Could you please point me to a description of the changes so I know
> what sort of improvement should be expected. 

Prior to 1.35, equal_range(k) was simply implemented as 
make_pair(lower_bound(x),upper_bound(x)),
that is, both ends of the range were computed independently. The new 
implementation takes advantage
of the fact that search paths down a rb-tree for the left and right ends 
of the range share their initial portion
(from the tree root down to the "top" element in the range). In terms of 
algorithmic complexity the operation
is still O(log n), but the work can de reduced by as much as 50% (when 
the range has only one element,
for instance). If you're curious about the code, look for 
"ordered_index_equal_range" at
http://boost.org/doc/libs/1_35_0/boost/multi_index/detail/ord_index_ops.hpp 
.

> And does this mean that the predicate based range lookup functions exposed by
> multi-index (ones that take a lower & uper bounder) are more efficient as well?
>   

Yep, range() has also been improved, the release notes mention both 
equal_range and range.

Best,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo