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
- browse files at revision 4593.4.1
- compare with another revision
- compare with revision 5200.3.6
- download diff
- download tarball
- view history from revision 4593.4.1
- Committer: John Arbash Meinel
- Date: 2009-08-06 22:05:45 UTC
- mto: This revision was merged to the branch mainline in revision 4613.
- Revision ID: john@arbash-meinel.com-20090806220545-f5dvwvy6tculb64o
Implement a function on btree that inlines the get_parent_map loop.
It basically looks for direct parents within a single LeafNode, until it
hits one that goes outside that node.
Also include some performance notes.
At least for the number of calls, the new function is *much* better than get_parent_map.
It takes only 50 calls to walk all of bzr.dev, while for get_parent_map it
takes 1108 calls.
Part of that is the 'long tail problem', which is better, albeit not perfect with
the new function.
It basically looks for direct parents within a single LeafNode, until it
hits one that goes outside that node.
Also include some performance notes.
At least for the number of calls, the new function is *much* better than get_parent_map.
It takes only 50 calls to walk all of bzr.dev, while for get_parent_map it
takes 1108 calls.
Part of that is the 'long tail problem', which is better, albeit not perfect with
the new function.
- files added:
- NOTES
- files modified:
- bzrlib/btree_index.py
added
removed
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
So how to handle the multiple-index scenario. The issue is that ancestry can
1286
jump back and forth between indexes. Though if you consider it closely, it is
1287
actually quite unlikely to do so, because that would imply knowing about a
1288
revision in a previous pack, before that revision was transferred. Possible,
1289
yes (especially with ghosts), likely: no.
1290
1291
However, certainly parents that are missing in one index are likely to be found
1292
in another index, and we don't really know the actual ordering between the
1293
indexes.
1294
1295
# We want to keep looping until keys_to_search converges to 0, or we
1296
# determine that all indexes are missing the keys that we are currently
1297
# searching for.
1298
# I think we could do something like take the set intersection of the keys
1299
# that each index says are missing, and then after a given pass, we would
1300
# stop searching all of the keys that all indexes are missing.
1301
1302
My thought is to have a loop like:
1303
1304
keys_to_search = set(input_keys)
1305
missing_keys = set()
1306
while keys_to_search:
1307
all_index_missing = None
1308
for index in self._indices:
1309
this_search_keys = keys_to_search
1310
# keys this *this* index cannot resolve
1311
index_missing_keys = set()
1312
while this_search_keys:
1313
this_missing_keys, this_search_keys =
1314
index.get_ancestry(this_search_keys, ...)
1315
index_missing_keys.update(this_missing_keys)
1316
keys_to_search = index_missing_keys
1317
if all_index_missing is None:
1318
all_index_missing = set(index_missing_keys)
1319
else:
1320
all_index_missing = all_index_missing.intersection(index_missing_keys)
1321
missing_keys.update(all_index_missing)
1322
keys_to_search = keys_to_search.difference(all_index_missing)
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0