Package io.timeandspace.smoothie

Class SmoothieMapBuilder<K,​V>

  • Type Parameters:
    K - the type of keys in created SmoothieMaps
    V - the type of values in created SmoothieMaps
    public final class SmoothieMapBuilder<K,​V>
extends Object
    SmoothieMapBuilder is used to configure and create SmoothieMaps. A new builder could be created via SmoothieMap.newBuilder() method. A SmoothieMap is created using build() method.

    SmoothieMapBuilder is mutable: all its configuration methods change its state, and return the receiver builder object to enable the "fluent builder" pattern: 

    
 SmoothieMap.newBuilder().expectedSize(100_000).doShrink(false).build();

    SmoothieMapBuilder could be used to create any number of SmoothieMap objects. Created SmoothieMaps don't retain a link to the builder and therefore don't depend on any possible subsequent modifications of the builder's state.

    • Method Detail

      • allocateIntermediateCapacitySegments

        @CanIgnoreReturnValue
@Contract("_ -> this")
public SmoothieMapBuilder<K,​V> allocateIntermediateCapacitySegments​(boolean allocateIntermediateCapacitySegments)
        Specifies whether during the growth of SmoothieMaps created with this builder they should first allocate intermediate-capacity segments and then reallocate them as full-capacity segments when needed, or allocate full-capacity segments right away.

        SmoothieMap stores the entries in small segments which are mini hash tables on their own. This hash table becomes full when the number of entries stored in it exceeds N. At this point, a segment is split into two parts. At least one new segment should be allocated upon a split to become the second part (or two new segments, if configured via splitBetweenTwoNewSegments(boolean)). The population of each of these two parts just after the split is approximately N/2, subject to some variability (while their joint population is N + 1). The entry storage capacity of segments is decoupled from the hash table, so a newly allocated segment may have entry storage capacity smaller than N. A segment of storage capacity of approximately (2/3) * N is called an intermediate-capacity segment, and a segment of storage capacity N is called a full-capacity segment.

        Thus, upon a segment split, a newly allocated intermediate-capacity segment is on average 75% full in terms of the entry storage capacity, while a newly allocated full-capacity segment is on average 50% full. When the number of entries stored in an intermediate-capacity segment grows beyond its storage capacity (approximately, (2/3) * N), it's reallocated in place as a full-capacity segment.

        Thus, intermediate-capacity segments reduce the total SmoothieMap's footprint per stored entry as well as the variability of the footprint at different SmoothieMap's sizes. The drawbacks of intermediate-capacity segments are:

        • They are transient: being allocated and reclaimed during the growth of a SmoothieMap. The total amount of garbage produced by a SmoothieMap instance (assuming it grows from size 0 and neither expectedSize(long) nor minPeakSize(long) was configured) becomes comparable with the SmoothieMap's footprint, though still lower than the total amount of garbage produced by a typical open-addressing hash table implementation such as IdentityHashMap, and comparable to the the total amount of garbage produced by entry-based hash maps (HashMap and ConcurrentHashMap) without pre-configured capacity and assuming that entries are not removed from them.
        • Reallocation of intermediate-capacity segments into full-capacity segments contributes the amortized cost of inserting entries into a SmoothieMap.
        • The mix of full-capacity and intermediate-capacity segments precludes certain variables to be hard-coded and generally adds some unpredictability (from the CPU perspective) to SmoothieMap's key lookup and insertion operations which might slower them relative to the setup where only full-capacity segments are used.

        By default, intermediate-capacity segments are allocated as a part of the "mixed" mode (the default mode) of SmoothieMap's operation. Intermediate-capacity segments are allocated in the "mixed" and the "footprint" modes, but are not allocated in the "low-garbage" mode.

        Disabling allocating intermediate-capacity segments (that is, passing false into this method) also implicitly disables splitting between two new segments because it doesn't make sense to allocate two new full-capacity segments and move entries there while we already have one full-capacity segment at hand (the old one).

        Parameters:
        allocateIntermediateCapacitySegments - whether the created SmoothieMaps should allocate intermediate-capacity segments during the growth
        Returns:
        this builder back
        See Also:
        splitBetweenTwoNewSegments(boolean)

      • splitBetweenTwoNewSegments

        @CanIgnoreReturnValue
@Contract("_ -> this")
public SmoothieMapBuilder<K,​V> splitBetweenTwoNewSegments​(boolean splitBetweenTwoNewSegments)
        Specifies whether when segments are split in SmoothieMaps created with this builder, the entries from the segment being split should be moved into two new intermediate-capacity segments or the entries should be distributed between the old segment one newly allocated segment (full-capacity or intermediate-capacity).

        See the description of the model of segments and the definitions of intermediate-capacity and full-capacity segments in the documentation for allocateIntermediateCapacitySegments(boolean). Moving entries from the old segment into two newly allocated intermediate-capacity segments means that just after the split they are jointly 75% full in terms of the entry storage capacity. Both newly allocated segments may then be reallocated as full-capacity segments when needed. One full-capacity segment and one newly allocated intermediate-capacity segment are jointly 60% full. Two full-capacity segments, the old one and a newly allocated one (if the allocation of intermediate-capacity segments is turned off) are jointly 50% full.

        Thus, splitting between two newly allocated segments lowers the footprint per entry and the footprint variability at different SmoothieMap's sizes as much as possible. The downside of this strategy is that during SmoothieMap's growth, one full-capacity and two intermediate-capacity segments are allocated and then dropped per every 2 * N entries (given that a segment's hash table capacity is N) every time the map doubles in size. This is a significant rate of heap memory churn, exceeding that of typical open-addressing hash table implementations such as IdentityHashMap and entry-based hash maps: HashMap or ConcurrentHashMap.

        By default, during a split, entries are distributed between the old (full-capacity) segment and a newly allocated intermediate-capacity segment, as per the "mixed" mode (the default mode) of SmoothieMap's operation, that is, by default, splitting is not done between two newly allocated segments. Splitting between two new segments is not done in the "low-garbage" and the "mixed" modes. It's enabled only in the "footprint" mode.

        Enabling splitting between two new segments also implicitly enables allocation of intermediate-capacity segments because the former doesn't make sense without the latter.

        Parameters:
        splitBetweenTwoNewSegments - whether created SmoothieMaps should move entries from full-capacity segments into two newly allocated intermediate-capacity segments during growth
        Returns:
        this builder back
        See Also:
        allocateIntermediateCapacitySegments(boolean), OptimizationObjective.FOOTPRINT

      • doShrink

        @CanIgnoreReturnValue
@Contract("_ -> this")
public SmoothieMapBuilder<K,​V> doShrink​(boolean doShrink)
        Specifies whether SmoothieMaps created with this builder should automatically shrink, i. e. reclaim the allocated heap space when they reduce in size.

        By default, shrinking is turned on as a part of the "mixed" mode (the default mode) of SmoothieMap's operation. The "mixed" and the "footprint" modes turn shrinking on, but the "low-garbage" mode turns shrinking off.

        Automatic shrinking creates some low-volume stream of allocations and reclamations of heap memory objects when entries are dynamically put into and removed from the SmoothieMap even if the number of entries in the map remains relatively stable during this process, though at a much lower rate than garbage is produced by entry-based Map implementations such as HashMap, TreeMap, or ConcurrentHashMap during a similar process.

        Parameters:
        doShrink - whether the created SmoothieMaps should automatically reclaim memory when they reduce in size
        Returns:
        this builder back

      • expectedSize

        @CanIgnoreReturnValue
@Contract("_ -> this")
public SmoothieMapBuilder<K,​V> expectedSize​(long expectedSize)
        Specifies the expected steady-state size of each SmoothieMap created using this builder. The steady-state size is the map size after it's fully populated (when the map is used in a simple populate-then-access pattern), or if entries are dynamically inserted into and removed from the map, the steady-state size is the map size at which it should eventually balance.

        The default expected size is considered unknown. Calling unknownExpectedSize() after this method has been once called on the builder with a specific value overrides that values and sets the expected size to be unknown again.

        Calling this method is a performance hint for created SmoothieMap(s) and doesn't affect the semantics of operations. The configured value must not be the exact steady-state size of a created SmoothieMap, but it should be within 5% from the actual steady-state size. If the steady-state size of created SmoothieMap(s) cannot be known with this level of precision, configuring expectedSize() might make more harm than good and therefore shouldn't be done. minPeakSize(long) might be known with more confidence though and it's recommended to configure it instead.

        In theory, the minimum peak size might be less than the expected size by at most 5% (higher difference is not possible if the expected size is configured according with the configuration above). If both expected size and minimum peak size are specified and the latter is less than the former by more than 5% an IllegalStateException is thrown when build() is called.

        Most often, the minimum peak size should be equal to the expected size (e. g. in the populate-then-access usage pattern, there is no ground for differentiating the peak and the expected sizes). Because of this, by default, if the expected size is configured for a builder and the minimum peak size is not configured, the expected size is used as a substitute for the minimum peak size.

        When entries are dynamically put into and removed from a SmoothieMap, the minimum peak size might also be greater than the expected size, if after reaching the peak size SmoothieMaps are consistently expected to shrink. This might also be the case when X entries are first inserted into a SmoothieMap and then some entries are removed until the map reduces to some specific size Y smaller than X.

        Parameters:
        expectedSize - the expected steady-state size of created SmoothieMaps
        Returns:
        this builder back
        Throws:
        IllegalArgumentException - if the provided expected size is not positive
        See Also:
        unknownExpectedSize(), minPeakSize(long)

      • minPeakSize

        @CanIgnoreReturnValue
@Contract("_ -> this")
public SmoothieMapBuilder<K,​V> minPeakSize​(long minPeakSize)
        Specifies the minimum bound of the peak size of each SmoothieMap created using this builder. For example, it may be unknown what size the created SmoothieMap will have after it is fully populated (or reaches "saturation" if entries are dynamically put into and removed from the map): 1 million entries, or 2 million, or 3 million. But if it known that under no circumstance the peak size of the map will be less than 1 million, then it makes sense to configure this bound via this method.

        The default minimum bound for the peak size of created SmoothieMaps is considered unknown, or 0. However, to configure unknown minimum bound of the peak size (the override a specific values which may have been once specified for the builder), unknownMinPeakSize() should be called and not this method.

        Calling this method is a performance hint for created SmoothieMap(s) and doesn't affect the semantics of operations. The configured value may be used to preallocate data structure when a SmoothieMap is created, so it's better to err towards a value lower than the actual peak size than towards a value higher than the actual peak size, especially when the optimization objective is set to OptimizationObjective.LOW_GARBAGE.

        If the minimum peak size is not configured for a SmoothieMapBuilder, but expected size is configured, the minimum peak size of created maps is assumed to be equal to the expected size, although in some cases it may be about 5% less than that even if the expected size is configured properly. If this is the case, configure the minimum peak size along with the expected size explicitly. See the documentation for expectedSize(long) method for more information.

        Parameters:
        minPeakSize - the minimum bound for the peak size of created SmoothieMaps
        Returns:
        this builder back
        Throws:
        IllegalArgumentException - if the provided minimum peak size is not positive
        See Also:
        unknownMinPeakSize(), expectedSize(long)

      • build

        @Contract(" -> new")
public SmoothieMap<K,​V> build()
        Creates a new SmoothieMap with the configurations from this builder. The created SmoothieMap doesn't hold an internal reference to the builder, and all subsequent changes to the builder doesn't affect the configurations of the map.
        Returns:
        a new SmoothieMap with the configurations from this builder