Package org.HdrHistogram.packedarray

Class AbstractPackedArrayContext

  • All Implemented Interfaces:
    java.io.Serializable
    Direct Known Subclasses:
    PackedArrayContext
    abstract class AbstractPackedArrayContext
extends java.lang.Object
implements java.io.Serializable
    A packed-value, sparse array context used for storing 64 bit signed values. An array context is optimised for tracking sparsely set (as in mostly zeros) values that tend to not make use pof the full 64 bit value range even when they are non-zero. The array context's internal representation is such that the packed value at each virtual array index may be represented by 0-8 bytes of actual storage. An array context encodes the packed values in 8 "set trees" with each set tree representing one byte of the packed value at the virtual index in question. The getPackedIndex(int, int, boolean) method is used to look up the byte-index corresponding to the given (set tree) value byte of the given virtual index, and can be used to add entries to represent that byte as needed. As a succesful getPackedIndex(int, int, boolean) may require a resizing of the array, it can throw a ResizeException to indicate that the requested packed index cannot be found or added without a resize of the physical storage.

    • Field Detail

      • PACKED_ARRAY_GROWTH_INCREMENT

        private static final int PACKED_ARRAY_GROWTH_INCREMENT
        The physical representation uses an insert-at-the-end mechanism for adding contents to the array. Any insertion will occur at the very end of the array, and any expansion of an element will move it to the end, leaving an empty slot behind. Terminology: long-word: a 64-bit-aligned 64 bit word short-word: a 16-bit-aligned 16 bit word byte: an 8-bit-aligned byte long-index: an index of a 64-bit-aligned word within the overall array (i.e. in multiples of 8 bytes) short-index: an index of a 16-bit aligned short within the overall array (i.e. in multiples of 2 bytes) byte-index: an index of an 8-bit aligned byte within the overall array (i.e. in multiples of 1 byte) The storage array stores long (64 bit) words. Lookups for the variuous sizes are done as such: long getAtLongIndex(int longIndex) { return array[longIndex]; } short getAtShortIndex(int shortIndex) { return (short)((array[shortIndex >> 2] >> (shortIndex & 0x3)) & 0xffff); } byte getAtByteIndex(int byteIndex) { return (byte)((array[byteIndex >> 3] >> (byteIndex & 0x7)) & 0xff); } [Therefore there is no dependence on byte endiannes of the underlying arhcitecture] Structure: The packed array captures values at virtual indexes in a collection of striped "set trees" (also called "sets"), with each set tree representing one byte of the value at the virtual index in question. As such, there are 8 sets in the array, each corresponding to a byte in the overall value being stored. Set 0 contains the LSByte of the value, and Set 7 contains the MSByte of the value. The array contents is comprised of thre types of entries: - The root indexes: A fixed size 8 short-words array of short indexes at the start of the array, containing the short-index of the root entry of each of the 8 set trees. - Non-Leaf Entires: Variable sized, 2-18 short-words entries representing non-leaf entries in a set tree. Non-Leaf entries comprise of a 2 short-word header containing a packed slot indicators bitmask and the (optional non-zero) index of previous version of the entry, followed by an array of 0-16 shortwords. The short-word found at a given slot in this array holds an index to an entry in the next level of the set tree. - Leaf Entries: comprised of long-words. Each byte [0-7] in the longword holds an actual value. Specifically, the byte-index of that LeafEntry byte in the array is the byte-index for the given set's byte value of a virtual index. If a given virtual index for a given set has no entry in a given set tree, the byte value for that set of that virtual index interpreted as 0. If a given set tree does not have an entry for a given virtual index, it is safe to assume that no higher significance set tree have one either. Non-leaf entries structure and mutation protocols: The structure of a Non-Leaf entry in the array can be roughly desctibed in terms of this C-stylre struct: struct nonLeafEntry { short packedSlotIndicators; short previousVersionIndex; short[] enrtrySlotsIndexes; } Non-leaf entries are 2-18 short-words in length, with the length determined by the number of bits set in the packedSlotIndicators short-word in the entry. The packed slot indicators short-word is a bit mask which represents the 16 possible next-level entries below the given entry, and has a bit set (to '1') for each slot that is actually populated with a next level entry. Each of the short-words in the enrtrySlots is associated with a specific active ('1') bit in the packedSlotIndicators short-word, and holds the index to the next level's entry associated with ta given path in the tree. [Note: the values in enrtrySlotsIndexes[] are short-indexes if the next level is not a leaf level, and long-indexes if the next level is a leaf.] Summary of Non-leaf entry use and replacement protocol: - No value in any enrtrySlotsIndexes[] array is ever initialized to a zero value. Zero values in enrtrySlotsIndexes[] can only appear through consolidation (see below). Once an enrtrySlotsIndexes[] slot is observed to contain a zero, it cannot change to a non-zero value. - Zero values encountered in enrtrySlotsIndexes[] arrays are never followed. If a zero value is found when looking for the index to a lower level entry during a tree walk, the tree walking operation is restarted from the root. - A Non-Leaf entry with an active (non zero index) previous version is never followed or expanded. Instead, any thread encountering a Non-leaf entry with an active previous version will consolidate the previous version with the current one. the consolidation opeartion will clear (zero) the previousVersionIndex, which will then allow the caller to continue with whatever use the thread was attempting to make of the entry. - Expansion of entries: Since entries hold only enough storage to represent currently populated paths below them in the set tree, any addition of entries at a lower level requires the expansion of the entry to make room for a larger enrtrySlotsIndexes array. Expansion allocates a new and larger entry structure, and populates the newly inserted slot in it with an index to a newly allocated next-level entry. It then links the newly expanded entry the previous entry structure via the previousVersionIndex field, and publishes the newly expanded entry by [atomically] replacing the "pointer index" to the previous entry (located at a higher level entry's slot, or in the root indexes) with a "pointer index" to the newly expanded entry structure. A failure to atomically publish a newly expanded entry (e.g. if the "pointer index" being replaced holds a value other than that in our not-yet-published previousVersionIndex) will restart the expansion operation from the beginning. When first published, a newly-visible expanded entry is immediately "usable" because it has an active, "not yet consolidated" previous version entry, and any user of the entry will first have to consolidate it. The expansion will follow publication of the expanded entry with a consolidation of the previous entry into the new one, clearing the previousVersionIndex field in the process, and enabling normal use of the expanded entry. - Concurrent consolidation: While expansion and consolidation are ongoing, other threads can be concurrently walking the set trees. Per the protocol stated here, any tree walk encountering a Non-Leaf entry with an active previous version will consolidate the entry before using it. Consolidation can of a given entry can occur concurrently by an an expanding thread and by multiple walking threads. - Consolidation of a a previous version entry into a current one is done by: - For each non-zero index in the previous version enrty, copy that index to the new assocaited entry slot in the entry, and CAS a zero in the old entry slot. If the CAS fails, repeat (including the zero check). - Once all entry slots in the previous version entry have been consolidated and zeroed, zero the index to the previous version entry.
        See Also:
        Constant Field Values

      • PACKED_ARRAY_GROWTH_FRACTION_POW2

        private static final int PACKED_ARRAY_GROWTH_FRACTION_POW2
        See Also:
        Constant Field Values

      • NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS

        private static final int NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
        See Also:
        Constant Field Values

      • NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET

        private static final int NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET
        See Also:
        Constant Field Values

      • NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET

        private static final int NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET
        See Also:
        Constant Field Values

      • MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY

        static final int MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
        See Also:
        Constant Field Values

      • MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH

        static final int MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH
        See Also:
        Constant Field Values

      • isPacked

        private final boolean isPacked

      • physicalLength

        private int physicalLength

      • virtualLength

        private int virtualLength

      • topLevelShift

        private int topLevelShift

    • Constructor Detail

      • AbstractPackedArrayContext

        AbstractPackedArrayContext​(int virtualLength,
                           int initialPhysicalLength)

    • Method Detail

      • init

        void init​(int virtualLength)

      • length

        abstract int length()

      • getPopulatedShortLength

        abstract int getPopulatedShortLength()

      • casPopulatedShortLength

        abstract boolean casPopulatedShortLength​(int expectedPopulatedShortLength,
                                         int newPopulatedShortLength)

      • casPopulatedLongLength

        abstract boolean casPopulatedLongLength​(int expectedPopulatedShortLength,
                                        int newPopulatedShortLength)

      • getAtLongIndex

        abstract long getAtLongIndex​(int longIndex)

      • casAtLongIndex

        abstract boolean casAtLongIndex​(int longIndex,
                                long expectedValue,
                                long newValue)

      • lazySetAtLongIndex

        abstract void lazySetAtLongIndex​(int longIndex,
                                 long newValue)

      • clearContents

        abstract void clearContents()

      • resizeArray

        abstract void resizeArray​(int newLength)

      • getAtUnpackedIndex

        abstract long getAtUnpackedIndex​(int index)

      • setAtUnpackedIndex

        abstract void setAtUnpackedIndex​(int index,
                                 long newValue)

      • lazysetAtUnpackedIndex

        abstract void lazysetAtUnpackedIndex​(int index,
                                     long newValue)

      • incrementAndGetAtUnpackedIndex

        abstract long incrementAndGetAtUnpackedIndex​(int index)

      • addAndGetAtUnpackedIndex

        abstract long addAndGetAtUnpackedIndex​(int index,
                                       long valueToAdd)

      • unpackedToString

        abstract java.lang.String unpackedToString()

      • setValuePart

        void setValuePart​(int longIndex,
                  long valuePartAsLong,
                  long valuePartMask,
                  int valuePartShift)

      • getAtShortIndex

        short getAtShortIndex​(int shortIndex)

      • getIndexAtShortIndex

        short getIndexAtShortIndex​(int shortIndex)

      • setAtShortIndex

        void setAtShortIndex​(int shortIndex,
                     short value)

      • casAtShortIndex

        boolean casAtShortIndex​(int shortIndex,
                        short expectedValue,
                        short newValue)

      • getAtByteIndex

        byte getAtByteIndex​(int byteIndex)

      • setAtByteIndex

        void setAtByteIndex​(int byteIndex,
                    byte value)

      • addAtByteIndex

        long addAtByteIndex​(int byteIndex,
                    byte valueToAdd)
        add a byte value to a current byte value in the array
        Parameters:
        byteIndex - index of byte value to add to
        valueToAdd - byte value to add
        Returns:
        the afterAddValue. ((afterAddValue & 0x100) != 0) indicates a carry.

      • getPackedSlotIndicators

        private int getPackedSlotIndicators​(int entryIndex)

      • setPackedSlotIndicators

        private void setPackedSlotIndicators​(int entryIndex,
                                     short newPackedSlotIndicators)

      • getPreviousVersionIndex

        private short getPreviousVersionIndex​(int entryIndex)

      • setPreviousVersionIndex

        private void setPreviousVersionIndex​(int entryIndex,
                                     short newPreviosVersionIndex)

      • getIndexAtEntrySlot

        private short getIndexAtEntrySlot​(int entryIndex,
                                  int slot)

      • setIndexAtEntrySlot

        private void setIndexAtEntrySlot​(int entryIndex,
                                 int slot,
                                 short newIndexValue)

      • casIndexAtEntrySlot

        private boolean casIndexAtEntrySlot​(int entryIndex,
                                    int slot,
                                    short expectedIndexValue,
                                    short newIndexValue)

      • casIndexAtEntrySlotIfNonZeroAndLessThan

        private boolean casIndexAtEntrySlotIfNonZeroAndLessThan​(int entryIndex,
                                                        int slot,
                                                        short newIndexValue)

      • consolidateEntry

        private void consolidateEntry​(int entryIndex)
        Consolidate entry with previous entry verison if one exists
        Parameters:
        entryIndex - The shortIndex of the entry to be consolidated

      • expandEntry

        private int expandEntry​(int existingEntryIndex,
                        int entryPointerIndex,
                        int insertedSlotIndex,
                        int insertedSlotMask,
                        boolean nextLevelIsLeaf)
                 throws AbstractPackedArrayContext.RetryException,
                        ResizeException
        Expand entry as indicated.
        Parameters:
        existingEntryIndex - the index of the entry
        entryPointerIndex - index to the slot pointing to the entry (needs to be fixed up)
        insertedSlotIndex - realtive [packed] index of slot being inserted into entry
        insertedSlotMask - mask value fo slot being inserted
        nextLevelIsLeaf - the level below this one is a leaf level
        Returns:
        the updated index of the entry (-1 if epansion failed due to conflict)
        Throws:
        AbstractPackedArrayContext.RetryException - if expansion fails due to concurrent conflict, and caller should try again.
        ResizeException

      • getRootEntry

        private int getRootEntry​(int setNumber)

      • getPackedIndex

        int getPackedIndex​(int setNumber,
                   int virtualIndex,
                   boolean insertAsNeeded)
            throws ResizeException
        Get the byte-index (into the packed array) corresponding to a given (set tree) value byte of given virtual index. Inserts new set tree nodes as needed if indicated.
        Parameters:
        setNumber - The set tree number (0-7, 0 corresponding with the LSByte set tree)
        virtualIndex - The virtual index into the PackedArray
        insertAsNeeded - If true, will insert new set tree nodes as needed if they do not already exist
        Returns:
        the byte-index corresponding to the given (set tree) value byte of the given virtual index
        Throws:
        ResizeException

      • contextLocalGetValueAtIndex

        private long contextLocalGetValueAtIndex​(int virtualIndex)

      • populateEquivalentEntriesWithZerosFromOther

        void populateEquivalentEntriesWithZerosFromOther​(AbstractPackedArrayContext other)

      • copyEntriesAtLevelFromOther

        private void copyEntriesAtLevelFromOther​(AbstractPackedArrayContext other,
                                         int otherLevelEntryIndex,
                                         int levelEntryIndexPointer,
                                         int otherIndexShift)

      • findFirstPotentiallyPopulatedVirtualIndexStartingAt

        private int findFirstPotentiallyPopulatedVirtualIndexStartingAt​(int startingVirtualIndex)

      • nonZeroValues

        java.lang.Iterable<IterationValue> nonZeroValues()
        An Iterator over all non-Zero values in the array
        Returns:
        an Iterator over all non-Zero values in the array

      • isPacked

        boolean isPacked()

      • getPhysicalLength

        int getPhysicalLength()

      • getVirtualLength

        int getVirtualLength()

      • determineTopLevelShiftForVirtualLength

        int determineTopLevelShiftForVirtualLength​(int virtualLength)

      • setVirtualLength

        void setVirtualLength​(int virtualLength)

      • getTopLevelShift

        int getTopLevelShift()

      • setTopLevelShift

        private void setTopLevelShift​(int topLevelShift)

      • getPopulatedLongLength

        int getPopulatedLongLength()

      • getPopulatedByteLength

        int getPopulatedByteLength()

      • nonLeafEntryToString

        private java.lang.String nonLeafEntryToString​(int entryIndex,
                                              int indexShift,
                                              int indentLevel)

      • leafEntryToString

        private java.lang.String leafEntryToString​(int entryIndex,
                                           int indentLevel)

      • recordedValuesToString

        private java.lang.String recordedValuesToString()

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object