-
Notifications
You must be signed in to change notification settings - Fork 8
/
bench-hash.g
117 lines (98 loc) · 2.78 KB
/
bench-hash.g
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
LoadPackage("datastructures");
# mygap4currL -m 500m
LoadPackage("cvec"); # HACK
LoadPackage("atlasrep");
LoadPackage("orb");
gens := AtlasGenerators("HN",8).generators;
s := AtlasStraightLineProgram("HN",1).program;
ugens := ResultOfStraightLineProgram(s,gens);
guck := List(ugens,x->x-One(x));
guck := List(guck,NullspaceMat);
v := SumIntersectionMat(guck[1],guck[2])[2][1];
v*ugens[1]=v;
v*ugens[2]=v;
o := Orb(gens,v,OnRight,rec( treehashsize := 2000000, report := 100000,
storenumbers := true ));
ti := Runtime();
Enumerate(o);
Print("Time: ",Runtime()-ti,"\n"); # 34 seconds
l := o!.orbit;; # length: 1140000
#
# Test orb's tree hash table speed
#
Print("Creating tree hash...\n");
t := HTCreate(v,rec(treehashsize := 200000));
GASMAN("collect");
Print("Adding values...\n");
ti := Runtime();
for i in [1..Length(l)] do
HTAdd(t,l[i],i);
od;
Print("Time: ",Runtime()-ti,"\n"); # 4.128 seconds
#
Print("Lookup...\n");
ti := Runtime();
for i in [1..Length(l)] do
if HTValue(t,l[i]) <> i then Error(); fi;
od;
Print("Time: ",Runtime()-ti,"\n"); # 1.817 seconds
Print("\n");
#
# Test orb's regular hash table speed
#
Print("Creating regular hash...\n");
t := HTCreate(v,rec(hashlen := 200000));
GASMAN("collect");
Print("Adding values...\n");
ti := Runtime();
for i in [1..Length(l)] do
HTAdd(t,l[i],i);
od;
Print("Time: ",Runtime()-ti,"\n"); # 3.469, 4.432 seconds
#
Print("Lookup...\n");
ti := Runtime();
for i in [1..Length(l)] do
if HTValue(t,l[i]) <> i then Error(); fi;
od;
Print("Time: ",Runtime()-ti,"\n"); # 1.845, 1.738 seconds
Print("\n");
#
#
#
sample_vec:=l[1];
q := Q_VEC8BIT(sample_vec);
i := LogInt(256,q);
# i is now the number of field elements per byte
bytelen := QuoInt(Length(sample_vec),i);
#SIZE_OBJ(sample_vec) - 3*GAPInfo.BytesPerVariable;
hashfun := function(vec8bit)
return HashKeyBag(vec8bit, 101, 3*GAPInfo.BytesPerVariable, bytelen);
end;
Print("Creating hashmap...\n");
dsHashMap := DS_Hash_Create( hashfun, \=, 20000 );;
GASMAN("collect");
Print("Adding values...\n");
ti := Runtime();
for i in [1..Length(l)] do
DS_Hash_SetValue(dsHashMap, l[i], i);
od;
Print("Time: ",Runtime()-ti,"\n"); # 2.210 seconds; 1.64 with "hardcode EQ"-hack
#
Print("Lookup...\n");
ti := Runtime();
for i in [1..Length(l)] do
if DS_Hash_Value(dsHashMap,l[i]) <> i then Error(); fi;
od;
Print("Time: ",Runtime()-ti,"\n"); # 0.971 / 0.944 seconds
Print("\n");
#
# HACK
#
# 3.205 / 1.31
for i in [1..Length(l)] do if HTValue(t,l[i]) <> i then Error(); fi; od; time;
# 3.049 / 0.99
for i in [1..Length(l)] do if DS_Hash_Value(dsHashMap,l[i]) <> i then Error(); fi; od; time;
for i in [1..Length(l)] do DS_Hash_Value(dsHashMap,l[i]); od; time;
# 2.674 / 0.69
for i in [1..Length(l)] do _DS_Hash_Lookup(dsHashMap,l[i]); od; time;