From: Marek Zawirski <marek.zawirski@gmail.com>
Date: Mon, 16 Jun 2008 16:27:12 GMT
Subject: Re: [EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex
Message-ID: <48569460.4000401@gmail.com>
In-Reply-To: <20080616040635.GU11793@spearce.org>

Shawn O. Pearce wrote:
> Marek Zawirski <marek.zawirski@gmail.com> wrote:
>> Let us quickly find ObjectId or next object for specified offset in a
>> pack, in O(log n) time.
> ...
>> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java
> ...
>> +	/**
>> +	 * Object ids corresponding to {@link #offsets32} and {@link #offsets64}.
>> +	 */
>> +	private final int names[];
> 
> This could be smaller if it was an array of indexes into the index,
> rather than the ObjectId itself.  Thus we need only 1 int per object
> and not 5 ints per object.
> 
> But I see why you are doing it; PackIndex.MutableEntry exposes the
> ObjectId and not the nth position of the object within the index.

Hmm, that's smart.
I can change array of names to second level indices, but I think that in 
such a case PackReverseIndex should be an inner class of PackIndex and 
some refactor/additional assumptions at PackIndex may be needed. What do 
you think?

>> +	PackReverseIndex(final PackIndex index) {
>> +		final long count = index.getObjectCount();
>> +		if (count > Integer.MAX_VALUE)
>> +			throw new IllegalArgumentException(
>> +					"Huge indexes (> 2^31 entries) are not supported by jgit, yet");
> 
> For what its worth, this limit is actually:
> 
> 	Integer.MAX_VALUE / Constants.OBJECT_ID_LENGTH / 4
> 
> as you store the entire ObjectId data for the index in a single int[]
> array called names.  So you'll get an ArrayIndexOutOfBoundsException
> or maybe OutOfMemoryError when you try to build names later on, and
> never really hit this case here.
>> +	ObjectId findObject(final long offset) {
>> +		if (offset <= Integer.MAX_VALUE) {
>> +			final int i32 = Arrays.binarySearch(offsets32, (int) offset);
>> +			if (i32 < 0)
>> +				return null;
>> +			final int iNames = i32 * Constants.OBJECT_ID_LENGTH / 4;
> 
> This probably should be:
> 
> 	final int iNames = i32 * (Constants.OBJECT_ID_LENGTH / 4);
> 
> as then we don't overflow the precision of int when i32 is large.
> 
>> +			return ObjectId.fromRaw(names, iNames);
>> +		} else {
>> +			final int i64 = Arrays.binarySearch(offsets64, offset);
>> +			if (i64 < 0)
>> +				return null;
>> +			final int iNames = (i64 + offsets32.length)
>> +					* Constants.OBJECT_ID_LENGTH / 4;
> 
> Again, watch out for overflow.

Right, my faults.

-- 
Marek Zawirski [zawir]
marek.zawirski@gmail.com