Package edu.berkeley.cs.jqf.fuzz.util

Class FastNonCollidingCounter

java.lang.Object
edu.berkeley.cs.jqf.fuzz.util.Counter
edu.berkeley.cs.jqf.fuzz.util.FastNonCollidingCounter
public class FastNonCollidingCounter extends Counter
An implementation of Counter that uses an IntIntHashMap to store values "Fast" in that it is faster than using something that involves other HashMaps, and boxing to-and-from primitive values. There is surely a way to make it *faster* than this too, without avoiding the collisions, but given the performance improvement compared to the original (and collision-prone) coverage, I made the opinionated decision to implement it this way to avoid other concerns from high collisions rates on some particular target applications. Further experimentation with fast (non-colliding) coverage implementations might help to determine which approach is preferable.
Author:
Jonathan Bell

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected org.eclipse.collections.impl.list.mutable.primitive.IntArrayList
    nonZeroKeys
     

    Fields inherited from class edu.berkeley.cs.jqf.fuzz.util.Counter

    size

  • Constructor Summary

    Constructors
    Constructor
    Description
    FastNonCollidingCounter(int size)
    Creates a new counter

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Clears the counter by setting all values to zero.
    void
    copyFrom(FastNonCollidingCounter counter)
     
    int
    get(int key)
    Retreives a value for a given key.
    int
    getAtIndex(int idx)
     
    org.eclipse.collections.api.list.primitive.IntList
    getNonZeroIndices()
    Returns a set of indices at which the count is non-zero.
    org.eclipse.collections.api.list.primitive.IntList
    getNonZeroKeys()
    Returns a set of keys at which the count is non-zero.
    int
    getNonZeroSize()
    Returns the number of indices with non-zero counts.
    org.eclipse.collections.api.list.primitive.IntList
    getNonZeroValues()
    Returns a set of non-zero count values in this counter.
    boolean
    hasNonZeros()
    Checks if all indices have zero counts and returns a boolean as result.
    int
    increment(int key)
    Increments the count at the given key.
    int
    increment(int key, int delta)
    Increments the count at the given key by a given delta.
    protected int
    incrementAtIndex(int index, int delta)
     
    void
    setAtIndex(int idx, int value)
     
    int
    size()
    Returns the size of this counter.

    Methods inherited from class edu.berkeley.cs.jqf.fuzz.util.Counter

    increment1

    Methods inherited from class java.lang.Object

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

  • Field Details

    • nonZeroKeys

      protected org.eclipse.collections.impl.list.mutable.primitive.IntArrayList nonZeroKeys

  • Constructor Details

    • FastNonCollidingCounter

      public FastNonCollidingCounter(int size)
      Creates a new counter

  • Method Details

    • size

      public int size()
      Returns the size of this counter.
      Overrides:
      size in class Counter
      Returns:
      the size of this counter

    • clear

      public void clear()
      Clears the counter by setting all values to zero.
      Overrides:
      clear in class Counter

    • increment

      public int increment(int key)
      Increments the count at the given key.
      Overrides:
      increment in class Counter
      Parameters:
      key - the key whose count to increment
      Returns:
      the new value after incrementing the count

    • increment

      public int increment(int key, int delta)
      Increments the count at the given key by a given delta.
      Overrides:
      increment in class Counter
      Parameters:
      key - the key whose count to increment
      delta - the amount to increment by
      Returns:
      the new value after incrementing the count

    • incrementAtIndex

      protected int incrementAtIndex(int index, int delta)
      Overrides:
      incrementAtIndex in class Counter

    • setAtIndex

      public void setAtIndex(int idx, int value)
      Overrides:
      setAtIndex in class Counter

    • getAtIndex

      public int getAtIndex(int idx)
      Overrides:
      getAtIndex in class Counter

    • getNonZeroSize

      public int getNonZeroSize()
      Returns the number of indices with non-zero counts.
      Overrides:
      getNonZeroSize in class Counter
      Returns:
      the number of indices with non-zero counts

    • getNonZeroKeys

      public org.eclipse.collections.api.list.primitive.IntList getNonZeroKeys()
      Returns a set of keys at which the count is non-zero.
      Returns:
      a set of keys at which the count is non-zero

    • getNonZeroIndices

      public org.eclipse.collections.api.list.primitive.IntList getNonZeroIndices()
      Description copied from class: Counter
      Returns a set of indices at which the count is non-zero.

      Note that indices are different from keys, in that multiple keys can map to the same index due to hash collisions.

      Overrides:
      getNonZeroIndices in class Counter
      Returns:
      a set of indices at which the count is non-zero

    • getNonZeroValues

      public org.eclipse.collections.api.list.primitive.IntList getNonZeroValues()
      Returns a set of non-zero count values in this counter.
      Overrides:
      getNonZeroValues in class Counter
      Returns:
      a set of non-zero count values in this counter.

    • get

      public int get(int key)
      Retreives a value for a given key.

      The key is first hashed to retreive a value from the counter, and hence the result is modulo collisions.

      Overrides:
      get in class Counter
      Parameters:
      key - the key to query
      Returns:
      the count for the index corresponding to this key

    • copyFrom

      public void copyFrom(FastNonCollidingCounter counter)

    • hasNonZeros

      public boolean hasNonZeros()
      Description copied from class: Counter
      Checks if all indices have zero counts and returns a boolean as result.
      Overrides:
      hasNonZeros in class Counter
      Returns:
      true if some indices have non-zero counts, otherwise false.