FastCollect

A multi-platform library for high-performance primitive collections in the JVM/Kotlin ecosystem. FastCollect is highly memory efficient and performant, and is competitive with - if not faster than - every primitive collections library in the JVM ecosystem. See the benchmarking section for further details. Performance is complicated and any library that claims to be the de-facto fastest is probably not taking performance seriously. FastCollect is quite well tested, and has rounded off many of the sharp edges found in some collections libraries. First-class Java support is a stated goal - while not every feature is as idiomatic to use from Java as it would be from Kotlin, extensive work has gone into ensuring that it is not difficult or non-idiomatic either.

As a drop-in replacement for standard JRE collections, FastCollect generally reduces memory usage by 4–5× and improves CPU performance by 2-3×. FastCollect distinguishes itself with a much smaller footprint (supporting only necessary and useful collections), but performance comparable to or better than much larger and more complex libraries.

Note that performance has only been tested on JVM platforms.

Quick Start

FastCollect ships different artifacts depending on your target:

1. Kotlin Multi-Platform: Use fastcollect
2. Kotlin Single-Platform: Use fastcollect-[jvm|iosArm64|...]
3. Non-Kotlin JVM Target (Java/Scala/etc): Use fastcollect-jvm

You can add FastCollect as a dependency with:

Gradle:

implementation 'io.github.sooniln:fastcollect-jvm:6.1.0'

Maven:

<dependency>
    <groupId>io.github.sooniln</groupId>
    <artifactId>fastcollect-jvm</artifactId>
    <version>6.1.0</version>
</dependency>

FastCollect can be used as a replacement for Kotlin standard library collections and should provide immediate memory and CPU improvements without any further changes. As with most Kotlin libraries, you are encouraged to import the entire library space via import io.github.sooniln.fastcollect.* so that extension functions 'just work'.

FastCollect can interact with normal Kotlin collections through the use of extension methods like asList(), asSet(), asMap(), and asQueue(), which produce a thin wrapper around the FastCollect collection which allows it to be used as a Kotlin/Java collection, safe for use in any legacy APIs. Beware that using these wrappers may incur boxing penalties.

Using FastCollect types should be quite straightforward for anyone familiar with standard Kotlin/Java collections. FastCollect provides ArrayList/ArrayDeque, HashSet, HashMap, and PriorityQueue analogues that can store primitives (and in the case of maps, primitive keys with reference or primitive values).

Note

FastCollect currently only supports Int/Long keys for HashMap (all types of values are supported). This is out of a desire to reduce binary size and bloat by eliminating use cases that are unlikely to be very common or useful. If you feel you have a compelling use case that is not currently supported, please file a bug, as support is generally trivial to add.

Overview

Concrete primitive collection types supported:

• Iterator
• ArrayList/Deque
• HashSet
• HashMap
• PriorityQueue

Unsupported collection types:

• LinkedList - primitive linked lists are assumed useless in any reasonable scenarios until proven otherwise.
• ConcurrentHashMap - supporting arbitrary concurrency within a hashmap is assumed to be useless in any reasonable scenario until proven otherwise. In scenarios where arbitrary levels of concurrency are useful (such as in a cache perhaps), ConcurrentHashMap is almost always inferior to specialized designs for the problem domain. In scenarios where a lower level of concurrency is required, explicit synchronization is assumed to be superior.
• LinkedHashSet/Map - stable ordering within a HashSet/Map is assumed to be unnecessary until proven otherwise.
• TreeSet/Map - useful in some important scenarios, but often too niche to justify including for the moment.
• Big collections (64-bit indexing) - useful only in very niche scenarios.
• Fully immutable types - occasionally useful, but do not currently give a sufficient benefit vs read-only types and effective immutability to justify inclusion.

Floating-Point Comparisons

On the JVM, primitive floating-point types obey IEEE floating-point comparisons (positive and negative zeros are equal, NaN is never equal to anything including itself). Boxed floating-point types however do not obey normal IEEE floating-point rules (positive and negative zeros are not equal, NaN can be equal to other Nan values).

In order to make the primitive collections in this library maximally useful, all collections internally implement equality as bit-wise equality. This means that equality used in this library is closer to JVM boxed type equality than primitive type equality. Within the collections for example, Float.NaN == Float.Nan and -0.0 != 0.0. Care must be used when interacting with these collections via external lambdas, for example:

import io.github.sooniln.fastcollect.*

var set = FloatHashSet(...)
// option 1 - removes NaN from the set
set.remove(Float.NaN)
// option 2 - does not remove NaN from the set
set.removeAll { value -> value == Float.NaN }

Default JVM equality uses IEEE conventions for primitives. For this reason, FastCollect exposes publicly the comparison methods it uses internally, as equalsRaw() and notEqualsRaw().

import io.github.sooniln.fastcollect.*

var set = FloatHashSet(...)
// option 1 - removes NaN from the set
set.remove(Float.NaN)
// option 2 - removes NaN from the set
set.removeAll { value -> value equalsRaw Float.NaN}

ConcurrentModificationException

The standard JRE libraries make reasonable efforts to throw ConcurrentModificationException if they detect collections being modified in inappropriate ways. This already only a best effort with no guarantees made, but FastCollect makes even less of an effort in the interests of performance. Do not expect FastCollect to throw ConcurrentModificationException every time you shoot yourself in the foot, only occasionally.

Iteration

All collection classes do not implement Iterable, but do offer an iterator method (this is deliberate, to avoid the usage of standard library extension methods defined on Iterable, which have numerous problems). This means that in Kotlin they can be used in normal for-each loops, but not in Java. The returned iterator should avoid any boxing of primitive values. Concrete classes (as opposed to interfaces) offer forEach methods (forEachWhile for Java clients) which are guaranteed to be as fast as or faster than iterators.

Map iteration is allocation free: Map.iterator() returns the same Entry instance repeatedly, repositioned over each successive entry. Read what you need from an entry before advancing the iterator again, and never retain an entry beyond that point.

See the following examples section for further usage.

Examples

You'll find that FastCollect collection usage is pretty much exactly like Kotlin collection usage. A few (non-exhaustive) examples of common APIs follow:

import io.github.sooniln.fastcollect.*

// creating a list
var list = IntArrayDeque()
list = mutableIntListOf(1, 2, 3)

// get/set by index
var i = list[1]
list[1] = 2

// search for value in list
list.indexOf(1)
list.lastIndexOf(2)
list.contains(3)

// iterate over list
for (value in list) {
    println(value)
}

// mutate list
list.add(5)
list.remove(5)
list.removeAt(0)
list.clear()

// other operations
list.sort()
list.shuffle()
list.fill(0)

// use the list somewhere a Kotlin list is required
legacyApi(list.asList())

// creating a set
var set = IntHashSet() // create FastCollect set directly
set = mutableIntSetOf(1, 2, 3) // directly create FastCollect set

// search for presence in set
set.contains(3)

// iterate over set
for (value in set) {
    println(value)
}

// mutate set
set.add(5)
set.remove(5)
set.clear()

// use the set somewhere a Kotlin set is required
legacyApi(set.asSet())

// creating a map
var map = Int2IntHashMap() // create FastCollect map directly
map = mutableInt2IntMapOf(1 to 2, 2 to 4, 3 to 7) // directly create FastCollect map

// get/set by index
var v = map[1]
map[1] = 5

// search for key/value in map
map.containsKey(1)
map.containsValue(2)

// iterate over map
for (entry in map) {
    println("${entry.key} -> ${entry.value}")
}
for (key in map.keys) {
    println(key)
}

// mutate map
map.remove(5)
map.clear()

// other operations
map.getOrElse(1) { -1 }

// use the map somewhere a Kotlin map is required
legacyApi(map.asMap())

// creating a priority queue
var priorityQueue = IntPriorityQueue(descending = true)

// mutate priority queue
priorityQueue.add(5)
priorityQueue.add(2)
priorityQueue.add(8)
priorityQueue.remove(5) // O(N)
priorityQueue.first() // returns 8
priorityQueue.removeFirst() // returns 8
priorityQueue.clear()

// iterate over priority queue (no ordering guarantees)
for (value in priorityQueue) {
    println(value)
}

// use the priority queue somewhere a Kotlin queue is required
legacyApi(priorityQueue.asQueue())

Indirect Priority Queues

In addition to standard priority queues, FastCollect's AbstractPriorityQueue also offers extension points to easily build an indirect priority queue:

class IndirectPriorityQueue(private val priorities: IntArray): AbstractIntPriorityQueue() {
    private val elementToIndexMap = IntArray(priorities.size) { -1 }

    override fun isHigherPriority(element1: Int, element2: Int): Boolean {
        return priorities[element1] > priorities[element2]
    }

    override fun onIndexChanged(element: Int, index: Int) {
        elementToIndexMap[element] = index
    }

    override fun onRemoved(element: Int, index: Int) {
        elementToIndexMap[element] = -1
    }

    fun update(element: Int) {
        val index = elementToIndexMap[element]
        if (index == -1) {
            add(element)
        } else {
            updatePriority(index)
        }
    }
}

This is a trivial example - more complex shapes are possible as well.

Performance and Memory Usage

A key advantage of primitive collections is not just reduced CPU usage, but substantially lower memory usage, which has compounding benefits — more data fitting in CPU caches further reduces memory access latency.

A more detailed examination of performance and memory usage can be found in this post. In benchmarking, FastCollect unsurprisingly outperforms standard Kotlin collections, as well as many other primitive collection libraries.

Memory Usage

A more detailed examination of memory usage can be found in the Memory Benchmarks doc. FastCollect has put effort into ensuring that not only are large collections memory efficient (which most primitive collections libraries accomplish), but also that small/empty collections are memory efficient (which some primitive collections are shockingly bad at).

Generated Code

FastCollect generates most of its collection classes from templates in order to reduce the amount of copy/pasted code present. Contrary to common practice, this project checks the generated code directly into the repository. While this is non-standard from a build pipeline perspective, this project has public APIs composed of generated code, and it is important for clients and users that the actual code (rather than just the generation templates) is viewable, searchable, and parseable within the repository itself.