LayerKeySort v3.0.0-preview.2

LayerKeySort v3.0.0-preview.2

Experimental V3 prerelease. For normal use, prefer stable v2.0.0. V3 APIs, generated coordinates, and private placement policies remain provisional.

Endpoint coordinate optimization

Preview.1 established separate manual LksTree and comparator-bound LksOrderedTree APIs, with Path-keyed AVL indexing and logical coordinate relabeling. Preview.2 improves repeated managed endpoint insertion. It carries a saturated slot into an available Path ancestor, uses a one-slot stride after a sustained endpoint run, and allows valid direct endpoint Paths through private depth 16 before attempting relabel. Interior insertion retains adaptive geometric logical-window relabeling. No physical replacement-Tree rebuild was reintroduced.

Final endpoint-policy audit

The original Preview.2 candidate used direct endpoint depth eight. At ascending insertion 261,579 it successfully generated a valid depth-nine Path, but the private threshold alone triggered a full-range relabel of 261,578 existing nodes. The final depth-16 policy removes this particular 300k cliff.

Depth 16 is a provisional engineering tradeoff, not a public contract or mathematical optimum. Depth 12 still caused repeated relabels. Removing the depth trigger entirely avoided relabels in the tested monotone range but produced substantially deeper Paths and higher peak memory. A size-dependent limit added complexity and used more memory than depth 16 at one million items.

Performance and tradeoffs

On the documented test machine, the independent final-source ascending insertion medians were 54.574 ms at 100k, 339.946 ms at 300k, 889.976 ms at 500k, and 2,580.855 ms at 1m. All-equal append medians were 55.956 ms at 100k and 355.181 ms at 300k. These are workload measurements, not universal speed claims.

The matched depth-eight/depth-16 policy audit exposes a real regression at 500k ascending: 749.108 ms versus 882.634 ms. At 1m ascending, depth eight performed four full-range relabels of 2,487,584 old nodes in total; depth 16 performed one of 523,722 old nodes. The depth-16 final mean/P95/P99/maximum Path depths were 6.173/14/15/16, with 165,980,120 peak live bytes. With no depth trigger they were 15.780/30/31/31, with 288,763,760 peak live bytes.

Detailed methodology and raw results: benchmark report, final-source timings, and matched policy audit.

Complexity and remaining limits

Comparator upper-bound search visits O(log n) AVL nodes, excluding comparator cost. Direct insertion also creates or copies a Path in work proportional to relevant Path depth and rebalances the AVL. Adaptive relabel processes and generates replacement Paths for a logical region of k old nodes; k can equal n. Geometric expansion controls cumulative region scanning relative to the final attempted region, while Path construction also depends on depth. At 1m ascending, Preview.2 still performed one full-range relabel of 523,722 old nodes. Complete managed insertion has no claimed worst-case O(log n) or formal amortized bound.

Validation

The release-state commit passed Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang CI. Each configuration ran CTest 7/7 and both examples. The test suite covers ordered-tree invariants, endpoint and relabel OOM rollback, mutation soak, parser torture, Path/LK1 contracts, and benchmark smoke cases. The release-state commit changes documentation only; the final candidate's larger benchmark and 20-seed soak evidence remains applicable.

Designing beyond the algorithm

V3 development is beginning to treat API clarity, integration, distribution, documentation, migration, and first-use experience as product work. Preview.2 does not complete that work; later V3 Previews may continue it.

Stable release

Stable v2.0.0 remains the recommended release for normal use. Preview.2 is experimental, is not an API freeze, and is not marked GitHub Latest.

Release-state commit: 8e4f0c6a88dbff0c5eebaf00bd24381d4a6c85f9.