Package org.stianloader.concurrent

Class ConcurrentInt62Set

  • All Implemented Interfaces:
    it.unimi.dsi.fastutil.longs.LongCollection, it.unimi.dsi.fastutil.longs.LongIterable, it.unimi.dsi.fastutil.longs.LongSet, Iterable<Long>, Collection<Long>, Set<Long>
    public final class ConcurrentInt62Set
extends Object
implements it.unimi.dsi.fastutil.longs.LongSet

    Description

    A concurrent set for 62 bit unsigned integers, that is all integers between 0 and 1L << 62 - 1 (or 0x3FFF_FFFF_FFFF_FFFF). The two remaining bits are used for access control logic.

    This set supports high level of concurrency similar that of ConcurrentHashMap, however unlike ConcurrentHashMap ConcurrentInt62Set does not support resizing the amounts of buckets. Performance of this map degrades if too few buckets are used for too many elements. The size of each bucket increases exponentially in factors of two with a starting size of 16 elements. All buckets are initialized eagerly, that is either at creation time or when clear() is invoked. Buckets cannot be shrunk down after expanding to a certain size. Only clear() (or discarding the set itself) would cause the allocated memory to be freed. The amount of buckets is defined from the start and cannot be changed later on. For performance reasons, it must be a power of two.

    Atomicity of method calls

    The atomic operations add(long), remove(long) and contains(long) are the smallest unit from which the set can be altered. All other operations (aside from the iterator) are based on either the atomic operations or the iterator. These operations are not atomic, that is the effects might not fully take effect. For example a call to retainAll(LongCollection) might remove a value added via add(long) shortly after calling retainAll(LongCollection). However, it is also possible that it keeps that value. Should this atomic behaviour be required nonetheless, the set should be synchronised via LongSets.synchronize(LongSet) or similar.

    Even though add(long) and remove(long) are considered atomic, they are not guaranteed to be non-blocking. During a resizing operation, a thread may need to wait on other threads in order to gain exclusive control over a bucket's internal array. Conversely, once the lock has been acquired, other threads will need to wait until the lock has been relinquished. This behaviour is required in order to guarantee that the effects of add(long) and remove(long) persist even across a resize. To reduce the likelihood of this occurring, a larger amount of buckets may need to be used. To expand on this it may be beneficial to redistribute the bits of the longs so that the least significant bits are less frequent to occur in a given combination. This is especially beneficial when storing values that are aligned (for example address values that might frequently be only multiples of 4, 8 or another value), as this will necessarily cause some buckets to be empty.

    Iteration

    Multiple iterators are supported at the same time. Furthermore, this set implementation also supports modification of the set without causing the iterators to fail - except if the modification would cause the iterator to be exhausted. However, as iterators do not represent an atomic snapshot (or any snapshot at all for that matter) it is possible that underlying changes may improperly reflect on the iteration results. That is an Iterator.next() call can fail even though Iterator.hasNext() has been called beforehand as a LongSet.remove(long) operation which was called in between hasNext and next caused the iterator to be exhausted. Extreme care should be taken when using Iterators in concurrent environments involving additions to the set coupled with removals.

    Important non-features

    This set does not implement Object.hashCode() and Object.equals(Object). Should these methods be required nonetheless a wrapper may be appropriate.

    This set expects that values are distributed evenly and randomly. More specifically, the bucket for any given value is ((value & 0xFFFF) ^ (value >> 32)) & (bucketCount - 1). This contrasts collections such as ConcurrentHashMap where the value to bucket mapping appears a bit more random. more specifically, this causes issues when values inserted into the collection are guaranteed to be multiples of 2, 4, 8 or 16 (and further), as the buckets will not be used efficiently, causing lookup and mutation times to increase larger than usually.

    Author:
    Emeric "geolykt" Werner

    • Constructor Detail

      • ConcurrentInt62Set

        public ConcurrentInt62Set​(int bucketCount)

    • Method Detail

      • add

        public boolean add​(long element)
        Specified by:
        add in interface it.unimi.dsi.fastutil.longs.LongCollection

      • remove

        public boolean remove​(long element)
        Specified by:
        remove in interface it.unimi.dsi.fastutil.longs.LongSet

      • contains

        public boolean contains​(long element)
        Specified by:
        contains in interface it.unimi.dsi.fastutil.longs.LongCollection

      • toLongArray

        public long[] toLongArray()
        Specified by:
        toLongArray in interface it.unimi.dsi.fastutil.longs.LongCollection

      • toArray

        public long[] toArray​(long[] a)
        Specified by:
        toArray in interface it.unimi.dsi.fastutil.longs.LongCollection

      • addAll

        public boolean addAll​(it.unimi.dsi.fastutil.longs.LongCollection c)
        Specified by:
        addAll in interface it.unimi.dsi.fastutil.longs.LongCollection

      • containsAll

        public boolean containsAll​(it.unimi.dsi.fastutil.longs.LongCollection c)
        Specified by:
        containsAll in interface it.unimi.dsi.fastutil.longs.LongCollection

      • removeAll

        public boolean removeAll​(it.unimi.dsi.fastutil.longs.LongCollection c)
        Specified by:
        removeAll in interface it.unimi.dsi.fastutil.longs.LongCollection

      • retainAll

        public boolean retainAll​(it.unimi.dsi.fastutil.longs.LongCollection c)
        Specified by:
        retainAll in interface it.unimi.dsi.fastutil.longs.LongCollection

      • iterator

        public it.unimi.dsi.fastutil.longs.LongIterator iterator()
        Specified by:
        iterator in interface Collection<Long>
        Specified by:
        iterator in interface Iterable<Long>
        Specified by:
        iterator in interface it.unimi.dsi.fastutil.longs.LongCollection
        Specified by:
        iterator in interface it.unimi.dsi.fastutil.longs.LongIterable
        Specified by:
        iterator in interface it.unimi.dsi.fastutil.longs.LongSet
        Specified by:
        iterator in interface Set<Long>