multi_index's hashed_index 2 performance bugs

[anonymous]

Hello

The hashed_index within the multi_index project has such a major performance problem on anything that erases (i.e. erase, replace, modify) that the hash_index is unusable unless one never erases.

The bug is reproduced by:

• rehash()ing the table to 2 million buckets
• inserting an element (which is correctly O(1))
• erasing that element

Yes, the hashed_index is documented to be O(size of bucket vector), but it should not be. erase on a hash table should be O(1) just like in the TR1.

A Possible solution to this bug is to keep an intrusive list of the nodes in the table, so begin() and the returned iterator are O(1). Another possible solution is to make begin() O(size of bucket vector) which is acceptable given that begin() is a linear interface.

Obviously, the initial rehashing of the buckets to 1 million is standard practice for optimizing hash table performance, so this should not be eliminated. Since, the bucket vector never shrinks, the problem can also be reproduced by insert()ing 2 million objects, then erase()ing them. The erase()ing will take forever.

Thanks, Sasha

[Joaquín M López Muñoz]

Hi Sasha, closing this as it's a duplicate of ​#4264, please follow the discussion there.