Skip to content

LayerKeySort v4.0.0-preview.1

Pre-release
Pre-release

Choose a tag to compare

View all tags
@RXY712200 RXY712200 released this 05 Oct 16:00
v4.0.0-preview.1
21b2902

LayerKeySort v4.0.0-preview.1

This is an experimental V4 prerelease. For normal use, prefer stable v3.1.0.

V4 Preview.1 is the first production implementation of the new V4 architecture. It introduces the explicit live-order core while intentionally keeping the existing V3 APIs available alongside it.

New V4 live-order core

Preview.1 adds provisional LksOrder and LksOrderHandle APIs for:

  • front/back insertion
  • insert before/after a resident handle
  • exact removal
  • first/last/next/previous traversal
  • borrowed item access
  • contextual order comparison

Resident handles are stable while resident. They survive local shifts, block splits, redistribution, merges and AVL rotations. Removal or container destruction invalidates them.

Handles are not Paths, persistent IDs, serialization keys or standalone ordering coordinates.

New architecture

V4 live order no longer maintains a globally sortable Path for every resident item.

The core uses:

  • bounded blocks with capacity 128
  • local resident-pointer arrays
  • an implicit AVL ordering the blocks
  • subtree block counts
  • threaded block neighbors
  • stable separately allocated resident records

Global logical order is the concatenation of block order and local order.

Ordinary insertion performs bounded local maintenance and at most one block split. Removal performs bounded neighboring merge or redistribution. There is no global resident-coordinate rewrite, relabel pass, deferred maintenance backlog or cascading split.

Why V4 changes direction

V3 research found that large synchronous coordinate relabels, recurring rewrite work and Path/LK1 growth formed a significant engineering tradeoff.

V4 separates contextual live order from the future snapshot/export representation instead of requiring every live item to continuously own a standalone serialized sortable coordinate.

Preview.1 implements only the live explicit-order half of that architecture.

Validation

The exact release commit passed the repository's GitHub Actions workflow in all five configurations:

  • Windows MSVC
  • Ubuntu GCC
  • Ubuntu Clang
  • Ubuntu Clang configuration with the repository's enabled checks
  • macOS AppleClang

Local validation additionally included:

  • 120,000 randomized oracle operations across deterministic seeds
  • 388,599 instrumented structural operations
  • adversarial front/back/hotspot/alternating campaigns
  • exact forward and reverse traversal verification
  • handle-stability checks across structural maintenance
  • deterministic allocation-failure sweeps
  • MSVC AddressSanitizer
  • C/C++ source, FetchContent and installed-package consumers
  • reproducible amalgamation/package validation

Observed structural maxima remained bounded by the block architecture. No tested operation triggered a global resident rewrite or deferred maintenance backlog.

These results are validation evidence, not realtime guarantees or final V4 performance acceptance.

Provisional API

V4 Preview.1 adds 14 provisional lks_order_* functions while preserving the existing 59 V3 public functions.

The V4 API is not frozen.

The latest stable release remains v3.1.0.

Deferred to later V4 Previews

Not yet implemented:

  • move-before / move-after
  • comparator-managed V4 ordering
  • snapshots and exported sortable keys
  • persistence/load
  • V3 LK1 migration
  • V4 Group/Batch integration
  • final API/wire-format freeze
  • final performance acceptance

These omissions are intentional Preview.1 scope boundaries.

Documentation

Release-state commit:

21b2902555534d10d97e704161066197cebc13ae

Assets 2
Loading