Class Packed64

  • All Implemented Interfaces:
    Accountable

    class Packed64
    extends PackedInts.MutableImpl
    Space optimized random access capable array of values with a fixed number of bits/value. Values are packed contiguously.

    The implementation strives to perform as fast as possible under the constraint of contiguous bits, by avoiding expensive operations. This comes at the cost of code clarity.

    Technical details: This implementation is a refinement of a non-branching version. The non-branching get and set methods meant that 2 or 4 atomics in the underlying array were always accessed, even for the cases where only 1 or 2 were needed. Even with caching, this had a detrimental effect on performance. Related to this issue, the old implementation used lookup tables for shifts and masks, which also proved to be a bit slower than calculating the shifts and masks on the fly. See https://issues.apache.org/jira/browse/LUCENE-4062 for details.

    • Constructor Summary

      Constructors 
      Constructor Description
      Packed64​(int valueCount, int bitsPerValue)
      Creates an array with the internal structures adjusted for the given limits and initialized to 0.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Sets all values to 0.
      void fill​(int fromIndex, int toIndex, long val)
      Fill the mutable from fromIndex (inclusive) to toIndex (exclusive) with val.
      private static int gcd​(int a, int b)  
      long get​(int index)
      Get the long at the given index.
      int get​(int index, long[] arr, int off, int len)
      Bulk get: read at least one and at most len longs starting from index into arr[off:off+len] and return the actual number of values that have been read.
      long ramBytesUsed()
      Return the memory usage of this object in bytes.
      void set​(int index, long value)
      Set the value at the given index in the array.
      int set​(int index, long[] arr, int off, int len)
      Bulk set: set at least one and at most len longs starting at off in arr into this mutable, starting at index.
      java.lang.String toString()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • blocks

        private final long[] blocks
        Values are stores contiguously in the blocks array.
      • maskRight

        private final long maskRight
        A right-aligned mask of width BitsPerValue used by get(int).
      • bpvMinusBlockSize

        private final int bpvMinusBlockSize
        Optimization: Saves one lookup in get(int).
    • Constructor Detail

      • Packed64

        public Packed64​(int valueCount,
                        int bitsPerValue)
        Creates an array with the internal structures adjusted for the given limits and initialized to 0.
        Parameters:
        valueCount - the number of elements.
        bitsPerValue - the number of bits available for any given value.
    • Method Detail

      • get

        public long get​(int index)
        Description copied from class: PackedInts.Reader
        Get the long at the given index. Behavior is undefined for out-of-range indices.
        Specified by:
        get in class PackedInts.Reader
        Parameters:
        index - the position of the value.
        Returns:
        the value at the given index.
      • get

        public int get​(int index,
                       long[] arr,
                       int off,
                       int len)
        Description copied from class: PackedInts.Reader
        Bulk get: read at least one and at most len longs starting from index into arr[off:off+len] and return the actual number of values that have been read.
        Overrides:
        get in class PackedInts.Reader
      • set

        public void set​(int index,
                        long value)
        Description copied from class: PackedInts.Mutable
        Set the value at the given index in the array.
        Specified by:
        set in class PackedInts.Mutable
        Parameters:
        index - where the value should be positioned.
        value - a value conforming to the constraints set by the array.
      • set

        public int set​(int index,
                       long[] arr,
                       int off,
                       int len)
        Description copied from class: PackedInts.Mutable
        Bulk set: set at least one and at most len longs starting at off in arr into this mutable, starting at index. Returns the actual number of values that have been set.
        Overrides:
        set in class PackedInts.Mutable
      • ramBytesUsed

        public long ramBytesUsed()
        Description copied from interface: Accountable
        Return the memory usage of this object in bytes. Negative values are illegal.
      • fill

        public void fill​(int fromIndex,
                         int toIndex,
                         long val)
        Description copied from class: PackedInts.Mutable
        Fill the mutable from fromIndex (inclusive) to toIndex (exclusive) with val.
        Overrides:
        fill in class PackedInts.Mutable
      • gcd

        private static int gcd​(int a,
                               int b)