Re: [Boost-users] boost::multi_index_container::erase very slow on FreeBSD 6.0

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-03-16 17:58:31

----- Mensaje original -----
De: bert hubert <bert.hubert_at_[hidden]>
Fecha: Jueves, Marzo 16, 2006 10:59 pm
Asunto: [Boost-users] boost::multi_index_container::erase very slow
        on	FreeBSD 6.0

> Ok, regarding my previous message, I've now boiled down the 
> problem of
> quadratically slower erases to something that does happen on 
> FreeBSD 6.0 and
> doesn't happen on my Linux machines.
> 
> The problem may be due to:
> 	1) boost::multi_index container (highly unlikely)
> 	2) g++ allocator
> 	3) FreeBSD libc, if the g++ allocator relies on it
> 	4) FreeBSD kernel
> 
> And I don't even know where to start.
> 

Hello Bert,

I've just compiled and run your benchmark in Windows
(with minor modifications to substitute for Unix-specific
timing functions) and the behavior is O(N). I'm sorry
I can't be more helpful, the following is a series of
steps you can use to gain more insight into the problem:

1) Use a multimap instead of the multi_index_container.
Double the number of elements to compensate for the fact
that the multi-index container takes more memory per
element (as it has two indices.)

2) Undo 1) and try running the 100..5000 loop in reverse
order 5000..100. What do you get? If the quadratic behavior
shows as we approach n=100 (the opposite of the original
benchmark) I would tend to think the issue has to do
with memory fragmentation.

3) Try a pool allocator like for instance
boost::fast_pool_allocator:

http://boost.org/libs/pool/doc/interfaces/pool_alloc.html

I hope some of this can shed some light.

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