bitvector-jvm

Build-time code-execution for java, a bit like bitvector in C++11

License

License

Categories

Categories

Net
GroupId

GroupId

net.onedaybeard.bitvector
ArtifactId

ArtifactId

bitvector-jvm
Last Version

Last Version

0.1.4
Release Date

Release Date

Type

Type

jar
Description

Description

bitvector-jvm
Build-time code-execution for java, a bit like bitvector in C++11

Download bitvector-jvm

How to add to project

<!-- https://jarcasting.com/artifacts/net.onedaybeard.bitvector/bitvector-jvm/ -->
<dependency>
    <groupId>net.onedaybeard.bitvector</groupId>
    <artifactId>bitvector-jvm</artifactId>
    <version>0.1.4</version>
</dependency>
// https://jarcasting.com/artifacts/net.onedaybeard.bitvector/bitvector-jvm/
implementation 'net.onedaybeard.bitvector:bitvector-jvm:0.1.4'
// https://jarcasting.com/artifacts/net.onedaybeard.bitvector/bitvector-jvm/
implementation ("net.onedaybeard.bitvector:bitvector-jvm:0.1.4")
'net.onedaybeard.bitvector:bitvector-jvm:jar:0.1.4'
<dependency org="net.onedaybeard.bitvector" name="bitvector-jvm" rev="0.1.4">
  <artifact name="bitvector-jvm" type="jar" />
</dependency>
@Grapes(
@Grab(group='net.onedaybeard.bitvector', module='bitvector-jvm', version='0.1.4')
)
libraryDependencies += "net.onedaybeard.bitvector" % "bitvector-jvm" % "0.1.4"
[net.onedaybeard.bitvector/bitvector-jvm "0.1.4"]

Dependencies

provided (1)

Group / Artifact Type Version
org.jetbrains.kotlin : kotlin-stdlib-jre8 jar 1.1.3

test (2)

Group / Artifact Type Version
org.jetbrains.kotlin : kotlin-test jar 1.1.3
junit : junit jar 4.12

Project Modules

There are no modules declared in this project.

Build Status

BitVector

  • Uncompressed, dynamically resizeable bitset, similar to java.util.BitSet
  • Fast-ish enumeration of set bits (JS not yet profiled)
  • Compatible with JavaScript and JVM/Android backends

The gist

Constructing

val bv: BitVector = bitsOf(1, 2, 56, 64, 128, 129, 130, 131, 420)

Individual bits

val bv = BitVector()
bv[142] = true // or bv.set(142)
assert(142 in bv)

bv.clear(142)  // or bv[142] = false
assert(142 !in bv)

or, and, andNot, xor

As with java.util.BitSet, these operations mutate the callee. Do a copy() if the original BitVector needs to stick around.

These functions are not infix functions, as such syntax would suggest a value copy.

val a = bitsOf(0, 1, 2, 3, 120,                130)
val b = bitsOf(0, 1, 2,    120, 121, 122, 123, 130)

assert(a.and(b) == bitsOf(0, 1, 2, 120, 130))

// caveat: bitvector was mutated above
assert(a == bitsOf(0, 1, 2, 120, 130))

vs other BitVectors

// 1, 4 contained in other 
bitsOf(1, 4) in bitsOf(0, 1, 4, 5, 6) 

Looping over bits: fast way

bitsOf(*bits).forEachBit { println("bit $it says hi") }

Looping over bits: Iterable

// can be combined with filter/map etc
bitsOf(*bits).forEach { println("bit $it says hi") }

Getting Started

Maven: JVM/Android

<dependency>
	<groupId>net.onedaybeard.bitvector</groupId>
	<artifactId>bitvector-jvm</artifactId>
	<version>0.1.4</version>
</dependency>

Maven: JavaScript

<dependency>
	<groupId>net.onedaybeard.bitvector</groupId>
	<artifactId>bitvector-js</artifactId>
	<version>0.1.4</version>
</dependency>

Gradle: JVM/Android

  dependencies { compile "net.onedaybeard.bitvector:bitvector-jvm:0.1.4" }

Gradle: JavaScript

  dependencies { compile "net.onedaybeard.bitvector:bitvector-js:0.1.4" }

JVM Benchmarks / enumerating set bits

Mapping true bit positions into integers, inserting each into an IntBag (thin wrapper around int[]).

artemis-odb's BitVector was the basis for this implementation. The benchmark setup favors the artemis implementation, as it provides an optimized toIntBag method: it serves as a reference for best possible performance.

See jmh-logs for the full logs.

benchmark.png

Discrepancy to artemis' BitVector is unwelcome. The implementation is for the most part the same, except that this implementation uses int for words, instead of long. 4 or 8 byte words did not have a significant impact on performance.

The for-loop performs poorly due to all the Integer boxing, extra indirection and allocation, compared to forEachBit.

java.util.BitSet suffers from not having a way of enumerating all bits at once, instead relying on repeatedly calling nextSetBit.

Tests

Verifying platform-specific implementations

mvn clean install -P impltest

Running JS tests

Build project, mvn clean install, then point the browser to file://$PROJECT_ROOT/js/target/test-classes/index.html

Versions

Version
0.1.4
0.1.3