Package io.deephaven.engine.table.impl.by

Class BitmapRandomBuilder

java.lang.Object
io.deephaven.engine.table.impl.by.BitmapRandomBuilder
All Implemented Interfaces:
RowSetBuilderRandom
public class BitmapRandomBuilder extends Object implements RowSetBuilderRandom
The output RowSet of an aggregation is fairly special. It is always from zero to the number of output rows, and while modifying states we randomly add rows to it, potentially touching the same state many times. The normal index random builder does not guarantee those values are de-duplicated and requires O(lg n) operations for each insertion and building the RowSet.

This version is O(1) for updating a modified slot, then linear in the number of output positions (not the number of result values) to build the RowSet. The memory usage is 1 bit per output position, vs. the standard builder is 128 bits per used value (though with the possibility of collapsing adjacent ranges when they are modified back-to-back). For random access patterns, this version will be more efficient; for friendly patterns the default random builder is likely more efficient.

We also know that we will only modify the rows that existed when we start, so that we can clamp the maximum key for the builder to the maximum output position without loss of fidelity.

A builder may be reused from one update to the next: reset(int) sets the new maximum key and permits another build, and building clears each word as it is read, so the bitset needs no clearing between uses and grows geometrically as the output positions do. Between resets, a builder builds at most once.

  • Constructor Details

    • BitmapRandomBuilder

      public BitmapRandomBuilder(int maxKey)

  • Method Details

    • reset

      public void reset(int maxKey)
      Prepare to build another RowSet, discarding any keys added and not yet built.
      Parameters:
      maxKey - keys at or above this one are ignored

    • build

      public WritableRowSet build()
      Description copied from interface: RowSetBuilderRandom
      Build the WritableRowSet from the accumulated row keys. Builders are single use: at most one build call is permitted, and subsequent calls throw IllegalStateException. The effect of providing further row keys after building is undefined.
      Specified by:
      build in interface RowSetBuilderRandom
      Returns:
      The built RowSet

    • build

      public WritableRowSet build(RowSet... excluded)
      Build the RowSet of the keys added, less the keys of excluded, leaving the builder empty. Like build(), this may be called only once until the builder is reset.
      Parameters:
      excluded - row sets whose keys are left out of the result; clearing their bits first costs time in proportion to their sizes, rather than removing them from the result afterward
      Returns:
      the keys added and not excluded

    • addKey

      public void addKey(long rowKey)
      Specified by:
      addKey in interface RowSetBuilderRandom

    • addRange

      public void addRange(long firstRowKey, long lastRowKey)
      Specified by:
      addRange in interface RowSetBuilderRandom