Boost C++ Libraries: Ticket #4220: Performance of erase in multi-index-container

Steven Watanabe — Sat, 15 May 2010 02:00:18 GMT

I believe this is because computing the iterator to return can be expensive.

Joaquín M López Muñoz — Sat, 15 May 2010 08:19:37 GMT

That was my hunch at first also, but the test shown as stackoverflow uses the size_type erase(const key_type& x) version of erase, not the problematic one. I've just posted there a guess along a different line.

anonymous — Sat, 15 May 2010 12:59:45 GMT

Replying to joaquin:

That was my hunch at first also, but the test shown as stackoverflow uses the size_type erase(const key_type& x) version of erase, not the problematic one. I've just posted there a guess along a different line.

Thx for your reply. yes, possibility of m_nTransactionHandle could be same value and that's why I have used it as hash_non_unique. But primary index m_nId is hashed_unique (no duplicate) and I am using that to erase from container. I think non-unique/secondary index values shouldn't impact performance while erasing entry via a primary hashed index. Anyway, I will try that out and let you know.

Rohit Joshi — Sun, 16 May 2010 19:00:25 GMT

Replying to anonymous:

Replying to joaquin:

That was my hunch at first also, but the test shown as stackoverflow uses the size_type erase(const key_type& x) version of erase, not the problematic one. I've just posted there a guess along a different line.

Thx for your reply. yes, possibility of m_nTransactionHandle could be same value and that's why I have used it as hash_non_unique. But primary index m_nId is hashed_unique (no duplicate) and I am using that to erase from container. I think non-unique/secondary index values shouldn't impact performance while erasing entry via a primary hashed index. Anyway, I will try that out and let you know.

Yes, when I make 2nd index hashed_unique, performance increased drastically. Than I tried 2ns index as ordered_unique and ordered_non_unique and performance was similar to hashed_unique. So I don't understand why hash_non_unique looses performance even though I use primary key hashed_unique to erase the objects. I have posted a link on stackoverflow (It seems I can't post a link here) for performance test results. Thx for your help.

status changed; resolution set

anonymous — Mon, 17 May 2010 06:19:34 GMT

status new → closed
resolution → invalid

Closing this report as a non-bug. Hashed indices aren't designed to work efficiently when there are *many* different equal elements.

status changed; resolution deleted

anonymous — Mon, 17 May 2010 06:21:03 GMT

status closed → reopened
resolution invalid

status changed; resolution set

Joaquín M López Muñoz — Mon, 17 May 2010 10:58:20 GMT

status reopened → closed
resolution → invalid

Closing this report as a non-bug. Hashed indices aren't designed to work efficiently when there are *many* different equal elements.

anonymous — Mon, 17 May 2010 17:56:06 GMT

Replying to joaquin:

Closing this report as a non-bug. Hashed indices aren't designed to work efficiently when there are *many* different equal elements.

Thanks for your explanation. I just found that the performance for hashed_non_unique versus hashed_unique for 2nd index is the almost same except slight overhead of checking duplicate. The bottleneck was with boost::object_pool. I don't know internal implementation but it seem it is a list where it iterate through the list to find objects.

To delete 10,000 objects from object_pool:0.480829439

To delete 20,000 objects from object_pool:5.37241036

To delete 30,000 objects from object_pool:21.4259488218

I think we need to create a bug for boost::object_pool.