[boost] [multi-index] Changing hash_index_node.hpp to double linked list

Subject: [boost] [multi-index] Changing hash_index_node.hpp to double linked list
From: brad higgins (bhiggins_at_[hidden])
Date: 2009-04-28 10:03:57

I am using boost multi-index, with a hashed-non-unique lookup.  In my  
data, I am expecting many hash collisions.  When I erase the multi- 
index, I find very poor performance.  On investigation, I found that  
the hash collision data structure is a single linked list, and that  
removing an element involves traversing the entire list.  Removing all  
of the elements involves traversing the list many times.  Since my  
data has many collisions, I am traversing a very long list very many  
times.

I know that the hash table is not designed for use with many  
collisions, but it is still faster in my testing on insert and  
serialization than the ordered_non_unique index specifier.  I may end  
up using ordered_non_unique to avoid the worst-case erase()  
performance, and it may be good enough for the insert() performance.   
However, I would like to investigate making the hash collisions double- 
linked.

I tried editing boost/multi_index/detail/hash_index_node.hpp, to make  
it a double-linked list, but I am seeing one of the included tests  
fail (test_safe_mode).

I can't spot any bugs in my hash_index_node.hpp changes.  What, apart  
from hash_index_node.hpp, needs to be updated, to support a double- 
linked list?  boost/multi_index/detail/bucket_array.hpp?  Others?

Thanks,
Brad