Request a v0.12.3 backport of the bulk_load Vec over-capacity fix

[hxsf]

This is an english version translated by chatGPT.

Summary

Would you consider releasing rstar v0.12.3 with a backport of the
RTree::bulk_load excessive memory retention fix from #220?

The fix is already included in v0.13.0, but upgrading to 0.13 also
requires adopting its breaking API changes. A 0.12.x patch release would
allow downstream users to receive this bug fix independently.

Relevant links:

• PR: Fix excessive memory usage in bulk_load due to Vec over-capacity #220
• Commit: f93071f

Motivation

This is a substantial memory-retention bug rather than a new feature.

The bulk_load implementation in 0.12.2 uses Vec::split_off while
partitioning elements into slabs. The retained capacity can propagate into
leaf-node child vectors through Rust's in-place collect optimization.

In an OSM-based routing workload, we measured the following after bulk-loading
a regional spatial index:

• Logical R-tree node storage: approximately 169 MB
• Actual child-vector allocations: approximately 1.80 GB
• Allocation overhead: approximately 1.63 GB, or about 90%
• Rebuilding the same tree through a compact clone reduced it to approximately
  164 MB without changing query results

The effect becomes much larger for country-scale OSM datasets.

Downstream compatibility

Several downstream geospatial crates currently use rstar 0.12. For example,
the latest published geo 0.33.1 still depends on rstar ^0.12.0.

Support for rstar 0.13 has been merged into the geo repository, but it has
not yet been included in a crates.io release:

georust/geo#1536

This means downstream applications currently have to choose between:

1. retaining the excessive memory usage;
2. rebuilding or cloning the tree after bulk loading;
3. patching/forking rstar 0.12; or
4. adopting unreleased or breaking dependency upgrades.

Requested scope

If maintainers are open to a 0.12.3 release, the requested scope would be:

• branch from v0.12.2;
• backport the internal bulk-load changes from Fix excessive memory usage in bulk_load due to Vec over-capacity #220;
• backport the capacity regression tests;
• avoid including the public API changes introduced in 0.13;
• publish the result as v0.12.3.

The fix appears isolated to the bulk-load implementation and should not require
public API changes.

I can help validate the backport against the OSM routing workload described
above if useful.

[adamreichold]

This means downstream applications currently have to choose between:

It is hard to tell without seeing your code base, but the larger part of the issue itself requires that

size_of::<T> == size_of::<RTreeNode<T>>

so it only applies if you type T: RTreeObject has a niche in which the discriminant of RTreeNode<T> can be stored. If you add some useless padding like a _padding: [u8; N] field to remove its niche, you should be able to force a re-collection into an exactly-sized Vec<RTreeNode<T>> even with the existing v0.12.2 code.

[adamreichold]

If you add some useless padding like a _padding: [u8; N] field to remove its niche,

Or probably simpler, make your struct repr(C) to prevent Rust's layout optimisations.

[hxsf]

@adamreichold

If you add some useless padding like a _padding: [u8; N] field to remove its niche

But padding cannot remove its niche. struct { some_fields: [u64; 7], niche_field: bool, _padding: [u8;7 or larger] }. niche_field: bool always niche.

#[repr(C)] will be add to RTreeNode. add to T will get nothing.

a playground link: https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=0da35c0de97a6a9d730ba81f5dde0b0f

[adamreichold]

@hxsf You are right that those particularly remedies do not work in this situation and I did not think this through. I am sorry for that!

I think that the general of locally suppressing the niche optimisation is still valid though, c.f. https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=0d52e3ee0529b82048af0ba37c25e19c

If bool provides the niche in your case, I would expect using Cell<bool> is an ugly but tolerable workaround w.r.t. code ergonomics and performance.

[hxsf]

@adamreichold yes, wrapping T with Cell/XXXCell makes it non-niche.

But for some reasons (reuse memory/reuse logic), T is used in many places. Wrapping is too expensive.

In my case, just build the over-cap tree, and .clone() + drop(over_cap_tree) to make it fit. Worked with stable Rust (1.96.1). The only cost is some extra memory waste at startup (which will be reused elsewhere after being freed).

So, I'm waiting for geo next release, or rstar backport release