Package io.deephaven.engine.table.impl.util.hash

Class NullableLongLongMaps

java.lang.Object

io.deephaven.engine.table.impl.util.hash.NullableLongLongMaps

public final class NullableLongLongMaps
extends Object

The one way to construct a NullableLongLongMap, and the one place where "which shape?" decisions live: a map consults shapeForRebuild(io.deephaven.engine.table.impl.util.hash.NullableLongLongMaps.Shape, double, int, boolean) whenever it builds an array, so no owner ever decides — or even notices — when a map widens. Callers name a NullableLongLongMaps.Shape, never a class: every implementation class in this package is package-private, and the shape a map was built with is an implementation detail behind the interface.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	NullableLongLongMaps.ReadMode	How a NullableLongLongMaps.Shape.K4V4 map's chunked gets choose between the serial probe loop and the AMAC window.
static enum	NullableLongLongMaps.Shape	The bucket width of a map: how many key/value pairs each hash bucket holds.

Field Summary

Fields

Modifier and Type	Field	Description
static final double	AMAC_LOAD_FACTOR_FLOOR	The load factor at and above which a map that is big enough is rebuilt in the wide-bucket (K4V4) shape; below it the shape does not pay, regardless of size.
static final int	DEFAULT_AMAC_THRESHOLD_ENTRIES	Entry capacity at and above which a K4V4 map services chunked gets through the AMAC window (16 bytes per entry, so 1M entries is a 16MB array).
static final int	MIN_WINDOWED_CHUNK	The narrowest chunk a K4V4 map services through the AMAC window: the window's own width, K4V4Kernel.GET_WINDOW, so that retuning the window moves this gate with it.
static final int	MONOTONE_KEYS_MAX_LOCAL_STEP	The walk must also be local: a monotone chunk whose consecutive keys are, on average, more than this many keys apart lands each lookup in its own far-off bucket, and the prefetcher has nothing to stream.
static final double	MONOTONE_KEYS_SERIAL_BELOW_OCCUPANCY	Second stage of the read-strategy gate, for a chunk whose keys walk memory in order: below this occupancy (occupied slots over entry capacity, tombstones counting as occupied, since a probe chain runs past them exactly as it runs past entries) such a chunk takes the serial loop even though the footprint gate would open the window.

Method Summary

Modifier and Type	Method	Description
static boolean	isLocalWalk(long first, long last, int n)	Is a monotone chunk running from first to last over n keys a local walk, at most MONOTONE_KEYS_MAX_LOCAL_STEP keys per step on average? A span a long cannot hold, or whose absolute value it cannot, is not local.
static NullableLongLongMap	of(NullableLongLongMaps.Shape shape, int desiredInitialCapacity, double loadFactor, long noEntryValue)	Creates a map of the given NullableLongLongMaps.Shape with the given initial capacity, load factor, and noEntryValue (the value returned by reads that find no mapping).
static NullableLongLongMap	of(NullableLongLongMaps.Shape shape, int desiredInitialCapacity, double loadFactor, long noEntryValue, NullableLongLongMaps.ReadMode readMode)	As of(Shape, int, double, long), with the read strategy pinned.
static NullableLongLongMap	ofExpectedSize(NullableLongLongMaps.Shape shape, int expectedSize, double loadFactor, long noEntryValue)	Creates a map of the given NullableLongLongMaps.Shape, presized so that expectedSize entries at loadFactor fit without a rehash.
static boolean	wantSerialForMonotoneKeys(int occupiedSlots, int entryCapacity)	Second stage of the read-strategy gate, consulted only after wantWindowedReads(int, int) has said yes: is this map sparse enough that a chunk of monotone, local keys is better served by the serial loop? The map answers with its occupied slot count — entries and tombstones alike, since a probe chain runs past both — and its entry capacity; whether the chunk's keys are in fact a local monotone walk is the map's own check, made only when this says yes.
static boolean	wantWindowedReads(int entryCapacity, int chunkSize)	Should a K4V4-shaped map service this chunked get through the AMAC window? Yes exactly when its FOOTPRINT is past the measured crossover — entry capacity at or above DEFAULT_AMAC_THRESHOLD_ENTRIES, which the footprint sweep above puts near L2, well inside the last-level cache — because the window's whole job is overlapping cache misses, and a table that fits the near caches has none worth overlapping (there the window is pure bookkeeping, measured as a tax); and when the chunk is at least MIN_WINDOWED_CHUNK keys wide, because a chunk that cannot fill the window pays its fixed cost for nothing (a single-key chunk — the scalar cursor's case — has nothing to overlap at all).

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_AMAC_THRESHOLD_ENTRIES

public static final int DEFAULT_AMAC_THRESHOLD_ENTRIES

Entry capacity at and above which a K4V4 map services chunked gets through the AMAC window (16 bytes per entry, so 1M entries is a 16MB array). This is a FOOTPRINT threshold. The footprint sweep on a Ryzen 9 9950X3D2 (1MB L2, ~96MB per-CCD L3; serial vs forced-window, 2M..16M entries, load factors 0.5 and 0.9, sorted and shuffled, three forks) found the window winning or tying at EVERY size from 2M up — 13-38% faster on shuffled lookups and 12-20% on sorted at load factor 0.9 — even though a 2M-entry array (32MB) fits in that L3: the window overlaps L3 latency, not just DRAM latency, so the real boundary is near L2, not the last-level cache. At 100K entries (1.6MB) the two strategies measured as parity. The crossover therefore lies between 100K and 2M, and this value sits inside that bracket, bounded below by parity and above by a measured win. Re-sweep before trusting it on hardware with a materially larger L2. The same size is where a dense narrow map widens itself into the K4V4 shape (see shapeForRebuild(io.deephaven.engine.table.impl.util.hash.NullableLongLongMaps.Shape, double, int, boolean)): an array big enough to want the window is built wide.

See Also:

• Constant Field Values

MIN_WINDOWED_CHUNK

public static final int MIN_WINDOWED_CHUNK

The narrowest chunk a K4V4 map services through the AMAC window: the window's own width, K4V4Kernel.GET_WINDOW, so that retuning the window moves this gate with it. Below it a chunked get runs serially even when the footprint says window, because the window only pays when it is full: a chunk narrower than the window cannot overlap a window's worth of misses, while the window's fixed cost (the per-thread scratch, per-job setup) is paid regardless. Measured at 10M entries on an i9-13900K (three forks, serial vs forced window, window/serial time ratio): single-key chunks cost 1.6-2.3x under the window on every load factor and pattern; four-key chunks lose on everything but dense shuffled lookups; sixteen-key chunks win 10% on sparse shuffled and 2.4x on dense shuffled; sixty-four-key chunks win 23% and 3x there and tie dense sorted. Sixteen is the window width: the smallest chunk that can fill it. (Sorted sparse lookups lose under the window at every chunk size on that machine and tie or win on a Ryzen 9 9950X3D2 — a lookup-pattern question, which the gate's second stage answers: see wantSerialForMonotoneKeys(int, int).)

See Also:

• Constant Field Values

MONOTONE_KEYS_SERIAL_BELOW_OCCUPANCY

public static final double MONOTONE_KEYS_SERIAL_BELOW_OCCUPANCY

Second stage of the read-strategy gate, for a chunk whose keys walk memory in order: below this occupancy (occupied slots over entry capacity, tombstones counting as occupied, since a probe chain runs past them exactly as it runs past entries) such a chunk takes the serial loop even though the footprint gate would open the window. The maps' first probe is deliberately weak — consecutive keys land in consecutive buckets — so monotone keys into a sparse table are a straight walk through memory that almost always ends at the first bucket; the hardware prefetcher already hides that walk, and the window's bookkeeping then costs 16 to 38% on an i9-13900K and 4 to 8% on a Ryzen 9 9950X3D2 at 30 to 38% occupancy (measured at 1M to 10M entries). At 61% occupancy and above the probe chains wander and the window wins by 8 to 19% even on monotone keys, so the threshold sits between the two, at one half. A map's occupancy sawtooths within [loadFactor/2, loadFactor] as rehash doubles overshoot: a load-factor-0.5 map never rises above it, so its monotone reads are always serial, and a load-factor-0.9 map dips below it only in the first ninth of each doubling cycle, where the window's gain is smallest. Shuffled keys never consult this: their misses are what the window exists to overlap.

See Also:

• Constant Field Values

MONOTONE_KEYS_MAX_LOCAL_STEP

public static final int MONOTONE_KEYS_MAX_LOCAL_STEP

The walk must also be local: a monotone chunk whose consecutive keys are, on average, more than this many keys apart lands each lookup in its own far-off bucket, and the prefetcher has nothing to stream. In K4V4 buckets of 64 bytes, 2048 keys is 128KB between consecutive first probes. Measured on the i9: 100,000 sorted lookups into 10M entries (about 100 keys apart) are 14% faster serial; into 100M (about 1,000 apart) 6% faster serial; into 500M (about 5,000 apart) 19% faster through the window. The threshold sits between the last two.

See Also:

• Constant Field Values

AMAC_LOAD_FACTOR_FLOOR

public static final double AMAC_LOAD_FACTOR_FLOOR

The load factor at and above which a map that is big enough is rebuilt in the wide-bucket (K4V4) shape; below it the shape does not pay, regardless of size. This gates the LAYOUT only: whether the wide map's reads then go through the AMAC window is decided separately, by footprint (wantWindowedReads(int, int)). Measured at 10M entries: at load factor 0.5 the wide shape loses (~30-40% slower — probe chains barely exist, so the window has nothing to hide and wider buckets just cost more bytes per probe); at 0.75 it is a wash (sorted lookups trend against it, shuffled trend for it, error bars overlapping); at 0.9 it wins 20% on sorted and 2.5x on shuffled. The floor sits above the measured wash and below the measured win.

See Also:

• Constant Field Values

Method Details

of

public static NullableLongLongMap of(NullableLongLongMaps.Shape shape,
 int desiredInitialCapacity,
 double loadFactor,
 long noEntryValue)

Creates a map of the given NullableLongLongMaps.Shape with the given initial capacity, load factor, and noEntryValue (the value returned by reads that find no mapping). A K4V4 map's reads adapt by footprint (NullableLongLongMaps.ReadMode.ADAPTIVE).

of

public static NullableLongLongMap of(NullableLongLongMaps.Shape shape,
 int desiredInitialCapacity,
 double loadFactor,
 long noEntryValue,
 NullableLongLongMaps.ReadMode readMode)

As of(Shape, int, double, long), with the read strategy pinned. For pricing and tests; production code should let the map adapt.

Throws:

IllegalArgumentException - for NullableLongLongMaps.ReadMode.WINDOW with a shape other than NullableLongLongMaps.Shape.K4V4

ofExpectedSize

public static NullableLongLongMap ofExpectedSize(NullableLongLongMaps.Shape shape,
 int expectedSize,
 double loadFactor,
 long noEntryValue)

Creates a map of the given NullableLongLongMaps.Shape, presized so that expectedSize entries at loadFactor fit without a rehash.

wantWindowedReads

public static boolean wantWindowedReads(int entryCapacity,
 int chunkSize)

Should a K4V4-shaped map service this chunked get through the AMAC window? Yes exactly when its FOOTPRINT is past the measured crossover — entry capacity at or above DEFAULT_AMAC_THRESHOLD_ENTRIES, which the footprint sweep above puts near L2, well inside the last-level cache — because the window's whole job is overlapping cache misses, and a table that fits the near caches has none worth overlapping (there the window is pure bookkeeping, measured as a tax); and when the chunk is at least MIN_WINDOWED_CHUNK keys wide, because a chunk that cannot fill the window pays its fixed cost for nothing (a single-key chunk — the scalar cursor's case — has nothing to overlap at all). Footprint is the first-order predictor, and this gate is the first stage: it looks only at the array and the chunk width, so its answer is stable between rehashes and flips exactly when the array grows past the crossover. Occupancy on its own is second-order — at a fixed large footprint the window ties or wins at every occupancy measured when keys arrive shuffled — and is not an input here. It matters in one combination, monotone local keys into a sparse table, which the second stage handles: see wantSerialForMonotoneKeys(int, int), MONOTONE_KEYS_SERIAL_BELOW_OCCUPANCY and isLocalWalk(long, long, int).

wantSerialForMonotoneKeys

public static boolean wantSerialForMonotoneKeys(int occupiedSlots,
 int entryCapacity)

Second stage of the read-strategy gate, consulted only after wantWindowedReads(int, int) has said yes: is this map sparse enough that a chunk of monotone, local keys is better served by the serial loop? The map answers with its occupied slot count — entries and tombstones alike, since a probe chain runs past both — and its entry capacity; whether the chunk's keys are in fact a local monotone walk is the map's own check, made only when this says yes. See MONOTONE_KEYS_SERIAL_BELOW_OCCUPANCY for the evidence.

isLocalWalk

public static boolean isLocalWalk(long first,
 long last,
 int n)

Is a monotone chunk running from first to last over n keys a local walk, at most MONOTONE_KEYS_MAX_LOCAL_STEP keys per step on average? A span a long cannot hold, or whose absolute value it cannot, is not local.