Capsule - The Capsule Hash Trie Collections Library

  •        49

Capsule aims to become a full-fledged (immutable) collections library for Java 8+ that is solely built around persistent tries. The library is designed for standalone use and for being embedded in domain-specific languages. Capsule still has to undergo some incubation before it can ship as a well-rounded collection library. Nevertheless, the code is stable and performance is solid.

The standard libraries of recent Java Virtual Machine languages, such as Clojure or Scala, contain scalable and well-performing immutable collection data structures that are implemented as Hash-Array Mapped Tries (HAMTs). HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts.

We introduce CHAMP (Compressed Hash-Array Mapped Prefix-tree), an evolutionary improvement over HAMTs. The new design increases the overall performance of immutable sets and maps. Furthermore, its resulting general purpose design increases cache locality and features a canonical representation.

https://github.com/usethesource/capsule

Tags
Implementation
License
Platform

   




Related Projects

Immutable-js - Immutable persistent data collections for Javascript which increase efficiency and simplicity

  •    Javascript

Immutable data cannot be changed once created, leading to much simpler application development, no defensive copying, and enabling advanced memoization and change detection techniques with simple logic. Persistent data presents a mutative API which does not update the data in-place, but instead always yields new updated data.

Paguro - Immutable Collections and Functional Transformations for the JVM

  •    Java

Immutable Clojure collections and a Transformation abstraction for Java 8+, immutably, type-safely, and with good performance. It provide support for RRB Tree, which is an immutable List (like Clojure's PersistentVector) that also supports random inserts, deletes, and can be split and joined back together in logarithmic time.

PCollections - A Persistent Java Collections Library

  •    Java

A Persistent Java Collections Library. PCollections serves as a persistent and immutable analogue of the Java Collections Framework. This includes efficient, thread-safe, generic, immutable, and persistent stacks, maps, vectors, sets, and bags, compatible with their Java Collections counterparts.

pyrsistent - Persistent/Immutable/Functional data structures for Python

  •    Python

Pyrsistent is a number of persistent collections (by some referred to as functional data structures). Persistent in the sense that they are immutable. All methods on a data structure that would normally mutate it instead return a new copy of the structure containing the requested updates. The original structure is left untouched.

immutable-js - Immutable persistent data collections for Javascript which increase efficiency and simplicity

  •    Javascript

Immutable data cannot be changed once created, leading to much simpler application development, no defensive copying, and enabling advanced memoization and change detection techniques with simple logic. Persistent data presents a mutative API which does not update the data in-place, but instead always yields new updated data. Immutable.js provides many Persistent Immutable data structures including: List, Stack, Map, OrderedMap, Set, OrderedSet and Record.


bifurcan - impure functional data structures

  •    Java

This library provides high-quality Java implementations of mutable and immutable data structures, each sharing a common API. Rather than using the existing collection interfaces in java.util such as List or Map, it provides its own interfaces (IList, IMap, ISet) that provide functional semantics - each update to a collection returns a reference to a new collection.

immutable - Immutable collections for Go

  •    Go

This repository contains immutable collection types for Go. It includes List, Map, and SortedMap implementations. Immutable collections can provide efficient, lock free sharing of data by requiring that edits to the collections return new collections. The collection types in this library are meant to mimic Go built-in collections such asslice and map. The primary usage difference between Go collections and immutable collections is that immutable collections always return a new collection on mutation so you will need to save the new reference.

icepick - Utilities for treating frozen JavaScript objects as persistent immutable collections

  •    Javascript

Utilities for treating frozen JavaScript objects as persistent immutable collections. Object.freeze() is a quick and easy way to get immutable collections in plain JavaScript. If you recursively freeze an object hierarchy, you have a nice structure you can pass around without fear of mutation. The problem is that if you want to modify properties inside this hierarchical collection, you have to return a new copy with the properties changed.

immutable-devtools - Chrome Dev Tools custom formatter for Immutable-js values

  •    Javascript

The Immutable library is fantastic, but inspecting immutable collections in Chrome's Dev Tools is awkward. You only see the internal data structure, not the logical contents. For example, when inspecting the contents of an Immutable List, you'd really like to see the items in the list.Chrome (v47+) has support for custom "formatters". A formatter tells Chrome's Dev Tools how to display values in the Console, Scope list, etc. This means we can display Lists, Maps and other collections, in a much better way.

list - 🐆 An immutable list with unmatched performance and a comprehensive functional API.

  •    TypeScript

A fast immutable list with a functional API. List is a purely functional alternative to arrays. It is an implementation of a fast persistent sequence data structure. Compared to JavaScript's Array List has three major benefits.

gs-collections - A supplement or replacement for the Java Collections Framework

  •    Java

GS Collections is a collections framework for Java. It has JDK-compatible List, Set and Map implementations with a rich API and set of utility classes that work with any JDK compatible Collections, Arrays, Maps or Strings. The iteration protocol was inspired by the Smalltalk collection framework. It provides replacements for ArrayList, HashSet, and HashMap optimized for performance and memory usage.

transducers

  •    Javascript

A small library for generalized transformation of data. This provides a bunch of transformation functions that can be applied to any data structure. It is a direct port of Clojure's transducers in JavaScript. Read more in this post. The algorithm behind this, explained in the above post, not only allows for it to work with any data structure (arrays, objects, iterators, immutable data structures, you name it) but it also provides better performance than other alternatives such as underscore or lodash. This is because there are no intermediate collections. See this post for benchmarks.

rpds - Rust Persistent Data Structures

  •    Rust

Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Your classic functional list.

immer - Postmodern immutable and persistent data structures for C++

  •    C++

immer is a library of persistent and immutable data structures written in C++. These enable whole new kinds of architectures for interactive and concurrent programs of striking simplicity, correctness, and performance. In the last few years, there has been a growing interest in immutable data structures, motivated by the horizontal scaling of our processing power and the ubiquity of highly interactive systems. Languages like Clojure and Scala provide them by default, and implementations for JavaScript like Mori and Immutable.js are widely used, specially in combination with modern UI frameworks like React.

Redisson - Redis based In-Memory Data Grid for Java

  •    Java

Redisson - distributed Java objects and services (Set, Multimap, SortedSet, Map, List, Queue, BlockingQueue, Deque, BlockingDeque, Semaphore, Lock, AtomicLong, Map Reduce, Publish / Subscribe, Bloom filter, Spring Cache, Executor service, Tomcat Session Manager, Scheduler service, JCache API) on top of Redis server. Rich Redis client.

Eclipse Collections - Best Java Collection Framework

  •    Java

Eclipse Collections is a collections framework for Java. It has JDK-compatible List, Set and Map implementations with a rich API, additional types not found in the JDK like Bags, Multimaps, and set of utility classes that work with any JDK compatible Collections, Arrays, Maps, or Strings. The iteration protocol was inspired by the Smalltalk collection framework. It maximizes the power of Java 8 Lambda expressions and method references with rich APIs directly available on your collections.

immu - A TINY, fail-fast, lazy, immutable Javascript objects library.

  •    Javascript

A TINY, fail-fast, lazy, "naked", simple immutable Javascript objects library. Immu does not attempt to add functionality to Arrays, introduce complex data structures like Map and Set, or provide a complete solution with cursors and stores. Immu is meant to be the simplest possible solution to providing immutable objects while maintaining the native API for those objects (including Array methods).