[m-rev.] diff: bug fixes and improvements for string switches
Zoltan Somogyi
zs at csse.unimelb.edu.au
Tue Aug 2 10:04:30 AEST 2011
Further improvements in the implementation of string switches, along with
some bug fixes.
If the chosen hash function does not yield any collisions for the strings
in the switch arms, then we can optimize away the table column that we would
otherwise need for open addressing. This was implemented in a previous diff.
For an ordinary (non-lookup) string switch, the hash table has two columns
in the presence of collisions and one column in their absence. Therefore if
doubling the size of the table allows us to eliminate collisions, the table
size is unaffected, though the corresponding array of labels we have to put
into the computed_goto instruction we generate has to double as well.
Thus the only cost of such doubling is an increase in "code" size, and
for small tables, the elimination of the open addressing loop may compensate
for this, at least partially.
For lookup string switches, doubling the table size this way has a bigger
space cost, but the elimination of the open addressing loop still brings
a useful speed boost.
We therefore now DO double the table size if this eliminates collisions.
In the library, compiler etc directories, this eliminates collisions in
19 out of 47 switch switches that had collisions with the standard table size.
compiler/switch_util.m:
Replace the separate sets of predicates we used to have for computing
hash maps (one for lookup switches and one for non-lookup switches)
with a single set that works for both.
Change this set to double the table size if this eliminates collisions.
This requires it to decide the table size, a task previously done
separately by each of its callers.
One version of this set had an old bug, which caused it to effectively
ignore the second and third string hash functions. This diff fixes it.
There were two bugs in my previous diff: the unneeded table column
was not being optimized away from several_soln lookup switches, and the
lookup code for one_soln lookup switches used the wrong column offset.
This diff fixes these too.
Since doubling the table size requires recalculating all the hash
values, decouple the computation of the hash values from generating
code for each switch arm, since the latter shouldn't be done more than
once.
Add a note on an old problem.
compiler/ml_string_switch.m:
compiler/string_switch.m:
Bring the code for generating code for the arms of string switches
here from switch_util.m.
tests/hard_coded/Mmakefile:
Fix the reason why the bugs mentioned above were not detected:
the relevant test cases weren't enabled.
tests/hard_coded/string_hash.m:
Update this test case to test the correspondence of the compiler's
and the runtime's versions of not just the first hash function,
but also the second and third.
runtime/mercury_string.h:
Fix a typo in a comment.
Zoltan.
cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/extra
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/extra
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/doc
cvs diff: Diffing boehm_gc/libatomic_ops/src
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/armcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops/tests
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/m4
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/ml_string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ml_string_switch.m,v
retrieving revision 1.52
diff -u -r1.52 ml_string_switch.m
--- compiler/ml_string_switch.m 27 Jul 2011 01:16:15 -0000 1.52
+++ compiler/ml_string_switch.m 27 Jul 2011 02:07:43 -0000
@@ -93,20 +93,13 @@
GotoEndStatement =
statement(ml_stmt_goto(goto_label(EndLabel)), MLDS_Context),
- % Determine how big to make the hash table. Currently we round the number
- % of cases up to the nearest power of two, and then double it. This should
- % hopefully ensure that we don't get too many hash collisions.
- list.length(Cases, NumCases),
- int.log2(NumCases, LogNumCases),
- int.pow(2, LogNumCases, RoundedNumCases),
- TableSize = 2 * RoundedNumCases,
- HashMask = TableSize - 1,
+ gen_tagged_case_codes_for_string_switch(CodeModel, Cases, StrsCaseNums,
+ map.init, CodeMap, !Info),
% Compute the hash table.
- construct_string_hash_jump_cases(Cases, TableSize, HashMask,
- gen_tagged_case_code_for_string_switch(CodeModel),
- map.init, CodeMap, unit, _, !Info, HashSlotsMap,
- HashOp, NumCollisions),
+ construct_string_hash_cases(StrsCaseNums, allow_doubling,
+ TableSize, HashSlotsMap, HashOp, NumCollisions),
+ HashMask = TableSize - 1,
% Generate the code for when the hash lookup fails.
(
@@ -278,13 +271,41 @@
%-----------------------------------------------------------------------------%
-:- pred gen_tagged_case_code_for_string_switch(code_model::in,
- tagged_case::in, int::out,
- map(int, statement)::in, map(int, statement)::out, unit::in, unit::out,
+:- pred gen_tagged_case_codes_for_string_switch(code_model::in,
+ list(tagged_case)::in, assoc_list(string, int)::out,
+ map(int, statement)::in, map(int, statement)::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+gen_tagged_case_codes_for_string_switch(_CodeModel, [], [],
+ !CodeMap, !Info).
+gen_tagged_case_codes_for_string_switch(CodeModel, [TaggedCase | TaggedCases],
+ !:StrsCaseNums, !CodeMap, !Info) :-
+ gen_tagged_case_code_for_string_switch(CodeModel,
+ TaggedCase, CaseNum, !CodeMap, !Info),
+ gen_tagged_case_codes_for_string_switch(CodeModel,
+ TaggedCases, !:StrsCaseNums, !CodeMap, !Info),
+ TaggedCase = tagged_case(MainTaggedConsId, OtherTaggedConsIds, _, _),
+ add_to_strs_casenums(CaseNum, MainTaggedConsId, !StrsCaseNums),
+ list.foldl(add_to_strs_casenums(CaseNum), OtherTaggedConsIds,
+ !StrsCaseNums).
+
+:- pred add_to_strs_casenums(int::in, tagged_cons_id::in,
+ assoc_list(string, int)::in, assoc_list(string, int)::out) is det.
+
+add_to_strs_casenums(CaseNum, TaggedConsId, !StrsCaseNums) :-
+ TaggedConsId = tagged_cons_id(_ConsId, ConsTag),
+ ( ConsTag = string_tag(String) ->
+ !:StrsCaseNums = [String - CaseNum | !.StrsCaseNums]
+ ;
+ unexpected($module, $pred, "non-string tag")
+ ).
+
+:- pred gen_tagged_case_code_for_string_switch(code_model::in, tagged_case::in,
+ int::out, map(int, statement)::in, map(int, statement)::out,
ml_gen_info::in, ml_gen_info::out) is det.
gen_tagged_case_code_for_string_switch(CodeModel, TaggedCase, CaseNum,
- !CodeMap, !Unit, !Info) :-
+ !CodeMap, !Info) :-
TaggedCase = tagged_case(MainTaggedConsId, OtherTaggedConsIds,
CaseNum, Goal),
ml_gen_goal_as_branch_block(CodeModel, Goal, GoalStatement, !Info),
Index: compiler/string_switch.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/string_switch.m,v
retrieving revision 1.74
diff -u -r1.74 string_switch.m
--- compiler/string_switch.m 26 Jul 2011 00:25:22 -0000 1.74
+++ compiler/string_switch.m 28 Jul 2011 07:23:33 -0000
@@ -30,7 +30,12 @@
% duplicate them, and dupelim, which can replace them with other labels)
% would have to be taught to reflect any changes they make in the global
% data. It is the last step that is the killer in terms of difficulty
-% of implementation.
+% of implementation. One possible way around the problem would be to do
+% the code generation and optimization as we do now, just recording a bit
+% more information during code generation about which numbers in static data
+% refer to which computed_gotos, and then, after all the optimizations are
+% done, to go back and replace all the indicated numbers with the corresponding
+% final labels.
%
%-----------------------------------------------------------------------------%
@@ -72,6 +77,7 @@
:- import_module backend_libs.builtin_ops.
:- import_module backend_libs.switch_util.
+:- import_module hlds.hlds_data.
:- import_module hlds.hlds_goal.
:- import_module hlds.hlds_llds.
:- import_module ll_backend.lookup_util.
@@ -102,22 +108,15 @@
llds_instr(comment("string hash jump switch"), "")
),
- % Determine how big to make the hash table. Currently we round the number
- % of cases up to the nearest power of two, and then double it.
- % This should hopefully ensure that we don't get too many hash collisions.
-
- list.length(Cases, NumCases),
- int.log2(NumCases, LogNumCases),
- int.pow(2, LogNumCases, RoundedNumCases),
- TableSize = 2 * RoundedNumCases,
- HashMask = TableSize - 1,
+ % Generate code for the cases, and remember the label of each case.
+ map.init(CaseLabelMap0),
+ represent_tagged_cases_in_string_switch(Params, Cases, StrsLabels,
+ CaseLabelMap0, CaseLabelMap, no, MaybeEnd, !CI),
% Compute the hash table.
- map.init(CaseLabelMap0),
- construct_string_hash_jump_cases(Cases, TableSize, HashMask,
- represent_tagged_case_for_llds(Params),
- CaseLabelMap0, CaseLabelMap, no, MaybeEnd, !CI, HashSlotsMap,
- HashOp, NumCollisions),
+ construct_string_hash_cases(StrsLabels, allow_doubling,
+ TableSize, HashSlotsMap, HashOp, NumCollisions),
+ HashMask = TableSize - 1,
% Generate the data structures for the hash table.
FailLabel = HashSwitchInfo ^ shsi_fail_label,
@@ -190,6 +189,34 @@
FailLabel, NumCollisions, !RevTableRows, !RevMaybeTargets)
).
+:- pred represent_tagged_cases_in_string_switch(represent_params::in,
+ list(tagged_case)::in, assoc_list(string, label)::out,
+ case_label_map::in, case_label_map::out,
+ branch_end::in, branch_end::out, code_info::in, code_info::out) is det.
+
+represent_tagged_cases_in_string_switch(_, [], [],
+ !CaseLabelMap, !MaybeEnd, !CI).
+represent_tagged_cases_in_string_switch(Params, [Case | Cases], !:StrsLabels,
+ !CaseLabelMap, !MaybeEnd, !CI) :-
+ represent_tagged_case_for_llds(Params, Case, Label,
+ !CaseLabelMap, !MaybeEnd, !CI),
+ represent_tagged_cases_in_string_switch(Params, Cases, !:StrsLabels,
+ !CaseLabelMap, !MaybeEnd, !CI),
+ Case = tagged_case(MainTaggedConsId, OtherTaggedConsIds, _, _),
+ add_to_strs_labels(Label, MainTaggedConsId, !StrsLabels),
+ list.foldl(add_to_strs_labels(Label), OtherTaggedConsIds, !StrsLabels).
+
+:- pred add_to_strs_labels(label::in, tagged_cons_id::in,
+ assoc_list(string, label)::in, assoc_list(string, label)::out) is det.
+
+add_to_strs_labels(Label, TaggedConsId, !StrsLabels) :-
+ TaggedConsId = tagged_cons_id(_ConsId, Tag),
+ ( Tag = string_tag(String) ->
+ !:StrsLabels = [String - Label | !.StrsLabels]
+ ;
+ unexpected($module, $pred, "non-string tag")
+ ).
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -232,15 +259,10 @@
llds_instr(comment("string hash simple lookup switch"), "")
),
- list.length(CaseValues, NumCases),
- int.log2(NumCases, LogNumCases),
- int.pow(2, LogNumCases, RoundedNumCases),
- TableSize = 2 * RoundedNumCases,
- HashMask = TableSize - 1,
-
% Compute the hash table.
- construct_string_hash_lookup_cases(CaseValues, TableSize, HashMask,
- HashSlotsMap, HashOp, NumCollisions),
+ construct_string_hash_cases(CaseValues, allow_doubling,
+ TableSize, HashSlotsMap, HashOp, NumCollisions),
+ HashMask = TableSize - 1,
list.length(OutVars, NumOutVars),
% For the LLDS backend, array indexing ops don't need the element
@@ -248,10 +270,12 @@
list.duplicate(NumOutVars, scalar_elem_generic, OutElemTypes),
DummyOutRvals = list.map(default_value_for_type, OutTypes),
( NumCollisions = 0 ->
+ NumPrevColumns = 1,
NumColumns = 1 + NumOutVars,
ArrayElemTypes = [scalar_elem_string | OutElemTypes],
RowElemTypes = [lt_string | OutTypes]
;
+ NumPrevColumns = 2,
NumColumns = 2 + NumOutVars,
ArrayElemTypes = [scalar_elem_string, scalar_elem_int | OutElemTypes],
RowElemTypes = [lt_string, lt_integer | OutTypes]
@@ -287,7 +311,7 @@
mem_addr(heap_ref(VectorAddrRval, 0, lval(RowStartReg)))),
"set up base reg")
),
- generate_offset_assigns(OutVars, 2, BaseReg, !CI)
+ generate_offset_assigns(OutVars, NumPrevColumns, BaseReg, !CI)
),
% We keep track of what variables are supposed to be live at the end
@@ -368,15 +392,10 @@
llds_instr(comment("string hash several soln lookup switch"), "")
),
- list.length(CaseSolns, NumCases),
- int.log2(NumCases, LogNumCases),
- int.pow(2, LogNumCases, RoundedNumCases),
- TableSize = 2 * RoundedNumCases,
- HashMask = TableSize - 1,
-
% Compute the hash table.
- construct_string_hash_lookup_cases(CaseSolns, TableSize, HashMask,
+ construct_string_hash_cases(CaseSolns, allow_doubling, TableSize,
HashSlotsMap, HashOp, NumCollisions),
+ HashMask = TableSize - 1,
list.length(OutVars, NumOutVars),
% For the LLDS backend, array indexing ops don't need the element
@@ -415,8 +434,9 @@
DummyOutRvals = list.map(default_value_for_type, OutTypes),
LaterSolnArrayCord0 = singleton(DummyOutRvals),
construct_string_hash_several_soln_lookup_vector(0, TableSize,
- HashSlotsMap, DummyOutRvals, NumOutVars, [], RevMainRows,
- InitLaterSolnRowNumber, LaterSolnArrayCord0, LaterSolnArrayCord,
+ HashSlotsMap, DummyOutRvals, NumOutVars, NumCollisions,
+ [], RevMainRows, InitLaterSolnRowNumber,
+ LaterSolnArrayCord0, LaterSolnArrayCord,
0, OneSolnCaseCount, 0, SeveralSolnsCaseCount),
list.reverse(RevMainRows, MainRows),
LaterSolnArray = cord.list(LaterSolnArrayCord),
@@ -462,13 +482,13 @@
Code = CommentCode ++ HashSearchCode ++ EndLabelCode.
:- pred construct_string_hash_several_soln_lookup_vector(int::in, int::in,
- map(int, string_hash_slot(soln_consts(rval)))::in, list(rval)::in, int::in,
- list(list(rval))::in, list(list(rval))::out,
+ map(int, string_hash_slot(soln_consts(rval)))::in, list(rval)::in,
+ int::in, int::in, list(list(rval))::in, list(list(rval))::out,
int::in, cord(list(rval))::in, cord(list(rval))::out,
int::in, int::out, int::in, int::out) is det.
construct_string_hash_several_soln_lookup_vector(Slot, TableSize, HashSlotMap,
- DummyOutRvals, NumOutVars,
+ DummyOutRvals, NumOutVars, NumCollisions,
!RevMainRows, !.LaterNextRow, !LaterSolnArray,
!OneSolnCaseCount, !SeveralSolnsCaseCount) :-
( Slot = TableSize ->
@@ -482,8 +502,15 @@
Soln = one_soln(OutVarRvals),
!:OneSolnCaseCount = !.OneSolnCaseCount + 1,
ZeroRval = const(llconst_int(0)),
- MainRow = [StringRval, NextSlotRval, ZeroRval, ZeroRval
- | OutVarRvals]
+ % The first ZeroRval means there is exactly one solution for
+ % this case; the second ZeroRval is a dummy that won't be
+ % referenced.
+ MainRowTail = [ZeroRval, ZeroRval | OutVarRvals],
+ ( NumCollisions = 0 ->
+ MainRow = [StringRval | MainRowTail]
+ ;
+ MainRow = [StringRval, NextSlotRval | MainRowTail]
+ )
;
Soln = several_solns(FirstSolnRvals, LaterSolns),
!:SeveralSolnsCaseCount = !.SeveralSolnsCaseCount + 1,
@@ -493,24 +520,30 @@
* NumOutVars,
FirstRowRval = const(llconst_int(FirstRowOffset)),
LastRowRval = const(llconst_int(LastRowOffset)),
- MainRow = [StringRval, NextSlotRval, FirstRowRval, LastRowRval
- | FirstSolnRvals],
+ MainRowTail = [FirstRowRval, LastRowRval | FirstSolnRvals],
+ ( NumCollisions = 0 ->
+ MainRow = [StringRval | MainRowTail]
+ ;
+ MainRow = [StringRval, NextSlotRval | MainRowTail]
+ ),
!:LaterNextRow = !.LaterNextRow + NumLaterSolns,
!:LaterSolnArray = !.LaterSolnArray ++ from_list(LaterSolns)
)
;
+ % The zero in the StringRval slot means that this bucket is empty.
StringRval = const(llconst_int(0)),
NextSlotRval = const(llconst_int(-2)),
ZeroRval = const(llconst_int(0)),
- % The first ZeroRval means there is exactly one solution for
- % this case; the second ZeroRval is a dummy that won't be
- % referenced.
- MainRow = [StringRval, NextSlotRval, ZeroRval, ZeroRval
- | DummyOutRvals]
+ MainRowTail = [ZeroRval, ZeroRval | DummyOutRvals],
+ ( NumCollisions = 0 ->
+ MainRow = [StringRval | MainRowTail]
+ ;
+ MainRow = [StringRval, NextSlotRval | MainRowTail]
+ )
),
!:RevMainRows = [MainRow | !.RevMainRows],
construct_string_hash_several_soln_lookup_vector(Slot + 1, TableSize,
- HashSlotMap, DummyOutRvals, NumOutVars,
+ HashSlotMap, DummyOutRvals, NumOutVars, NumCollisions,
!RevMainRows, !.LaterNextRow, !LaterSolnArray,
!OneSolnCaseCount, !SeveralSolnsCaseCount)
).
Index: compiler/switch_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/switch_util.m,v
retrieving revision 1.58
diff -u -r1.58 switch_util.m
--- compiler/switch_util.m 26 Jul 2011 00:25:22 -0000 1.58
+++ compiler/switch_util.m 29 Jul 2011 05:57:11 -0000
@@ -184,21 +184,19 @@
:- type string_hash_slot(CaseRep)
---> string_hash_slot(string, int, CaseRep).
- % For a string jump switch, compute the hash value for each case in the
- % list of cases, and store the cases in a map from hash values to cases.
- %
-:- pred construct_string_hash_jump_cases(list(tagged_case)::in,
- int::in, int::in,
- pred(tagged_case, CaseRep, StateA, StateA, StateB, StateB, StateC, StateC)
- ::in(pred(in, out, in, out, in, out, in, out) is det),
- StateA::in, StateA::out, StateB::in, StateB::out, StateC::in, StateC::out,
- map(int, string_hash_slot(CaseRep))::out, unary_op::out, int::out) is det.
+:- type table_size_upgrade
+ ---> keep_first_size
+ ; allow_doubling.
- % For a string lookup switch, compute the hash value for each string,
- % and store the associated data in a map from the hash values.
+ % construct_string_hash_cases(StrsData, AllowDouble,
+ % TableSize, HashMap, HashOp, NumCollisions):
+ %
+ % For a string switch, compute the hash value for each string in the
+ % arms, and store the results as a map from hash values to case
+ % representations.
%
-:- pred construct_string_hash_lookup_cases(assoc_list(string, CaseRep)::in,
- int::in, int::in, map(int, string_hash_slot(CaseRep))::out,
+:- pred construct_string_hash_cases(assoc_list(string, CaseRep)::in,
+ table_size_upgrade::in, int::out, map(int, string_hash_slot(CaseRep))::out,
unary_op::out, int::out) is det.
%-----------------------------------------------------------------------------%
@@ -742,37 +740,102 @@
% Stuff for string hash switches.
%
-construct_string_hash_jump_cases(TaggedCases, TableSize, HashMask,
- RepresentCase, !StateA, !StateB, !StateC, HashSlotsMap,
- HashOp, NumCollisions) :-
- string_hash_jump_cases(TaggedCases, HashMask, RepresentCase,
- !StateA, !StateB, !StateC,
- map.init, HashValsMap1, map.init, HashValsMap2, map.init, HashValsMap3,
- 0, NumCollisions1, 0, NumCollisions2, 0, NumCollisions3),
+construct_string_hash_cases(StrsDatas, Upgrade, TableSize,
+ HashSlotsMap, HashOp, NumCollisions) :-
+ % Determine how big to make the hash table. Currently we round the number
+ % of strings up to the nearest power of two, and then double it.
+ % If this yields a hash table without collisions, fine.
+ % Otherwise, if our caller allows us, we see whether we can avoid
+ % coliisions if we double the table size again.
+
+ list.length(StrsDatas, NumStrs),
+ int.log2(NumStrs, LogNumStrs),
+ int.pow(2, LogNumStrs, RoundedUpNumStrs),
+
+ TableSizeA = 2 * RoundedUpNumStrs,
+ % With this tablesize, the hash table load factor will be
+ % between 0.25 and 0.5.
+ HashMaskA = TableSizeA - 1,
+ string_hash_cases(StrsDatas, HashMaskA,
+ map.init, HashValsMap1A, map.init, HashValsMap2A,
+ map.init, HashValsMap3A,
+ 0, NumCollisions1A, 0, NumCollisions2A, 0, NumCollisions3A),
trace [compiletime(flag("hashcollisions")), io(!IO)] (
- io.format("string jump hash collisions: %d %d %d\n",
- [i(NumCollisions1), i(NumCollisions2), i(NumCollisions3)], !IO)
+ io.format("string hash collisions A: %d %d %d\n",
+ [i(NumCollisions1A), i(NumCollisions2A), i(NumCollisions3A)], !IO)
),
- ( NumCollisions1 =< NumCollisions2, NumCollisions1 =< NumCollisions3 ->
- HashValsMap = HashValsMap1,
- HashOp = hash_string,
- NumCollisions = NumCollisions1
- ; NumCollisions2 =< NumCollisions3 ->
- HashValsMap = HashValsMap2,
- HashOp = hash_string2,
- NumCollisions = NumCollisions2
- ;
- HashValsMap = HashValsMap3,
- HashOp = hash_string3,
- NumCollisions = NumCollisions3
+ ( NumCollisions1A =< NumCollisions2A, NumCollisions1A =< NumCollisions3A ->
+ HashValsMapA = HashValsMap1A,
+ HashOpA = hash_string,
+ NumCollisionsA = NumCollisions1A
+ ; NumCollisions2A =< NumCollisions3A ->
+ HashValsMapA = HashValsMap2A,
+ HashOpA = hash_string2,
+ NumCollisionsA = NumCollisions2A
+ ;
+ HashValsMapA = HashValsMap3A,
+ HashOpA = hash_string3,
+ NumCollisionsA = NumCollisions3A
+ ),
+
+ (
+ ( NumCollisionsA = 0
+ ; Upgrade = keep_first_size
+ )
+ ->
+ TableSize = TableSizeA,
+ HashValsMap = HashValsMapA,
+ HashOp = HashOpA,
+ NumCollisions = NumCollisionsA
+ ;
+ TableSizeB = 4 * RoundedUpNumStrs,
+ % With this tablesize, the hash table load factor will be
+ % between 0.125 and 0.25.
+ HashMaskB = TableSizeB - 1,
+ string_hash_cases(StrsDatas, HashMaskB,
+ map.init, HashValsMap1B, map.init, HashValsMap2B,
+ map.init, HashValsMap3B,
+ 0, NumCollisions1B, 0, NumCollisions2B, 0, NumCollisions3B),
+ trace [compiletime(flag("hashcollisions")), io(!IO)] (
+ io.format("string hash collisions B: %d %d %d\n",
+ [i(NumCollisions1B), i(NumCollisions2B), i(NumCollisions3B)],
+ !IO)
+ ),
+ ( NumCollisions1B = 0 ->
+ TableSize = TableSizeB,
+ HashValsMap = HashValsMap1B,
+ HashOp = hash_string,
+ NumCollisions = NumCollisions1B
+ ; NumCollisions2B = 0 ->
+ TableSize = TableSizeB,
+ HashValsMap = HashValsMap2B,
+ HashOp = hash_string2,
+ NumCollisions = NumCollisions2B
+ ; NumCollisions3B = 0 ->
+ TableSize = TableSizeB,
+ HashValsMap = HashValsMap3B,
+ HashOp = hash_string3,
+ NumCollisions = NumCollisions3B
+ ;
+ TableSize = TableSizeA,
+ HashValsMap = HashValsMapA,
+ HashOp = HashOpA,
+ NumCollisions = NumCollisionsA
+ ),
+ trace [compiletime(flag("hashcollisions")), io(!IO)] (
+ ( NumCollisions = 0, NumCollisionsA > 0 ->
+ io.write_string("string hash IMPROVEMENT\n", !IO)
+ ;
+ io.write_string("string hash NO IMPROVEMENT\n", !IO)
+ )
+ )
),
map.to_assoc_list(HashValsMap, HashValsList),
calc_string_hash_slots(TableSize, HashValsList, HashValsMap, HashSlotsMap).
-:- pred string_hash_jump_cases(list(tagged_case)::in, int::in,
- pred(tagged_case, CaseRep, StateA, StateA, StateB, StateB, StateC, StateC)
- ::in(pred(in, out, in, out, in, out, in, out) is det),
- StateA::in, StateA::out, StateB::in, StateB::out, StateC::in, StateC::out,
+%-----------------------------------------------------------------------------%
+
+:- pred string_hash_cases(assoc_list(string, CaseRep)::in, int::in,
map(int, assoc_list(string, CaseRep))::in,
map(int, assoc_list(string, CaseRep))::out,
map(int, assoc_list(string, CaseRep))::in,
@@ -781,25 +844,19 @@
map(int, assoc_list(string, CaseRep))::out,
int::in, int::out, int::in, int::out, int::in, int::out) is det.
-string_hash_jump_cases([], _, _,
- !StateA, !StateB, !StateC, !HashMap1, !HashMap2, !HashMap3,
+string_hash_cases([], _, !HashMap1, !HashMap2, !HashMap3,
!NumCollisions1, !NumCollisions2, !NumCollisions3).
-string_hash_jump_cases([TaggedCase | TaggedCases], HashMask, RepresentCase,
- !StateA, !StateB, !StateC, !HashMap1, !HashMap2, !HashMap3,
+string_hash_cases([StrData | StrsDatas], HashMask,
+ !HashMap1, !HashMap2, !HashMap3,
!NumCollisions1, !NumCollisions2, !NumCollisions3) :-
- RepresentCase(TaggedCase, CaseRep, !StateA, !StateB, !StateC),
- TaggedCase = tagged_case(MainTaggedConsId, OtherTaggedConsIds, _, _),
- string_hash_cons_id(CaseRep, HashMask, MainTaggedConsId,
+ string_hash_case(StrData, HashMask,
!HashMap1, !HashMap2, !HashMap3,
!NumCollisions1, !NumCollisions2, !NumCollisions3),
- list.foldl6(string_hash_cons_id(CaseRep, HashMask), OtherTaggedConsIds,
+ string_hash_cases(StrsDatas, HashMask,
!HashMap1, !HashMap2, !HashMap3,
- !NumCollisions1, !NumCollisions2, !NumCollisions3),
- string_hash_jump_cases(TaggedCases, HashMask, RepresentCase,
- !StateA, !StateB, !StateC, !HashMap1, !HashMap2, !HashMap3,
!NumCollisions1, !NumCollisions2, !NumCollisions3).
-:- pred string_hash_cons_id(CaseRep::in, int::in, tagged_cons_id::in,
+:- pred string_hash_case(pair(string, CaseRep)::in, int::in,
map(int, assoc_list(string, CaseRep))::in,
map(int, assoc_list(string, CaseRep))::out,
map(int, assoc_list(string, CaseRep))::in,
@@ -808,107 +865,34 @@
map(int, assoc_list(string, CaseRep))::out,
int::in, int::out, int::in, int::out, int::in, int::out) is det.
-string_hash_cons_id(CaseRep, HashMask, TaggedConsId,
+string_hash_case(StrCaseRep, HashMask,
!HashMap1, !HashMap2, !HashMap3,
!NumCollisions1, !NumCollisions2, !NumCollisions3) :-
- TaggedConsId = tagged_cons_id(_ConsId, Tag),
- ( Tag = string_tag(StringPrime) ->
- String = StringPrime
- ;
- unexpected($module, $pred, "non-string case?")
- ),
- StringCaseRep = String - CaseRep,
+ StrCaseRep = String - _CaseRep,
HashVal1 = string.hash(String) /\ HashMask,
HashVal2 = string.hash2(String) /\ HashMask,
HashVal3 = string.hash3(String) /\ HashMask,
( map.search(!.HashMap1, HashVal1, OldEntries1) ->
- map.det_update(HashVal1, [StringCaseRep | OldEntries1], !HashMap1),
+ map.det_update(HashVal1, [StrCaseRep | OldEntries1], !HashMap1),
!:NumCollisions1 = !.NumCollisions1 + 1
;
- map.det_insert(HashVal1, [StringCaseRep], !HashMap1)
+ map.det_insert(HashVal1, [StrCaseRep], !HashMap1)
),
( map.search(!.HashMap2, HashVal2, OldEntries2) ->
- map.det_update(HashVal2, [StringCaseRep | OldEntries2], !HashMap2),
+ map.det_update(HashVal2, [StrCaseRep | OldEntries2], !HashMap2),
!:NumCollisions2 = !.NumCollisions2 + 1
;
- map.det_insert(HashVal2, [StringCaseRep], !HashMap2)
+ map.det_insert(HashVal2, [StrCaseRep], !HashMap2)
),
( map.search(!.HashMap3, HashVal3, OldEntries3) ->
- map.det_update(HashVal3, [StringCaseRep | OldEntries3], !HashMap3),
+ map.det_update(HashVal3, [StrCaseRep | OldEntries3], !HashMap3),
!:NumCollisions3 = !.NumCollisions3 + 1
;
- map.det_insert(HashVal3, [StringCaseRep], !HashMap3)
+ map.det_insert(HashVal3, [StrCaseRep], !HashMap3)
).
%-----------------------------------------------------------------------------%
-construct_string_hash_lookup_cases(StrsDatas, TableSize, HashMask,
- HashSlotsMap, HashOp, NumCollisions) :-
- string_hash_lookup_cases(StrsDatas, HashMask,
- map.init, HashValsMap1, map.init, HashValsMap2, map.init, HashValsMap3,
- 0, NumCollisions1, 0, NumCollisions2, 0, NumCollisions3),
- trace [compiletime(flag("hash_collisions")), io(!IO)] (
- io.format("string lookup hash collisions: %d %d %d\n",
- [i(NumCollisions1), i(NumCollisions2), i(NumCollisions3)], !IO)
- ),
- ( NumCollisions1 =< NumCollisions2, NumCollisions1 =< NumCollisions3 ->
- HashValsMap = HashValsMap1,
- HashOp = hash_string,
- NumCollisions = NumCollisions1
- ; NumCollisions2 =< NumCollisions3 ->
- HashValsMap = HashValsMap2,
- HashOp = hash_string2,
- NumCollisions = NumCollisions2
- ;
- HashValsMap = HashValsMap3,
- HashOp = hash_string3,
- NumCollisions = NumCollisions3
- ),
- map.to_assoc_list(HashValsMap, HashValsList),
- calc_string_hash_slots(TableSize, HashValsList, HashValsMap, HashSlotsMap).
-
-:- pred string_hash_lookup_cases(assoc_list(string, CaseRep)::in, int::in,
- map(int, assoc_list(string, CaseRep))::in,
- map(int, assoc_list(string, CaseRep))::out,
- map(int, assoc_list(string, CaseRep))::in,
- map(int, assoc_list(string, CaseRep))::out,
- map(int, assoc_list(string, CaseRep))::in,
- map(int, assoc_list(string, CaseRep))::out,
- int::in, int::out, int::in, int::out, int::in, int::out) is det.
-
-string_hash_lookup_cases([], _, !HashMap1, !HashMap2, !HashMap3,
- !NumCollisions1, !NumCollisions2, !NumCollisions3).
-string_hash_lookup_cases([StrData | StrsDatas], HashMask,
- !HashMap1, !HashMap2, !HashMap3,
- !NumCollisions1, !NumCollisions2, !NumCollisions3) :-
- StrData = Str - _Data,
- HashVal1 = string.hash(Str) /\ HashMask,
- HashVal2 = string.hash(Str) /\ HashMask,
- HashVal3 = string.hash(Str) /\ HashMask,
- ( map.search(!.HashMap1, HashVal1, OldEntries1) ->
- map.det_update(HashVal1, [StrData | OldEntries1], !HashMap1),
- !:NumCollisions1 = !.NumCollisions1 + 1
- ;
- map.det_insert(HashVal1, [StrData], !HashMap1)
- ),
- ( map.search(!.HashMap2, HashVal2, OldEntries2) ->
- map.det_update(HashVal2, [StrData | OldEntries2], !HashMap2),
- !:NumCollisions2 = !.NumCollisions2 + 1
- ;
- map.det_insert(HashVal2, [StrData], !HashMap2)
- ),
- ( map.search(!.HashMap3, HashVal3, OldEntries3) ->
- map.det_update(HashVal3, [StrData | OldEntries3], !HashMap3),
- !:NumCollisions3 = !.NumCollisions3 + 1
- ;
- map.det_insert(HashVal3, [StrData], !HashMap3)
- ),
- string_hash_lookup_cases(StrsDatas, HashMask,
- !HashMap1, !HashMap2, !HashMap3,
- !NumCollisions1, !NumCollisions2, !NumCollisions3).
-
-%-----------------------------------------------------------------------------%
-
% calc_string_hash_slots(AssocList, HashMap, Map):
%
% For each (HashVal - Case) pair in AssocList, allocate a hash slot in Map
cvs diff: Diffing compiler/notes
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_cairo
cvs diff: Diffing extras/graphics/mercury_cairo/samples
cvs diff: Diffing extras/graphics/mercury_cairo/samples/data
cvs diff: Diffing extras/graphics/mercury_cairo/tutorial
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/monte
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
Index: runtime/mercury_string.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_string.h,v
retrieving revision 1.40
diff -u -r1.40 mercury_string.h
--- runtime/mercury_string.h 20 May 2011 04:16:55 -0000 1.40
+++ runtime/mercury_string.h 29 Jul 2011 06:19:34 -0000
@@ -196,7 +196,7 @@
** It should not be used directly. Use MR_hash_string{,2,3}() instead.
**
** Note that these functions are also defined in library/string.m.
-** The definition heres and in string.m must be kept equivalent.
+** The definition here and in string.m must be kept equivalent.
*/
#define MR_do_hash_string(hash, s) \
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/appengine
cvs diff: Diffing samples/appengine/war
cvs diff: Diffing samples/appengine/war/WEB-INF
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/concurrency
cvs diff: Diffing samples/concurrency/dining_philosophers
cvs diff: Diffing samples/concurrency/midimon
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/java_interface
cvs diff: Diffing samples/java_interface/java_calls_mercury
cvs diff: Diffing samples/java_interface/mercury_calls_java
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.411
diff -u -r1.411 Mmakefile
--- tests/hard_coded/Mmakefile 28 Jul 2011 04:52:53 -0000 1.411
+++ tests/hard_coded/Mmakefile 1 Aug 2011 03:41:28 -0000
@@ -266,6 +266,8 @@
string_substring \
string_suffix_bug \
string_switch \
+ string_switch2 \
+ string_switch3 \
string_various \
sv_nested_closures \
sv_record_update \
@@ -643,7 +645,7 @@
# string_hash tests features of the Mercury C runtime.
# It requires too much memory to be used in non-GC grades.
ifeq "$(filter il% csharp% java%,$(GRADE))$(findstring gc,$(GRADE))" "gc"
- C_AND_GC_ONLY_PROGS =string_hash
+ C_AND_GC_ONLY_PROGS = string_hash
else
C_AND_GC_ONLY_PROGS =
endif
Index: tests/hard_coded/string_hash.m
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/string_hash.m,v
retrieving revision 1.4
diff -u -r1.4 string_hash.m
--- tests/hard_coded/string_hash.m 4 Apr 2011 07:10:41 -0000 1.4
+++ tests/hard_coded/string_hash.m 28 Jul 2011 07:05:38 -0000
@@ -1,4 +1,8 @@
-% Test that string__hash and MR_hash_string return the same value.
+% vim: ts=4 sw=4 et ft=mercury
+
+% Test that string.hash and MR_hash_string return the same value.
+% Do the same for string.hash2 and MR_hash_string2, and for
+% string.hash3 and MR_hash_string3.
:- module string_hash.
@@ -6,77 +10,133 @@
:- import_module io.
-:- pred main(io__state::di, io__state::uo) is det.
+:- pred main(io::di, io::uo) is det.
:- implementation.
-:- import_module bool, char, int, list, random, require, string.
+:- import_module bool.
+:- import_module char.
+:- import_module int.
+:- import_module list.
+:- import_module random.
+:- import_module require.
+:- import_module string.
main(!IO) :-
- MaxLength = 1024,
- random__init(1, RS0),
- test(MaxLength, yes, Succeeded, RS0, _, !IO),
- ( Succeeded = yes ->
- io__write_string("all tests succeeded\n", !IO)
- ;
- io__write_string("some tests failed\n", !IO)
- ).
+ MaxLength = 1024,
+ random.init(1, RS0),
+ test(MaxLength, yes, Succeeded, RS0, _, !IO),
+ (
+ Succeeded = yes,
+ io.write_string("all tests succeeded\n", !IO)
+ ;
+ Succeeded = no,
+ io.write_string("some tests failed\n", !IO)
+ ).
:- pred test(int::in, bool::in, bool::out,
- random__supply::mdi, random__supply::muo,
- io__state::di, io__state::uo) is det.
+ random.supply::mdi, random.supply::muo, io::di, io::uo) is det.
test(Length, !Succeeded, !RS, !IO) :-
- ( Length = 0 ->
- true
- ;
- make_char_list(Length, [], List, !RS),
- string__from_char_list(List, String),
- LibHash = string__hash(String),
- RuntimeHash = runtime_string_hash(String),
- ( LibHash = RuntimeHash ->
- true
- ;
- !:Succeeded = no,
- io__write_string("failed: runtime ", !IO),
- io__write_int(RuntimeHash, !IO),
- io__write_string(", library ", !IO),
- io__write_int(LibHash, !IO),
- io__write_string(": """, !IO),
- io__write_string(String, !IO),
- io__write_string("""\n", !IO)
- ),
- test(Length - 1, !Succeeded, !RS, !IO)
- ).
+ ( Length < 0 ->
+ true
+ ;
+ make_char_list(Length, [], List, !RS),
+ string.from_char_list(List, String),
+
+ LibHash1 = string.hash(String),
+ RuntimeHash1 = runtime_string_hash(String),
+ ( LibHash1 = RuntimeHash1 ->
+ true
+ ;
+ !:Succeeded = no,
+ io.write_string("failed hash1: runtime ", !IO),
+ io.write_int(RuntimeHash1, !IO),
+ io.write_string(", library ", !IO),
+ io.write_int(LibHash1, !IO),
+ io.write_string(": """, !IO),
+ io.write_string(String, !IO),
+ io.write_string("""\n", !IO)
+ ),
+
+ LibHash2 = string.hash2(String),
+ RuntimeHash2 = runtime_string_hash2(String),
+ ( LibHash2 = RuntimeHash2 ->
+ true
+ ;
+ !:Succeeded = no,
+ io.write_string("failed hash2: runtime ", !IO),
+ io.write_int(RuntimeHash2, !IO),
+ io.write_string(", library ", !IO),
+ io.write_int(LibHash2, !IO),
+ io.write_string(": """, !IO),
+ io.write_string(String, !IO),
+ io.write_string("""\n", !IO)
+ ),
+
+ LibHash3 = string.hash3(String),
+ RuntimeHash3 = runtime_string_hash3(String),
+ ( LibHash3 = RuntimeHash3 ->
+ true
+ ;
+ !:Succeeded = no,
+ io.write_string("failed hash3: runtime ", !IO),
+ io.write_int(RuntimeHash3, !IO),
+ io.write_string(", library ", !IO),
+ io.write_int(LibHash3, !IO),
+ io.write_string(": """, !IO),
+ io.write_string(String, !IO),
+ io.write_string("""\n", !IO)
+ ),
+
+ test(Length - 1, !Succeeded, !RS, !IO)
+ ).
:- pred make_char_list(int::in, list(char)::in, list(char)::out,
- random__supply::mdi, random__supply::muo) is det.
+ random.supply::mdi, random.supply::muo) is det.
make_char_list(Length, !List, !RS) :-
- ( Length = 0 ->
- true
- ;
- rand_char(Char, !RS),
- !:List = [Char | !.List],
- make_char_list(Length - 1, !List, !RS)
- ).
+ ( Length = 0 ->
+ true
+ ;
+ rand_char(Char, !RS),
+ !:List = [Char | !.List],
+ make_char_list(Length - 1, !List, !RS)
+ ).
-:- pred rand_char(char::out, random__supply::mdi, random__supply::muo) is det.
+:- pred rand_char(char::out, random.supply::mdi, random.supply::muo) is det.
rand_char(Char, !RS) :-
- random__random(Rand, !RS),
- % U+0001..U+10ffff (avoid null character).
- Int = 1 + (Rand `mod` char__max_char_value),
- char__det_from_int(Int, Char).
+ random.random(Rand, !RS),
+ % U+0001..U+10ffff (avoid null character).
+ Int = 1 + (Rand `mod` char.max_char_value),
+ char.det_from_int(Int, Char).
:- pragma foreign_decl("C", "#include ""mercury_string.h""").
:- func runtime_string_hash(string) = int.
:- pragma foreign_proc("C",
- runtime_string_hash(StringArg::in) = (Hash::out),
- [promise_pure, will_not_call_mercury],
+ runtime_string_hash(StringArg::in) = (Hash::out),
+ [promise_pure, will_not_call_mercury],
"
- Hash = MR_hash_string(StringArg);
+ Hash = MR_hash_string(StringArg);
").
+:- func runtime_string_hash2(string) = int.
+
+:- pragma foreign_proc("C",
+ runtime_string_hash2(StringArg::in) = (Hash::out),
+ [promise_pure, will_not_call_mercury],
+"
+ Hash = MR_hash_string2(StringArg);
+").
+
+:- func runtime_string_hash3(string) = int.
+
+:- pragma foreign_proc("C",
+ runtime_string_hash3(StringArg::in) = (Hash::out),
+ [promise_pure, will_not_call_mercury],
+"
+ Hash = MR_hash_string3(StringArg);
+").
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the reviews
mailing list