succinctly

High-performance succinct data structures for Rust.

Succinctly provides space-efficient data structures with fast rank and select operations, optimized for both x86_64 (with AVX2/AVX-512) and ARM (NEON) architectures. The library is no_std compatible and designed for high-throughput applications.

Features

• Bitvector with O(1) rank and O(log n) select - Poppy-style 3-level directory with ~3% space overhead
• Balanced parentheses for tree navigation - RangeMin structure with O(1) operations and ~6% overhead
• JSON semi-indexing with SIMD acceleration - Up to 950 MiB/s throughput on x86_64 (AMD Zen 4) with table-driven PFSM parser
• YAML semi-indexing - Complete YAML 1.2 parser with anchor/alias resolution (~250-400 MiB/s)
• DSV/CSV semi-indexing - High-performance CSV/TSV parsing (85-1676 MiB/s) with BMI2 acceleration
• jq/yq-style query expressions - Navigate JSON and YAML without full parsing
• no_std compatible - Works in embedded and WASM environments
• Cross-platform SIMD - Runtime detection for AVX2, AVX-512, SSE4.2, and ARM NEON

Installation

Add to your Cargo.toml:

[dependencies]
succinctly = "0.2"

Or with cargo:

cargo add succinctly

Quick Start

Bitvector with Rank/Select

use succinctly::{BitVec, RankSelect};

// Create a bitvector from u64 words
let words = vec![0b1010_1010_1010_1010u64; 8];
let bv = BitVec::from_words(words, 512);

// Query rank (count of 1-bits in [0, i))
assert_eq!(bv.rank1(8), 4);

// Query select (position of k-th 1-bit, 0-indexed)
assert_eq!(bv.select1(0), Some(1));  // First 1-bit is at position 1
assert_eq!(bv.select1(3), Some(7));  // Fourth 1-bit is at position 7

Balanced Parentheses for Tree Navigation

use succinctly::bp::BalancedParens;

// Encode a tree as balanced parentheses: ((()())())
// In bits: 1=open, 0=close -> 1110100100
let bp = BalancedParens::new(&[0b0010010111], 10);

// Find matching close parenthesis
assert_eq!(bp.find_close(0), Some(9));  // Outermost pair
assert_eq!(bp.find_close(1), Some(6));  // Second level

// Navigate the tree
assert_eq!(bp.first_child(0), Some(1));   // First child of root
assert_eq!(bp.next_sibling(1), Some(7));  // Sibling of first child

JSON Semi-Indexing

use succinctly::json::{JsonIndex, StandardJson};

let json = br#"{"users": [{"name": "Alice"}, {"name": "Bob"}]}"#;
let index = JsonIndex::build(json);
let root = index.root(json);

// Navigate without parsing the entire document
if let StandardJson::Object(obj) = root {
    if let Some(StandardJson::Array(users)) = obj.get("users") {
        // Iterate array elements
        for user in users {
            // Access nested fields efficiently
        }
    }
}

jq-Style Queries

use succinctly::jq::{parse, eval, QueryResult};
use succinctly::json::{JsonIndex, StandardJson};

let json = br#"{"users": [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]}"#;
let index = JsonIndex::build(json);
let cursor = index.root(json);

// Get all user names
let expr = parse(".users[].name").unwrap();
if let QueryResult::Many(names) = eval(&expr, cursor) {
    // names contains ["Alice", "Bob"]
}

// Get first user's age
let expr = parse(".users[0].age").unwrap();
if let QueryResult::One(StandardJson::Number(age)) = eval(&expr, cursor) {
    assert_eq!(age, 30.0);
}

Performance

Comparison with Rust JSON Parsers

Benchmark comparing succinctly against popular Rust JSON libraries (x86_64, 1MB file):

Key findings:

• 18-46x less memory than DOM parsers (consistent 46% overhead vs JSON size)
• Competitive parsing speed: Only 1.6x slower than fastest DOM parser
• 3-5x faster than serde_json and simd-json

See docs/benchmarks/rust-parsers.md for detailed benchmarks across all file sizes.

JSON Semi-Indexing

Rank/Select Operations

jq Comparison: Identity Operation (.)

Comparison of succinctly jq . vs jq . for formatting/printing JSON files.

x86_64 (AMD Ryzen 9 7950X, 10MB files)

ARM (Apple M1 Max, 10MB files)

Key findings:

• 1.2-6.3x faster across all patterns
• 5-25x less memory on most patterns due to streaming lazy evaluation
• Best speedup on nested/string-heavy data

Platform-Specific Optimizations

See docs/benchmarks/rust-parsers.md, docs/benchmarks/jq.md, and docs/optimizations/history.md for detailed benchmarks.

Feature Flags

Popcount Strategies (mutually exclusive)

Other Features

Test Features

CLI Tool

The library includes CLI tools for JSON, YAML, and DSV operations:

# Build the CLI
cargo build --release --features cli

# Generate synthetic JSON/YAML for benchmarking
./target/release/succinctly json generate 10mb -o benchmark.json
./target/release/succinctly yaml generate 10kb -o benchmark.yaml

# Query JSON files (jq-compatible)
./target/release/succinctly jq '.users[].name' input.json
./target/release/succinctly jq -r '.users[0]' input.json

# Query YAML files (yq-compatible)
./target/release/succinctly yq '.users[].name' config.yaml
./target/release/succinctly yq -o json '.' config.yaml          # Output as JSON
./target/release/succinctly yq '.spec.containers[]' k8s.yaml
./target/release/succinctly yq --doc 0 '.' multi-doc.yaml       # First document only

# Query CSV/TSV files (converted to JSON on-the-fly)
./target/release/succinctly jq --input-dsv ',' '.[] | .[0]' users.csv
./target/release/succinctly jq --input-dsv '\t' '.[0]' data.tsv

# Output as CSV/TSV/DSV
./target/release/succinctly jq -r '.users[] | [.name, .age] | @csv' data.json
./target/release/succinctly jq -r '.users[] | [.name, .age] | @dsv("|")' data.json
./target/release/succinctly yq -r '.users[] | [.name, .age] | @csv' data.yaml

# Find jq/yq expression for a position (useful for editor integration)
./target/release/succinctly jq-locate input.json --offset 42
./target/release/succinctly jq-locate input.json --line 5 --column 10
./target/release/succinctly yq-locate config.yaml --offset 42
./target/release/succinctly yq-locate config.yaml --line 5 --column 10

Architecture

Module Structure

succinctly
├── bits         # Bitvector with rank/select
├── trees        # Tree encodings (balanced parentheses)
├── json         # JSON semi-indexing
├── yaml         # YAML semi-indexing
├── dsv          # DSV/CSV semi-indexing
└── jq           # jq/yq query language evaluator

Core Data Structures

• bits::BitVec - Bitvector with 3-level Poppy-style rank directory (~3% overhead) and sampled select index (~1-3% overhead)
• trees::BalancedParens - Hierarchical min-excess structure for O(1) tree navigation (~6% overhead)
• json::JsonIndex - Semi-index combining Interest Bits (IB) and Balanced Parentheses (BP) for fast JSON navigation
• yaml::YamlIndex - YAML semi-index with anchor/alias resolution and multi-document support
• dsv::DsvIndex - Lightweight DSV semi-index with BMI2-accelerated quote masking

SIMD Support

The library uses runtime CPU feature detection to select the best implementation:

Documentation

Choose your path:

• New to succinctly? -> Getting Started
• Using the library? -> API Guide
• Using the CLI? -> CLI Guide
• Contributing? -> CONTRIBUTING.md
• Performance tuning? -> Optimization Techniques
• Understanding internals? -> Architecture
• Benchmarks? -> Performance Comparisons
• Full documentation map -> docs/

For AI-assisted development, see CLAUDE.md.

Contributing

Contributions are welcome! Please see CONTRIBUTING.md for guidelines.

Before submitting a PR:

# Run tests
cargo test

# Run clippy
cargo clippy --all-targets --all-features -- -D warnings

# Format code
cargo fmt

License

Licensed under the MIT license.

Acknowledgments

This library implements algorithms from:

• Vigna, "Broadword Implementation of Rank/Select Queries" (WEA 2008)
• Zhou, Andersen, Kaminsky, "Space-Efficient, High-Performance Rank & Select" (SEA 2013)
• Sadakane & Navarro, "Fully-Functional Succinct Trees" (SODA 2010)
• Langdale & Lemire, "Parsing Gigabytes of JSON per Second" (VLDB 2019)
• Muła, Kurz, Lemire, "Faster Population Counts Using AVX2 Instructions" (2016)

Related Work

• haskell-works - Haskell implementations of the same techniques (hw-json, hw-json-simd, hw-rankselect, hw-balancedparens)