bzr branch
http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar
|
4593.4.1
by John Arbash Meinel
Implement a function on btree that inlines the get_parent_map loop. |
1 |
Some quick notes about get_ancestry results when tested with bzr's ancestry |
2 |
and:
|
|
3 |
4401 Canonical.com Patch Queue Manager 2009-06-03 [merge]
|
|
4 |
revision-id:pqm@pqm.ubuntu.com-20090603080435-2gbqwzvbx31zr7ok
|
|
5 |
(andrew) Fix tracebacks when receiving error responses to
|
|
6 |
BzrDirFormat.initialize* RPCs.
|
|
7 |
||
8 |
This is in a fully packed repository, so there is only a single btree index,
|
|
9 |
and thus there should be only a small handful of genuinely missing keys.
|
|
10 |
||
11 |
First call to get_ancestry reads the root node, +1 internal node, +1 leaf node
|
|
12 |
It is able to expand from 1 key into 74 already know parent keys, and 75
|
|
13 |
missing parent tips.
|
|
14 |
||
15 |
Second call expands to 2 internal nodes (all of them), 14 leaf nodes, and 398
|
|
16 |
known parents, and 82 search tips. Of those 82 tips, 51 of them are present on
|
|
17 |
nodes that we had already read, we just didn't find them because we don't |
|
18 |
search outside the current page for parent keys.
|
|
19 |
||
20 |
||
21 |
Third call:
|
|
22 |
112 search keys
|
|
23 |
36 actually present on an unread LeafNode
|
|
24 |
794 parent_map (found parents)
|
|
25 |
30 leaf nodes
|
|
26 |
||
27 |
Fourth:
|
|
28 |
185 search keys
|
|
29 |
48 really missing
|
|
30 |
1243 parent_map
|
|
31 |
40 leaf nodes
|
|
32 |
||
33 |
Fifth:
|
|
34 |
246 search keys
|
|
35 |
108 really missing
|
|
36 |
2034 parent_map
|
|
37 |
52 leaf nodes
|
|
38 |
||
39 |
Sixth:
|
|
40 |
431 search keys
|
|
41 |
119 really missing
|
|
42 |
3272 parent_map
|
|
43 |
79 leaf nodes
|
|
44 |
||
45 |
Seventh:
|
|
46 |
529 search keys
|
|
47 |
103 really missing # went down?
|
|
48 |
5472 parent_map
|
|
49 |
103 leaf nodes (out of 221 total)
|
|
50 |
||
51 |
Eighth:
|
|
52 |
455 search keys (down?)
|
|
53 |
75 really missing
|
|
54 |
7759 parent_map
|
|
55 |
119 leaf nodes
|
|
56 |
||
57 |
Ninth:
|
|
58 |
430 search keys
|
|
59 |
157 really missing
|
|
60 |
10004 parent_map
|
|
61 |
130 leaf nodes
|
|
62 |
||
63 |
Tenth:
|
|
64 |
407 search keys
|
|
65 |
157 really missing?
|
|
66 |
11788 parent_map
|
|
67 |
148 leaf nodes
|
|
68 |
||
69 |
Eleventh:
|
|
70 |
400 search keys
|
|
71 |
127 missing
|
|
72 |
13502 parent_map
|
|
73 |
165 leaf nodes
|
|
74 |
||
75 |
12:
|
|
76 |
389 search keys
|
|
77 |
145 missing
|
|
78 |
15,500 parent_map
|
|
79 |
179 leaf nodes
|
|
80 |
||
81 |
13:
|
|
82 |
289 search keys
|
|
83 |
72 missing
|
|
84 |
17,586 parent_map
|
|
85 |
194 leaf nodes
|
|
86 |
||
87 |
# I wonder if at this point a major limitation is the parents that are read but
|
|
88 |
# are not on the same page. You could have flip-flop cases, where you have:
|
|
89 |
# pqm@ => john@ => pqm@ => john@ => pqm@ => john@
|
|
90 |
# And each one of those is going to require another re-entrance into
|
|
91 |
# get_ancestry
|
|
92 |
||
93 |
gen search_keys parent_map parents_found
|
|
94 |
not loaded num_leaf_nodes_cached
|
|
95 |
0 1 1 0 0
|
|
96 |
1 75 75 74 1 74
|
|
97 |
2 82 31 398 14 324
|
|
98 |
3 112 36 794 30 396
|
|
99 |
4 185 48 1243 40 449
|
|
100 |
5 246 108 2034 52 791
|
|
101 |
6 431 119 3272 79 1238
|
|
102 |
7 529 103 5472 103 2200
|
|
103 |
8 455 75 7759 119 2287
|
|
104 |
9 430 157 10004 130 2245
|
|
105 |
10 407 157 11788 148 1784
|
|
106 |
11 400 127 13502 165 1714
|
|
107 |
12 389 145 15500 179 1998
|
|
108 |
13 289 72 17586 194 2086
|
|
109 |
14 210 46 19185 203 1599
|
|
110 |
15 140 2 20474 210 1289
|
|
111 |
16 63 5 21331 211 857
|
|
112 |
17 53 9 21761 212 430
|
|
113 |
18 30 3 22159 214 398
|
|
114 |
19 23 4 22700 216 541
|
|
115 |
20 15 1 23055 217 355
|
|
116 |
21 11 1 23266 218 211
|
|
117 |
22 8 1 23485 219 219
|
|
118 |
23 8 0 23651 220 166
|
|
119 |
24 6 0 23672 220 21
|
|
120 |
25 8 1 23716 220 44
|
|
121 |
26 6 0 23905 221 189
|
|
122 |
27 5 0 23994 221 89
|
|
123 |
28 12 0 24037 221 43
|
|
124 |
29 13 0 24102 221 65
|
|
125 |
30 14 0 24192 221 90
|
|
126 |
31 15 0 24284 221 92
|
|
127 |
32 10 0 24344 221 60
|
|
128 |
33 13 0 24419 221 75
|
|
129 |
34 15 0 24465 221 46
|
|
130 |
35 8 0 24612 221 147
|
|
131 |
36 5 0 24663 221 51
|
|
132 |
37 4 0 24744 221 81
|
|
133 |
38 3 0 24758 221 14
|
|
134 |
39 3 0 24769 221 11
|
|
135 |
40 3 0 24786 221 17
|
|
136 |
41 2 0 24809 221 23
|
|
137 |
42 1 0 24827 221 18
|
|
138 |
43 1 0 24828 221 1
|
|
139 |
44 1 0 24848 221 20
|
|
140 |
45 1 0 24853 221 5
|
|
141 |
46 1 0 24874 221 21
|
|
142 |
47 6 0 24883 221 9
|
|
143 |
48 4 0 24905 221 22
|
|
144 |
49 1 0 24938 221 33
|
|
145 |
50 0 0 24941 221 3
|
|
146 |
||
147 |
||
148 |
# Note the *really* long tail where after we have 20k keys we've pretty much |
|
149 |
# read all the pages, and at this point, we only have a small handful |
|
150 |
# (sometimes only 1) parent to search for. |
|
151 |
# Then again, if you look at the number of parents found count, it is going |
|
152 |
# up by easily 20-100 at each step, so it is still fairly efficient. |
|
153 |
||
154 |
# Also, we can compare this to the performance of just looping over |
|
155 |
# 'get_parent_map()' calls |
|
156 |
gen search_keys next_keys |
|
157 |
parent_map |
|
158 |
0 1 0 1 |
|
159 |
1 1 1 2 |
|
160 |
2 2 3 3 |
|
161 |
3 3 6 4 |
|
162 |
4 4 10 5 |
|
163 |
5 5 15 7 |
|
164 |
6 7 22 11 |
|
165 |
7 11 33 17 |
|
166 |
8 17 50 20 |
|
167 |
9 20 70 23 |
|
168 |
10 23 93 24 |
|
169 |
11 24 117 24 |
|
170 |
12 24 141 28 |
|
171 |
13 28 169 30 |
|
172 |
14 30 199 33 |
|
173 |
15 33 232 34 |
|
174 |
16 34 266 39 |
|
175 |
17 39 305 42 |
|
176 |
18 42 347 46 |
|
177 |
19 46 393 48 |
|
178 |
20 48 441 58 |
|
179 |
21 58 499 67 |
|
180 |
22 67 566 75 |
|
181 |
23 75 641 87 |
|
182 |
24 87 728 95 |
|
183 |
25 95 823 96 |
|
184 |
26 96 919 103 |
|
185 |
27 103 1022 109 |
|
186 |
28 109 1131 121 |
|
187 |
29 121 1252 140 |
|
188 |
30 140 1392 144 |
|
189 |
31 144 1536 162 |
|
190 |
32 162 1698 175 |
|
191 |
33 175 1873 189 |
|
192 |
34 189 2062 202 |
|
193 |
35 202 2264 219 |
|
194 |
36 219 2483 225 |
|
195 |
37 225 2708 235 |
|
196 |
38 235 2943 250 |
|
197 |
39 250 3193 245 |
|
198 |
40 245 3438 252 |
|
199 |
41 252 3690 269 |
|
200 |
42 269 3959 270 |
|
201 |
43 270 4229 291 |
|
202 |
44 291 4520 300 |
|
203 |
45 300 4820 311 |
|
204 |
46 311 5131 340 |
|
205 |
47 340 5471 362 |
|
206 |
48 362 5833 364 |
|
207 |
49 364 6197 372 |
|
208 |
50 372 6569 366 |
|
209 |
51 366 6935 363 |
|
210 |
52 363 7298 354 |
|
211 |
53 354 7652 360 |
|
212 |
54 360 8012 337 |
|
213 |
55 337 8349 336 |
|
214 |
56 336 8685 307 |
|
215 |
57 307 8992 291 |
|
216 |
58 291 9283 290 |
|
217 |
59 290 9573 290 |
|
218 |
60 290 9863 280 |
|
219 |
61 280 10143 261 |
|
220 |
62 261 10404 253 |
|
221 |
63 253 10657 248 |
|
222 |
64 248 10905 239 |
|
223 |
65 239 11144 248 |
|
224 |
66 248 11392 235 |
|
225 |
67 235 11627 228 |
|
226 |
68 228 11855 232 |
|
227 |
69 232 12087 233 |
|
228 |
70 233 12320 238 |
|
229 |
71 238 12558 251 |
|
230 |
72 251 12809 269 |
|
231 |
73 269 13078 280 |
|
232 |
74 280 13358 286 |
|
233 |
75 286 13644 280 |
|
234 |
76 280 13924 284 |
|
235 |
77 284 14208 305 |
|
236 |
78 305 14513 298 |
|
237 |
79 298 14811 291 |
|
238 |
80 291 15102 299 |
|
239 |
81 299 15401 285 |
|
240 |
82 285 15686 272 |
|
241 |
83 272 15958 270 |
|
242 |
84 270 16228 264 |
|
243 |
85 264 16492 245 |
|
244 |
86 245 16737 237 |
|
245 |
87 237 16974 212 |
|
246 |
88 212 17186 201 |
|
247 |
89 201 17387 194 |
|
248 |
90 194 17581 182 |
|
249 |
91 182 17763 176 |
|
250 |
92 176 17939 178 |
|
251 |
93 178 18117 171 |
|
252 |
94 171 18288 169 |
|
253 |
95 169 18457 173 |
|
254 |
96 173 18630 160 |
|
255 |
97 160 18790 154 |
|
256 |
98 154 18944 154 |
|
257 |
99 154 19098 147 |
|
258 |
100 147 19245 140 |
|
259 |
101 140 19385 130 |
|
260 |
102 130 19515 123 |
|
261 |
103 123 19638 113 |
|
262 |
104 113 19751 107 |
|
263 |
105 107 19858 102 |
|
264 |
106 102 19960 93 |
|
265 |
107 93 20053 90 |
|
266 |
108 90 20143 89 |
|
267 |
109 89 20232 79 |
|
268 |
110 79 20311 77 |
|
269 |
111 77 20388 76 |
|
270 |
112 76 20464 77 |
|
271 |
113 77 20541 76 |
|
272 |
114 76 20617 74 |
|
273 |
115 74 20691 68 |
|
274 |
116 68 20759 69 |
|
275 |
117 69 20828 64 |
|
276 |
118 64 20892 66 |
|
277 |
119 66 20958 63 |
|
278 |
120 63 21021 56 |
|
279 |
121 56 21077 57 |
|
280 |
122 57 21134 54 |
|
281 |
123 54 21188 57 |
|
282 |
124 57 21245 58 |
|
283 |
125 58 21303 54 |
|
284 |
126 54 21357 47 |
|
285 |
127 47 21404 48 |
|
286 |
128 48 21452 45 |
|
287 |
129 45 21497 45 |
|
288 |
130 45 21542 41 |
|
289 |
131 41 21583 41 |
|
290 |
132 41 21624 41 |
|
291 |
133 41 21665 42 |
|
292 |
134 42 21707 43 |
|
293 |
135 43 21750 42 |
|
294 |
136 42 21792 36 |
|
295 |
137 36 21828 37 |
|
296 |
138 37 21865 36 |
|
297 |
139 36 21901 32 |
|
298 |
140 32 21933 34 |
|
299 |
141 34 21967 33 |
|
300 |
142 33 22000 31 |
|
301 |
143 31 22031 32 |
|
302 |
144 32 22063 29 |
|
303 |
145 29 22092 33 |
|
304 |
146 33 22125 34 |
|
305 |
147 34 22159 32 |
|
306 |
148 32 22191 29 |
|
307 |
149 29 22220 27 |
|
308 |
150 27 22247 28 |
|
309 |
151 28 22275 25 |
|
310 |
152 25 22300 24 |
|
311 |
153 24 22324 21 |
|
312 |
154 21 22345 21 |
|
313 |
155 21 22366 20 |
|
314 |
156 20 22386 20 |
|
315 |
157 20 22406 19 |
|
316 |
158 19 22425 19 |
|
317 |
159 19 22444 19 |
|
318 |
160 19 22463 19 |
|
319 |
161 19 22482 18 |
|
320 |
162 18 22500 20 |
|
321 |
163 20 22520 20 |
|
322 |
164 20 22540 20 |
|
323 |
165 20 22560 19 |
|
324 |
166 19 22579 18 |
|
325 |
167 18 22597 17 |
|
326 |
168 17 22614 17 |
|
327 |
169 17 22631 17 |
|
328 |
170 17 22648 17 |
|
329 |
171 17 22665 17 |
|
330 |
172 17 22682 17 |
|
331 |
173 17 22699 17 |
|
332 |
174 17 22716 17 |
|
333 |
175 17 22733 17 |
|
334 |
176 17 22750 15 |
|
335 |
177 15 22765 15 |
|
336 |
178 15 22780 15 |
|
337 |
179 15 22795 14 |
|
338 |
180 14 22809 14 |
|
339 |
181 14 22823 14 |
|
340 |
182 14 22837 15 |
|
341 |
183 15 22852 17 |
|
342 |
184 17 22869 17 |
|
343 |
185 17 22886 17 |
|
344 |
186 17 22903 16 |
|
345 |
187 16 22919 15 |
|
346 |
188 15 22934 15 |
|
347 |
189 15 22949 15 |
|
348 |
190 15 22964 15 |
|
349 |
191 15 22979 15 |
|
350 |
192 15 22994 14 |
|
351 |
193 14 23008 14 |
|
352 |
194 14 23022 14 |
|
353 |
195 14 23036 14 |
|
354 |
196 14 23050 15 |
|
355 |
197 15 23065 15 |
|
356 |
198 15 23080 15 |
|
357 |
199 15 23095 15 |
|
358 |
200 15 23110 15 |
|
359 |
201 15 23125 16 |
|
360 |
202 16 23141 16 |
|
361 |
203 16 23157 16 |
|
362 |
204 16 23173 15 |
|
363 |
205 15 23188 15 |
|
364 |
206 15 23203 14 |
|
365 |
207 14 23217 14 |
|
366 |
208 14 23231 13 |
|
367 |
209 13 23244 16 |
|
368 |
210 15 23259 14 |
|
369 |
211 14 23273 14 |
|
370 |
212 14 23287 15 |
|
371 |
213 14 23301 14 |
|
372 |
214 14 23315 14 |
|
373 |
215 14 23329 14 |
|
374 |
216 14 23343 14 |
|
375 |
217 14 23357 14 |
|
376 |
218 14 23371 15 |
|
377 |
219 15 23386 15 |
|
378 |
220 15 23401 15 |
|
379 |
221 15 23416 15 |
|
380 |
222 15 23431 14 |
|
381 |
223 14 23445 14 |
|
382 |
224 14 23459 12 |
|
383 |
225 12 23471 11 |
|
384 |
226 11 23482 11 |
|
385 |
227 11 23493 11 |
|
386 |
228 11 23504 11 |
|
387 |
229 11 23515 11 |
|
388 |
230 11 23526 11 |
|
389 |
231 11 23537 11 |
|
390 |
232 11 23548 11 |
|
391 |
233 11 23559 11 |
|
392 |
234 11 23570 10 |
|
393 |
235 10 23580 11 |
|
394 |
236 11 23591 10 |
|
395 |
237 10 23601 10 |
|
396 |
238 10 23611 10 |
|
397 |
239 10 23621 10 |
|
398 |
240 10 23631 10 |
|
399 |
241 10 23641 10 |
|
400 |
242 10 23651 9 |
|
401 |
243 9 23660 9 |
|
402 |
244 9 23669 9 |
|
403 |
245 9 23678 9 |
|
404 |
246 9 23687 9 |
|
405 |
247 9 23696 9 |
|
406 |
248 9 23705 9 |
|
407 |
249 9 23714 8 |
|
408 |
250 8 23722 8 |
|
409 |
251 8 23730 8 |
|
410 |
252 8 23738 8 |
|
411 |
253 8 23746 9 |
|
412 |
254 9 23755 9 |
|
413 |
255 9 23764 10 |
|
414 |
256 10 23774 12 |
|
415 |
257 12 23786 13 |
|
416 |
258 13 23799 13 |
|
417 |
259 13 23812 13 |
|
418 |
260 13 23825 13 |
|
419 |
261 13 23838 11 |
|
420 |
262 11 23849 9 |
|
421 |
263 9 23858 9 |
|
422 |
264 9 23867 8 |
|
423 |
265 8 23875 8 |
|
424 |
266 8 23883 7 |
|
425 |
267 7 23890 7 |
|
426 |
268 7 23897 7 |
|
427 |
269 7 23904 7 |
|
428 |
270 7 23911 7 |
|
429 |
271 7 23918 7 |
|
430 |
272 7 23925 7 |
|
431 |
273 7 23932 6 |
|
432 |
274 6 23938 6 |
|
433 |
275 6 23944 6 |
|
434 |
276 6 23950 6 |
|
435 |
277 6 23956 6 |
|
436 |
278 6 23962 5 |
|
437 |
279 5 23967 5 |
|
438 |
280 5 23972 5 |
|
439 |
281 5 23977 5 |
|
440 |
282 5 23982 5 |
|
441 |
283 5 23987 5 |
|
442 |
284 5 23992 5 |
|
443 |
285 5 23997 5 |
|
444 |
286 5 24002 5 |
|
445 |
287 5 24007 4 |
|
446 |
288 4 24011 4 |
|
447 |
289 4 24015 4 |
|
448 |
290 4 24019 4 |
|
449 |
291 4 24023 4 |
|
450 |
292 4 24027 4 |
|
451 |
293 4 24031 3 |
|
452 |
294 3 24034 3 |
|
453 |
295 3 24037 3 |
|
454 |
296 3 24040 3 |
|
455 |
297 3 24043 3 |
|
456 |
298 3 24046 3 |
|
457 |
299 3 24049 3 |
|
458 |
300 3 24052 3 |
|
459 |
301 3 24055 3 |
|
460 |
302 3 24058 3 |
|
461 |
303 3 24061 3 |
|
462 |
304 3 24064 3 |
|
463 |
305 3 24067 3 |
|
464 |
306 3 24070 3 |
|
465 |
307 3 24073 3 |
|
466 |
308 3 24076 3 |
|
467 |
309 3 24079 3 |
|
468 |
310 3 24082 3 |
|
469 |
311 3 24085 3 |
|
470 |
312 3 24088 3 |
|
471 |
313 3 24091 3 |
|
472 |
314 3 24094 3 |
|
473 |
315 3 24097 3 |
|
474 |
316 3 24100 3 |
|
475 |
317 3 24103 3 |
|
476 |
318 3 24106 3 |
|
477 |
319 3 24109 3 |
|
478 |
320 3 24112 3 |
|
479 |
321 3 24115 3 |
|
480 |
322 3 24118 3 |
|
481 |
323 3 24121 3 |
|
482 |
324 3 24124 3 |
|
483 |
325 3 24127 3 |
|
484 |
326 3 24130 3 |
|
485 |
327 3 24133 3 |
|
486 |
328 3 24136 3 |
|
487 |
329 3 24139 2 |
|
488 |
330 2 24141 2 |
|
489 |
331 2 24143 2 |
|
490 |
332 2 24145 2 |
|
491 |
333 2 24147 2 |
|
492 |
334 2 24149 2 |
|
493 |
335 2 24151 2 |
|
494 |
336 2 24153 2 |
|
495 |
337 2 24155 2 |
|
496 |
338 2 24157 2 |
|
497 |
339 2 24159 2 |
|
498 |
340 2 24161 2 |
|
499 |
341 2 24163 2 |
|
500 |
342 2 24165 2 |
|
501 |
343 2 24167 2 |
|
502 |
344 2 24169 2 |
|
503 |
345 2 24171 2 |
|
504 |
346 2 24173 2 |
|
505 |
347 2 24175 2 |
|
506 |
348 2 24177 2 |
|
507 |
349 2 24179 2 |
|
508 |
350 2 24181 2 |
|
509 |
351 2 24183 2 |
|
510 |
352 2 24185 1 |
|
511 |
353 1 24186 1 |
|
512 |
354 1 24187 1 |
|
513 |
355 1 24188 1 |
|
514 |
356 1 24189 1 |
|
515 |
357 1 24190 1 |
|
516 |
358 1 24191 1 |
|
517 |
359 1 24192 1 |
|
518 |
360 1 24193 1 |
|
519 |
361 1 24194 1 |
|
520 |
362 1 24195 1 |
|
521 |
363 1 24196 1 |
|
522 |
364 1 24197 1 |
|
523 |
365 1 24198 1 |
|
524 |
366 1 24199 1 |
|
525 |
367 1 24200 1 |
|
526 |
368 1 24201 1 |
|
527 |
369 1 24202 1 |
|
528 |
370 1 24203 1 |
|
529 |
371 1 24204 1 |
|
530 |
372 1 24205 1 |
|
531 |
373 1 24206 1 |
|
532 |
374 1 24207 1 |
|
533 |
375 1 24208 1 |
|
534 |
376 1 24209 1 |
|
535 |
377 1 24210 1 |
|
536 |
378 1 24211 1 |
|
537 |
379 1 24212 1 |
|
538 |
380 1 24213 1 |
|
539 |
381 1 24214 1 |
|
540 |
382 1 24215 1 |
|
541 |
383 1 24216 1 |
|
542 |
384 1 24217 1 |
|
543 |
385 1 24218 1 |
|
544 |
386 1 24219 1 |
|
545 |
387 1 24220 1 |
|
546 |
388 1 24221 1 |
|
547 |
389 1 24222 1 |
|
548 |
390 1 24223 1 |
|
549 |
391 1 24224 1 |
|
550 |
392 1 24225 1 |
|
551 |
393 1 24226 1 |
|
552 |
394 1 24227 1 |
|
553 |
395 1 24228 1 |
|
554 |
396 1 24229 1 |
|
555 |
397 1 24230 1 |
|
556 |
398 1 24231 1 |
|
557 |
399 1 24232 1 |
|
558 |
400 1 24233 1 |
|
559 |
401 1 24234 1 |
|
560 |
402 1 24235 1 |
|
561 |
403 1 24236 1 |
|
562 |
404 1 24237 1 |
|
563 |
405 1 24238 1 |
|
564 |
406 1 24239 1 |
|
565 |
407 1 24240 1 |
|
566 |
408 1 24241 1 |
|
567 |
409 1 24242 1 |
|
568 |
410 1 24243 1 |
|
569 |
411 1 24244 1 |
|
570 |
412 1 24245 1 |
|
571 |
413 1 24246 1 |
|
572 |
414 1 24247 1 |
|
573 |
415 1 24248 1 |
|
574 |
416 1 24249 1 |
|
575 |
417 1 24250 1 |
|
576 |
418 1 24251 1 |
|
577 |
419 1 24252 1 |
|
578 |
420 1 24253 1 |
|
579 |
421 1 24254 1 |
|
580 |
422 1 24255 1 |
|
581 |
423 1 24256 1 |
|
582 |
424 1 24257 1 |
|
583 |
425 1 24258 1 |
|
584 |
426 1 24259 1 |
|
585 |
427 1 24260 1 |
|
586 |
428 1 24261 1 |
|
587 |
429 1 24262 1 |
|
588 |
430 1 24263 1 |
|
589 |
431 1 24264 1 |
|
590 |
432 1 24265 1 |
|
591 |
433 1 24266 1 |
|
592 |
434 1 24267 1 |
|
593 |
435 1 24268 1 |
|
594 |
436 1 24269 1 |
|
595 |
437 1 24270 1 |
|
596 |
438 1 24271 1 |
|
597 |
439 1 24272 1 |
|
598 |
440 1 24273 1 |
|
599 |
441 1 24274 1 |
|
600 |
442 1 24275 1 |
|
601 |
443 1 24276 1 |
|
602 |
444 1 24277 1 |
|
603 |
445 1 24278 1 |
|
604 |
446 1 24279 1 |
|
605 |
447 1 24280 1 |
|
606 |
448 1 24281 1 |
|
607 |
449 1 24282 1 |
|
608 |
450 1 24283 1 |
|
609 |
451 1 24284 1 |
|
610 |
452 1 24285 1 |
|
611 |
453 1 24286 1 |
|
612 |
454 1 24287 1 |
|
613 |
455 1 24288 1 |
|
614 |
456 1 24289 1 |
|
615 |
457 1 24290 1 |
|
616 |
458 1 24291 1 |
|
617 |
459 1 24292 1 |
|
618 |
460 1 24293 1 |
|
619 |
461 1 24294 1 |
|
620 |
462 1 24295 1 |
|
621 |
463 1 24296 1 |
|
622 |
464 1 24297 1 |
|
623 |
465 1 24298 1 |
|
624 |
466 1 24299 1 |
|
625 |
467 1 24300 1 |
|
626 |
468 1 24301 1 |
|
627 |
469 1 24302 1 |
|
628 |
470 1 24303 1 |
|
629 |
471 1 24304 1 |
|
630 |
472 1 24305 1 |
|
631 |
473 1 24306 1 |
|
632 |
474 1 24307 1 |
|
633 |
475 1 24308 1 |
|
634 |
476 1 24309 1 |
|
635 |
477 1 24310 1 |
|
636 |
478 1 24311 1 |
|
637 |
479 1 24312 1 |
|
638 |
480 1 24313 1 |
|
639 |
481 1 24314 1 |
|
640 |
482 1 24315 1 |
|
641 |
483 1 24316 1 |
|
642 |
484 1 24317 1 |
|
643 |
485 1 24318 1 |
|
644 |
486 1 24319 1 |
|
645 |
487 1 24320 1 |
|
646 |
488 1 24321 1 |
|
647 |
489 1 24322 1 |
|
648 |
490 1 24323 1 |
|
649 |
491 1 24324 1 |
|
650 |
492 1 24325 1 |
|
651 |
493 1 24326 1 |
|
652 |
494 1 24327 1 |
|
653 |
495 1 24328 1 |
|
654 |
496 1 24329 1 |
|
655 |
497 1 24330 1 |
|
656 |
498 1 24331 1 |
|
657 |
499 1 24332 1 |
|
658 |
500 1 24333 1 |
|
659 |
501 1 24334 1 |
|
660 |
502 1 24335 1 |
|
661 |
503 1 24336 1 |
|
662 |
504 1 24337 1 |
|
663 |
505 1 24338 1 |
|
664 |
506 1 24339 1 |
|
665 |
507 1 24340 1 |
|
666 |
508 1 24341 1 |
|
667 |
509 1 24342 1 |
|
668 |
510 1 24343 1 |
|
669 |
511 1 24344 1 |
|
670 |
512 1 24345 1 |
|
671 |
513 1 24346 1 |
|
672 |
514 1 24347 1 |
|
673 |
515 1 24348 1 |
|
674 |
516 1 24349 1 |
|
675 |
517 1 24350 1 |
|
676 |
518 1 24351 1 |
|
677 |
519 1 24352 1 |
|
678 |
520 1 24353 1 |
|
679 |
521 1 24354 1 |
|
680 |
522 1 24355 1 |
|
681 |
523 1 24356 1 |
|
682 |
524 1 24357 1 |
|
683 |
525 1 24358 1 |
|
684 |
526 1 24359 1 |
|
685 |
527 1 24360 1 |
|
686 |
528 1 24361 1 |
|
687 |
529 1 24362 1 |
|
688 |
530 1 24363 1 |
|
689 |
531 1 24364 1 |
|
690 |
532 1 24365 1 |
|
691 |
533 1 24366 1 |
|
692 |
534 1 24367 1 |
|
693 |
535 1 24368 1 |
|
694 |
536 1 24369 1 |
|
695 |
537 1 24370 1 |
|
696 |
538 1 24371 1 |
|
697 |
539 1 24372 1 |
|
698 |
540 1 24373 1 |
|
699 |
541 1 24374 1 |
|
700 |
542 1 24375 1 |
|
701 |
543 1 24376 1 |
|
702 |
544 1 24377 1 |
|
703 |
545 1 24378 1 |
|
704 |
546 1 24379 1 |
|
705 |
547 1 24380 1 |
|
706 |
548 1 24381 1 |
|
707 |
549 1 24382 1 |
|
708 |
550 1 24383 1 |
|
709 |
551 1 24384 1 |
|
710 |
552 1 24385 1 |
|
711 |
553 1 24386 1 |
|
712 |
554 1 24387 1 |
|
713 |
555 1 24388 1 |
|
714 |
556 1 24389 1 |
|
715 |
557 1 24390 1 |
|
716 |
558 1 24391 1 |
|
717 |
559 1 24392 1 |
|
718 |
560 1 24393 1 |
|
719 |
561 1 24394 1 |
|
720 |
562 1 24395 1 |
|
721 |
563 1 24396 1 |
|
722 |
564 1 24397 1 |
|
723 |
565 1 24398 1 |
|
724 |
566 1 24399 1 |
|
725 |
567 1 24400 1 |
|
726 |
568 1 24401 1 |
|
727 |
569 1 24402 1 |
|
728 |
570 1 24403 1 |
|
729 |
571 1 24404 1 |
|
730 |
572 1 24405 1 |
|
731 |
573 1 24406 1 |
|
732 |
574 1 24407 1 |
|
733 |
575 1 24408 1 |
|
734 |
576 1 24409 1 |
|
735 |
577 1 24410 1 |
|
736 |
578 1 24411 1 |
|
737 |
579 1 24412 1 |
|
738 |
580 1 24413 1 |
|
739 |
581 1 24414 1 |
|
740 |
582 1 24415 1 |
|
741 |
583 1 24416 1 |
|
742 |
584 1 24417 1 |
|
743 |
585 1 24418 1 |
|
744 |
586 1 24419 1 |
|
745 |
587 1 24420 1 |
|
746 |
588 1 24421 1 |
|
747 |
589 1 24422 1 |
|
748 |
590 1 24423 1 |
|
749 |
591 1 24424 1 |
|
750 |
592 1 24425 1 |
|
751 |
593 1 24426 1 |
|
752 |
594 1 24427 1 |
|
753 |
595 1 24428 1 |
|
754 |
596 1 24429 1 |
|
755 |
597 1 24430 1 |
|
756 |
598 1 24431 1 |
|
757 |
599 1 24432 1 |
|
758 |
600 1 24433 1 |
|
759 |
601 1 24434 1 |
|
760 |
602 1 24435 1 |
|
761 |
603 1 24436 1 |
|
762 |
604 1 24437 1 |
|
763 |
605 1 24438 1 |
|
764 |
606 1 24439 1 |
|
765 |
607 1 24440 1 |
|
766 |
608 1 24441 1 |
|
767 |
609 1 24442 1 |
|
768 |
610 1 24443 1 |
|
769 |
611 1 24444 1 |
|
770 |
612 1 24445 1 |
|
771 |
613 1 24446 1 |
|
772 |
614 1 24447 1 |
|
773 |
615 1 24448 1 |
|
774 |
616 1 24449 1 |
|
775 |
617 1 24450 1 |
|
776 |
618 1 24451 1 |
|
777 |
619 1 24452 1 |
|
778 |
620 1 24453 1 |
|
779 |
621 1 24454 1 |
|
780 |
622 1 24455 1 |
|
781 |
623 1 24456 1 |
|
782 |
624 1 24457 1 |
|
783 |
625 1 24458 1 |
|
784 |
626 1 24459 1 |
|
785 |
627 1 24460 1 |
|
786 |
628 1 24461 1 |
|
787 |
629 1 24462 1 |
|
788 |
630 1 24463 1 |
|
789 |
631 1 24464 1 |
|
790 |
632 1 24465 1 |
|
791 |
633 1 24466 1 |
|
792 |
634 1 24467 1 |
|
793 |
635 1 24468 1 |
|
794 |
636 1 24469 1 |
|
795 |
637 1 24470 1 |
|
796 |
638 1 24471 1 |
|
797 |
639 1 24472 1 |
|
798 |
640 1 24473 1 |
|
799 |
641 1 24474 1 |
|
800 |
642 1 24475 1 |
|
801 |
643 1 24476 1 |
|
802 |
644 1 24477 1 |
|
803 |
645 1 24478 1 |
|
804 |
646 1 24479 1 |
|
805 |
647 1 24480 1 |
|
806 |
648 1 24481 1 |
|
807 |
649 1 24482 1 |
|
808 |
650 1 24483 1 |
|
809 |
651 1 24484 1 |
|
810 |
652 1 24485 1 |
|
811 |
653 1 24486 1 |
|
812 |
654 1 24487 1 |
|
813 |
655 1 24488 1 |
|
814 |
656 1 24489 1 |
|
815 |
657 1 24490 1 |
|
816 |
658 1 24491 1 |
|
817 |
659 1 24492 1 |
|
818 |
660 1 24493 1 |
|
819 |
661 1 24494 1 |
|
820 |
662 1 24495 1 |
|
821 |
663 1 24496 1 |
|
822 |
664 1 24497 1 |
|
823 |
665 1 24498 1 |
|
824 |
666 1 24499 1 |
|
825 |
667 1 24500 1 |
|
826 |
668 1 24501 1 |
|
827 |
669 1 24502 1 |
|
828 |
670 1 24503 1 |
|
829 |
671 1 24504 1 |
|
830 |
672 1 24505 1 |
|
831 |
673 1 24506 1 |
|
832 |
674 1 24507 1 |
|
833 |
675 1 24508 1 |
|
834 |
676 1 24509 1 |
|
835 |
677 1 24510 1 |
|
836 |
678 1 24511 1 |
|
837 |
679 1 24512 1 |
|
838 |
680 1 24513 1 |
|
839 |
681 1 24514 1 |
|
840 |
682 1 24515 1 |
|
841 |
683 1 24516 1 |
|
842 |
684 1 24517 1 |
|
843 |
685 1 24518 1 |
|
844 |
686 1 24519 1 |
|
845 |
687 1 24520 1 |
|
846 |
688 1 24521 1 |
|
847 |
689 1 24522 1 |
|
848 |
690 1 24523 1 |
|
849 |
691 1 24524 1 |
|
850 |
692 1 24525 1 |
|
851 |
693 1 24526 1 |
|
852 |
694 1 24527 1 |
|
853 |
695 1 24528 1 |
|
854 |
696 1 24529 1 |
|
855 |
697 1 24530 1 |
|
856 |
698 1 24531 1 |
|
857 |
699 1 24532 1 |
|
858 |
700 1 24533 1 |
|
859 |
701 1 24534 1 |
|
860 |
702 1 24535 1 |
|
861 |
703 1 24536 1 |
|
862 |
704 1 24537 1 |
|
863 |
705 1 24538 1 |
|
864 |
706 1 24539 1 |
|
865 |
707 1 24540 1 |
|
866 |
708 1 24541 1 |
|
867 |
709 1 24542 1 |
|
868 |
710 1 24543 1 |
|
869 |
711 1 24544 1 |
|
870 |
712 1 24545 1 |
|
871 |
713 1 24546 1 |
|
872 |
714 1 24547 1 |
|
873 |
715 1 24548 1 |
|
874 |
716 1 24549 1 |
|
875 |
717 1 24550 1 |
|
876 |
718 1 24551 1 |
|
877 |
719 1 24552 1 |
|
878 |
720 1 24553 1 |
|
879 |
721 1 24554 1 |
|
880 |
722 1 24555 1 |
|
881 |
723 1 24556 1 |
|
882 |
724 1 24557 1 |
|
883 |
725 1 24558 1 |
|
884 |
726 1 24559 1 |
|
885 |
727 1 24560 1 |
|
886 |
728 1 24561 1 |
|
887 |
729 1 24562 1 |
|
888 |
730 1 24563 1 |
|
889 |
731 1 24564 1 |
|
890 |
732 1 24565 1 |
|
891 |
733 1 24566 1 |
|
892 |
734 1 24567 1 |
|
893 |
735 1 24568 1 |
|
894 |
736 1 24569 1 |
|
895 |
737 1 24570 1 |
|
896 |
738 1 24571 1 |
|
897 |
739 1 24572 1 |
|
898 |
740 1 24573 1 |
|
899 |
741 1 24574 1 |
|
900 |
742 1 24575 1 |
|
901 |
743 1 24576 1 |
|
902 |
744 1 24577 1 |
|
903 |
745 1 24578 1 |
|
904 |
746 1 24579 1 |
|
905 |
747 1 24580 1 |
|
906 |
748 1 24581 1 |
|
907 |
749 1 24582 1 |
|
908 |
750 1 24583 1 |
|
909 |
751 1 24584 1 |
|
910 |
752 1 24585 1 |
|
911 |
753 1 24586 1 |
|
912 |
754 1 24587 1 |
|
913 |
755 1 24588 1 |
|
914 |
756 1 24589 1 |
|
915 |
757 1 24590 1 |
|
916 |
758 1 24591 1 |
|
917 |
759 1 24592 1 |
|
918 |
760 1 24593 1 |
|
919 |
761 1 24594 1 |
|
920 |
762 1 24595 1 |
|
921 |
763 1 24596 1 |
|
922 |
764 1 24597 1 |
|
923 |
765 1 24598 1 |
|
924 |
766 1 24599 1 |
|
925 |
767 1 24600 1 |
|
926 |
768 1 24601 1 |
|
927 |
769 1 24602 1 |
|
928 |
770 1 24603 1 |
|
929 |
771 1 24604 1 |
|
930 |
772 1 24605 1 |
|
931 |
773 1 24606 1 |
|
932 |
774 1 24607 1 |
|
933 |
775 1 24608 1 |
|
934 |
776 1 24609 1 |
|
935 |
777 1 24610 1 |
|
936 |
778 1 24611 1 |
|
937 |
779 1 24612 1 |
|
938 |
780 1 24613 1 |
|
939 |
781 1 24614 1 |
|
940 |
782 1 24615 1 |
|
941 |
783 1 24616 1 |
|
942 |
784 1 24617 1 |
|
943 |
785 1 24618 1 |
|
944 |
786 1 24619 1 |
|
945 |
787 1 24620 1 |
|
946 |
788 1 24621 1 |
|
947 |
789 1 24622 1 |
|
948 |
790 1 24623 1 |
|
949 |
791 1 24624 1 |
|
950 |
792 1 24625 1 |
|
951 |
793 1 24626 1 |
|
952 |
794 1 24627 1 |
|
953 |
795 1 24628 1 |
|
954 |
796 1 24629 1 |
|
955 |
797 1 24630 1 |
|
956 |
798 1 24631 1 |
|
957 |
799 1 24632 1 |
|
958 |
800 1 24633 1 |
|
959 |
801 1 24634 1 |
|
960 |
802 1 24635 1 |
|
961 |
803 1 24636 1 |
|
962 |
804 1 24637 1 |
|
963 |
805 1 24638 1 |
|
964 |
806 1 24639 1 |
|
965 |
807 1 24640 1 |
|
966 |
808 1 24641 1 |
|
967 |
809 1 24642 1 |
|
968 |
810 1 24643 1 |
|
969 |
811 1 24644 1 |
|
970 |
812 1 24645 1 |
|
971 |
813 1 24646 1 |
|
972 |
814 1 24647 1 |
|
973 |
815 1 24648 1 |
|
974 |
816 1 24649 1 |
|
975 |
817 1 24650 1 |
|
976 |
818 1 24651 1 |
|
977 |
819 1 24652 1 |
|
978 |
820 1 24653 1 |
|
979 |
821 1 24654 1 |
|
980 |
822 1 24655 1 |
|
981 |
823 1 24656 1 |
|
982 |
824 1 24657 1 |
|
983 |
825 1 24658 1 |
|
984 |
826 1 24659 1 |
|
985 |
827 1 24660 1 |
|
986 |
828 1 24661 1 |
|
987 |
829 1 24662 1 |
|
988 |
830 1 24663 1 |
|
989 |
831 1 24664 1 |
|
990 |
832 1 24665 1 |
|
991 |
833 1 24666 1 |
|
992 |
834 1 24667 1 |
|
993 |
835 1 24668 1 |
|
994 |
836 1 24669 1 |
|
995 |
837 1 24670 1 |
|
996 |
838 1 24671 1 |
|
997 |
839 1 24672 1 |
|
998 |
840 1 24673 1 |
|
999 |
841 1 24674 1 |
|
1000 |
842 1 24675 1 |
|
1001 |
843 1 24676 1 |
|
1002 |
844 1 24677 1 |
|
1003 |
845 1 24678 1 |
|
1004 |
846 1 24679 1 |
|
1005 |
847 1 24680 1 |
|
1006 |
848 1 24681 1 |
|
1007 |
849 1 24682 1 |
|
1008 |
850 1 24683 1 |
|
1009 |
851 1 24684 1 |
|
1010 |
852 1 24685 1 |
|
1011 |
853 1 24686 1 |
|
1012 |
854 1 24687 1 |
|
1013 |
855 1 24688 1 |
|
1014 |
856 1 24689 1 |
|
1015 |
857 1 24690 1 |
|
1016 |
858 1 24691 1 |
|
1017 |
859 1 24692 1 |
|
1018 |
860 1 24693 1 |
|
1019 |
861 1 24694 1 |
|
1020 |
862 1 24695 1 |
|
1021 |
863 1 24696 1 |
|
1022 |
864 1 24697 1 |
|
1023 |
865 1 24698 1 |
|
1024 |
866 1 24699 1 |
|
1025 |
867 1 24700 1 |
|
1026 |
868 1 24701 1 |
|
1027 |
869 1 24702 1 |
|
1028 |
870 1 24703 1 |
|
1029 |
871 1 24704 1 |
|
1030 |
872 1 24705 1 |
|
1031 |
873 1 24706 1 |
|
1032 |
874 1 24707 1 |
|
1033 |
875 1 24708 1 |
|
1034 |
876 1 24709 1 |
|
1035 |
877 1 24710 1 |
|
1036 |
878 1 24711 1 |
|
1037 |
879 1 24712 1 |
|
1038 |
880 1 24713 1 |
|
1039 |
881 1 24714 1 |
|
1040 |
882 1 24715 1 |
|
1041 |
883 1 24716 1 |
|
1042 |
884 1 24717 1 |
|
1043 |
885 1 24718 1 |
|
1044 |
886 1 24719 1 |
|
1045 |
887 1 24720 1 |
|
1046 |
888 1 24721 1 |
|
1047 |
889 1 24722 1 |
|
1048 |
890 1 24723 1 |
|
1049 |
891 1 24724 1 |
|
1050 |
892 1 24725 1 |
|
1051 |
893 1 24726 1 |
|
1052 |
894 1 24727 1 |
|
1053 |
895 1 24728 1 |
|
1054 |
896 1 24729 1 |
|
1055 |
897 1 24730 1 |
|
1056 |
898 1 24731 1 |
|
1057 |
899 1 24732 1 |
|
1058 |
900 1 24733 1 |
|
1059 |
901 1 24734 1 |
|
1060 |
902 1 24735 1 |
|
1061 |
903 1 24736 1 |
|
1062 |
904 1 24737 1 |
|
1063 |
905 1 24738 1 |
|
1064 |
906 1 24739 1 |
|
1065 |
907 1 24740 1 |
|
1066 |
908 1 24741 1 |
|
1067 |
909 1 24742 1 |
|
1068 |
910 1 24743 1 |
|
1069 |
911 1 24744 1 |
|
1070 |
912 1 24745 1 |
|
1071 |
913 1 24746 1 |
|
1072 |
914 1 24747 1 |
|
1073 |
915 1 24748 1 |
|
1074 |
916 1 24749 1 |
|
1075 |
917 1 24750 1 |
|
1076 |
918 1 24751 1 |
|
1077 |
919 1 24752 1 |
|
1078 |
920 1 24753 1 |
|
1079 |
921 1 24754 1 |
|
1080 |
922 1 24755 1 |
|
1081 |
923 1 24756 1 |
|
1082 |
924 1 24757 1 |
|
1083 |
925 1 24758 1 |
|
1084 |
926 1 24759 1 |
|
1085 |
927 1 24760 1 |
|
1086 |
928 1 24761 1 |
|
1087 |
929 1 24762 1 |
|
1088 |
930 1 24763 1 |
|
1089 |
931 1 24764 1 |
|
1090 |
932 1 24765 1 |
|
1091 |
933 1 24766 1 |
|
1092 |
934 1 24767 1 |
|
1093 |
935 1 24768 1 |
|
1094 |
936 1 24769 1 |
|
1095 |
937 1 24770 1 |
|
1096 |
938 1 24771 1 |
|
1097 |
939 1 24772 1 |
|
1098 |
940 1 24773 1 |
|
1099 |
941 1 24774 1 |
|
1100 |
942 1 24775 1 |
|
1101 |
943 1 24776 1 |
|
1102 |
944 1 24777 1 |
|
1103 |
945 1 24778 1 |
|
1104 |
946 1 24779 1 |
|
1105 |
947 1 24780 1 |
|
1106 |
948 1 24781 1 |
|
1107 |
949 1 24782 1 |
|
1108 |
950 1 24783 1 |
|
1109 |
951 1 24784 1 |
|
1110 |
952 1 24785 1 |
|
1111 |
953 1 24786 1 |
|
1112 |
954 1 24787 1 |
|
1113 |
955 1 24788 1 |
|
1114 |
956 1 24789 1 |
|
1115 |
957 1 24790 1 |
|
1116 |
958 1 24791 1 |
|
1117 |
959 1 24792 1 |
|
1118 |
960 1 24793 1 |
|
1119 |
961 1 24794 1 |
|
1120 |
962 1 24795 1 |
|
1121 |
963 1 24796 1 |
|
1122 |
964 1 24797 1 |
|
1123 |
965 1 24798 1 |
|
1124 |
966 1 24799 1 |
|
1125 |
967 1 24800 1 |
|
1126 |
968 1 24801 1 |
|
1127 |
969 1 24802 1 |
|
1128 |
970 1 24803 1 |
|
1129 |
971 1 24804 1 |
|
1130 |
972 1 24805 1 |
|
1131 |
973 1 24806 1 |
|
1132 |
974 1 24807 1 |
|
1133 |
975 1 24808 1 |
|
1134 |
976 1 24809 1 |
|
1135 |
977 1 24810 1 |
|
1136 |
978 1 24811 1 |
|
1137 |
979 1 24812 1 |
|
1138 |
980 1 24813 1 |
|
1139 |
981 1 24814 1 |
|
1140 |
982 1 24815 1 |
|
1141 |
983 1 24816 1 |
|
1142 |
984 1 24817 1 |
|
1143 |
985 1 24818 1 |
|
1144 |
986 1 24819 1 |
|
1145 |
987 1 24820 1 |
|
1146 |
988 1 24821 1 |
|
1147 |
989 1 24822 1 |
|
1148 |
990 1 24823 1 |
|
1149 |
991 1 24824 1 |
|
1150 |
992 1 24825 1 |
|
1151 |
993 1 24826 1 |
|
1152 |
994 1 24827 1 |
|
1153 |
995 1 24828 1 |
|
1154 |
996 1 24829 1 |
|
1155 |
997 1 24830 1 |
|
1156 |
998 1 24831 1 |
|
1157 |
999 1 24832 1 |
|
1158 |
1000 1 24833 1 |
|
1159 |
1001 1 24834 1 |
|
1160 |
1002 1 24835 1 |
|
1161 |
1003 1 24836 1 |
|
1162 |
1004 1 24837 1 |
|
1163 |
1005 1 24838 1 |
|
1164 |
1006 1 24839 1 |
|
1165 |
1007 1 24840 1 |
|
1166 |
1008 1 24841 1 |
|
1167 |
1009 1 24842 1 |
|
1168 |
1010 1 24843 1 |
|
1169 |
1011 1 24844 1 |
|
1170 |
1012 1 24845 1 |
|
1171 |
1013 1 24846 1 |
|
1172 |
1014 1 24847 1 |
|
1173 |
1015 1 24848 1 |
|
1174 |
1016 1 24849 1 |
|
1175 |
1017 1 24850 1 |
|
1176 |
1018 1 24851 1 |
|
1177 |
1019 1 24852 1 |
|
1178 |
1020 1 24853 1 |
|
1179 |
1021 1 24854 1 |
|
1180 |
1022 1 24855 1 |
|
1181 |
1023 1 24856 1 |
|
1182 |
1024 1 24857 1 |
|
1183 |
1025 1 24858 1 |
|
1184 |
1026 1 24859 1 |
|
1185 |
1027 1 24860 1 |
|
1186 |
1028 1 24861 1 |
|
1187 |
1029 1 24862 1 |
|
1188 |
1030 1 24863 1 |
|
1189 |
1031 1 24864 1 |
|
1190 |
1032 1 24865 1 |
|
1191 |
1033 1 24866 1 |
|
1192 |
1034 1 24867 1 |
|
1193 |
1035 1 24868 1 |
|
1194 |
1036 1 24869 1 |
|
1195 |
1037 1 24870 1 |
|
1196 |
1038 1 24871 1 |
|
1197 |
1039 1 24872 1 |
|
1198 |
1040 1 24873 1 |
|
1199 |
1041 1 24874 1 |
|
1200 |
1042 1 24875 1 |
|
1201 |
1043 1 24876 1 |
|
1202 |
1044 1 24877 1 |
|
1203 |
1045 1 24878 1 |
|
1204 |
1046 1 24879 1 |
|
1205 |
1047 1 24880 1 |
|
1206 |
1048 1 24881 1 |
|
1207 |
1049 1 24882 1 |
|
1208 |
1050 1 24883 1 |
|
1209 |
1051 1 24884 1 |
|
1210 |
1052 1 24885 1 |
|
1211 |
1053 1 24886 1 |
|
1212 |
1054 1 24887 1 |
|
1213 |
1055 1 24888 1 |
|
1214 |
1056 1 24889 1 |
|
1215 |
1057 1 24890 1 |
|
1216 |
1058 1 24891 1 |
|
1217 |
1059 1 24892 1 |
|
1218 |
1060 1 24893 1 |
|
1219 |
1061 1 24894 1 |
|
1220 |
1062 1 24895 1 |
|
1221 |
1063 1 24896 1 |
|
1222 |
1064 1 24897 1 |
|
1223 |
1065 1 24898 1 |
|
1224 |
1066 1 24899 1 |
|
1225 |
1067 1 24900 1 |
|
1226 |
1068 1 24901 1 |
|
1227 |
1069 1 24902 1 |
|
1228 |
1070 1 24903 1 |
|
1229 |
1071 1 24904 1 |
|
1230 |
1072 1 24905 1 |
|
1231 |
1073 1 24906 1 |
|
1232 |
1074 1 24907 1 |
|
1233 |
1075 1 24908 1 |
|
1234 |
1076 1 24909 1 |
|
1235 |
1077 1 24910 1 |
|
1236 |
1078 1 24911 1 |
|
1237 |
1079 1 24912 1 |
|
1238 |
1080 1 24913 1 |
|
1239 |
1081 1 24914 1 |
|
1240 |
1082 1 24915 1 |
|
1241 |
1083 1 24916 1 |
|
1242 |
1084 1 24917 1 |
|
1243 |
1085 1 24918 1 |
|
1244 |
1086 1 24919 1 |
|
1245 |
1087 1 24920 1 |
|
1246 |
1088 1 24921 1 |
|
1247 |
1089 1 24922 1 |
|
1248 |
1090 1 24923 1 |
|
1249 |
1091 1 24924 1 |
|
1250 |
1092 1 24925 1 |
|
1251 |
1093 1 24926 1 |
|
1252 |
1094 1 24927 1 |
|
1253 |
1095 1 24928 1 |
|
1254 |
1096 1 24929 1 |
|
1255 |
1097 1 24930 1 |
|
1256 |
1098 1 24931 1 |
|
1257 |
1099 1 24932 1 |
|
1258 |
1100 1 24933 1 |
|
1259 |
1101 1 24934 1 |
|
1260 |
1102 1 24935 1 |
|
1261 |
1103 1 24936 1 |
|
1262 |
1104 1 24937 1 |
|
1263 |
1105 1 24938 1 |
|
1264 |
1106 1 24939 1 |
|
1265 |
1107 1 24940 1 |
|
1266 |
1108 1 24941 0 |
|
1267 |
||
1268 |
||
1269 |
Note that it takes 1100 trips to the index layer to generate the 25k revision |
|
1270 |
history, versus only 50 when we fast-loop on a given index node. |
|
1271 |
||
1272 |
Note also that from 300=>1100 we are iterating over a single revision. This is |
|
1273 |
because bzr has a *very* long single-parent ancestry because of Martin's |
|
1274 |
initial work. However a project like OOo is going to have *much* more of this.
|
|
1275 |
||
1276 |
We do get to 20k revisions in 107 round trips, but it only takes 15 round trips
|
|
1277 |
to do the same with the get_ancestry version.
|
|
1278 |
||
1279 |
get_parent_map peaks at a width of 360 revisions per lookup
|
|
1280 |
get_ancestry peaks at 529 search_keys, but peaks at finding 2287 keys in a
|
|
1281 |
single pass, and only has 1 pass where it failed to find more than 1 parent,
|
|
1282 |
and only 4 passes where it found fewer than 10.
|
|
1283 |
||
1284 |
||
|
4593.4.9
by John Arbash Meinel
Add some debugging statements for now. |
1285 |
Notes from CombinedGraphIndex.get_ancestry
|
1286 |
||
1287 |
you can see that in a real-world repository it takes 1 pass across all indexes
|
|
1288 |
to really 'get primed' and start yielding results. However once that has |
|
1289 |
happened, we end up getting a lot of results quickly from the 'deep history' |
|
1290 |
index, and then we spin around a few times to finally fill in the rest of the
|
|
1291 |
indexes.
|
|
|
4593.4.1
by John Arbash Meinel
Implement a function on btree that inlines the get_parent_map loop. |
1292 |
One possibility would be to reprioritise the various indexes, so that if an
|
|
4593.4.9
by John Arbash Meinel
Add some debugging statements for now. |
1293 |
index has recently had good success returning information, we move it earlier
|
1294 |
in the list. Or conversely, if we don't get any information, we move the index |
|
1295 |
to the end. I don't have anything concrete, but the idea is to avoid polling |
|
1296 |
*all* of the indexes on every pass, but instead to have a tighter loop around |
|
1297 |
ones that we think are going to give us good info. |
|
1298 |
||
1299 |
gen idx sub n_keys n_pmap n_miss |
|
1300 |
1 1 0 0 |
|
1301 |
0 1 0 0 |
|
1302 |
1 0 0 1 |
|
1303 |
1 1 0 0 |
|
1304 |
1 0 0 1 |
|
1305 |
2 1 0 0 |
|
1306 |
1 0 0 1 |
|
1307 |
3 1 0 0 |
|
1308 |
1 0 0 1 |
|
1309 |
4 1 0 0 |
|
1310 |
1 0 0 1 |
|
1311 |
5 1 0 0 |
|
1312 |
1 0 0 1 |
|
1313 |
6 1 0 0 |
|
1314 |
1 0 0 1 |
|
1315 |
7 1 0 0 |
|
1316 |
1 0 0 1 |
|
1317 |
8 1 0 0 |
|
1318 |
1 0 4 1 |
|
1319 |
9 1 4 0 |
|
1320 |
1 0 4 1 |
|
1321 |
10 1 4 0 |
|
1322 |
1 0 4 1 |
|
1323 |
11 1 4 0 |
|
1324 |
1 0 4 1 |
|
1325 |
12 1 4 0 |
|
1326 |
1 0 4 1 |
|
1327 |
13 1 4 0 |
|
1328 |
1 0 4 1 |
|
1329 |
14 1 4 0 |
|
1330 |
1 0 4 1 |
|
1331 |
15 1 4 0 |
|
1332 |
1 0 4 1 |
|
1333 |
16 1 4 0 |
|
1334 |
1 0 4 1 |
|
1335 |
17 1 4 0 |
|
1336 |
1 0 4 1 |
|
1337 |
18 1 4 0 |
|
1338 |
1 0 4 1 |
|
1339 |
19 1 4 0 |
|
1340 |
1 0 4 1 |
|
1341 |
gen idx sub n_keys n_pmap n_miss |
|
1342 |
2 1 4 0 |
|
1343 |
0 1 4 0 |
|
1344 |
1 0 4 1 |
|
1345 |
1 1 4 0 |
|
1346 |
1 0 4 1 |
|
1347 |
2 1 4 0 |
|
1348 |
1 0 4 1 |
|
1349 |
3 1 4 0 |
|
1350 |
1 0 45 7 |
|
1351 |
4 7 45 0 |
|
1352 |
1 0 45 7 |
|
1353 |
5 7 45 0 |
|
1354 |
1 0 45 7 |
|
1355 |
6 7 45 0 |
|
1356 |
1 0 45 7 |
|
1357 |
7 7 45 0 |
|
1358 |
1 0 45 7 |
|
1359 |
8 7 45 0 |
|
1360 |
1 0 45 7 |
|
1361 |
9 7 45 0 |
|
1362 |
1 0 49 7 |
|
1363 |
10 7 49 0 |
|
1364 |
1 0 49 7 |
|
1365 |
11 7 49 0 |
|
1366 |
1 0 49 7 |
|
1367 |
12 7 49 0 |
|
1368 |
1 0 49 7 |
|
1369 |
13 7 49 0 |
|
1370 |
1 0 49 7 |
|
1371 |
14 7 49 0 |
|
1372 |
1 0 49 7 |
|
1373 |
15 7 49 0 |
|
1374 |
1 0 54 7 |
|
1375 |
16 7 54 0 |
|
1376 |
1 63 115 5 |
|
1377 |
2 151 443 5 |
|
1378 |
3 143 1026 5 |
|
1379 |
4 113 1577 5 |
|
1380 |
5 291 2215 5 |
|
1381 |
6 574 3707 5 |
|
1382 |
7 569 6047 5 |
|
1383 |
8 540 8814 5 |
|
1384 |
9 476 11157 5 |
|
1385 |
10 352 13153 5 |
|
1386 |
11 411 14748 5 |
|
1387 |
12 359 16704 5 |
|
1388 |
13 289 18287 5 |
|
1389 |
14 136 19853 5 |
|
1390 |
15 76 20655 5 |
|
1391 |
16 63 21249 5 |
|
1392 |
17 37 21748 5 |
|
1393 |
18 39 22017 5 |
|
1394 |
19 36 22322 5 |
|
1395 |
20 22 22650 5 |
|
1396 |
21 14 23060 5 |
|
1397 |
22 17 23280 5 |
|
1398 |
23 13 23478 7 |
|
1399 |
24 8 23683 7 |
|
1400 |
25 6 23867 7 |
|
1401 |
26 7 24052 7 |
|
1402 |
27 19 24191 7 |
|
1403 |
28 15 24275 7 |
|
1404 |
29 19 24476 7 |
|
1405 |
30 13 24726 7 |
|
1406 |
31 14 24826 7 |
|
1407 |
32 10 24874 7 |
|
1408 |
33 6 24953 7 |
|
1409 |
34 5 24977 7 |
|
1410 |
35 5 25035 7 |
|
1411 |
36 4 25076 7 |
|
1412 |
37 4 25129 7 |
|
1413 |
38 3 25145 7 |
|
1414 |
39 2 25158 7 |
|
1415 |
40 2 25163 7 |
|
1416 |
41 2 25166 7 |
|
1417 |
42 2 25188 7 |
|
1418 |
43 2 25205 7 |
|
1419 |
44 1 25241 7 |
|
1420 |
45 6 25248 7 |
|
1421 |
46 4 25272 7 |
|
1422 |
47 1 25305 7 |
|
1423 |
48 0 25308 7 |
|
1424 |
17 7 25308 0 |
|
1425 |
1 0 25348 6 |
|
1426 |
18 6 25348 0 |
|
1427 |
1 7 25415 9 |
|
1428 |
2 2 25441 11 |
|
1429 |
3 0 25441 13 |
|
1430 |
19 13 25441 0 |
|
1431 |
1 0 25441 13 |
|
1432 |
gen idx sub n_keys n_pmap n_miss |
|
1433 |
3 13 25441 0 |
|
1434 |
0 13 25441 0 |
|
1435 |
1 0 25441 13 |
|
1436 |
1 13 25441 0 |
|
1437 |
1 0 25441 13 |
|
1438 |
2 13 25441 0 |
|
1439 |
1 0 25442 14 |
|
1440 |
3 14 25442 0 |
|
1441 |
1 0 25442 14 |
|
1442 |
4 14 25442 0 |
|
1443 |
1 0 25442 14 |
|
1444 |
5 14 25442 0 |
|
1445 |
1 0 25442 14 |
|
1446 |
6 14 25442 0 |
|
1447 |
1 1 25453 16 |
|
1448 |
2 0 25453 17 |
|
1449 |
7 17 25453 0 |
|
1450 |
1 0 25453 17 |
|
1451 |
8 17 25453 0 |
|
1452 |
1 0 25453 17 |
|
1453 |
9 17 25453 0 |
|
1454 |
1 0 25459 16 |
|
1455 |
10 16 25459 0 |
|
1456 |
1 0 25459 16 |
|
1457 |
11 16 25459 0 |
|
1458 |
1 0 25459 16 |
|
1459 |
12 16 25459 0 |
|
1460 |
1 0 25459 16 |
|
1461 |
13 16 25459 0 |
|
1462 |
1 0 25459 16 |
|
1463 |
14 16 25459 0 |
|
1464 |
1 33 25531 12 |
|
1465 |
2 14 25677 19 |
|
1466 |
3 6 25717 25 |
|
1467 |
4 1 25728 26 |
|
1468 |
5 0 25729 26 |
|
1469 |
15 26 25729 0 |
|
1470 |
1 0 25748 24 |
|
1471 |
16 24 25748 0 |
|
1472 |
1 72 25870 6 |
|
1473 |
2 30 26173 6 |
|
1474 |
3 6 26321 6 |
|
1475 |
4 3 26346 6 |
|
1476 |
5 0 26355 6 |
|
1477 |
17 6 26355 0 |
|
1478 |
1 0 26362 6 |
|
1479 |
18 6 26362 0 |
|
1480 |
1 4 26376 4 |
|
1481 |
2 0 26391 5 |
|
1482 |
19 5 26391 0 |
|
1483 |
1 0 26391 5 |
|
1484 |
gen idx sub n_keys n_pmap n_miss |
|
1485 |
4 3 26391 2 |
|
1486 |
0 3 26391 0 |
|
1487 |
1 0 26391 3 |
|
1488 |
1 3 26391 0 |
|
1489 |
1 0 26391 3 |
|
1490 |
2 3 26391 0 |
|
1491 |
1 0 26391 3 |
|
1492 |
3 3 26391 0 |
|
1493 |
1 0 26391 3 |
|
1494 |
4 3 26391 0 |
|
1495 |
1 0 26391 3 |
|
1496 |
5 3 26391 0 |
|
1497 |
1 0 26391 3 |
|
1498 |
6 3 26391 0 |
|
1499 |
1 0 26391 3 |
|
1500 |
7 3 26391 0 |
|
1501 |
1 0 26391 3 |
|
1502 |
8 3 26391 0 |
|
1503 |
1 0 26391 3 |
|
1504 |
9 3 26391 0 |
|
1505 |
1 0 26391 3 |
|
1506 |
10 3 26391 0 |
|
1507 |
1 0 26391 3 |
|
1508 |
11 3 26391 0 |
|
1509 |
1 0 26391 3 |
|
1510 |
12 3 26391 0 |
|
1511 |
1 0 26391 3 |
|
1512 |
13 3 26391 0 |
|
1513 |
1 0 26391 3 |
|
1514 |
14 3 26391 0 |
|
1515 |
1 1 26394 1 |
|
1516 |
2 0 26401 1 |
|
1517 |
15 1 26401 0 |
|
1518 |
1 0 26401 1 |
|
1519 |
16 1 26401 0 |
|
1520 |
1 0 26401 1 |
|
1521 |
17 1 26401 0 |
|
1522 |
1 0 26401 1 |
|
1523 |
18 1 26401 0 |
|
1524 |
1 0 26402 0 |
|
1525 |
||
|
4593.4.2
by John Arbash Meinel
Removing the min(keys) and max(keys) calls saves 100ms in the inner loop |
1526 |
Performance notes so far: |
1527 |
time ancestry_from_get_parent_map() |
|
1528 |
1530ms (down from 567ms when there was a single real index) |
|
|
4593.4.9
by John Arbash Meinel
Add some debugging statements for now. |
1529 |
time ancestry_from_get_ancestry() |
|
4593.4.2
by John Arbash Meinel
Removing the min(keys) and max(keys) calls saves 100ms in the inner loop |
1530 |
309ms (down from 245ms when there was a single real index) |
|
4593.4.9
by John Arbash Meinel
Add some debugging statements for now. |
1531 |
|
1532 |
So even without optimizing that inner loop much, we are at about 20% |
|
1533 |
time.(5:1 faster). (also note that being done on different repos, the |
|
1534 |
real-world test has another ~1500 revisions in the ancestry.) |
|
1535 |
||
1536 |
This also shows how much better things scale when we have lots of indexes. It |
|
1537 |
allows us to not try to search across all the indexes all the time, because we |
|
1538 |
follow whatever parent threads a given index can give us. |
|
1539 |
||
1540 |
The overhead of 20 indexes was only 245 => 309 or 1.26:1, rather than 3:1 for |
|
|
4593.4.11
by John Arbash Meinel
Snapshot the work in progress. |
1541 |
the get_parent_map implementation. |
|
4593.4.9
by John Arbash Meinel
Add some debugging statements for now. |
1542 |
|
1543 |
Also of interest is that in the single-index case the improvement was only |
|
1544 |
about 2x, so this seems quite significant overall. |
|
1545 |
||
|
4593.4.10
by John Arbash Meinel
Notes for improvement on the OOo tree. |
1546 |
|
1547 |
For OOo with a single index: |
|
1548 |
time ancestry_from_get_parent_map |
|
1549 |
32.998s |
|
1550 |
||
1551 |
time ancestry_from_get_ancestry |
|
1552 |
10.462s |
|
1553 |
||
1554 |
This is 3.15:1 faster, even without the benefits of pyrex or a real-world case |
|
1555 |
when we have more than one pack file. |
|
1556 |