Skip to content

Releases: dco-dev/ordered-collections

Specialized Ropes and Core Optimizations

17 Apr 18:41
cd29c14

Choose a tag to compare

Two new collection types

  • string-rope — persistent chunked text backed by java.lang.String chunks. Implements java.lang.CharSequence, so it drops into re-find / re-seq / re-matches, clojure.string, and any Java
    API expecting text. #string/rope "…" EDN tag, content-based equality with String, String.hashCode-compatible. Constructors: string-rope, string-rope-concat. Up to ~38× faster than
    String at 100K characters on random structural edits, growing to ~130× at 500K.
  • byte-rope — persistent chunked binary backed by byte[] chunks. Unsigned [0, 255] semantics exposed as long, unsigned lexicographic Comparable via Arrays.compareUnsigned, #byte/rope
    "hex" EDN tag. Framed as persistent memory: structural editing, zero-cost snapshots, structure sharing. Extras: byte-rope-bytes, -hex, -write, -input-stream, -get-byte/-short/-int/-long
    (with -le variants), -index-of, streaming -digest through MessageDigest. At 500K: ~110× vs byte[] on splice, ~128× on remove.

Rope kernel: one kernel, three variants

  • PRopeChunk protocol extracted into kernel/chunk.clj with extensions for APersistentVector, String, and byte[]. The rope kernel is now honestly chunk-protocol-parameterized — concat /
    split / splice / reduce / fold / CSI maintenance are written once.
  • Per-variant CSI — each rope variant declares its own +target-chunk-size+ / +min-chunk-size+ and binds them via its with-tree macro into the kernel's dynamic vars. All three variants
    default to 1024/512 after lein bench-rope-tuning sweep (up from 256/128).
  • Flat-mode optimization — a rope under its per-variant flat threshold (1024 elements) stores content directly as the natural collection (PersistentVector, String, byte[]), with zero
    tree overhead and transparent promotion on edits. Memory parity with the raw baseline.
  • Monomorphic nth / reduce — each variant inlines the tree walk with direct chunk-type calls, bypassing PRopeChunk dispatch on hot paths. ~2–2.6× faster nth, ~1.7–3.3× faster reduce.
  • Cursor cache removed — the volatile-mutable field set on StringRope/ByteRope had torn-read races (three volatile writes aren't atomic as a group) and cache thrashing under concurrent
    access. Monomorphic walk is fast enough that the cache's benefit didn't justify the thread-safety cost.
  • rope-splice-inplace fused single-chunk splice path avoids an intermediate chunk allocation on the overflow path.
  • RopeSeq / RopeSeqReverse moved out of the kernel into types/rope.clj — they were only used by the generic Rope deftype. Kernel drops ~220 lines.

Performance pass (late in cycle)

  • Primitive rank for long-ordered-* / string-ordered-*. rank-of / indexOf now dispatch through the same primitive-specialized pattern already used for contains / find / find-val.
    node-rank-long, node-rank-string added. string-ordered-set rank ~1.9× faster; long-ordered-set rank at parity (the LongComparator was already HotSpot-inlined).
  • Range-map bulk construction. (range-map coll) with sorted disjoint input now takes an O(n) balanced-build path via tree/node-build-sorted. Overlapping input still falls through to the
    general carving path, preserving "later wins" semantics. ~10× faster than the previous per-insert path; ~2× faster than Guava TreeRangeMap bulk put.
  • Non-allocating java.util.Iterator for OrderedSet / OrderedMap via tree/NodeIterator. Advances the enumerator in place with unsynchronized-mutable state, matching
    clojure.lang.SeqIterator's memory model — thread-safety contract unchanged (per-call fresh, not shared). Java iteration is ~2× faster than sorted-set and ~3.6× faster than data.avl.

0.2.0: Ropes and Ordered Collections

08 Apr 20:00
c3c9c82

Choose a tag to compare

Merge pull request #16 for version 0.2.0

Performance, Ordered Collections release