Subject: Re: [boost] [multi-index] Changing hash_index_node.hpp to double linked list
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2009-04-28 14:36:35
brad higgins <bhiggins <at> arbor.net> writes:
> 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.
Hi Brad,
Yep, that's a shortcoming of the singly linked approach
in the non_unique case. I decided to keep it like that
for simplicity (code is shared with the unique variant) and
because the case of having many duplicates is definitely
not a normal scenario for hashed containers.
[...]
> 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).
Do you mean you're passing the rest of the tests? Wow,
that's a feat taking into account that the internal
structure of the code is not documented.
>
> 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?
Off the top of my head I couldn't say whether you
need to change bucket_array, I'd say it depends on the
way you're implementing the doubly linked stuff.
If you send me the modified files (eiher privately or
through the list) I can take a look and report back.
JoaquÃn M López Muñoz
Telefónica, Investigación y Desarrollo