JDK-8181704 : (bf) Support large scale scatter/gather of byte buffers
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.nio
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2017-06-06
  • Updated: 2018-08-28
Related Reports
Relates :  
JDK-8180628 - (bf) Retrofit direct buffer support for size beyond gigabyte scales
Description
When working directly with large-scale chunks of data, it is likely that scatter/gather data structures are important.  There are two reasons.  First, large-scale data is likely to profit from copy reduction, where the data is mapped from a file or other OS resource, but not copied into the Java heap.  Second, the Java heap is likely to benefit from a size limit on data (currently 2Gb is the built-in limit).  In both cases, it is sometimes desirable to have a data structure which resembles a byte-buffer, but is internally redirected to two or more contiguous segments of memory.

A third use case is the logical limit of the zero-copy scenario, where a large region of virtual memory hardware is comprised under a single object.  In that case, the virtual addresses of the region are likely to appear as direct indexes into the composite object, which may refer internally to a patchwork of address mappings.

There may be a Java API that can efficiently cover these use cases.  Likely requirements are:

- byte-indexed data structure
- supports byte-buffer style views onto small-scale slices
- supports looping over slices at all scales (stream-of-segment loops)
- no intrinsic limit on index size, up to 64 bits (for now)
- allows existing byte buffers to be assembled as groups
- maybe allows arbitrary ranges of long values as indexes (not zero based)
- supports paged (array-let or page table) style constant-time indexing
- supports irregular (binary search or skip-list) style composition with log-time indexing

(Note:  Irregularly blocked large arrays can provide an efficient "bucket" for
collecting the output of large parallel streams in cases where the stream
output cannot be sized in advance.  The simpler regularly blocked arrays are
a way to be friendly to the garbage collector and/or storage manager.)

See comments for a sketch.
Comments
Sketch of possible API, in the form of an interface: package java.nio; interface GatheredByteBuffer { public List<ByteBuffer> components(); public IndexMap indexMap(); /** A contiguous segment of data in this array of buffers. */ public class Segment { /** External starting index of this segment within the overall index space. */ public final long componentStart; /** Number of indexes in this segment. */ public final long length; /** Component containing this segment. */ public final ByteBuffer component; /** Internal Start offsets within the component. */ public final long componentLocation; /** Pointer to the enclosing sequence of buffers. */ GatheredByteBuffer outer() { return GatheredByteBuffer.this; } /** Derived byte buffer slice for this segment. */ ByteBuffer slice() { long pos = componentLocation; long lim = pos + length; assert(pos <= lim); if (HAVE_LONG_SLICES) return component.slice(pos, lim); assert(pos == (int)pos && len == (int)len); return component.slice((int)pos, (int)lim); } } /** Stream over a range of indexes. * Each stream element reports one component which overlaps with the desired slice. * Usually the stream will perform a sub-loop over each segment, * achieving the effect of a strip-mined loop. */ Stream<Segment> sliceSegments(long begin, long end); // should have a default method /** Copy out a run of bytes starting at the given index. */ void copyOutBytes(long start, int len, byte[] array, int offset); // If a GBB is going to model a large segment of virtual memory, // and if it is going to have a sunk cost for address translation, // it seems reasonable *not* to dictate a starting index of zero. // Therefore, the following methods supply not only a length but // also a minimum and maximum index. Again, in order to support // extreme index values (such as Long.MAX_VALUE), all end indexes // are *inclusive*. /** Minimum index stored in this array of buffers. */ default public long indexStart() { return indexMap().indexStart(); } /** Maximum index stored in this array of buffers. */ default public long indexEnd() { return indexMap().indexEnd(); } /** Total number of indexes stored in this array of buffers. */ default public long indexLength() { return indexMap().indexLength(); } /** Data and algorithm for mapping a long index to a selected * component and an index within that component. * If the component has a 32-int indexing limit, then the * mapped long index must derive a valid positive 32-bit index, * after mapping, (optional) local ofsetting, and truncation. */ interface IndexMap { /** How many components? */ int componentCount(); /** What is the index of the first component? */ default int componentStart() { return 0; } /** Lowest index mapped to the selected component. */ long componentStart(int cn); /** Number of contiguous indexes mapped to the selected component. */ long componentLength(int cn); /** Minimum index assigned by this map, else 0 if no indexes are assigned. */ default long indexStart() { int cn = componentCount(); return cn == 0 ? 0 : componentStart(0); } /** The maximum index assigned by this map, else -1 if no indexes are assigned. */ default long indexEnd() { int cn = componentCount(); return cn == 0 ? -1 : componentEnd(cn-1); } /** The total number of indexes in this map. */ default long indexLength() { int cn = componentCount(); return cn == 0 ? 0 : componentEnd(cn-1)+1-componentStart(0); } /** The highest index mapped to the selected component. */ default long componentEnd(int cn) { return componentStart(cn) + componentLength(cn) - 1; }; /** Number of elements within the selected component which are skipped by this map. */ default long componentInternalOffset(int cn) { return 0; } /** Decide which component contains the desired index, else return -1 if none does. * A positive result is always at least componentStart(). */ default int selectComponent(long index) { // binary search; implementation can improve this, esp. w/ fixed-size pages int lo = componentStart(), hi = lo + componentCount() - 1; if (hi < lo) return -1; // subtract 1 to avoid overflow on Long.MAX_VALUE long min = componentStart(lo), max = componentLimit(hi) - 1; for (;;) { if (index < min || index > max) return -1; if (lo == hi) return lo; int next = lo + (hi - lo + 1)/2; long mid = componentStart(next); if (index < mid) { hi = next; max = mid-1; } else { lo = next; min = mid; } } } /** After deciding which component is selected by the given index, * decide the internal index within that component to begin accessing. */ default long selectComponentLocation(int cn, long index) { assert(cn == selectComponent(index)); long start = componentStart(cn); assert(index >= start && index <= componentEnd(cn)-1); return index - start + componentInternalOffset(cn); } /** After deciding which component is selected by the given index, * decide the maximum number of elements that can be accessed within * that component before the index map requires advance to the next. * This method is useful for strip-mining loops. * The segment stream {@code sliceSegments} uses this method to * assign a length to each segment. */ default long selectMaxLength(int cn, long index) { return componentLength(cn) - (index - componentStart(cn)); } /** Slice a sub-range of the map, from start to end inclusive. * Components that do not overlap with the slice will be dropped. * Trailing components are dropped by reducing componentCount(). * Leading components are dropped by increasing componentStart(). * If the start index does not coincide with the start of a component, * the leading component of the sliced will have an adjusted internal offset. */ IndexMap slice(long start, long end); // default method should return a standard Impl wrapper /** Create a new map over the same components in the same sequence, * with the same number of indexes, but with the given starting index. */ IndexMap withStart(long start); // default method should return a standard Impl wrapper /** Create a new map over the same components in the same sequence, * with the same number of indexes, but with the given ending index. */ default IndexMap withEnd(long end) { return withStart(end - indexLength()); } } }
06-06-2017