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.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) static final int
     
    (package private) static final int
     
    private final long[]
    Values are stores contiguously in the blocks array.
    private final int
    Optimization: Saves one lookup in get(int).
    private final long
    A right-aligned mask of width BitsPerValue used by get(int).
    (package private) static final int
     

    Fields inherited from class org.apache.lucene.util.packed.PackedInts.MutableImpl

    bitsPerValue, valueCount

    Fields inherited from interface org.apache.lucene.util.Accountable

    NULL_ACCOUNTABLE
  • 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

    Modifier and Type
    Method
    Description
    void
    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
    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.
     

    Methods inherited from class org.apache.lucene.util.packed.PackedInts.MutableImpl

    getBitsPerValue, size

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    Methods inherited from interface org.apache.lucene.util.Accountable

    getChildResources
  • Field Details

    • BLOCK_SIZE

      static final int BLOCK_SIZE
      See Also:
    • BLOCK_BITS

      static final int BLOCK_BITS
      See Also:
    • MOD_MASK

      static final int MOD_MASK
      See Also:
    • 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 Details

    • 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 Details

    • 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
    • toString

      public String toString()
      Overrides:
      toString in class PackedInts.MutableImpl
    • 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)
    • clear

      public void clear()
      Description copied from class: PackedInts.Mutable
      Sets all values to 0.
      Overrides:
      clear in class PackedInts.Mutable