[m-rev.] for review: Optimise hash table bucket lookup/set.
Peter Wang
novalazy at gmail.com
Thu Dec 1 13:13:46 AEDT 2022
hash_table is implemented on top of array, and version_hash_table is
implemented on top of version_array. To look up an array element, it is
necessary to pass a type_info representing the element type to the
lookup predicate. But the type_info is never used, so constructing it
dynamically is a waste of time.
The following change to version_hash_table.m improves the run time of a
do-nothing build of Prince (using mmc --make) on my machine
from 1.6 s to 1.55 s, with the standard library and compiler
built at the default optimisation level. When version_hash_table.m is
built with -O3, the run time improves further to 1.43 s.
library/hash_table.m:
library/version_hash_table.m:
When looking up a hash table bucket, first cast the buckets array to
a monomorphic type, look up the array element (now passing a
constant type_info), then cast the element back to its correct type.
Similarly for setting a hash table bucket, though the relative cost
of constructing a type_info should be less significant to hash table
updates.
Don't use 'elem' getter and setters.
---
library/hash_table.m | 84 +++++++++++++++++++++++-------------
library/version_hash_table.m | 49 +++++++++++++++------
2 files changed, 91 insertions(+), 42 deletions(-)
diff --git a/library/hash_table.m b/library/hash_table.m
index c91ff14bf..8d94fdf30 100644
--- a/library/hash_table.m
+++ b/library/hash_table.m
@@ -350,13 +350,56 @@ copy(Orig) = Copy :-
%---------------------------------------------------------------------------%
+:- func find_slot(hash_table(K, V), K) = int.
+:- mode find_slot(hash_table_ui, in) = out is det.
+% :- mode find_slot(in, in) = out is det.
+:- pragma inline(func(find_slot/2)).
+
+find_slot(HT, K) = HashSlot :-
+ find_slot_2(HT ^ hash_pred, K, HT ^ num_buckets, HashSlot).
+
+:- pred find_slot_2(hash_pred(K)::in(hash_pred), K::in, int::in, int::out)
+ is det.
+:- pragma inline(pred(find_slot_2/4)).
+
+find_slot_2(HashPred, K, NumBuckets, HashSlot) :-
+ HashPred(K, Hash),
+ % Since NumBuckets is a power of two, we can avoid mod.
+ HashSlot = Hash /\ (NumBuckets - 1).
+
+%---------------------------------------------------------------------------%
+
+:- pred unsafe_lookup_bucket(array(hash_bucket(K, V))::array_ui, int::in,
+ hash_bucket(K, V)::out) is det.
+
+unsafe_lookup_bucket(Buckets0, Slot, AL) :-
+ % array.unsafe_lookup takes a type_info argument but does not use it.
+ % Cast Buckets0 to a monomorphic type so the lookup call does not incur the
+ % cost of dynamically constructing a type_info.
+ private_builtin.unsafe_type_cast(Buckets0, Buckets),
+ array.unsafe_lookup(Buckets, Slot, AL0 : c_pointer),
+ private_builtin.unsafe_type_cast(AL0, AL).
+
+:- pred unsafe_set_bucket(int::in, hash_bucket(K, V)::in,
+ array(hash_bucket(K, V))::array_di, array(hash_bucket(K, V))::array_uo)
+ is det.
+
+unsafe_set_bucket(Slot, AL0, !Buckets) :-
+ % Similarly for array.unsafe_set.
+ private_builtin.unsafe_type_cast(!Buckets),
+ private_builtin.unsafe_type_cast(AL0, AL : c_pointer),
+ array.unsafe_set(Slot, AL, !Buckets),
+ private_builtin.unsafe_type_cast(!Buckets).
+
+%---------------------------------------------------------------------------%
+
set(HT0, Key, Value) = HT :-
set(Key, Value, HT0, HT).
set(Key, Value, HT0, HT) :-
HashSlot = find_slot(HT0, Key),
HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0),
- array.unsafe_lookup(Buckets0, HashSlot, HB0),
+ unsafe_lookup_bucket(Buckets0, HashSlot, HB0),
(
HB0 = hb_zero,
HB = hb_one(Key, Value),
@@ -380,7 +423,7 @@ set(Key, Value, HT0, HT) :-
InsertedNew = yes
)
),
- array.unsafe_set(HashSlot, HB, Buckets0, Buckets),
+ unsafe_set_bucket(HashSlot, HB, Buckets0, Buckets),
(
InsertedNew = no,
HT = ht(NumOccupants0, MaxOccupants, HashPred, Buckets)
@@ -396,23 +439,6 @@ set(Key, Value, HT0, HT) :-
'elem :='(K, HT, V) = set(HT, K, V).
-:- func find_slot(hash_table(K, V), K) = int.
-:- mode find_slot(hash_table_ui, in) = out is det.
-% :- mode find_slot(in, in) = out is det.
-:- pragma inline(func(find_slot/2)).
-
-find_slot(HT, K) = HashSlot :-
- find_slot_2(HT ^ hash_pred, K, HT ^ num_buckets, HashSlot).
-
-:- pred find_slot_2(hash_pred(K)::in(hash_pred), K::in, int::in, int::out)
- is det.
-:- pragma inline(pred(find_slot_2/4)).
-
-find_slot_2(HashPred, K, NumBuckets, HashSlot) :-
- HashPred(K, Hash),
- % Since NumBuckets is a power of two, we can avoid mod.
- HashSlot = Hash /\ (NumBuckets - 1).
-
:- pred update_item_in_bucket(K, V, hash_bucket(K, V), hash_bucket(K, V)).
:- mode update_item_in_bucket(in, in, in(hb_two_plus), out) is semidet.
:- mode update_item_in_bucket(in, in, in, out) is semidet.
@@ -454,7 +480,7 @@ det_insert(HT0, Key, Value) = HT :-
det_insert(Key, Value, HT0, HT) :-
HashSlot = find_slot(HT0, Key),
HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0),
- array.unsafe_lookup(Buckets0, HashSlot, HB0),
+ unsafe_lookup_bucket(Buckets0, HashSlot, HB0),
(
HB0 = hb_zero,
HB = hb_one(Key, Value)
@@ -475,7 +501,7 @@ det_insert(Key, Value, HT0, HT) :-
HB = hb_two_plus(Key, Value, K0, V0, kv_cons(K1, V1, KVs))
)
),
- array.unsafe_set(HashSlot, HB, Buckets0, Buckets),
+ unsafe_set_bucket(HashSlot, HB, Buckets0, Buckets),
NumOccupants = NumOccupants0 + 1,
( if NumOccupants > MaxOccupants then
HT = expand(NumOccupants, MaxOccupants, HashPred, Buckets)
@@ -491,13 +517,13 @@ det_update(!.HT, Key, Value) = !:HT :-
det_update(Key, Value, !HT) :-
HashSlot = find_slot(!.HT, Key),
Buckets0 = !.HT ^ buckets,
- array.unsafe_lookup(Buckets0, HashSlot, HB0),
+ unsafe_lookup_bucket(Buckets0, HashSlot, HB0),
( if update_item_in_bucket(Key, Value, HB0, HB1) then
HB = HB1
else
error($pred, "key not found")
),
- array.unsafe_set(HashSlot, HB, Buckets0, Buckets),
+ unsafe_set_bucket(HashSlot, HB, Buckets0, Buckets),
!HT ^ buckets := Buckets.
%---------------------------------------------------------------------------%
@@ -507,11 +533,11 @@ delete(HT0, Key) = HT :-
delete(Key, HT0, HT) :-
HashSlot = find_slot(HT0, Key),
- array.unsafe_lookup(HT0 ^ buckets, HashSlot, HB0),
+ unsafe_lookup_bucket(HT0 ^ buckets, HashSlot, HB0),
( if hash_bucket_remove(Key, HB0, HB) then
HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0),
NumOccupants = NumOccupants0 - 1,
- array.unsafe_set(HashSlot, HB, Buckets0, Buckets),
+ unsafe_set_bucket(HashSlot, HB, Buckets0, Buckets),
HT = ht(NumOccupants, MaxOccupants, HashPred, Buckets)
else
HT = HT0
@@ -563,7 +589,7 @@ search(HT, Key) = Value :-
search(HT, Key, Value) :-
HashSlot = find_slot(HT, Key),
- array.unsafe_lookup(HT ^ buckets, HashSlot, HB),
+ unsafe_lookup_bucket(HT ^ buckets, HashSlot, HB),
hash_bucket_search(HB, Key, Value).
:- pred hash_bucket_search(hash_bucket(K, V)::in, K::in, V::out) is semidet.
@@ -691,7 +717,7 @@ unsafe_insert_hash_buckets(I, OldBuckets, HashPred, NumBuckets, !Buckets) :-
( if I >= array.size(OldBuckets) then
true
else
- array.unsafe_lookup(OldBuckets, I, HB),
+ unsafe_lookup_bucket(OldBuckets, I, HB),
unsafe_insert_hash_bucket(HB, HashPred, NumBuckets, !Buckets),
unsafe_insert_hash_buckets(I + 1, OldBuckets, HashPred, NumBuckets,
!Buckets)
@@ -735,7 +761,7 @@ unsafe_insert_kv_list(KVs, HashPred, NumBuckets, !Buckets) :-
unsafe_insert(Key, Value, HashPred, NumBuckets, !Buckets) :-
find_slot_2(HashPred, Key, NumBuckets, HashSlot),
- array.unsafe_lookup(!.Buckets, HashSlot, HB0),
+ unsafe_lookup_bucket(!.Buckets, HashSlot, HB0),
% Unlike det_insert, we *assume* that Key is not already in HB0.
% This assumption is justified in that "no duplicate keys"
% is an invariant that the old hash table whose size we are now
@@ -750,7 +776,7 @@ unsafe_insert(Key, Value, HashPred, NumBuckets, !Buckets) :-
HB0 = hb_two_plus(K0, V0, K1, V1, KVs),
HB = hb_two_plus(Key, Value, K0, V0, kv_cons(K1, V1, KVs))
),
- array.unsafe_set(HashSlot, HB, !Buckets).
+ unsafe_set_bucket(HashSlot, HB, !Buckets).
%---------------------------------------------------------------------------%
diff --git a/library/version_hash_table.m b/library/version_hash_table.m
index d4c7a823c..8a0968373 100644
--- a/library/version_hash_table.m
+++ b/library/version_hash_table.m
@@ -307,6 +307,29 @@ find_slot_2(HashPred, K, NumBuckets, H) :-
%---------------------------------------------------------------------------%
+:- pred lookup_bucket(buckets(K, V)::in, int::in, hash_table_alist(K, V)::out)
+ is det.
+
+lookup_bucket(Buckets0, Slot, AL) :-
+ % version_array.lookup takes a type_info argument but does not use it.
+ % Cast Buckets0 to a monomorphic type so the lookup call does not incur the
+ % cost of dynamically constructing a type_info.
+ private_builtin.unsafe_type_cast(Buckets0, Buckets),
+ version_array.lookup(Buckets, Slot, AL0 : c_pointer),
+ private_builtin.unsafe_type_cast(AL0, AL).
+
+:- pred set_bucket(int::in, hash_table_alist(K, V)::in,
+ buckets(K, V)::in, buckets(K, V)::out) is det.
+
+set_bucket(Slot, AL0, !Buckets) :-
+ % Similarly for version_array.set.
+ private_builtin.unsafe_type_cast(!Buckets),
+ private_builtin.unsafe_type_cast(AL0, AL : c_pointer),
+ version_array.set(Slot, AL, !Buckets),
+ private_builtin.unsafe_type_cast(!Buckets).
+
+%---------------------------------------------------------------------------%
+
copy(HT0) = HT :-
promise_equivalent_solutions [HT] (
HT0 = ht(NumOccupants, MaxOccupants, HashPred, Buckets0),
@@ -324,7 +347,7 @@ search(HT, K, V) :-
promise_equivalent_solutions [Buckets] (
Buckets = HT ^ ht_buckets
),
- AL = Buckets ^ elem(H),
+ lookup_bucket(Buckets, H, AL),
alist_search(AL, K, V).
:- pred alist_search(hash_table_alist(K, V)::in, K::in, V::out) is semidet.
@@ -367,7 +390,7 @@ set(HT0, K, V) = HT :-
Buckets0] (
HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0)
),
- AL0 = Buckets0 ^ elem(H),
+ lookup_bucket(Buckets0, H, AL0),
(
AL0 = ht_nil,
AL = ht_single(K, V),
@@ -391,7 +414,7 @@ set(HT0, K, V) = HT :-
MayExpand = yes
)
),
- Buckets = Buckets0 ^ elem(H) := AL,
+ set_bucket(H, AL, Buckets0, Buckets),
(
MayExpand = no,
HT = ht(NumOccupants0, MaxOccupants, HashPred, Buckets)
@@ -439,7 +462,7 @@ det_insert(HT0, K, V) = HT :-
(
HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0)
),
- AL0 = Buckets0 ^ elem(H),
+ lookup_bucket(Buckets0, H, AL0),
(
AL0 = ht_nil,
AL = ht_single(K, V)
@@ -454,7 +477,7 @@ det_insert(HT0, K, V) = HT :-
AL = ht_cons(K, V, AL0)
)
),
- Buckets = Buckets0 ^ elem(H) := AL,
+ set_bucket(H, AL, Buckets0, Buckets),
NumOccupants = NumOccupants0 + 1,
( if NumOccupants > MaxOccupants then
HT = expand(NumOccupants, MaxOccupants, HashPred, Buckets)
@@ -471,13 +494,13 @@ det_update(HT0, K, V) = HT :-
promise_equivalent_solutions [Buckets0] (
Buckets0 = HT0 ^ ht_buckets
),
- AL0 = Buckets0 ^ elem(H),
+ lookup_bucket(Buckets0, H, AL0),
( if alist_replace(AL0, K, V, AL1) then
AL = AL1
else
error($pred, "key not found")
),
- Buckets = Buckets0 ^ elem(H) := AL,
+ set_bucket(H, AL, Buckets0, Buckets),
promise_equivalent_solutions [HT] (
HT = HT0 ^ ht_buckets := Buckets
).
@@ -493,9 +516,9 @@ delete(HT0, K) = HT :-
(
HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0)
),
- AL0 = Buckets0 ^ elem(H),
+ lookup_bucket(Buckets0, H, AL0),
( if alist_remove(AL0, K, AL) then
- Buckets = Buckets0 ^ elem(H) := AL,
+ set_bucket(H, AL, Buckets0, Buckets),
NumOccupants = NumOccupants0 - 1,
HT = ht(NumOccupants, MaxOccupants, HashPred, Buckets)
else
@@ -561,7 +584,7 @@ from_assoc_list(HashPred, AList) = HT :-
from_assoc_list_2([], !HT).
from_assoc_list_2([K - V | T], !HT) :-
- !HT ^ elem(K) := V,
+ set(K, V, !HT),
from_assoc_list_2(T, !HT).
%---------------------------------------------------------------------------%
@@ -596,7 +619,7 @@ reinsert_bindings(I, OldBuckets, HashPred, NumBuckets, !Buckets) :-
( if I >= size(OldBuckets) then
true
else
- AL = OldBuckets ^ elem(I),
+ lookup_bucket(OldBuckets, I, AL),
reinsert_alist(AL, HashPred, NumBuckets, !Buckets),
reinsert_bindings(I + 1, OldBuckets, HashPred, NumBuckets, !Buckets)
).
@@ -621,7 +644,7 @@ reinsert_alist(AL, HashPred, NumBuckets, !Buckets) :-
unsafe_insert(K, V, HashPred, NumBuckets, Buckets0, Buckets) :-
find_slot_2(HashPred, K, NumBuckets, H),
- AL0 = Buckets0 ^ elem(H),
+ lookup_bucket(Buckets0, H, AL0),
(
AL0 = ht_nil,
AL = ht_single(K, V)
@@ -631,7 +654,7 @@ unsafe_insert(K, V, HashPred, NumBuckets, Buckets0, Buckets) :-
),
AL = ht_cons(K, V, AL0)
),
- Buckets = Buckets0 ^ elem(H) := AL.
+ set_bucket(H, AL, Buckets0, Buckets).
%---------------------------------------------------------------------------%
--
2.38.0
More information about the reviews
mailing list