v6.0.0
·
14 commits
to master
since this release
Immutable
release. Only release title and notes can be modified.
Almost a year in the making and counting, Kiddo v6 is effectively a full rewrite, addressing some
long-standing issues.
- V6 represents a fundamental shift to a unified single
KdTreestruct, replacing the previous
mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has
been removed by introducing theLeafStrategytrait, which theKdTreehas as a generic parameter.
LeafStrategies can be mutable or immutable. KdTreeis also now generic over the newStemStrategytrait too. The combination of these two
orthogonal traits allow experimentation and selection of alternative stem layouts and traversal
mechanisms, alongside configurable leaf strategies, for performance experimentation.- The query API has been refactored from a handful of separate methods that were not particularly
cohesive into a single unified fluent builder API. The builder approach is much more orthogonal,
and protects against breaking changes when new options are introduced in the future. It permits
constraints to be encoded in the type system for impossible option combinations, prevents the need
for as many methods that differ only by some combination of features; allowing for configurable
result type projection, query types, and query configurations with defaults that match the v5-era
separate methods. - Some of the other new features added include configurable boundary-inclusivity, periodic boundary
conditions, thewithin_unsorted_visitresult mode to avoid materialization of results,TryFrom
for converting between differentKdTreetypes,new_from_source, andreplace_item. - Distance metric coverage has also been expanded and tidied up, including the addition of Chebyshev
and Minkowski metrics and support for queries whose result type is wider than the
stored coordinate type, which is especially important for fixed-point trees. - With regard to the Stem Strategy trait system, alongside the Eytzinger ordering from v5 and prior
is still available but now supports configurable prefetch behaviour. I've introduced the new
Donnelly stem ordering via a family of stem strategies, featuring configurable pre-fetch and block size,
unrolled traversal, SIMD descent, and full SIMD pruning and backtracking variants. The SIMD variant
contains custom AVX2, AVX512, and NEON kernels.
🐛 Bug Fixes
- Preserve mutable leaf split associations (@sdd)