Re: boost::multi_index_container::erase very slow on FreeBSD 6.0

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: boost::multi_index_container::erase very slow on FreeBSD 6.0

Joaquin M LópezMuñoz


----- Mensaje original -----
De: bert hubert <[hidden email]>
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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::multi_index_container::erase very slow on FreeBSD 6.0

bert hubert-2
On Thu, Mar 16, 2006 at 11:58:31PM +0100, JOAQUIN_LOPEZ_MU?Z wrote:

> 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.

Didn't make a difference I'm afraid.

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

That might be an option but has other drawbacks, but I'll try. Joaquin, many
thanks for your help! I've mentioned you in the PowerDNS release notes:
http://doc.powerdns.com/changelog.html#CHANGELOG-2-9-20

I've reported the FreeBSD problem to the freebsd-hackers list:
http://lists.freebsd.org/pipermail/freebsd-hackers/2006-March/015765.html

I hope they can make something of it.

Thanks again!

--
http://www.PowerDNS.com      Open source, database driven DNS Software
http://netherlabs.nl              Open and Closed source services
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users