/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to NOTES

  • Committer: John Arbash Meinel
  • Date: 2009-08-13 19:56:26 UTC
  • mto: This revision was merged to the branch mainline in revision 4613.
  • Revision ID: john@arbash-meinel.com-20090813195626-tlsu5cexc1q8lzmr
Name the specific index api _find_ancestors, and the public CombinedGraphIndex api find_ancestry()

Show diffs side-by-side

added added

removed removed

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