/brz/remove-bazaar

Some quick notes about get_ancestry results when tested with bzr's ancestry
and:
4401 Canonical.com Patch Queue Manager 2009-06-03 [merge]
     revision-id:pqm@pqm.ubuntu.com-20090603080435-2gbqwzvbx31zr7ok
     (andrew) Fix tracebacks when receiving error responses to
       BzrDirFormat.initialize* RPCs.

This is in a fully packed repository, so there is only a single btree index,
and thus there should be only a small handful of genuinely missing keys.

First call to get_ancestry reads the root node, +1 internal node, +1 leaf node
It is able to expand from 1 key into 74 already know parent keys, and 75
missing parent tips.

Second call expands to 2 internal nodes (all of them), 14 leaf nodes, and 398
known parents, and 82 search tips. Of those 82 tips, 51 of them are present on
nodes that we had already read, we just didn't find them because we don't
search outside the current page for parent keys.


Third call:
    112 search keys
        36 actually present on an unread LeafNode
    794 parent_map (found parents)
    30 leaf nodes

Fourth:
    185 search keys
        48 really missing
    1243 parent_map
    40 leaf nodes

Fifth:
    246 search keys
        108 really missing
    2034 parent_map
    52 leaf nodes

Sixth:
    431 search keys
        119 really missing
    3272 parent_map
    79 leaf nodes

Seventh:
    529 search keys
        103 really missing # went down?
    5472 parent_map
    103 leaf nodes (out of 221 total)

Eighth:
    455 search keys (down?)
        75 really missing
    7759 parent_map
    119 leaf nodes

Ninth:
    430 search keys
        157 really missing
    10004 parent_map
    130 leaf nodes

Tenth:
    407 search keys
        157 really missing?
    11788 parent_map
    148 leaf nodes

Eleventh:
    400 search keys
        127 missing
    13502 parent_map
    165 leaf nodes

12:
    389 search keys
    145 missing
    15,500 parent_map
    179 leaf nodes

13:
    289 search keys
    72 missing
    17,586 parent_map
    194 leaf nodes

# I wonder if at this point a major limitation is the parents that are read but
# are not on the same page. You could have flip-flop cases, where you have:
# pqm@ => john@ => pqm@ => john@ => pqm@ => john@
# And each one of those is going to require another re-entrance into
# get_ancestry

gen     search_keys     parent_map      parents_found
                not loaded      num_leaf_nodes_cached
0       1       1       0       0
1	75	75	74	1       74
2	82	31	398	14      324
3	112	36	794	30      396
4	185	48	1243	40      449
5	246	108	2034	52      791
6	431	119	3272	79      1238
7	529	103	5472	103     2200
8	455	75	7759	119     2287
9	430	157	10004	130     2245
10	407	157	11788	148     1784
11	400	127	13502	165     1714
12	389	145	15500	179     1998
13	289	72	17586	194     2086
14	210	46	19185	203     1599
15	140	2	20474	210     1289
16	63	5	21331	211     857
17	53	9	21761	212     430
18	30	3	22159	214     398
19	23	4	22700	216     541
20	15	1	23055	217     355
21	11	1	23266	218     211
22	8	1	23485	219     219
23	8	0	23651	220     166
24	6	0	23672	220     21
25	8	1	23716	220     44
26	6	0	23905	221     189
27	5	0	23994	221     89
28	12	0	24037	221     43
29	13	0	24102	221     65
30	14	0	24192	221     90
31	15	0	24284	221     92
32	10	0	24344	221     60
33	13	0	24419	221     75
34	15	0	24465	221     46
35	8	0	24612	221     147
36	5	0	24663	221     51
37	4	0	24744	221     81
38	3	0	24758	221     14
39	3	0	24769	221     11
40	3	0	24786	221     17
41	2	0	24809	221     23
42	1	0	24827	221     18
43	1	0	24828	221     1
44	1	0	24848	221     20
45	1	0	24853	221     5
46	1	0	24874	221     21
47	6	0	24883	221     9
48	4	0	24905	221     22
49	1	0	24938	221     33
50	0	0	24941	221     3


# Note the *really* long tail where after we have 20k keys we've pretty much
# read all the pages, and at this point, we only have a small handful
# (sometimes only 1) parent to search for.
# Then again, if you look at the number of parents found count, it is going
# up by easily 20-100 at each step, so it is still fairly efficient.

# Also, we can compare this to the performance of just looping over
# 'get_parent_map()' calls
gen     search_keys     next_keys
                parent_map
0       1       0       1
1	1	1	2
2	2	3	3
3	3	6	4
4	4	10	5
5	5	15	7
6	7	22	11
7	11	33	17
8	17	50	20
9	20	70	23
10	23	93	24
11	24	117	24
12	24	141	28
13	28	169	30
14	30	199	33
15	33	232	34
16	34	266	39
17	39	305	42
18	42	347	46
19	46	393	48
20	48	441	58
21	58	499	67
22	67	566	75
23	75	641	87
24	87	728	95
25	95	823	96
26	96	919	103
27	103	1022	109
28	109	1131	121
29	121	1252	140
30	140	1392	144
31	144	1536	162
32	162	1698	175
33	175	1873	189
34	189	2062	202
35	202	2264	219
36	219	2483	225
37	225	2708	235
38	235	2943	250
39	250	3193	245
40	245	3438	252
41	252	3690	269
42	269	3959	270
43	270	4229	291
44	291	4520	300
45	300	4820	311
46	311	5131	340
47	340	5471	362
48	362	5833	364
49	364	6197	372
50	372	6569	366
51	366	6935	363
52	363	7298	354
53	354	7652	360
54	360	8012	337
55	337	8349	336
56	336	8685	307
57	307	8992	291
58	291	9283	290
59	290	9573	290
60	290	9863	280
61	280	10143	261
62	261	10404	253
63	253	10657	248
64	248	10905	239
65	239	11144	248
66	248	11392	235
67	235	11627	228
68	228	11855	232
69	232	12087	233
70	233	12320	238
71	238	12558	251
72	251	12809	269
73	269	13078	280
74	280	13358	286
75	286	13644	280
76	280	13924	284
77	284	14208	305
78	305	14513	298
79	298	14811	291
80	291	15102	299
81	299	15401	285
82	285	15686	272
83	272	15958	270
84	270	16228	264
85	264	16492	245
86	245	16737	237
87	237	16974	212
88	212	17186	201
89	201	17387	194
90	194	17581	182
91	182	17763	176
92	176	17939	178
93	178	18117	171
94	171	18288	169
95	169	18457	173
96	173	18630	160
97	160	18790	154
98	154	18944	154
99	154	19098	147
100	147	19245	140
101	140	19385	130
102	130	19515	123
103	123	19638	113
104	113	19751	107
105	107	19858	102
106	102	19960	93
107	93	20053	90
108	90	20143	89
109	89	20232	79
110	79	20311	77
111	77	20388	76
112	76	20464	77
113	77	20541	76
114	76	20617	74
115	74	20691	68
116	68	20759	69
117	69	20828	64
118	64	20892	66
119	66	20958	63
120	63	21021	56
121	56	21077	57
122	57	21134	54
123	54	21188	57
124	57	21245	58
125	58	21303	54
126	54	21357	47
127	47	21404	48
128	48	21452	45
129	45	21497	45
130	45	21542	41
131	41	21583	41
132	41	21624	41
133	41	21665	42
134	42	21707	43
135	43	21750	42
136	42	21792	36
137	36	21828	37
138	37	21865	36
139	36	21901	32
140	32	21933	34
141	34	21967	33
142	33	22000	31
143	31	22031	32
144	32	22063	29
145	29	22092	33
146	33	22125	34
147	34	22159	32
148	32	22191	29
149	29	22220	27
150	27	22247	28
151	28	22275	25
152	25	22300	24
153	24	22324	21
154	21	22345	21
155	21	22366	20
156	20	22386	20
157	20	22406	19
158	19	22425	19
159	19	22444	19
160	19	22463	19
161	19	22482	18
162	18	22500	20
163	20	22520	20
164	20	22540	20
165	20	22560	19
166	19	22579	18
167	18	22597	17
168	17	22614	17
169	17	22631	17
170	17	22648	17
171	17	22665	17
172	17	22682	17
173	17	22699	17
174	17	22716	17
175	17	22733	17
176	17	22750	15
177	15	22765	15
178	15	22780	15
179	15	22795	14
180	14	22809	14
181	14	22823	14
182	14	22837	15
183	15	22852	17
184	17	22869	17
185	17	22886	17
186	17	22903	16
187	16	22919	15
188	15	22934	15
189	15	22949	15
190	15	22964	15
191	15	22979	15
192	15	22994	14
193	14	23008	14
194	14	23022	14
195	14	23036	14
196	14	23050	15
197	15	23065	15
198	15	23080	15
199	15	23095	15
200	15	23110	15
201	15	23125	16
202	16	23141	16
203	16	23157	16
204	16	23173	15
205	15	23188	15
206	15	23203	14
207	14	23217	14
208	14	23231	13
209	13	23244	16
210	15	23259	14
211	14	23273	14
212	14	23287	15
213	14	23301	14
214	14	23315	14
215	14	23329	14
216	14	23343	14
217	14	23357	14
218	14	23371	15
219	15	23386	15
220	15	23401	15
221	15	23416	15
222	15	23431	14
223	14	23445	14
224	14	23459	12
225	12	23471	11
226	11	23482	11
227	11	23493	11
228	11	23504	11
229	11	23515	11
230	11	23526	11
231	11	23537	11
232	11	23548	11
233	11	23559	11
234	11	23570	10
235	10	23580	11
236	11	23591	10
237	10	23601	10
238	10	23611	10
239	10	23621	10
240	10	23631	10
241	10	23641	10
242	10	23651	9
243	9	23660	9
244	9	23669	9
245	9	23678	9
246	9	23687	9
247	9	23696	9
248	9	23705	9
249	9	23714	8
250	8	23722	8
251	8	23730	8
252	8	23738	8
253	8	23746	9
254	9	23755	9
255	9	23764	10
256	10	23774	12
257	12	23786	13
258	13	23799	13
259	13	23812	13
260	13	23825	13
261	13	23838	11
262	11	23849	9
263	9	23858	9
264	9	23867	8
265	8	23875	8
266	8	23883	7
267	7	23890	7
268	7	23897	7
269	7	23904	7
270	7	23911	7
271	7	23918	7
272	7	23925	7
273	7	23932	6
274	6	23938	6
275	6	23944	6
276	6	23950	6
277	6	23956	6
278	6	23962	5
279	5	23967	5
280	5	23972	5
281	5	23977	5
282	5	23982	5
283	5	23987	5
284	5	23992	5
285	5	23997	5
286	5	24002	5
287	5	24007	4
288	4	24011	4
289	4	24015	4
290	4	24019	4
291	4	24023	4
292	4	24027	4
293	4	24031	3
294	3	24034	3
295	3	24037	3
296	3	24040	3
297	3	24043	3
298	3	24046	3
299	3	24049	3
300	3	24052	3
301	3	24055	3
302	3	24058	3
303	3	24061	3
304	3	24064	3
305	3	24067	3
306	3	24070	3
307	3	24073	3
308	3	24076	3
309	3	24079	3
310	3	24082	3
311	3	24085	3
312	3	24088	3
313	3	24091	3
314	3	24094	3
315	3	24097	3
316	3	24100	3
317	3	24103	3
318	3	24106	3
319	3	24109	3
320	3	24112	3
321	3	24115	3
322	3	24118	3
323	3	24121	3
324	3	24124	3
325	3	24127	3
326	3	24130	3
327	3	24133	3
328	3	24136	3
329	3	24139	2
330	2	24141	2
331	2	24143	2
332	2	24145	2
333	2	24147	2
334	2	24149	2
335	2	24151	2
336	2	24153	2
337	2	24155	2
338	2	24157	2
339	2	24159	2
340	2	24161	2
341	2	24163	2
342	2	24165	2
343	2	24167	2
344	2	24169	2
345	2	24171	2
346	2	24173	2
347	2	24175	2
348	2	24177	2
349	2	24179	2
350	2	24181	2
351	2	24183	2
352	2	24185	1
353	1	24186	1
354	1	24187	1
355	1	24188	1
356	1	24189	1
357	1	24190	1
358	1	24191	1
359	1	24192	1
360	1	24193	1
361	1	24194	1
362	1	24195	1
363	1	24196	1
364	1	24197	1
365	1	24198	1
366	1	24199	1
367	1	24200	1
368	1	24201	1
369	1	24202	1
370	1	24203	1
371	1	24204	1
372	1	24205	1
373	1	24206	1
374	1	24207	1
375	1	24208	1
376	1	24209	1
377	1	24210	1
378	1	24211	1
379	1	24212	1
380	1	24213	1
381	1	24214	1
382	1	24215	1
383	1	24216	1
384	1	24217	1
385	1	24218	1
386	1	24219	1
387	1	24220	1
388	1	24221	1
389	1	24222	1
390	1	24223	1
391	1	24224	1
392	1	24225	1
393	1	24226	1
394	1	24227	1
395	1	24228	1
396	1	24229	1
397	1	24230	1
398	1	24231	1
399	1	24232	1
400	1	24233	1
401	1	24234	1
402	1	24235	1
403	1	24236	1
404	1	24237	1
405	1	24238	1
406	1	24239	1
407	1	24240	1
408	1	24241	1
409	1	24242	1
410	1	24243	1
411	1	24244	1
412	1	24245	1
413	1	24246	1
414	1	24247	1
415	1	24248	1
416	1	24249	1
417	1	24250	1
418	1	24251	1
419	1	24252	1
420	1	24253	1
421	1	24254	1
422	1	24255	1
423	1	24256	1
424	1	24257	1
425	1	24258	1
426	1	24259	1
427	1	24260	1
428	1	24261	1
429	1	24262	1
430	1	24263	1
431	1	24264	1
432	1	24265	1
433	1	24266	1
434	1	24267	1
435	1	24268	1
436	1	24269	1
437	1	24270	1
438	1	24271	1
439	1	24272	1
440	1	24273	1
441	1	24274	1
442	1	24275	1
443	1	24276	1
444	1	24277	1
445	1	24278	1
446	1	24279	1
447	1	24280	1
448	1	24281	1
449	1	24282	1
450	1	24283	1
451	1	24284	1
452	1	24285	1
453	1	24286	1
454	1	24287	1
455	1	24288	1
456	1	24289	1
457	1	24290	1
458	1	24291	1
459	1	24292	1
460	1	24293	1
461	1	24294	1
462	1	24295	1
463	1	24296	1
464	1	24297	1
465	1	24298	1
466	1	24299	1
467	1	24300	1
468	1	24301	1
469	1	24302	1
470	1	24303	1
471	1	24304	1
472	1	24305	1
473	1	24306	1
474	1	24307	1
475	1	24308	1
476	1	24309	1
477	1	24310	1
478	1	24311	1
479	1	24312	1
480	1	24313	1
481	1	24314	1
482	1	24315	1
483	1	24316	1
484	1	24317	1
485	1	24318	1
486	1	24319	1
487	1	24320	1
488	1	24321	1
489	1	24322	1
490	1	24323	1
491	1	24324	1
492	1	24325	1
493	1	24326	1
494	1	24327	1
495	1	24328	1
496	1	24329	1
497	1	24330	1
498	1	24331	1
499	1	24332	1
500	1	24333	1
501	1	24334	1
502	1	24335	1
503	1	24336	1
504	1	24337	1
505	1	24338	1
506	1	24339	1
507	1	24340	1
508	1	24341	1
509	1	24342	1
510	1	24343	1
511	1	24344	1
512	1	24345	1
513	1	24346	1
514	1	24347	1
515	1	24348	1
516	1	24349	1
517	1	24350	1
518	1	24351	1
519	1	24352	1
520	1	24353	1
521	1	24354	1
522	1	24355	1
523	1	24356	1
524	1	24357	1
525	1	24358	1
526	1	24359	1
527	1	24360	1
528	1	24361	1
529	1	24362	1
530	1	24363	1
531	1	24364	1
532	1	24365	1
533	1	24366	1
534	1	24367	1
535	1	24368	1
536	1	24369	1
537	1	24370	1
538	1	24371	1
539	1	24372	1
540	1	24373	1
541	1	24374	1
542	1	24375	1
543	1	24376	1
544	1	24377	1
545	1	24378	1
546	1	24379	1
547	1	24380	1
548	1	24381	1
549	1	24382	1
550	1	24383	1
551	1	24384	1
552	1	24385	1
553	1	24386	1
554	1	24387	1
555	1	24388	1
556	1	24389	1
557	1	24390	1
558	1	24391	1
559	1	24392	1
560	1	24393	1
561	1	24394	1
562	1	24395	1
563	1	24396	1
564	1	24397	1
565	1	24398	1
566	1	24399	1
567	1	24400	1
568	1	24401	1
569	1	24402	1
570	1	24403	1
571	1	24404	1
572	1	24405	1
573	1	24406	1
574	1	24407	1
575	1	24408	1
576	1	24409	1
577	1	24410	1
578	1	24411	1
579	1	24412	1
580	1	24413	1
581	1	24414	1
582	1	24415	1
583	1	24416	1
584	1	24417	1
585	1	24418	1
586	1	24419	1
587	1	24420	1
588	1	24421	1
589	1	24422	1
590	1	24423	1
591	1	24424	1
592	1	24425	1
593	1	24426	1
594	1	24427	1
595	1	24428	1
596	1	24429	1
597	1	24430	1
598	1	24431	1
599	1	24432	1
600	1	24433	1
601	1	24434	1
602	1	24435	1
603	1	24436	1
604	1	24437	1
605	1	24438	1
606	1	24439	1
607	1	24440	1
608	1	24441	1
609	1	24442	1
610	1	24443	1
611	1	24444	1
612	1	24445	1
613	1	24446	1
614	1	24447	1
615	1	24448	1
616	1	24449	1
617	1	24450	1
618	1	24451	1
619	1	24452	1
620	1	24453	1
621	1	24454	1
622	1	24455	1
623	1	24456	1
624	1	24457	1
625	1	24458	1
626	1	24459	1
627	1	24460	1
628	1	24461	1
629	1	24462	1
630	1	24463	1
631	1	24464	1
632	1	24465	1
633	1	24466	1
634	1	24467	1
635	1	24468	1
636	1	24469	1
637	1	24470	1
638	1	24471	1
639	1	24472	1
640	1	24473	1
641	1	24474	1
642	1	24475	1
643	1	24476	1
644	1	24477	1
645	1	24478	1
646	1	24479	1
647	1	24480	1
648	1	24481	1
649	1	24482	1
650	1	24483	1
651	1	24484	1
652	1	24485	1
653	1	24486	1
654	1	24487	1
655	1	24488	1
656	1	24489	1
657	1	24490	1
658	1	24491	1
659	1	24492	1
660	1	24493	1
661	1	24494	1
662	1	24495	1
663	1	24496	1
664	1	24497	1
665	1	24498	1
666	1	24499	1
667	1	24500	1
668	1	24501	1
669	1	24502	1
670	1	24503	1
671	1	24504	1
672	1	24505	1
673	1	24506	1
674	1	24507	1
675	1	24508	1
676	1	24509	1
677	1	24510	1
678	1	24511	1
679	1	24512	1
680	1	24513	1
681	1	24514	1
682	1	24515	1
683	1	24516	1
684	1	24517	1
685	1	24518	1
686	1	24519	1
687	1	24520	1
688	1	24521	1
689	1	24522	1
690	1	24523	1
691	1	24524	1
692	1	24525	1
693	1	24526	1
694	1	24527	1
695	1	24528	1
696	1	24529	1
697	1	24530	1
698	1	24531	1
699	1	24532	1
700	1	24533	1
701	1	24534	1
702	1	24535	1
703	1	24536	1
704	1	24537	1
705	1	24538	1
706	1	24539	1
707	1	24540	1
708	1	24541	1
709	1	24542	1
710	1	24543	1
711	1	24544	1
712	1	24545	1
713	1	24546	1
714	1	24547	1
715	1	24548	1
716	1	24549	1
717	1	24550	1
718	1	24551	1
719	1	24552	1
720	1	24553	1
721	1	24554	1
722	1	24555	1
723	1	24556	1
724	1	24557	1
725	1	24558	1
726	1	24559	1
727	1	24560	1
728	1	24561	1
729	1	24562	1
730	1	24563	1
731	1	24564	1
732	1	24565	1
733	1	24566	1
734	1	24567	1
735	1	24568	1
736	1	24569	1
737	1	24570	1
738	1	24571	1
739	1	24572	1
740	1	24573	1
741	1	24574	1
742	1	24575	1
743	1	24576	1
744	1	24577	1
745	1	24578	1
746	1	24579	1
747	1	24580	1
748	1	24581	1
749	1	24582	1
750	1	24583	1
751	1	24584	1
752	1	24585	1
753	1	24586	1
754	1	24587	1
755	1	24588	1
756	1	24589	1
757	1	24590	1
758	1	24591	1
759	1	24592	1
760	1	24593	1
761	1	24594	1
762	1	24595	1
763	1	24596	1
764	1	24597	1
765	1	24598	1
766	1	24599	1
767	1	24600	1
768	1	24601	1
769	1	24602	1
770	1	24603	1
771	1	24604	1
772	1	24605	1
773	1	24606	1
774	1	24607	1
775	1	24608	1
776	1	24609	1
777	1	24610	1
778	1	24611	1
779	1	24612	1
780	1	24613	1
781	1	24614	1
782	1	24615	1
783	1	24616	1
784	1	24617	1
785	1	24618	1
786	1	24619	1
787	1	24620	1
788	1	24621	1
789	1	24622	1
790	1	24623	1
791	1	24624	1
792	1	24625	1
793	1	24626	1
794	1	24627	1
795	1	24628	1
796	1	24629	1
797	1	24630	1
798	1	24631	1
799	1	24632	1
800	1	24633	1
801	1	24634	1
802	1	24635	1
803	1	24636	1
804	1	24637	1
805	1	24638	1
806	1	24639	1
807	1	24640	1
808	1	24641	1
809	1	24642	1
810	1	24643	1
811	1	24644	1
812	1	24645	1
813	1	24646	1
814	1	24647	1
815	1	24648	1
816	1	24649	1
817	1	24650	1
818	1	24651	1
819	1	24652	1
820	1	24653	1
821	1	24654	1
822	1	24655	1
823	1	24656	1
824	1	24657	1
825	1	24658	1
826	1	24659	1
827	1	24660	1
828	1	24661	1
829	1	24662	1
830	1	24663	1
831	1	24664	1
832	1	24665	1
833	1	24666	1
834	1	24667	1
835	1	24668	1
836	1	24669	1
837	1	24670	1
838	1	24671	1
839	1	24672	1
840	1	24673	1
841	1	24674	1
842	1	24675	1
843	1	24676	1
844	1	24677	1
845	1	24678	1
846	1	24679	1
847	1	24680	1
848	1	24681	1
849	1	24682	1
850	1	24683	1
851	1	24684	1
852	1	24685	1
853	1	24686	1
854	1	24687	1
855	1	24688	1
856	1	24689	1
857	1	24690	1
858	1	24691	1
859	1	24692	1
860	1	24693	1
861	1	24694	1
862	1	24695	1
863	1	24696	1
864	1	24697	1
865	1	24698	1
866	1	24699	1
867	1	24700	1
868	1	24701	1
869	1	24702	1
870	1	24703	1
871	1	24704	1
872	1	24705	1
873	1	24706	1
874	1	24707	1
875	1	24708	1
876	1	24709	1
877	1	24710	1
878	1	24711	1
879	1	24712	1
880	1	24713	1
881	1	24714	1
882	1	24715	1
883	1	24716	1
884	1	24717	1
885	1	24718	1
886	1	24719	1
887	1	24720	1
888	1	24721	1
889	1	24722	1
890	1	24723	1
891	1	24724	1
892	1	24725	1
893	1	24726	1
894	1	24727	1
895	1	24728	1
896	1	24729	1
897	1	24730	1
898	1	24731	1
899	1	24732	1
900	1	24733	1
901	1	24734	1
902	1	24735	1
903	1	24736	1
904	1	24737	1
905	1	24738	1
906	1	24739	1
907	1	24740	1
908	1	24741	1
909	1	24742	1
910	1	24743	1
911	1	24744	1
912	1	24745	1
913	1	24746	1
914	1	24747	1
915	1	24748	1
916	1	24749	1
917	1	24750	1
918	1	24751	1
919	1	24752	1
920	1	24753	1
921	1	24754	1
922	1	24755	1
923	1	24756	1
924	1	24757	1
925	1	24758	1
926	1	24759	1
927	1	24760	1
928	1	24761	1
929	1	24762	1
930	1	24763	1
931	1	24764	1
932	1	24765	1
933	1	24766	1
934	1	24767	1
935	1	24768	1
936	1	24769	1
937	1	24770	1
938	1	24771	1
939	1	24772	1
940	1	24773	1
941	1	24774	1
942	1	24775	1
943	1	24776	1
944	1	24777	1
945	1	24778	1
946	1	24779	1
947	1	24780	1
948	1	24781	1
949	1	24782	1
950	1	24783	1
951	1	24784	1
952	1	24785	1
953	1	24786	1
954	1	24787	1
955	1	24788	1
956	1	24789	1
957	1	24790	1
958	1	24791	1
959	1	24792	1
960	1	24793	1
961	1	24794	1
962	1	24795	1
963	1	24796	1
964	1	24797	1
965	1	24798	1
966	1	24799	1
967	1	24800	1
968	1	24801	1
969	1	24802	1
970	1	24803	1
971	1	24804	1
972	1	24805	1
973	1	24806	1
974	1	24807	1
975	1	24808	1
976	1	24809	1
977	1	24810	1
978	1	24811	1
979	1	24812	1
980	1	24813	1
981	1	24814	1
982	1	24815	1
983	1	24816	1
984	1	24817	1
985	1	24818	1
986	1	24819	1
987	1	24820	1
988	1	24821	1
989	1	24822	1
990	1	24823	1
991	1	24824	1
992	1	24825	1
993	1	24826	1
994	1	24827	1
995	1	24828	1
996	1	24829	1
997	1	24830	1
998	1	24831	1
999	1	24832	1
1000	1	24833	1
1001	1	24834	1
1002	1	24835	1
1003	1	24836	1
1004	1	24837	1
1005	1	24838	1
1006	1	24839	1
1007	1	24840	1
1008	1	24841	1
1009	1	24842	1
1010	1	24843	1
1011	1	24844	1
1012	1	24845	1
1013	1	24846	1
1014	1	24847	1
1015	1	24848	1
1016	1	24849	1
1017	1	24850	1
1018	1	24851	1
1019	1	24852	1
1020	1	24853	1
1021	1	24854	1
1022	1	24855	1
1023	1	24856	1
1024	1	24857	1
1025	1	24858	1
1026	1	24859	1
1027	1	24860	1
1028	1	24861	1
1029	1	24862	1
1030	1	24863	1
1031	1	24864	1
1032	1	24865	1
1033	1	24866	1
1034	1	24867	1
1035	1	24868	1
1036	1	24869	1
1037	1	24870	1
1038	1	24871	1
1039	1	24872	1
1040	1	24873	1
1041	1	24874	1
1042	1	24875	1
1043	1	24876	1
1044	1	24877	1
1045	1	24878	1
1046	1	24879	1
1047	1	24880	1
1048	1	24881	1
1049	1	24882	1
1050	1	24883	1
1051	1	24884	1
1052	1	24885	1
1053	1	24886	1
1054	1	24887	1
1055	1	24888	1
1056	1	24889	1
1057	1	24890	1
1058	1	24891	1
1059	1	24892	1
1060	1	24893	1
1061	1	24894	1
1062	1	24895	1
1063	1	24896	1
1064	1	24897	1
1065	1	24898	1
1066	1	24899	1
1067	1	24900	1
1068	1	24901	1
1069	1	24902	1
1070	1	24903	1
1071	1	24904	1
1072	1	24905	1
1073	1	24906	1
1074	1	24907	1
1075	1	24908	1
1076	1	24909	1
1077	1	24910	1
1078	1	24911	1
1079	1	24912	1
1080	1	24913	1
1081	1	24914	1
1082	1	24915	1
1083	1	24916	1
1084	1	24917	1
1085	1	24918	1
1086	1	24919	1
1087	1	24920	1
1088	1	24921	1
1089	1	24922	1
1090	1	24923	1
1091	1	24924	1
1092	1	24925	1
1093	1	24926	1
1094	1	24927	1
1095	1	24928	1
1096	1	24929	1
1097	1	24930	1
1098	1	24931	1
1099	1	24932	1
1100	1	24933	1
1101	1	24934	1
1102	1	24935	1
1103	1	24936	1
1104	1	24937	1
1105	1	24938	1
1106	1	24939	1
1107	1	24940	1
1108	1	24941	0


Note that it takes 1100 trips to the index layer to generate the 25k revision
history, versus only 50 when we fast-loop on a given index node.

Note also that from 300=>1100 we are iterating over a single revision. This is
because bzr has a *very* long single-parent ancestry because of Martin's
initial work. However a project like OOo is going to have *much* more of this.

We do get to 20k revisions in 107 round trips, but it only takes 15 round trips
to do the same with the get_ancestry version.

get_parent_map peaks at a width of 360 revisions per lookup
get_ancestry peaks at 529 search_keys, but peaks at finding 2287 keys in a
single pass, and only has 1 pass where it failed to find more than 1 parent,
and only 4 passes where it found fewer than 10.


Notes from CombinedGraphIndex.get_ancestry

you can see that in a real-world repository it takes 1 pass across all indexes
to really 'get primed' and start yielding results. However once that has
happened, we end up getting a lot of results quickly from the 'deep history'
index, and then we spin around a few times to finally fill in the rest of the
indexes.
One possibility would be to reprioritise the various indexes, so that if an
index has recently had good success returning information, we move it earlier
in the list. Or conversely, if we don't get any information, we move the index
to the end. I don't have anything concrete, but the idea is to avoid polling
*all* of the indexes on every pass, but instead to have a tighter loop around
ones that we think are going to give us good info.

gen	idx	sub	n_keys	n_pmap	n_miss
   1			   1	    0	    0
    	 0		   1	    0	    0
    	  	 1	   0	    0	    1
    	 1		   1	    0	    0
    	  	 1	   0	    0	    1
    	 2		   1	    0	    0
    	  	 1	   0	    0	    1
    	 3		   1	    0	    0
    	  	 1	   0	    0	    1
    	 4		   1	    0	    0
    	  	 1	   0	    0	    1
    	 5		   1	    0	    0
    	  	 1	   0	    0	    1
    	 6		   1	    0	    0
    	  	 1	   0	    0	    1
    	 7		   1	    0	    0
    	  	 1	   0	    0	    1
    	 8		   1	    0	    0
    	  	 1	   0	    4	    1
    	 9		   1	    4	    0
    	  	 1	   0	    4	    1
    	10		   1	    4	    0
    	  	 1	   0	    4	    1
    	11		   1	    4	    0
    	  	 1	   0	    4	    1
    	12		   1	    4	    0
    	  	 1	   0	    4	    1
    	13		   1	    4	    0
    	  	 1	   0	    4	    1
    	14		   1	    4	    0
    	  	 1	   0	    4	    1
    	15		   1	    4	    0
    	  	 1	   0	    4	    1
    	16		   1	    4	    0
    	  	 1	   0	    4	    1
    	17		   1	    4	    0
    	  	 1	   0	    4	    1
    	18		   1	    4	    0
    	  	 1	   0	    4	    1
    	19		   1	    4	    0
    	  	 1	   0	    4	    1
gen	idx	sub	n_keys	n_pmap	n_miss
   2			   1	    4	    0
    	 0		   1	    4	    0
    	  	 1	   0	    4	    1
    	 1		   1	    4	    0
    	  	 1	   0	    4	    1
    	 2		   1	    4	    0
    	  	 1	   0	    4	    1
    	 3		   1	    4	    0
    	  	 1	   0	   45	    7
    	 4		   7	   45	    0
    	  	 1	   0	   45	    7
    	 5		   7	   45	    0
    	  	 1	   0	   45	    7
    	 6		   7	   45	    0
    	  	 1	   0	   45	    7
    	 7		   7	   45	    0
    	  	 1	   0	   45	    7
    	 8		   7	   45	    0
    	  	 1	   0	   45	    7
    	 9		   7	   45	    0
    	  	 1	   0	   49	    7
    	10		   7	   49	    0
    	  	 1	   0	   49	    7
    	11		   7	   49	    0
    	  	 1	   0	   49	    7
    	12		   7	   49	    0
    	  	 1	   0	   49	    7
    	13		   7	   49	    0
    	  	 1	   0	   49	    7
    	14		   7	   49	    0
    	  	 1	   0	   49	    7
    	15		   7	   49	    0
    	  	 1	   0	   54	    7
    	16		   7	   54	    0
    	  	 1	  63	  115	    5
    	  	 2	 151	  443	    5
    	  	 3	 143	 1026	    5
    	  	 4	 113	 1577	    5
    	  	 5	 291	 2215	    5
    	  	 6	 574	 3707	    5
    	  	 7	 569	 6047	    5
    	  	 8	 540	 8814	    5
    	  	 9	 476	11157	    5
    	  	10	 352	13153	    5
    	  	11	 411	14748	    5
    	  	12	 359	16704	    5
    	  	13	 289	18287	    5
    	  	14	 136	19853	    5
    	  	15	  76	20655	    5
    	  	16	  63	21249	    5
    	  	17	  37	21748	    5
    	  	18	  39	22017	    5
    	  	19	  36	22322	    5
    	  	20	  22	22650	    5
    	  	21	  14	23060	    5
    	  	22	  17	23280	    5
    	  	23	  13	23478	    7
    	  	24	   8	23683	    7
    	  	25	   6	23867	    7
    	  	26	   7	24052	    7
    	  	27	  19	24191	    7
    	  	28	  15	24275	    7
    	  	29	  19	24476	    7
    	  	30	  13	24726	    7
    	  	31	  14	24826	    7
    	  	32	  10	24874	    7
    	  	33	   6	24953	    7
    	  	34	   5	24977	    7
    	  	35	   5	25035	    7
    	  	36	   4	25076	    7
    	  	37	   4	25129	    7
    	  	38	   3	25145	    7
    	  	39	   2	25158	    7
    	  	40	   2	25163	    7
    	  	41	   2	25166	    7
    	  	42	   2	25188	    7
    	  	43	   2	25205	    7
    	  	44	   1	25241	    7
    	  	45	   6	25248	    7
    	  	46	   4	25272	    7
    	  	47	   1	25305	    7
    	  	48	   0	25308	    7
    	17		   7	25308	    0
    	  	 1	   0	25348	    6
    	18		   6	25348	    0
    	  	 1	   7	25415	    9
    	  	 2	   2	25441	   11
    	  	 3	   0	25441	   13
    	19		  13	25441	    0
    	  	 1	   0	25441	   13
gen	idx	sub	n_keys	n_pmap	n_miss
   3			  13	25441	    0
    	 0		  13	25441	    0
    	  	 1	   0	25441	   13
    	 1		  13	25441	    0
    	  	 1	   0	25441	   13
    	 2		  13	25441	    0
    	  	 1	   0	25442	   14
    	 3		  14	25442	    0
    	  	 1	   0	25442	   14
    	 4		  14	25442	    0
    	  	 1	   0	25442	   14
    	 5		  14	25442	    0
    	  	 1	   0	25442	   14
    	 6		  14	25442	    0
    	  	 1	   1	25453	   16
    	  	 2	   0	25453	   17
    	 7		  17	25453	    0
    	  	 1	   0	25453	   17
    	 8		  17	25453	    0
    	  	 1	   0	25453	   17
    	 9		  17	25453	    0
    	  	 1	   0	25459	   16
    	10		  16	25459	    0
    	  	 1	   0	25459	   16
    	11		  16	25459	    0
    	  	 1	   0	25459	   16
    	12		  16	25459	    0
    	  	 1	   0	25459	   16
    	13		  16	25459	    0
    	  	 1	   0	25459	   16
    	14		  16	25459	    0
    	  	 1	  33	25531	   12
    	  	 2	  14	25677	   19
    	  	 3	   6	25717	   25
    	  	 4	   1	25728	   26
    	  	 5	   0	25729	   26
    	15		  26	25729	    0
    	  	 1	   0	25748	   24
    	16		  24	25748	    0
    	  	 1	  72	25870	    6
    	  	 2	  30	26173	    6
    	  	 3	   6	26321	    6
    	  	 4	   3	26346	    6
    	  	 5	   0	26355	    6
    	17		   6	26355	    0
    	  	 1	   0	26362	    6
    	18		   6	26362	    0
    	  	 1	   4	26376	    4
    	  	 2	   0	26391	    5
    	19		   5	26391	    0
    	  	 1	   0	26391	    5
gen	idx	sub	n_keys	n_pmap	n_miss
   4			   3	26391	    2
    	 0		   3	26391	    0
    	  	 1	   0	26391	    3
    	 1		   3	26391	    0
    	  	 1	   0	26391	    3
    	 2		   3	26391	    0
    	  	 1	   0	26391	    3
    	 3		   3	26391	    0
    	  	 1	   0	26391	    3
    	 4		   3	26391	    0
    	  	 1	   0	26391	    3
    	 5		   3	26391	    0
    	  	 1	   0	26391	    3
    	 6		   3	26391	    0
    	  	 1	   0	26391	    3
    	 7		   3	26391	    0
    	  	 1	   0	26391	    3
    	 8		   3	26391	    0
    	  	 1	   0	26391	    3
    	 9		   3	26391	    0
    	  	 1	   0	26391	    3
    	10		   3	26391	    0
    	  	 1	   0	26391	    3
    	11		   3	26391	    0
    	  	 1	   0	26391	    3
    	12		   3	26391	    0
    	  	 1	   0	26391	    3
    	13		   3	26391	    0
    	  	 1	   0	26391	    3
    	14		   3	26391	    0
    	  	 1	   1	26394	    1
    	  	 2	   0	26401	    1
    	15		   1	26401	    0
    	  	 1	   0	26401	    1
    	16		   1	26401	    0
    	  	 1	   0	26401	    1
    	17		   1	26401	    0
    	  	 1	   0	26401	    1
    	18		   1	26401	    0
    	  	 1	   0	26402	    0

Performance notes so far:
  time ancestry_from_get_parent_map()
  1530ms  (down from 567ms when there was a single real index)
  time ancestry_from_get_ancestry()
  309ms   (down from 245ms when there was a single real index)

So even without optimizing that inner loop much, we are at about 20%
time.(5:1 faster). (also note that being done on different repos, the
real-world test has another ~1500 revisions in the ancestry.)

This also shows how much better things scale when we have lots of indexes. It
allows us to not try to search across all the indexes all the time, because we
follow whatever parent threads a given index can give us.

The overhead of 20 indexes was only 245 => 309 or 1.26:1, rather than 3:1 for
the get_parent_map implementation.

Also of interest is that in the single-index case the improvement was only
about 2x, so this seems quite significant overall.


For OOo with a single index:
    time ancestry_from_get_parent_map
    32.998s

    time ancestry_from_get_ancestry
    10.462s

This is 3.15:1 faster, even without the benefits of pyrex or a real-world case
when we have more than one pack file.