compaKTset is a small library aimed at providing you with the most memory efficient
Set implementation for any particular data type of your choosing.
Currently supported and well-optimized types:
- Int
- Long
- Double
Getting Started
<dependency>
<groupId>me.beresnev</groupId>
<artifactId>compaktset</artifactId>
<version>0.1.1</version>
<dummy>unpublished</dummy>
</dependency>
Example:
val intSet = newCompactSet<Int>(16)
val meaningAdded = intSet.add(42)
val containsSatan = intSet.contains(666)
Memory footprint
To understand how compact compaKTset really is, we can measure it’s memory footprint and compare it with
java.util.HashSet for various set sizes.
First, let’s compare Int and Long with CompressedOops enabled
| implementation / size | 10^2 | 10^4 | 10^5 | 10^6 |
|---|---|---|---|---|
| java.util.HashSet<Int> | 5.9 KB | 545 KB | 5.8 MB | 56.3 MB |
| CompactSet<Int> | <1 KB | 40 KB | 0.4 MB | 4 MB |
| 10^2 | 10^4 | 10^5 | 10^6 | |
| java.util.HashSet<Long> | 6.7 KB | 625 KB | 6.6 MB | 64.3 MB |
| CompactSet<Long> | <1 KB | 80 KB | 0.8 MB | 8 MB |
Now let’s run it on the same VM, but with -XX:-UseCompressedOops
| implementation / size | 10^2 | 10^4 | 10^5 | 10^6 |
|---|---|---|---|---|
| java.util.HashSet<Int> | 9.3 KB | 851 KB | 9.2 MB | 88.7 MB |
| CompactSet<Int> | 4 KB | 40 KB | 0.4 MB | 4 MB |
For primitive types, memory saving is achieved mostly by getting rid of Entry elements
(that come with headers and references) and storing elements in plain arrays.
Measurements were done using JOL, 64-bit HotSpot VM, OpenJDK11, Kotlin 1.5
Contributing
Project is built by gradle wrapper shipped in the repository
./gradlew clean build
Build requirements:
- OpenJDK >11
