Skip to content

Releases: sdd-org/kiddo

Release list

v6.0.1

v6.0.1 Latest
Latest

Choose a tag to compare

View all tags
@sdd sdd released this 10 Aug 11:08
Immutable release. Only release title and notes can be modified.
v6.0.1
7dfd4e9

🐛 Bug Fixes

  • Ensure kibrary compiles for wasm32-unknown-unknown target (@sdd, Fixes:#515)

  • Dispatch the /fuzz command the way /benchmark does (@sdd)

  • Grant the aggregate gate the permissions its called workflows need (@sdd)

  • Chebyshev over-pruning found by fuzz testing (@sdd)

  • Simd block-4 construction panic found by fuzzer (@sdd)

  • Fuzzer-found SIMD backtracking optimisatition correctness issue (@sdd)

  • Fuzz-uncovered construction bug (@sdd)

  • Prevent f32 over-prune found in fuzz test (@sdd)

  • Block-at-once strats now immutable-only (@sdd)

🤖 CI

  • Aggregate required checks into a single PR Mergeable status (@sdd)

  • Run the v6 fuzz suite on demand via a /fuzz comment (@sdd)

🧹 Chore

Assets 3
Loading

v6.0.0

v6.0.0

Choose a tag to compare

View all tags
@sdd sdd released this 03 Aug 11:21
Immutable release. Only release title and notes can be modified.
v6.0.0
810c068

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 KdTree struct, replacing the previous
    mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has
    been removed by introducing the LeafStrategy trait, which the KdTree has as a generic parameter.
    LeafStrategies can be mutable or immutable.
  • KdTree is also now generic over the new StemStrategy trait 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, the within_unsorted_visit result mode to avoid materialization of results, TryFrom
    for converting between different KdTree types, new_from_source, and replace_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)
Loading

v6.0.0-alpha.4

v6.0.0-alpha.4 Pre-release
Pre-release

Choose a tag to compare

View all tags
@sdd sdd released this 27 Jul 01:49
Immutable release. Only release title and notes can be modified.
v6.0.0-alpha.4
dc44732

✨ Features

  • Add result capacity hint for radius queries (@sdd)

  • Add adaptive parallel tree construction (@sdd)

  • Specialize within-radius result projection (@sdd)

🐛 Bug Fixes

  • Handle padded stems in parallel construction (@sdd)

♻️ Refactor

  • Within_unsorted to a visitor (@sdd)

  • Switch from propagating points as indexes to actual values (@sdd)

🧪 Testing

  • Add result collection threshold profiler (@sdd)

  • Add v6 release parity benchmark suites (@sdd)

  • Add point projection benchmark (@sdd)

🤖 CI

  • Add stem strategy benchmark variant (@sdd)

  • Rename basic benchmark variant (@sdd)

  • Pass benchmark features explicitly (@sdd)

  • Cap leaf benchmark tree size (@sdd)

  • Fix leaf benchmark export filter (@sdd)

  • Cap benchmark trees at 2^25 (@sdd)

  • Fix benchmark v5-v6 chart matching (@sdd)

  • Add ISA-specific stem benchmark reporting (@sdd)

  • Add tree construction benchmarks (@sdd)

🧹 Chore

Loading

v5.3.3

v5.3.3

Choose a tag to compare

View all tags
@sdd sdd released this 27 Jul 02:04
Immutable release. Only release title and notes can be modified.
v5.3.3
6da2a42

Ci

  • Don't run comitlint for dependabot PRs
  • Add v5 eytzinger profile benchmarks
  • Split v5 nightly debug and release tests
  • Allow nightly chunks lint at MSRV
  • Stop ignoring the pinned v5 lockfile

🐛 Bug Fixes

  • Correct v5 unsorted nearest-n parity reporting
  • Preserve stem alignment in rkyv conversion
  • Use metric accumulation for immutable nearest one
  • Allow mutable splits past constant axes

🧪 Testing

  • Add v5 release parity benchmark reporting

🧹 Chore

Loading

v6.0.0-alpha.3

v6.0.0-alpha.3 Pre-release
Pre-release

Choose a tag to compare

View all tags
@sdd sdd released this 21 Jul 07:44
Immutable release. Only release title and notes can be modified.
v6.0.0-alpha.3
633e388

✨ Features

  • Make local query scratch the default (@sdd)

🐛 Bug Fixes

  • Remove broken dot product dist metric and associated code (@sdd)

⚡️ Performance

  • Alternate path to avoid wasted calcs on descent (@sdd)

  • Add IS_SIGNED assoc value to Axis (@sdd)

  • Dist1 on Manhattan and Chebyshev use saturating_dist (@sdd)

  • Improved offset update for Chebyshev and Manhattah (@sdd)

  • Use fused linear insertion for threshold vec results (@sdd)

  • Tune sorted and unsorted threshold vec limits (@sdd)

🤖 CI

  • Harden pre-release string updater workflow against no changes (@sdd)

  • Publish custom benchmark reports (@sdd)

  • Add bench chart justfile tasks (@sdd)

  • Fix benchmark workflow bootstrap (@sdd)

  • Derive benchmark key without just (@sdd)

  • Pass benchmark args to just correctly (@sdd)

  • Pass benchmark recipe arguments positionally (@sdd)

  • Authenticate initial benchmark pages push (@sdd)

  • Rank featured chart by relative change (@sdd)

  • Add distance metric ISA matrix (@sdd)

  • Fix distance metric ISA benchmark builds (@sdd)

  • Simplify benchmark workflows (@sdd)

  • Fix benchmark workflow shellcheck (@sdd)

  • Suggest benchmarks for performance-sensitive PRs (@sdd)

  • Use heuristic benchmark suggestions (@sdd)

  • Allow benchmark suggestion comment updates (@sdd)

  • Add leaf strategy benchmark variant (@sdd)

  • Allow org members to trigger benchmark runs (@sdd)

  • Clarify benchmark run names (@sdd)

  • Split nightly debug and release tests (@sdd)

🧹 Chore

Loading

v6.0.0-alpha.2

v6.0.0-alpha.2 Pre-release
Pre-release

Choose a tag to compare

View all tags
@sdd sdd released this 17 Jul 19:11
Immutable release. Only release title and notes can be modified.
v6.0.0-alpha.2
df12c72

✨ Features

  • Configurable scratch location (@sdd)

  • Introduce QueryMetric public trait (@sdd, Fixes:Issue #390)

  • Ensure third-party leaf strategies can be used (@sdd)

  • Add example showing how to embed a kd-tree (@sdd)

  • Add ThresholdVecResultCollection for small-k nearest_n (@cbueth)

🐛 Bug Fixes

  • Add dafault impl of LeafStrategy::new_with_empty_leaf (@sdd)

  • Cache threshold_distance in ThresholdVecResultCollection (@cbueth)

  • Apply ThresholdVecResultCollection to scratch-based nearest_n path (@cbueth)

  • Dispatch into_sorted_vec() through into_vec() in ThresholdVec (@cbueth)

  • Extend ThresholdVec optimisation to unsorted nearest_n path (@cbueth)

⚡️ Performance

  • Pre-allocate unsorted result Vec with capacity 64 (@cbueth)

  • Use select_nth_unstable extraction in ThresholdVecResultCollection (@cbueth)

  • Hybrid sorted-vec result collection for small-k nearest_n (@cbueth)

🧪 Testing

  • Add regression test to ensure KdTree::default works (@sdd)

  • Add k=21 nearest_n_within case for BinaryHeap coverage, remove padding test (@cbueth)

🤖 CI

  • Prepare embedded example artifacts in CI (@sdd)

  • Add bencher for master push and non-fork PRs (@sdd)

  • Run codspeed in simulation mode only (@sdd)

  • Install cmake for bencher runner (@sdd)

  • Add eytzinger nearest_n bencher profiles (@sdd)

  • Allow bencher runs for collaborators or manually permissioned forks (@sdd)

  • Switch to standard collab model now that repo is in a personal org (@sdd)

  • Ensure examples/data is .gitignored (@sdd)

  • Ensure git-cliff emits well-formatted md (@sdd)

  • Ensure git-cliff emits well-formatted md (@sdd)

  • Ensure git-cliff emits well-formatted md (@sdd)

  • Git-cliff nicer formatting (@sdd)

  • Git-cliff fix formatting yet again (@sdd)

🧹 Chore

Loading

v6.0.0-alpha.1

v6.0.0-alpha.1 Pre-release
Pre-release

Choose a tag to compare

View all tags
@sdd sdd released this 30 Jun 22:25
v6.0.0-alpha.1
b31cdd8

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 KdTree struct, replacing the previous
    mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has
    been removed by introducing the LeafStrategy trait, which the KdTree has as a generic parameter.
    LeafStrategies can be mutable or immutable.
  • KdTree is also now generic over the new StemStrategy trait 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, the within_unsorted_visit result mode to avoid materialization of results, TryFrom
    for converting between different KdTree types, new_from_source, and replace_item.
  • Distance metric coverage has also been expanded and tidied up, including the addition of Chebyshev
    Minkowski, and Dot Product 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.
Loading

v5.3.2

v5.3.2

Choose a tag to compare

View all tags
@github-actions github-actions released this 02 Jun 22:51
v5.3.2
ce7b753

Ci

  • Backport workflow and repo config updates
  • Backport build and coverage workflow updates

🐛 Bug Fixes

  • Add msrv, use algernative to f64::fract

💄 Styling

  • Formatting and clean up unneeded md file
Loading

v5.3.0

v5.3.0

Choose a tag to compare

View all tags
@sdd sdd released this 19 Mar 07:49
v5.3.0
586cf22

I'm extremely grateful to @cbueth for his fantastic set of contributions to this release. The new distance metrics are a great addition to the library, come with extensive tests, and he was even able to contribute a big fix and some welcome refactors along the way. Thanks very much, Carlson!

✨ Features

  • Add Chebyshev (L_∞ norm) distance metric (#290, @cbueth)
  • Add Generalised Minkowski (L_p norm) distance metric (#291, @cbueth)
  • Add *_exclusive methods for querying with an exclusive (<) rather than inclusive (<=) boundary check (#294, @cbueth)

🐛 Bug Fixes

  • Ensure that all existing query methods have boundary checks that are inclusive (<=), in line with typical k-d tree expectations (@cbueth)
    If you were relying on these checks being exclusive, switch over to using the new *_exclusive variants of the query methods.

📝 Docs

  • Correct a mistake in the docs for fixed::distance::Manhattan (#283, @Luca-spopo)

Deps

  • update cmov dep from 0.4 to 0.5 (@sdd)

Contributors

sdd, Luca-spopo, and cbueth
Loading

v5.2.1

v5.2.1

Choose a tag to compare

View all tags
@github-actions github-actions released this 29 Jun 16:41
v5.2.1
8adcd79

📝 Documentation

  • Update some stale documentation. Remove the global_allocate feature which is no longer used for anything
Loading