Re: [Swig-devel] How to insert into DohHash without breaking iterating over it?

[William S F. <ws...@fu...>]

On 10/11/11 15:54, Vadim Zeitlin wrote:
> On Thu, 10 Nov 2011 16:22:49 +0100 I wrote:
>
> VZ>   In any case, I want to fix this as this caused us a lot of grief. The
> VZ>  trouble is that I'm not sure what is the best way to do it. An obvious but
> VZ>  horrible solution is to restart iteration after each insertion but this
> VZ>  would make the linear search O(N^2) in number of hash elements and so is
> VZ>  unacceptable. Another straightforward solution would be to use Keys() to
> VZ>  get the list of all keys of the hash beforehand and iterate over them. This
> VZ>  is still O(N) but probably has a non negligible overhead for copying
> VZ>  (several thousands in my case) hash keys into a list and then also
> VZ>  accessing hash by key instead of using the iterator (again, both are O(1)
> VZ>  but I'd expect using the iterator to be more efficient).
>
>   Just as a proof of concept, the patch below does fix the bug but results
> in ~0.6% slowdown in my (limited) testing. This doesn't look like a lot but
> OTOH I'd prefer to avoid pessimizing SWIG even further as it's already not
> very fast (and the linear search used in this particular function
> definitely doesn't help) so I'll still try to implement the approach with a
> temporary hash, unless someone tells me it's a bad idea or suggests a
> better one.

Mmm, nasty. I don't think writing into the name hashes are written to 
that much so don't expect the list to be too long. Even in your possibly 
larger than average testcase, 0.6% slowdown isn't that much. Better a 
fix than fast and not working.

Your idea of creating a temporary hash is probably the best approach. A 
temporary List might be faster, but I doubt there will be much in it it 
because the temporary hash/list is probably not going to contain many 
members. The lookup will also need to look in the temporary hash. In 
fact, perhaps the temporary has needs to be a temporary List, because if 
you add a new node to the temporary list it will not change the order 
for further iteration.

William