Re: [jgit-dev] The benefit of BlockObjQueue

[Shawn Pearce <spearce@xxxxxxxxxxx>]

On Fri, Mar 18, 2016 at 11:01 AM, Dong Xie <xied75@xxxxxxxxx> wrote:
> New to the source and mail list. I’m having difficulty to understand the
> design of BlockObjQueue, it seems just a Block size 256 of RevObject, with a
> link to next block. What is the benefit of using this instead of plain
> Queue<T>? Is that memory or perf?

Both. Queue<T> requires a downcast to get to our RevObject or
RevCommit type. BlockObjQueue and BlockRevQueue don't have to execute
downcast instructions in the critical path.

We also are able to reduce memory consumption over a LinkedList type
of approach as we amortize the memory of the next pointers over 256
entries instead of 1 entry.

Also by using smaller fixed size blocks instead of a single very large
array we eliminate costs related to growing the array by copying
entries from the old smaller array into the new larger array, and we
reduce stress on the Java GC trying to find larger and larger
allocations in a fragmented heap. Instead we keep our old allocations
alive and just ask for many smaller allocations (~1-2 KiB depending on
32 bit or 64 bit references). These are usually satisfied very rapidly
by the Java memory allocator.

At the time we wrote these classes Java 5 was the current release. I
don't think it had any data structure in the standard library that
satisfied these points. I haven't looked at modern Java 8 to see if
there are better types, or if the JIT has advanced enough to be able
to completely erase the overhead associated with downcasts from a
generic Queue<T>.