Core Concepts: Linear vs. Forked Collections

One of Bifurcan's most powerful features is its nuanced approach to mutability, embodied by the concepts of linear and forked collections. This design allows developers to achieve the high performance of mutable data structures without sacrificing the safety and predictability of immutable ones.

The Problem with Pure Immutability

Immutable data structures are freeing. When you pass an immutable collection to a function, you don't have to worry about that function changing it unexpectedly. You can reason about your code locally without needing to understand the entire application's data flow. This freedom, however, comes at a performance cost. Every update requires a portion of the data structure to be copied.

Consider a typical batch update loop with a purely immutable set:

// Inefficient: Creates 999 intermediate, discarded sets
Set<Long> set = new Set<>();
for (long i = 0; i < 1000; i++) {
  set = set.add(i);
}

In this code, 999 intermediate Set objects are created and immediately discarded. There is only ever one reference to the set at any point in the loop. The data flow is a simple, linear chain. In such cases, the overhead of immutability is pure waste.

Bifurcan's Solution: Temporary Mutability

Bifurcan allows you to make a collection temporarily mutable for the duration of a linear chain of operations.

• A forked collection is the default: it's fully immutable and safe to share across multiple references.
• A linear collection has a single owner and can be safely updated in-place.

By switching between these two states, you can optimize performance-critical sections of your code.

Here is the same loop, optimized using linear() and forked():

// Efficient: In-place updates on a linear collection
IMap<Long, Long> map = new Map<Long, Long>().linear(); // Make it mutable

for (long i = 0; i < 1000; i++) {
  map.put(i, i); // All updates happen in-place
}

map = map.forked(); // Make it immutable again before sharing

The call to linear() signals that the collection now has a single owner and can be mutated. The subsequent put() calls modify the collection's internal structure directly. Finally, forked() returns a truly immutable version that can be safely passed around.

Permanently Linear Collections

While the linear()/forked() pattern is powerful, there is still a small overhead compared to a purely mutable data structure. For scenarios where a collection will never be shared, Bifurcan provides permanently linear variants of each collection, such as LinearMap, LinearSet, and LinearList.

// Using a permanently mutable collection
LinearSet<Long> set = new LinearSet<>();
for (long i = 0; i < 1000; i++) {
  set.add(i);
}

These collections offer the best possible performance for single-threaded, mutable workloads and share the same rich API as their immutable counterparts.

By understanding when data flow is linear (single-owner) versus when it forks (multiple owners), you can use Bifurcan's collections to write code that is both highly efficient and easy to reason about.