On Tuesday 08 September 2009, Junio C Hamano wrote: > Johannes Schindelin <Johannes.Schindelin@xxxxxx> writes: > > On Tue, 8 Sep 2009, Johan Herland wrote: > >> Algorithm / Notes tree git log -n10 (x100) git log --all > >> ------------------------------------------------------------ > >> next / no-notes 4.77s 63.84s > >> > >> before / no-notes 4.78s 63.90s > >> before / no-fanout 56.85s 65.69s > >> > >> 16tree / no-notes 4.77s 64.18s > >> 16tree / no-fanout 30.35s 65.39s > >> 16tree / 2_38 5.57s 65.42s > >> 16tree / 2_2_36 5.19s 65.76s > >> > >> flexible / no-notes 4.78s 63.91s > >> flexible / no-fanout 30.34s 65.57s > >> flexible / 2_38 5.57s 65.46s > >> flexible / 2_2_36 5.18s 65.72s > >> flexible / ym 5.13s 65.66s > >> flexible / ym_2_38 5.08s 65.63s > >> flexible / ymd 5.30s 65.45s > >> flexible / ymd_2_38 5.29s 65.90s > >> flexible / y_m 5.11s 65.72s > >> flexible / y_m_2_38 5.08s 65.67s > >> flexible / y_m_d 5.06s 65.50s > >> flexible / y_m_d_2_38 5.07s 65.79s > > > > I can see that some people may think that date-based fan-out is the > > cat's ass, > > Actually, my knee-jerk reaction was that 4.77 (next) vs 5.57 (16tree with > 2_38) is already a good enough performance/simplicity tradeoff, and 5.57 > vs 5.08 (16tree with ym_2_38) probably does not justify the risk of worst > case behaviour that can come from possible mismatch between the access > pattern and the date-optimized tree layout. Yes, 16tree / 2_38 looks like a reasonable tradeoff when you look at the absolute numbers, but it's also interesting to highlight the actual cost of doing the notes lookup. In that case, we see that 16tree / 2_38 costs 0.80s, whereas flexible / ym_2_38 only costs 0.31s, i.e. less than half the cost of the former... > But that only argues against supporting _only_ date-optimized layout. > > Support of "flexible layout" is not that flexible as its name suggests; > one single note tree needs to have a uniform fanout strategy. Actually, the uniform strategy is only required at each separate level. You are free to vary the strategy within independent subtrees. I.e. in the case where you have 1 note from 2007, and 1000 notes from 2008, you are free to use a mix of date-based and SHA1-based structures, like this: y2007/1234567... y2008/m01/d01/2345678... y2008/m01/d01/3456789... y2008/m01/d02/45/67890... y2008/m01/d02/56/78901... y2008/m01/d02/67/89012... ... > > - I find the restriction to commits rather limiting. > > Yeah, we would not want to be surprised to find many people want to > annotate non-commits with this mechanism. We could arbitrarily set the "commit date" for non-commit objects to the epoch, so that they can still be represented in a date-based fanout. (Of course, the notes code should be smart enough to choose a more optimal fanout if the number of non-commit notes is significant). > > - most of the performance difference between the date-based and the > > SHA-1 based fan-out looks to me as if the issue was the top-level tree. > > Basically, this tree has to be read _every_ time _anybody_ wants to > > read a note. > > A comparison between 'next' and another algorithm that opens the > top-level notes tree object and returns "I did not find any note" > without doing anything else would reveal that cost. But when you are > doing "log -n10" (or "log --all"), you would read the notes top-level > tree once, and it is likely to be cached in the obj_hash[] (or in > delta_base cache) already for the remaining invocations, even if notes > mechanism does not do its own cache, which I think it does, no? Yes it does, since Dscho's original hash_map based implementation, in fact. ...Johan -- Johan Herland, <johan@xxxxxxxxxxx> www.herland.net -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html