headers
Boris Zbarsky | 21 Apr 2007 22:22
Picon
Favicon

Hashtable performance

Does anyone happen to recall how the performance parameters of PLDHashTable and 
PLHashTable compare?  I seem to recall something about PLDHashTable being more 
efficient in terms of memory usage and PLHashTable being faster, but I could be 
wrong... and it could depend on the exact

The reason I ask is that if what I recall is correct it might make sense to use 
PLHashTable for "temporary" hashtables (e.g. the GCTable in the cycle 
collector), no?

-Boris
Permalink | Reply | 1 comment |
headers
Benjamin Smedberg | 22 Apr 2007 01:11
Picon

Re: Hashtable performance

Boris Zbarsky wrote:
> Does anyone happen to recall how the performance parameters of
> PLDHashTable and PLHashTable compare?  I seem to recall something about
> PLDHashTable being more efficient in terms of memory usage and
> PLHashTable being faster, but I could be wrong... and it could depend on
> the exact
> 
> The reason I ask is that if what I recall is correct it might make sense
> to use PLHashTable for "temporary" hashtables (e.g. the GCTable in the
> cycle collector), no?

The primary difference is how the entry is allocated. In PLDHashTable, the
entry is allocated inline in the hash array. In PLHashTable, the entry is
allocated separately and the array points to it. Therefore in some (many?)
cases, PLHashTable will have many more allocations.

PLHashTable has some advantages: the entry class doesn't move in memory, so
external code can hold a pointer to it.

IIRC PLHashTable has some inefficiencies that I didn't like, e.g.
PLHashEntry keeps separate pointers to the key and value, which frequently
just point to offsets within the entry itself.

--BDS
Permalink | Reply | 0 comments |
headers
Jonas Sicking | 24 Apr 2007 02:26
Gravatar

Re: Hashtable performance

Boris Zbarsky wrote:
> Does anyone happen to recall how the performance parameters of 
> PLDHashTable and PLHashTable compare?  I seem to recall something about 
> PLDHashTable being more efficient in terms of memory usage and 
> PLHashTable being faster, but I could be wrong... and it could depend on 
> the exact
> 
> The reason I ask is that if what I recall is correct it might make sense 
> to use PLHashTable for "temporary" hashtables (e.g. the GCTable in the 
> cycle collector), no?

As I recall it PLDHashTable is faster for modifications, whereas 
PLHashTable is, at least under some circumstances, faster for lookups.

Also, PLDHashTable is probably worse at dealing with large entry objects 
since it shuffles the objects around, whereas PLHashTable just shuffles 
pointers around.

In all cases PLDHashTable should be more memory efficient.

/ Jonas
Permalink | Reply | 0 comments |

Gmane