torsdag 05 februari 2009 16:21:08 skrev Shawn O. Pearce: > Yann Simon <yann.simon.fr@xxxxxxxxx> wrote: > > I can see in the code that the signed right shifting is used. > > Could it be a problem? Or do we manipulate only positive numbers? > > Heh. We shouldn't ever be dealing with a case where there are more > than 1 billion files in the index, and thus we should never see > the expression "low + high" wrap negative, and then try to divide > by 2 here. > > Binary search on a 1 billion file index would hurt, badly. I'm not Roughly three times the search time in the linux kernel repo. Not that bad. > sure what project even has 1 billion source files to checkout > on disk. Isn't that easily a 4 TB filesystem just for the ext2 Not even KDE or Eclipse. > inodes of the working tree files? :-) > Oh, and we can't even have an index with 1 billion entries in it > anyway. DirCache.readFrom allocates a byte[] of entryCnt * 62. > So our largest number of files permitted is 34,636,833, due to > the limit on byte[] maxing out at 2 GB. Thus high below cannot > ever be larger than 34 million, and we can't wrap. Assuming the whole index is in memory. But I guess we can discard it as most competing systems choke on a lot lot less and for very large indexes we get other problems with size. Binary search isn't one of them. Having i packed index is probably the biggest issue since it has to be completely rewritten when we add or remove files. But, OK, we won't solve this unless we have a case. I think our current challenge is dealing with 100k files real smoothly. Patching this to make findbugs shut up is ok with me. -- robin -- 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
