Bifurcan: persistent Java collections with linear and forked ownership

One API, two flavours, and interfaces that are not java.util

Bifurcan provides high-quality Java implementations of mutable and immutable data structures, each sharing a common API, and the design principles are listed up front: efficient random access, efficient inverted indices where all collections other than lists provide an `indexOf` method, efficient splitting and merging of collections, customizable equality semantics, contiguous memory used wherever possible, and performance equivalent to or better than existing alternatives.

The structural choice is the one that decides everything. Rather than using the existing collection interfaces in `java.util` such as `List` or `Map`, it provides its own interfaces, `IList`, `IMap` and `ISet`, that provide functional semantics, where each update to a collection returns a reference to a new collection.

That last clause is the crux. A `java.util.List` mutates in place, and a caller holding a reference to it sees the change, which is convenient and is the source of a whole category of aliasing bug. A Bifurcan `List` update returns a new collection and leaves the original alone.

Refusing to implement `java.util` interfaces has a cost, and the project is upfront about the escape hatch. Each interface provides a method, `toList`, `toMap` or `toSet`, for coercing the collection to a read-only version of the standard Java interfaces.

So the answer to the obvious objection, that a library not implementing the standard interfaces cannot be passed to code expecting a `List`, is that it can, read-only, and only when you ask. That is a sensible compromise: you keep the interoperability at the boundary and keep the safety inside.

The library is MIT licensed, the language is Java, and the last push was on 2026-10-17 with no GitHub releases, so the version in the dependency snippet is what there is.

The catalogue, from a mutable map to a Unicode rope

The collection list is long and each entry does something a specific job.

`LinearMap` is a mutable hash-map which allows for custom hash and equality semantics. It stores entries contiguously in memory, which the documentation says means iteration over the entries can be 20x faster than `java.util.HashMap` for larger collections. `Map` is the immutable counterpart, and it ensures that all equivalent collections have an equivalent layout in memory, which makes checking for equality and performing set operations significantly faster.

`LinearSet` and `Set` are built atop their respective map implementations and have similar properties.

`LinearList` is a mutable list which allows elements to be added or removed from both ends and allows random reads and writes within the list. `List` is the immutable version, and it is built on a relaxed radix structure, which gives it near constant-time slices and concatenation. That is the property that makes it interesting, because slicing a `java.util.List` is O(n) and slicing a `java.util.LinkedList` is worse.

`SortedMap` is an immutable sorted map built with a red-black tree.

`IntMap` is an immutable sorted map of integers onto arbitrary values and can be used as an efficient sparse vector, with `FloatMap` providing the same for floating-point keys. For anyone doing numeric work with a sparse index, a sorted map of integers is the right structure.

`Rope` is an immutable tree-based sequence of Unicode characters. Unlike Java's `String`, it uses UTF-8 encoding and can efficiently index via both full code points and Java's preferred UTF-16 code units. That double indexing is the point, because a Java `String` is UTF-16 and indexing it by code point means scanning, and a UTF-8 rope indexed by code unit means a scan in the other direction.

And there are graphs: `Graph`, `DirectedGraph` and `DirectedAcyclicGraph`, providing immutable graph data structures.

The full documentation is published under the io.lacuna.bifurcan package summary.

Linear and forked: making ownership a local property

This is the idea in the library that is worth understanding properly, and the documentation explains it in terms of dataflow.

The problem starts with mutable structures. If we pass a mutable data structure into a function, we have to know what that function intends to do with it. If it updates the data structure, we cannot safely read from it afterwards. If it stores the data structure, we cannot safely write to it afterwards. In other words, to use a mutable data structure safely we must ensure it has a single owner, and enforcing this may require us to hold a large amount of code in our head at once.

Immutable data structures free us from having to care. Functions can update or hold onto data without any risks, and we can reason locally about the flow of data without any care for what the rest of the code is doing. The documentation calls this enormously freeing.

The cost is that updates to immutable structures require a subset of the structure to be copied, which is much more expensive than overwriting existing memory. And if a data structure is referenced in multiple places, that is usually a cost worth paying. But if it is not, it is just wasteful:

Set<Long> set = new Set<>();
for (int i = 0; i < 1000; i++) {
  set = set.add(i);
}

This creates 999 intermediate copies of the set, none of which we care about. There is only a single reference to each copy and each is discarded as soon as `add()` is called, and the dataflow of these calls forms a simple, linear chain. To have more than one reference, the dataflow must diverge.

So the rule follows: where the dataflow is linear, we can safely use mutable collections, and where it is not, we prefer immutable collections. And since this linear flow is a local property, mutability should also be a local property:

Set<Long> set = new Set<>().linear();
for (int i = 0; i < 1000; i++) {
  set.add(i);
}
set = set.forked();

The call to `linear()` indicates that the collection has a single owner and may be updated in place. The call to `forked()` indicates that this is no longer true, and the set becomes immutable from that point.

This is a genuinely different design from the usual choice, where a collection is either mutable or immutable and the decision is made at the type level and inherited everywhere. Here the same type starts linear and becomes forked, so the point at which the safety guarantee changes is a single call in the code, visible at the call site, and it can change again later if the dataflow diverges again. The cost, as the documentation notes, is still a cost relative to purely mutable data structures, but it is paid only where it is needed.

Batch operations and generative testing

The performance claim is specific and the project explains how it is validated.

As shown in the in-depth comparisons referenced in the documentation, Bifurcan's performance is equivalent to the best existing implementations for basic operations, and significantly better for batch operations such as `union`, `intersection` and `difference`.

The reason for that advantage is stated without false modesty. These optimized batch operations require a high degree of complexity and are difficult to test, so it is understandable other library authors have not bothered. Bifurcan relies on extensive generative tests to validate its implementation, which the documentation says makes this additional complexity easier to manage.

The generative tests are the interesting bit, and the link points at a Clojure file, `collection_test.clj`, in the test tree. So the test suite is written in Clojure, and it is property based, generating collections and checking invariants rather than checking fixed expected values. That is the right way to test a structure whose whole selling point is that equivalent collections have equivalent layouts, since a layout invariant is a property and a property is what you can generate.

The repository layout is a bit unusual for a Java library, and it explains the Clojure. There is a `project.clj` at the top level, which is the Leiningen project file, and the source is under `src/` with tests under `test/`. There is also a `benchmarks/` directory, a `doc/` directory with the comparison document and the image of the labyrinth that the README opens with, and a `.travis.yml` for continuous integration.

So the build and test toolchain is Clojure and Leiningen rather than Maven or Gradle, and the artifact is published to Maven Central, since the dependency snippet in the README is a standard Maven coordinate with the groupId `io.lacuna`, the artifactId `bifurcan` and the version `0.2.0-rc1`.

That the version is a release candidate is worth flagging, and the changelog at the top of the repository is where to look for what is still moving.

Where Bifurcan is the wrong choice

There are two clear reasons not to reach for this, and one of them is about scale rather than features.

The first is that the API is not java.util. Every collection you pass to a library that expects a `java.util.List` has to be coerced with `toList()`, and the coerced version is read-only. So a Bifurcan collection cannot be handed to code that mutates it, and it cannot be used with most of the JDK API that takes a `List` and sorts it or reverses it in place. For a codebase that lives and dies on interop with existing code, that friction is the dominant cost, and it is a cost paid at every call site rather than once.

The second is that the immutable variants are not free. The documentation is clear that updates require a subset of the structure to be copied, and that this is much more expensive than overwriting memory. A `linear()` and `forked()` discipline mitigates that where the dataflow is local, but it only works if the discipline is actually followed, and a codebase that forks a collection early and keeps using it pays the copying cost without the safety benefit.

The third is the size of the commitment. Adopting Bifurcan is not adding a dependency, it is changing the collection types used throughout a module, with a different update discipline, a different exception behaviour to learn, and a different set of types for every colleague to read. That is worth it in a codebase where aliasing bugs are a recurring cost. It is not worth it in a codebase that merely wants a `HashMap` that happens to be persistent.

The alternatives are worth naming, and they are strong. The JDK's own `java.util` collections are the default, and for most workloads they are the right answer. Immutable collections libraries for the JVM exist and cover the persistent case with a smaller API surface. And for the specific structures where Bifurcan claims a real advantage, there are focused libraries, an off-the-shelf persistent map for the persistent map case, a rope implementation for the text case.

The difference in approach is that Bifurcan bundles the whole catalogue behind one API with one ownership discipline, and that the inverted indices, the `indexOf` on non-list collections, and the contiguous memory layout are designed together rather than added per structure. If you need one of those specific properties, that is the argument for it. If you need a persistent map, a smaller library is less to learn and less to maintain.

On maintenance, the repository is not archived, the last push was on 2026-10-17, the licence is MIT and there are no GitHub releases, so the version you get is the one in the Maven coordinate and the changelog is where the movement is recorded.

Editorial conclusion

Bifurcan fits a Java codebase that has outgrown java.util and wants persistent collections in the places where aliasing bites, because the same API covers mutable and immutable versions and because the linear and forked distinction lets a hot loop mutate in place without giving up the guarantee elsewhere. Skip it if your problem is solved by java.util, since adopting a new collection API is a cost with no return until the workload justifies it, and note the version, since the dependency snippet in the project documentation is `0.2.0-rc1`, a release candidate rather than a stable release. Before you commit, read the in-depth comparison in the project's doc directory, and check the `indexOf` methods across the non-list collections, since the inverted indices are the feature Bifurcan claims as unique and the reason to choose it over a generic persistent map.

Frequently asked questions

Official sources

1. Issues
2. lacuna/bifurcan on GitHub
3. License: MIT
4. README