andygrove commented on PR #5042:
URL:
https://github.com/apache/datafusion-comet/pull/5042#issuecomment-5441581243
> **Note on this review:** this was generated by an LLM (Claude Code) at my
request while I worked through a review backlog. I have not verified the
individual findings myself. Please treat everything below as suggestions to
evaluate rather than as authoritative review feedback, and push back on
anything that is wrong or already handled.
Thanks for working on this. The ASCII fast path is a good idea and the
benchmark numbers look worthwhile. I think there is a correctness problem in
the scratch-buffer reuse, though, and I would like to work through it before
this goes further.
**`Vec::resize` does not reset existing elements**
`resize` only fills the *new* slots when growing, and simply truncates when
shrinking. Existing elements keep whatever the previous call left in them. That
matters in `levenshtein_distance_with_threshold`, where the old code allocated
`vec![out_of_band; m + 1]` and therefore started from a fully initialized row,
but the new code only writes some of the cells.
Concretely, in the threshold path:
```rust
prev.resize(m + 1, out_of_band);
for (i, value) in prev.iter_mut().enumerate().take(m.min(threshold) + 1) {
*value = i as i32;
}
```
If the previous row used a longer buffer, `resize` truncates and leaves
`prev[0..=m]` holding stale distances. The loop then initializes only
`prev[0..=min(m, threshold)]`. With `threshold < m`, the cells from `threshold
+ 1` through `m` should be `out_of_band` but instead hold values from an
earlier, unrelated pair of strings.
The same applies to `curr`. Inside the `j` loop only `curr[0]`, `curr[start
- 1]`, `curr[start..=end]`, and `curr[end + 1]` are written. Everything outside
that band used to be `out_of_band` from the fresh allocation and is now stale.
So `levenshtein(s, t, threshold)` can return a different answer depending on
what the *previous* row on the same thread computed. That is the worst kind of
bug to find in production: nondeterministic, data-dependent, and invisible in a
test that evaluates one pair at a time.
The fix is to explicitly fill rather than rely on `resize`:
```rust
prev.clear();
prev.resize(m + 1, out_of_band);
```
or `prev.resize(m + 1, out_of_band); prev.fill(out_of_band);` before the
partial initialization. Same for `curr`. The plain `levenshtein_distance` path
happens to be safe because both rows are fully overwritten, but it would be
worth making the initialization uniform in both so the invariant is not
something a future reader has to rediscover.
**"Existing tests" is not enough for this change**
Because the bug only appears when one call leaves state behind for the next,
no single-pair test can catch it. Could you add a test that evaluates a whole
column in one `invoke`, mixing long and short strings and ASCII with non-ASCII,
and compares against a straightforward reference implementation? Something
like: compute a batch in one order, compute the same pairs in reverse order,
and assert the results match. That property directly targets the class of bug
above and would have caught it.
It would also be worth adding cases with a small threshold and a long
shorter-string, since that is the shape that leaves the most cells
uninitialized.
**Two smaller points**
`s.is_ascii()` is a full scan of the string, so non-ASCII inputs now pay an
extra pass before falling into the `chars()` path. For a mostly-non-ASCII
column that is a small regression. Probably fine, but worth confirming the
benchmark covers a non-ASCII case so we know the fallback did not get slower.
The `thread_local!` buffers grow to the longest string ever seen on that
thread and never shrink. On a pool of executor threads that could retain a fair
amount of memory after one pathological row. Is it worth calling `shrink_to`
when the buffer is far larger than the current need?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
