----- Mensaje original -----
De: bert hubert
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