[sldev] LLUUIDHashMap vs hash_map

[Douglas Soo]

The LLUUIDHashMap is an EXTREMELY specialized hash map that was primarily 
designed for extremely fast lookup and iteration over a map of objects 
keyed by UUIDs - specifically for the simulator, which spends a lot of its 
time iterating over lists of this type (looking up and iterating through 
objects and scripts on the simulator).

Unless you are iterating or looking through objects EXTREMELY often (enough 
to show up as more than a couple percent of time in a time-based profile), 
I would stay far away from it.  It doesn't use any of the standard STL 
semantics for iteration, and is assuredly not thread-safe, or anything else 
that you'd really like.  In fact, unless there are performance or memory 
utilization reasons, I would convert the existing code away from using it.

Also, hash_map isn't part of the official STL standard, so even though it's 
in common usage, I would stay away from it for portability reasons.  So, I 
would stick with a standard map unless you really need to iterate or look 
things up extremely frequently (> 10000 times/frame).

More about LLUUIDHashMap (for the interested):

The biggest performance bottleneck (by far) on most modern hardware is 
memory access - so all of the weird implementation of the LLUUIDHashMap is 
an attempt by me to reduce the number of times you have to do pointer 
dereferences, and reduce the resulting cache misses.  It's also pretty much 
entirely optimized to work with the number of objects/scripts that you 
typically see on a region, so it's tuned to work well for on the order of 
10s of thousands of elements - it will typically reduce the number of 
pointer dereferences to only 2 or 3 to get an item in the hash.  It also 
takes advantage of the essentially randomized bits in the UUID to reduce 
the amount of work being done to hash the elements.

It's an interesting exercise in profiling to optimize something like this - 
this is where timing-based profilers make a HUGE difference.  There was 
extensive profiling done against this implementation to optimize it.

When running synthetic benchmarks against std::map, it was substantially 
(at least 50%?) faster for both random lookups and iteration.  It was also 
being timed against our legacy containers (LLSkipMap), which were even 
slower at the time (and buggier).  We didn't look at hash_map for the 
aforementioned compatibility reasons.  That being said, this was written to 
improve the performance of some very specific inner loops on the simulator 
code.  If I remember correctly, we probably got around a 10% improvement in 
overall simulator performance by switching to this from the previous 
implementation.

- Doug

--On Thursday, September 20, 2007 2:52 PM +0200 Dale Glass 
<dale at daleglass.net> wrote:

> On Thu, Sep 20, 2007 at 01:20:48PM +0200, Dale Glass wrote:
>> I'm looking at implementing a cache storing data by LLUUID and found the
>> LLUUIDHashMap. I see it seems to be used only in LLMotionRegistry.
>>
>> Should I use it? How about making a hash function for LLUUID and using
>> that instead? I presume that simply using the first/last
>> sizeof(size_t)*8 bits of the LLUUID would work fine.
>
> Been looking a bit more at the source of LLUUIDHashMap, it's weird.
>
> It's hardcoded to 256 buckets, not even as a constant but as a magic
> number in the source (ick!)
>
> It uses an U8 for the hash key, so it can't go higher anyway.
>
> LLUUIDHashNode stores a number of elements that varies depending on the
> argument to the template (why?)
>
>
> So I'm thinking a hash_map could be better for my purposes, as I might
> want more than 256 elements (cache will probably be quite big).
>
> For the hash function I'm considering this:
>
> size_t operator()(const LLUUID&x)
> {
> 	return (size_t)x.getCRC32();
> }
>
>



--
Douglas Soo
Studio Director
Linden Lab