gistfile1.hpp

--- hash.cc.orig	2009-11-06 12:25:18.075000000 +0900
+++ hash.cc	2009-11-06 12:39:43.965625000 +0900
@@ -445,8 +445,8 @@
   if (xhash_table_used (hash_table) > xhash_table_size (hash_table) * 8 / 10)
     {
       int inc = xhash_table_rehash_size (hash_table);
-      if (inc < 10)
-        inc = min (max (xhash_table_size (hash_table) * 2 / 10, 10), 100);
+      if (inc < xhash_table_size (hash_table) / 2)
+        inc = xhash_table_size (hash_table) / 2;
       hash_table_rehash (hash_table, inc);
     }
   add_hash_entry (key, value, (lhash_table *)hash_table);

gistfile2.lisp

(defun hash-test (x)
  (let ((table (make-hash-table))
        (old-size 0)
        (n 1)
        (tick (si:performance-counter)))
    (dotimes (i x)
      (setf (gethash i table) i)
      (when (/= old-size (hash-table-size table))
        (format t "~D, ~D, ~D, ~D, ~D~%" n (hash-table-count table) (hash-table-size table) (- (si:performance-counter) tick) si:*performance-counter-frequency*)
        (incf n)
        (setf old-size (hash-table-size table))))
    (format t "~D, ~D, ~D, ~D, ~D~%" n (hash-table-count table) (hash-table-size table) (- (si:performance-counter) tick) si:*performance-counter-frequency*)))
(compile 'hash-test)
(hash-test 100000)

gistfile3.txt

xyzzyのハッシュテーブルは要素数が80000を越える辺りから遅くなる。
ハッシュテーブルのサイズの増やし方が原因。
上のpatchは最低でも前の1.5倍になるようにするもの。

;;; 前
(time (hash-test 100000))
1, 1, 17, 30, 3579545
2, 15, 47, 209, 3579545
3, 39, 101, 389, 3579545
4, 82, 149, 703, 3579545
5, 121, 199, 981, 3579545
6, 161, 307, 1271, 3579545
7, 247, 401, 1807, 3579545
8, 322, 499, 2310, 3579545
9, 401, 599, 2848, 3579545
10, 481, 701, 3476, 3579545
11, 562, 907, 4175, 3579545
12, 727, 1103, 5273, 3579545
13, 884, 1499, 6388, 3579545
14, 1201, 1999, 8786, 3579545
15, 1601, 2999, 11329, 3579545
16, 2401, 4001, 16036, 3579545
17, 3202, 4999, 22883, 3579545
18, 4001, 6007, 28246, 3579545
19, 4807, 7001, 33861, 3579545
20, 5602, 8009, 39549, 3579545
21, 6409, 8999, 45597, 3579545
22, 7201, 10007, 51872, 3579545
23, 8007, 19997, 60295, 3579545
24, 15999, 29989, 106202, 3579545
25, 23993, 39989, 156072, 3579545
26, 31993, 49999, 211194, 3579545
27, 40001, 59999, 331380, 3579545
28, 48001, 70001, 393277, 3579545
29, 56002, 79999, 453872, 3579545
30, 64001, 90001, 520313, 3579545
31, 72002, 99991, 644085, 3579545
32, 79994, 100091, 767931, 3579545
33, 80074, 100191, 795314, 3579545
34, 80154, 100291, 823831, 3579545
35, 80234, 100391, 851132, 3579545
36, 80314, 100491, 878302, 3579545
37, 80394, 100591, 918072, 3579545
38, 80474, 100691, 930886, 3579545
39, 80554, 100791, 943817, 3579545
40, 80634, 100891, 958184, 3579545
41, 80714, 100991, 977290, 3579545
42, 80794, 101091, 992780, 3579545
43, 80874, 101191, 1006308, 3579545
44, 80954, 101291, 1022943, 3579545
45, 81034, 101391, 1036228, 3579545
46, 81114, 101491, 1049646, 3579545
47, 81194, 101591, 1071149, 3579545
48, 81274, 101691, 1084383, 3579545
49, 81354, 101791, 1098747, 3579545
50, 81434, 101891, 1112360, 3579545
51, 81514, 101991, 1125946, 3579545
52, 81594, 102091, 1142899, 3579545
53, 81674, 102191, 1156339, 3579545
54, 81754, 102291, 1171053, 3579545
55, 81834, 102391, 1184835, 3579545
56, 81914, 102491, 1199679, 3579545
57, 81994, 102591, 1213369, 3579545
58, 82074, 102691, 1247170, 3579545
59, 82154, 102791, 1260328, 3579545
60, 82234, 102891, 1274550, 3579545
61, 82314, 102991, 1293049, 3579545
62, 82394, 103091, 1308746, 3579545
63, 82474, 103191, 1322177, 3579545
64, 82554, 103291, 1335690, 3579545
65, 82634, 103391, 1351397, 3579545
66, 82714, 103491, 1365518, 3579545
67, 82794, 103591, 1380456, 3579545
68, 82874, 103691, 1396426, 3579545
69, 82954, 103791, 1410112, 3579545
70, 83034, 103891, 1429217, 3579545
71, 83114, 103991, 1442965, 3579545
72, 83194, 104091, 1457980, 3579545
73, 83274, 104191, 1472591, 3579545
74, 83354, 104291, 1489080, 3579545
75, 83434, 104391, 1503441, 3579545
76, 83514, 104491, 1518518, 3579545
77, 83594, 104591, 1533782, 3579545
78, 83674, 104691, 1548121, 3579545
79, 83754, 104791, 1582202, 3579545
80, 83834, 104891, 1597035, 3579545
81, 83914, 104991, 1611099, 3579545
82, 83994, 105091, 1625378, 3579545
83, 84074, 105191, 1642491, 3579545
84, 84154, 105291, 1657206, 3579545
85, 84234, 105391, 1673480, 3579545
86, 84314, 105491, 1688686, 3579545
87, 84394, 105591, 1705016, 3579545
88, 84474, 105691, 1720642, 3579545
89, 84554, 105791, 1737071, 3579545
90, 84634, 105891, 1752612, 3579545
91, 84714, 105991, 1768169, 3579545
92, 84794, 106091, 1789421, 3579545
93, 84874, 106191, 1804910, 3579545
94, 84954, 106291, 1822714, 3579545
95, 85034, 106391, 1838307, 3579545
96, 85114, 106491, 1855269, 3579545
97, 85194, 106591, 1871154, 3579545
98, 85274, 106691, 1888257, 3579545
99, 85354, 106791, 1931391, 3579545
100, 85434, 106891, 1946633, 3579545
101, 85514, 106991, 1963166, 3579545
102, 85594, 107091, 1979248, 3579545
103, 85674, 107191, 1998072, 3579545
104, 85754, 107291, 2013903, 3579545
105, 85834, 107391, 2031020, 3579545
106, 85914, 107491, 2047061, 3579545
107, 85994, 107591, 2064328, 3579545
108, 86074, 107691, 2080777, 3579545
109, 86154, 107791, 2098015, 3579545
110, 86234, 107891, 2114132, 3579545
111, 86314, 107991, 2132749, 3579545
112, 86394, 108091, 2152967, 3579545
113, 86474, 108191, 2170128, 3579545
114, 86554, 108291, 2186152, 3579545
115, 86634, 108391, 2203517, 3579545
116, 86714, 108491, 2220230, 3579545
117, 86794, 108591, 2240392, 3579545
118, 86874, 108691, 2256506, 3579545
119, 86954, 108791, 2273748, 3579545
120, 87034, 108891, 2290059, 3579545
121, 87114, 108991, 2306476, 3579545
122, 87194, 109091, 2324825, 3579545
123, 87274, 109191, 2341221, 3579545
124, 87354, 109291, 2358725, 3579545
125, 87434, 109391, 2375199, 3579545
126, 87514, 109491, 2392776, 3579545
127, 87594, 109591, 2409531, 3579545
128, 87674, 109691, 2427227, 3579545
129, 87754, 109791, 2444018, 3579545
130, 87834, 109891, 2461716, 3579545
131, 87914, 109991, 2478140, 3579545
132, 87994, 110091, 2497252, 3579545
133, 88074, 110191, 2515957, 3579545
134, 88154, 110291, 2533486, 3579545
135, 88234, 110391, 2549879, 3579545
136, 88314, 110491, 2589685, 3579545
137, 88394, 110591, 2606608, 3579545
138, 88474, 110691, 2627103, 3579545
139, 88554, 110791, 2645671, 3579545
140, 88634, 110891, 2661827, 3579545
141, 88714, 110991, 2679504, 3579545
142, 88794, 111091, 2696132, 3579545
143, 88874, 111191, 2714184, 3579545
144, 88954, 111291, 2730842, 3579545
145, 89034, 111391, 2750185, 3579545
146, 89114, 111491, 2767027, 3579545
147, 89194, 111591, 2784978, 3579545
148, 89274, 111691, 2802286, 3579545
149, 89354, 111791, 2821608, 3579545
150, 89434, 111891, 2838408, 3579545
151, 89514, 111991, 2856400, 3579545
152, 89594, 112091, 2876918, 3579545
153, 89674, 112191, 2894637, 3579545
154, 89754, 112291, 2993466, 3579545
155, 89834, 112391, 3009863, 3579545
156, 89914, 112491, 3031772, 3579545
157, 89994, 112591, 3048151, 3579545
158, 90074, 112691, 3065873, 3579545
159, 90154, 112791, 3082697, 3579545
160, 90234, 112891, 3101376, 3579545
161, 90314, 112991, 3118325, 3579545
162, 90394, 113091, 3137846, 3579545
163, 90474, 113191, 3155042, 3579545
164, 90554, 113291, 3173372, 3579545
165, 90634, 113391, 3190492, 3579545
166, 90714, 113491, 3208693, 3579545
167, 90794, 113591, 3228462, 3579545
168, 90874, 113691, 3247188, 3579545
169, 90954, 113791, 3264216, 3579545
170, 91034, 113891, 3282436, 3579545
171, 91114, 113991, 3320656, 3579545
172, 91194, 114091, 3337148, 3579545
173, 91274, 114191, 3354934, 3579545
174, 91354, 114291, 3378024, 3579545
175, 91434, 114391, 3395798, 3579545
176, 91514, 114491, 3413097, 3579545
177, 91594, 114591, 3431308, 3579545
178, 91674, 114691, 3448775, 3579545
179, 91754, 114791, 3471652, 3579545
180, 91834, 114891, 3488555, 3579545
181, 91914, 114991, 3506878, 3579545
182, 91994, 115091, 3525584, 3579545
183, 92074, 115191, 3543101, 3579545
184, 92154, 115291, 3561545, 3579545
185, 92234, 115391, 3579553, 3579545
186, 92314, 115491, 3600583, 3579545
187, 92394, 115591, 3617901, 3579545
188, 92474, 115691, 3656162, 3579545
189, 92554, 115791, 3674069, 3579545
190, 92634, 115891, 3695681, 3579545
191, 92714, 115991, 3713768, 3579545
192, 92794, 116091, 3731991, 3579545
193, 92874, 116191, 3753453, 3579545
194, 92954, 116291, 3770855, 3579545
195, 93034, 116391, 3789425, 3579545
196, 93114, 116491, 3806975, 3579545
197, 93194, 116591, 3827309, 3579545
198, 93274, 116691, 3844708, 3579545
199, 93354, 116791, 3863511, 3579545
200, 93434, 116891, 3881572, 3579545
201, 93514, 116991, 3900388, 3579545
202, 93594, 117091, 3919821, 3579545
203, 93674, 117191, 3937374, 3579545
204, 93754, 117291, 3959848, 3579545
205, 93834, 117391, 3995142, 3579545
206, 93914, 117491, 4012564, 3579545
207, 93994, 117591, 4036751, 3579545
208, 94074, 117691, 4054068, 3579545
209, 94154, 117791, 4072713, 3579545
210, 94234, 117891, 4090537, 3579545
211, 94314, 117991, 4110066, 3579545
212, 94394, 118091, 4127940, 3579545
213, 94474, 118191, 4150812, 3579545
214, 94554, 118291, 4168263, 3579545
215, 94634, 118391, 4187403, 3579545
216, 94714, 118491, 4206391, 3579545
217, 94794, 118591, 4225308, 3579545
218, 94874, 118691, 4244462, 3579545
219, 94954, 118791, 4262930, 3579545
220, 95034, 118891, 4281976, 3579545
221, 95114, 118991, 4300051, 3579545
222, 95194, 119091, 4340919, 3579545
223, 95274, 119191, 4359507, 3579545
224, 95354, 119291, 4385387, 3579545
225, 95434, 119391, 4403054, 3579545
226, 95514, 119491, 4421947, 3579545
227, 95594, 119591, 4440961, 3579545
228, 95674, 119691, 4461452, 3579545
229, 95754, 119791, 4479438, 3579545
230, 95834, 119891, 4498585, 3579545
231, 95914, 119991, 4516754, 3579545
232, 95994, 120091, 4538124, 3579545
233, 96074, 120191, 4556051, 3579545
234, 96154, 120291, 4575290, 3579545
235, 96234, 120391, 4594101, 3579545
236, 96314, 120491, 4613702, 3579545
237, 96394, 120591, 4631943, 3579545
238, 96474, 120691, 4652495, 3579545
239, 96554, 120791, 4674495, 3579545
240, 96634, 120891, 4711454, 3579545
241, 96714, 120991, 4728963, 3579545
242, 96794, 121091, 4747853, 3579545
243, 96874, 121191, 4771288, 3579545
244, 96954, 121291, 4790294, 3579545
245, 97034, 121391, 4808436, 3579545
246, 97114, 121491, 4829779, 3579545
247, 97194, 121591, 4848019, 3579545
248, 97274, 121691, 4867569, 3579545
249, 97354, 121791, 4887105, 3579545
250, 97434, 121891, 4905821, 3579545
251, 97514, 121991, 4928148, 3579545
252, 97594, 122091, 4946262, 3579545
253, 97674, 122191, 4967566, 3579545
254, 97754, 122291, 4985935, 3579545
255, 97834, 122391, 5005653, 3579545
256, 97914, 122491, 5026388, 3579545
257, 97994, 122591, 5061587, 3579545
258, 98074, 122691, 5081017, 3579545
259, 98154, 122791, 5105895, 3579545
260, 98234, 122891, 5123924, 3579545
261, 98314, 122991, 5144553, 3579545
262, 98394, 123091, 5162943, 3579545
263, 98474, 123191, 5182726, 3579545
264, 98554, 123291, 5201385, 3579545
265, 98634, 123391, 5221364, 3579545
266, 98714, 123491, 5240011, 3579545
267, 98794, 123591, 5259906, 3579545
268, 98874, 123691, 5280734, 3579545
269, 98954, 123791, 5299431, 3579545
270, 99034, 123891, 5319597, 3579545
271, 99114, 123991, 5338344, 3579545
272, 99194, 124091, 5358257, 3579545
273, 99274, 124191, 5380007, 3579545
274, 99354, 124291, 5403735, 3579545
275, 99434, 124391, 5423489, 3579545
276, 99514, 124491, 5442305, 3579545
277, 99594, 124591, 5463682, 3579545
278, 99674, 124691, 5482478, 3579545
279, 99754, 124791, 5502449, 3579545
280, 99834, 124891, 5521322, 3579545
281, 99914, 124991, 5541427, 3579545
282, 99994, 125091, 5560621, 3579545
283, 100000, 125091, 5560771, 3579545
get-internal-real-time : 1547.0d0 ms
performance-counter : 1553.705009994287d0 ms

;;; 後
(time (hash-test 100000))
1, 1, 17, 32, 3579545
2, 15, 47, 218, 3579545
3, 39, 101, 403, 3579545
4, 82, 199, 686, 3579545
5, 161, 307, 1220, 3579545
6, 247, 499, 1782, 3579545
7, 401, 797, 2753, 3579545
8, 639, 1499, 4182, 3579545
9, 1201, 2999, 7388, 3579545
10, 2401, 4999, 14066, 3579545
11, 4001, 8009, 23258, 3579545
12, 6409, 19997, 39128, 3579545
13, 15999, 39989, 95564, 3579545
14, 31993, 59999, 255241, 3579545
15, 48001, 90001, 359019, 3579545
16, 72002, 135001, 570883, 3579545
17, 100000, 135001, 768162, 3579545
get-internal-real-time : 219.0d0 ms
performance-counter : 214.9507828508931d0 ms