{"thread":{"id":"17588","subject":"[JGIT] Questions about binary right shifting","startedAt":"2009-02-05T14:37:37Z","lastAt":"2009-02-05T20:32:01Z","messageCount":3,"participants":["Yann Simon","Shawn O. Pearce","Robin Rosenberg"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"103337","messageId":"498AF9B1.1060200@gmail.com","threadId":"17588","inReplyTo":null,"subject":"[JGIT] Questions about binary right shifting","fromName":"Yann Simon","fromEmail":"yann.simon.fr@gmail.com","sentAt":"2009-02-05T14:37:37Z","receivedAt":"2009-02-05T14:37:37Z","isPatch":false,"sender":{"key":"yann.simon.fr@gmail.com","avatar":"https://gravatar.com/avatar/2d926895d27ac988c5c8e591887e5a6a4c7036390403c74fce92519119b887a0?d=mp&s=160"},"body":"Hi,\n\nI can see in the code that the signed right shifting is used.\nCould it be a problem? Or do we manipulate only positive numbers?\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\nindex 8eb4022..d70eca0 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n@@ -577,7 +577,7 @@ int findEntry(final byte[] p, final int pLen) {\n \t\tint low = 0;\n \t\tint high = entryCnt;\n \t\tdo {\n-\t\t\tint mid = (low + high) >> 1;\n+\t\t\tint mid = (low + high) >>> 1;\n \t\t\tfinal int cmp = cmp(p, pLen, sortedEntries[mid]);\n \t\t\tif (cmp < 0)\n \t\t\t\thigh = mid;\n\nAnd could we used right shifting to optimize a division per 2?\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java\nindex 0ecd04d..ff9e666 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java\n@@ -136,7 +136,7 @@ private static final int binarySearch(final TreeEntry[] entries,\n \t\tint high = entries.length;\n \t\tint low = 0;\n \t\tdo {\n-\t\t\tfinal int mid = (low + high) / 2;\n+\t\t\tfinal int mid = (low + high) >>> 1;\n \t\t\tfinal int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,\n \t\t\t\t\tnameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);\n \t\t\tif (cmp < 0)\n\nYann\n"},{"id":"103340","messageId":"20090205152108.GE26880@spearce.org","threadId":"17588","inReplyTo":"498AF9B1.1060200@gmail.com","subject":"Re: [JGIT] Questions about binary right shifting","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-02-05T15:21:08Z","receivedAt":"2009-02-05T15:21:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Yann Simon <yann.simon.fr@gmail.com> wrote:\n> I can see in the code that the signed right shifting is used.\n> Could it be a problem? Or do we manipulate only positive numbers?\n\nHeh.  We shouldn't ever be dealing with a case where there are more\nthan 1 billion files in the index, and thus we should never see\nthe expression \"low + high\" wrap negative, and then try to divide\nby 2 here.\n\nBinary search on a 1 billion file index would hurt, badly.  I'm not\nsure what project even has 1 billion source files to checkout\non disk.  Isn't that easily a 4 TB filesystem just for the ext2\ninodes of the working tree files?  :-)\n\nOh, and we can't even have an index with 1 billion entries in it\nanyway.  DirCache.readFrom allocates a byte[] of entryCnt * 62.\nSo our largest number of files permitted is 34,636,833, due to\nthe limit on byte[] maxing out at 2 GB.  Thus high below cannot\never be larger than 34 million, and we can't wrap.\n\nThis is also true in the Tree class, where we have the entire tree\ndata stream in a byte[].  Each entry needs at least 23 bytes, but\nmore if you include some sort of unique file name.  That really puts\na limit on the number of unique names to the point that we cannot\nhave entries.length so large that the binary search would overflow.\n\nAnyway, if you tie this up into a patch with a message I'll apply,\nbut I don't care enough to write the message myself given how\nunlikely this is.  We'd have to overhaul other code anyway before\nwe start to run into problems with these search functions.\n\n\n> diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n> index 8eb4022..d70eca0 100644\n> --- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n> +++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n> @@ -577,7 +577,7 @@ int findEntry(final byte[] p, final int pLen) {\n>  \t\tint low = 0;\n>  \t\tint high = entryCnt;\n>  \t\tdo {\n> -\t\t\tint mid = (low + high) >> 1;\n> +\t\t\tint mid = (low + high) >>> 1;\n>  \t\t\tfinal int cmp = cmp(p, pLen, sortedEntries[mid]);\n>  \t\t\tif (cmp < 0)\n>  \t\t\t\thigh = mid;\n> \n> And could we used right shifting to optimize a division per 2?\n> \n> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java\n> index 0ecd04d..ff9e666 100644\n> --- a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java\n> +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java\n> @@ -136,7 +136,7 @@ private static final int binarySearch(final TreeEntry[] entries,\n>  \t\tint high = entries.length;\n>  \t\tint low = 0;\n>  \t\tdo {\n> -\t\t\tfinal int mid = (low + high) / 2;\n> +\t\t\tfinal int mid = (low + high) >>> 1;\n>  \t\t\tfinal int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,\n>  \t\t\t\t\tnameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);\n>  \t\t\tif (cmp < 0)\n> \n> Yann\n\n-- \nShawn.\n"},{"id":"103381","messageId":"200902052132.01797.robin.rosenberg.lists@dewire.com","threadId":"17588","inReplyTo":"20090205152108.GE26880@spearce.org","subject":"Re: [JGIT] Questions about binary right shifting","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2009-02-05T20:32:01Z","receivedAt":"2009-02-05T20:32:01Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"torsdag 05 februari 2009 16:21:08 skrev Shawn O. Pearce:\n> Yann Simon <yann.simon.fr@gmail.com> wrote:\n> > I can see in the code that the signed right shifting is used.\n> > Could it be a problem? Or do we manipulate only positive numbers?\n> \n> Heh.  We shouldn't ever be dealing with a case where there are more\n> than 1 billion files in the index, and thus we should never see\n> the expression \"low + high\" wrap negative, and then try to divide\n> by 2 here.\n> \n> Binary search on a 1 billion file index would hurt, badly.  I'm not\nRoughly three times the search time in the linux kernel repo. Not\nthat bad.\n\n> sure what project even has 1 billion source files to checkout\n> on disk.  Isn't that easily a 4 TB filesystem just for the ext2\nNot even KDE or Eclipse.\n> inodes of the working tree files?  :-)\n\n> Oh, and we can't even have an index with 1 billion entries in it\n> anyway.  DirCache.readFrom allocates a byte[] of entryCnt * 62.\n> So our largest number of files permitted is 34,636,833, due to\n> the limit on byte[] maxing out at 2 GB.  Thus high below cannot\n> ever be larger than 34 million, and we can't wrap.\nAssuming the whole index is in memory. But I guess we can discard\nit as most competing systems choke on a lot lot less and for very\nlarge indexes we get other problems with size. Binary search isn't\none of them. Having i packed index is probably the biggest issue\nsince it has to be completely rewritten when we add or remove\nfiles. But, OK, we won't solve this unless we have a case. I think\nour current challenge is dealing with 100k files real smoothly.\n\nPatching this to make findbugs shut up is ok with me.\n\n-- robin\n"}]}