Performance hash versus assoc-list?

[HPW]

I used to access big lists as assoc-list.

Now with the new hash example, it would be interesting, if it is worth

to change that structure to a hash-table.



Could I expect any performance improvment or is the symbol handling

in assoc-list equal in terms of performance.

[Lutz]

As a rule of thumb I would say, if you have more then 100 associations you are better of with using the module hash.lsp. This is, what I found out benchmarking both on simple number->number associations:



100 - 0.3ms - 0.4ms - about equal

500 - 7.7ms - 2.3ms - hash 3 x faster

1000 - 30.0 ms - 4.0ms - hash 7 x faster

10000 - 11.4sec-  47.0ms - hash 200 x faster



The time to retrieve all associations was measured.  Putting an asociation using symbol hashes takes about 50% longer than retrieving them. But pushing onto or appending at the end of an ascociation list is always much faster. The symbol hash almost scales linear, while the performance on association lists quickly gets un-acceptable.



It also depends on the pattern of access, if you tend to access those assocs which have been pushed recently assoc is fast because it rarely has to search deep into the association list. My benchmarks assume that all elements are accessed about equally.



Lutz