aai-institute / aai-institute/approx-chol

Restore the u32 zero-copy borrow arm in index narrowing

Aperta
#69 1 commento 0 reazioni 0 assegnatari Vedi su GitHub
enhancement
Lingua principale
Rust
Stelle
5
Fork
0
Merge medio
2g 19h
PR unite (30g)
2

Descrizione

## Problem

`Builder::build` narrows the index arrays unconditionally:

```rust
let narrowed = csr.narrow_indices()?;
self.build_validated(narrowed.with_values(csr.values()))
```

`narrow_indices` allocates two `Vec` and copies `n + 1 + nnz` elements. When `I` is already `u32` — the **default type parameter**, and the only shape the real consumers pass — this copies arrays that are already in the target representation.

Who passes `u32`:

- `crates/approx-chol-py/src/lib.rs:50` — `astype(uint32)` on every incoming array, so every Python/scipy call.
- `within/crates/within/src/block_elim/factor.rs:308` — feeds `CsrMatrix { indptr: Vec, indices: Vec, .. }` straight into `CsrRef::new`.
- Every doctest and example in this crate.

This is not a regression: the fast path existed only between `1e8f786` (Feb 27) and `64ba566` (Mar 3), both before v0.1.0 tagged on Mar 12. It was traded away for a zero-`unsafe` crate and never shipped. The docs are also honest about it — `Builder::build` says it converts to "owned `u32` storage", and `CsrRef`'s "zero-copy" refers to constructing the view, which is true.

## What restoring it requires

`NarrowedCsr` needs a `Borrowed` arm, which means learning `I == u32` *and* producing the reborrowed slice. Three options, and only three:

**(a) Sealed `CsrIndex` trait — safe, verified.**

```rust
trait CsrIndex: PrimInt { fn as_u32s(slice: &[Self]) -> Option<&[u32]>; }
impl CsrIndex for u32 { fn as_u32s(s: &[u32]) -> Option<&[u32]> { Some(s) } }
impl CsrIndex for u64 { fn as_u32s(_: &[u64]) -> Option<&[u32]> { None } }
```

Inside `impl for u32`, `Self` is statically `u32`, so this compiles with no `unsafe` and no `'static` bound. Tested: returns the same pointer for `u32`, `None` for `u64`/`usize`.

Cost: `build`/`factorize`'s bound goes `I: PrimInt` → `I: CsrIndex`, breaking. `num_traits::PrimInt` is implemented for exactly the twelve primitive integers, so twelve macro-generated impls keep every practically reachable `I` working, and `sprs::SpIndex` / `faer::Index` are likewise only primitives. A third-party `PrimInt` impl would break — possible, but it requires implementing ~15 supertraits.

**(b) `TypeId` + `unsafe` transmute.** What `1e8f786` had and `64ba566` deliberately removed. Reintroduces the crate's only `unsafe`.

**(c) Status quo.**

`Any`-based downcasting is **ruled out**, not merely unattractive: `downcast_ref` requires `Sized`, so `[u32]` is rejected outright, and the `&&[I]` form the compiler suggests fails with *"cast requires that `'a` must outlive `'static`"* because `Any: 'static` constrains the referent. `Any` can prove `I == u32` but cannot hand back a borrowed slice — which is exactly why the original needed `unsafe`.

## Acceptance criteria

1. Measure first. `benches/ingestion.rs` `ingest_only` and `full_build` arms across the degree sweep, with a same-day self-vs-self noise floor recorded in the PR. The copy is `O(nnz)` with two allocations, so the effect should be roughly **flat** across degree; a monotone-in-degree result would mean something else is being measured.
2. Only if the win clears the floor: implement (a), with `CsrIndex` sealed and impls generated for all twelve primitive integers.
3. `within` is unaffected at the source level either way — it names no index type, it passes `&[u32]` slices and lets inference do the rest.

Do **not** take (b). Zero `unsafe` is worth more than this.

## Blocked on

Whichever branch owns `NarrowedCsr` (currently #67).

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.