Hash class problem

[Hamish Rodda]

On Saturday 20 September 2008 22:13:24 Andreas Pakulat wrote:
> On 20.09.08 13:53:22, David Nolden wrote:
> > Am Samstag, 20. September 2008 13:26:20 schrieb Andreas Pakulat:
> > > Hi,
> > >
> > > I've recently restarted my kdevelop/win32 efforts as I really need to
> > > get an IDE on that platform up and running (one that doesn't suck for
> > > C++) and I'm having a problem with duchain and its use of a hash class.
> > >
> > > As far as I understood QHash is too slow for the needs of duchain, is
> > > that right? If so: Has somebody with insight why QHash is so slow told
> > > TT? Obviously using QHash would be the best solution to the problem.
> >
> > In test_duchain.cpp there is a test that also does some timing, and it
> > comes to the conclusion that ext::hash_map is about 2x faster then QHash.
> > Since the hashes in duchain are usually used in very tight loops,
> > performance is important, so we don't use QHash there. QHash has some
> > additional features like implicit sharing the we don't need at all in
> > those places, and those features will probably prevent QHash from ever
> > being as fast as
> > ext::hash_map.
> >
> > However now after I've removed some unused stuff from the cpp support, it
> > seems like there is only one place left where hash_map is used without
> > #ifdefs(and 2 places all in all), which is the cache in topducontext.cpp.
> > Since most of the hashes in duchain are implemented in the
> > item-repository, I think we won't need more hash_map than this, so you
> > could just do the same #ifdefs like in duchainlock.cpp/duchainlock.h for
> > the moment, and be fine.
>
> I've locally patched to use MSVC stdext::hash_map and that seems to work
> fine. So we'd only need that for MacOSX. The problem with the QHash
> fallback is that it needs ifdef's all over the code where the map is
> used because the API is different between QHash and the hash_map
> implementations. I'm currently not up to doing that, especially as I
> don't build on a platform that needs this.

If we really need the performance, it was suggested by either Roberto or Adam 
a long time back that we use Google's sparse hash - they have two versions, 
one optimised for memory consumption, and one optimised for speed.  If ever 
anyone needs efficient hash classes, it's google...:

http://code.google.com/p/google-sparsehash/

Cheers,
Hamish.