[m-rev.] for review: improve hash tables

[Peter Wang]

On 2010-07-19, Julien Fischer <juliensf at csse.unimelb.edu.au> wrote:

> >diff --git a/library/hash_table.m b/library/hash_table.m
> >index e535123..699b3da 100644
> >--- a/library/hash_table.m
> >+++ b/library/hash_table.m
> >@@ -228,6 +228,13 @@
> >
> >:- implementation.
> >
> >+    % We use a custom association list representation to reduce type_info
> >+    % allocations (assoc_list requires a type_info for list, and one for pair),
> >+    % and better locality.

That was wrong.  type_info allocations are optimised out in the common
cases for both representations.


Branches: main, 10.04.1

library/hash_table.m:
        The previous stated reason for why a fat list representation should
        perform better was partly incorrect: type_info allocations for either
        representation are irrelevant for the common paths.

diff --git a/library/hash_table.m b/library/hash_table.m
index 699b3da..e5f5562 100644
--- a/library/hash_table.m
+++ b/library/hash_table.m
@@ -228,9 +228,9 @@
 
 :- implementation.
 
-    % We use a custom association list representation to reduce type_info
-    % allocations (assoc_list requires a type_info for list, and one for pair),
-    % and better locality.
+    % We use a custom association list representation for better performance.
+    % assoc_list requires two cells to be allocated per table entry,
+    % and presumably has worse locality.
     %
     % Array bounds checks may be omitted in this module because the array
     % indices are computed by: hash(Key) mod size(Array)
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------