[m-dev.] Hash table performance

[Zoltan Somogyi]

On 30-Jan-2004, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> A spot of phorensic profiling shows why: while the hashing functions are
> fine (virtually no collisions at about 50% occupancy), every version
> hash table read incurrs at least three array accesses and every version
> hash table write incurrs at least four array accesses and seven or eight
> heap allocations.

What is the code doing with all those accesses and allocations?

> The lessons of the experience are:
> - open addressing can be much better than closed addressing;

"Can be" is not enough for many purposes, and open addressing has much
worse worst case behavior than separate chaining.

Zoltan.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------