Repository navigation
Fix OOM in multi-dim hist depending on argument order - #3949
Conversation
8472870 to
bc933b2
Compare
|
Here are some test cases that are failing in this branch but run in the latest released version (unless the example says something else): import scipp as sc
da = sc.data.table_xyz(100).bin(x=2, y=3)
del da.bins.coords['x']
da.coords['x'] = sc.midpoints(da.coords['x'])
da.hist(z=2, x=2, dim=da.dims)
# Raises DimensionError.import scipp as sc
da = sc.data.binned_x(nevent=100, nbin=12)
da.coords['p'] = sc.midpoints(da.coords['x'])
da.hist(y=4, p=3, x=4, dim=da.dims)
# Raises KeyError for 'p'.import scipp as sc
da = sc.data.table_xyz(1200).bin(x=40, y=30)
da.coords['p'] = sc.arange('x', 40, unit='s')
da.coords['r'] = (
sc.arange('x', 40, unit='K') + 40 * sc.arange('y', 30, unit='K')
)
da.hist(p=20, z=20, r=20, dim=da.dims)
# Large allocation: 40 * 30 * 20 * 20 = 480,000 intermediate bins.
# This issue also existed before this PR.import scipp as sc
da = sc.data.table_xyz(100).bin(x=2, y=3)
del da.bins.coords['y']
da.hist(z=2, y=2, dim=da.dims)
# Raises KeyError for 'y'.
# Before the PR this raised BinEdgeError. |
|
Thanks, these were very useful — all four reproduce. The first two were my regression: the reordering did not account for re-binning a dim dropping coords defined over that dim, nor for histogramming by an outer coord erasing that coord's dims (the latter would have silently changed which dims the result has, not just their order). Both now fall back to the given order. Your case 1 and case 4 also turned out to be latent bugs in I replaced my ad-hoc checks with a differential comparison against pre-PR behaviour over 8 data layouts x all edge combinations, argument orders and Your case 3 I left alone, since as you say it predates this PR and no ordering helps: none of |
| da = sc.data.table_xyz(1000).bin(x=5, y=4) | ||
| da.coords['p'] = sc.arange('x', 5, unit='s') | ||
| da.coords['r'] = sc.arange('x', 5, unit='K') + 5 * sc.arange('y', 4, unit='K') | ||
| expected = da.hist(r=2, p=3, dim=()) |
There was a problem hiding this comment.
This test only tests that the result is order independent, but the results can still be incorrect.
This test fails
def test_hist_by_1d_and_2d_outer_coords_preserves_existing_dims() -> None:
da = sc.data.table_xyz(4).bin(x=2, y=2)
da.coords['p'] = sc.arange('x', 2, unit='s')
da.coords['r'] = (
sc.arange('x', 2, unit='K')
+ 2 * sc.arange('y', 2, unit='K')
)
result = da.hist(r=2, p=2, dim=())
assert result.sizes == {'x': 2, 'y': 2, 'r': 2, 'p': 2}but I think it should succeed.
There was a problem hiding this comment.
Maybe we need to change/simplify the semantics of the dims= argument. It seems to me that we are running into a lot of edge cases (that probably are used very rarely) and it might be better to just explicitly disallow some of those cases.
As I understand it the dims argument was mainly introduced to avoid keeping (some or all) existing dimensions of the binning when histogramming or binning by new coordinates.
That avoided having to do a .concat() before the histogramming, and was a nice usability improvement.
But it also introduced the option of binning in coordinates with the same dimensions as the existing binning while keeping the existing binning (by passing dims=()).
That was new functionality that was not possible previously, because before dim= was introduced .hist always summed over the existing dimensions if the new binning coordinate shared dimensions with the existing binning. (As I understand it)
Seems to me that we could say .hist (and .bin) always sums over (or concatenates) existing binnings that share dimensions with the new binning coordinates, whatever is passed in dims=, and that would still keep the nice functionality of being able to concatenate some of the existing dimensions.
So basically, the semantics of dim= would then be "what more dimensions to sum/concat over, beyond the ones that the binning coordinates (the coordinates referenced by the arguments to .hist or .bin) refer to.
There was a problem hiding this comment.
First, see also ADR-0018.
Seems to me that we could say
.hist(and.bin) always sums over (or concatenates) existing binnings that share dimensions with the new binning coordinates, whatever is passed indims=
That was more or less how it worked before the ADR. I am not sure what the non-explicit definition (implicit by which dims the coord has) of which dims to sum/concat over would add. On the contrary, it seems it would make certain things impossible, e.g., if you have dims=('pixel', wavelength') with a 2D Q coord and want to turn that into ('pixel', 'Q') — if I understand your definition correctly you would always sum over pixel.
There was a problem hiding this comment.
if I understand your definition correctly you would always sum over pixel
Yes that's right. Yeah I see, removing the option to avoid that would be limiting and not what we want.
I am not sure what the non-explicit definition (implicit by which dims the coord has) of which dims to sum/concat over would add.
It would reduce the large increase in number of cases to handle, which is also the main drawback listed in the ADR.
There was a problem hiding this comment.
Regarding the failing test: This seems to be the same behavior as on main, but it is inconsistent with the ADR, I'll open a stacked PR. Should not block the OOM fix in this branch.
|
@jokasimr Do you have more comments about this fix? |
|
I haven't reviewed the details yet, but I'll do it today 👍 |
`hist` with more than one set of edges bins by all but the last edges and histograms the last one. Edges replacing an existing dim shrink that dim in the binning step, while a dim not touched by it survives at its original length. Deferring such edges to the final histogramming step therefore produced an intermediate with a bin count given by the product of the original and the new dim lengths, e.g. 1e6 x 200 bins for `binned_x(1e6, 1e6).hist(y=200, x=200)`, which OOMs. The same call with the edges given in the other order was fine. Edges are now ordered such that those replacing an existing dim are applied first, and the output is transposed back to the requested dim order. Co-Authored-By: Claude Opus 5 <[email protected]>
Reordering edges must not change which coords are available or which dims are erased: - Re-binning a dim drops coords defined over it. Keep the given order when any edges are derived from such a coord, since reordering could remove a coord that is still required for a later step. - Histogramming by an outer (non-event) coord erases that coord's dims, so do not reorder when that would move such edges last. The reordering also exposed two latent bugs in make_binned, both reachable via bin and group without any reordering: - combine_bins cannot use bin-edge coords, which are dropped when flattening, leading to a confusing KeyError. Reject them in _can_operate_on_bins so that binning falls through to the C++ implementation, which raises BinEdgeError. - Restoring the input dim order after combine_bins failed with DimensionError whenever dims were erased or added. Co-Authored-By: Claude Opus 5 <[email protected]>
Two pre-existing cases where hist depends on the argument order remain, both caused by re-binning a dim dropping coords defined over that dim. Capture them as strict xfail so that a future fix does not go unnoticed. Co-Authored-By: Claude Opus 5 <[email protected]>
Co-Authored-By: Claude Opus 5 <[email protected]>
The guard rejected bin-edge outer coords so that binning falls through to the C++ implementation, which raises BinEdgeError. That is the correct behavior, but it is a user-visible break that predates this branch: the combine_bins fast path has accepted such coords since it was introduced, and the filtering docs rely on it. Fixing it belongs in a dedicated change, tracked in #3955. Mark the affected cases as xfail, covering both flavors of the divergence: flattening more than one dim drops the coord and fails with a confusing KeyError, while flattening a single dim is a mere rename, so the coord survives and its first values are used, one per input bin. Co-Authored-By: Claude Opus 5 <[email protected]>
9bcd0fb to
75410e4
Compare
When the coord used for histogramming is not an event coord, make_histogrammed summed the bins and let the C++ dense histogram pick the dims to replace, which always consumes all dims of the coord. Dims outside `erase` were therefore erased anyway, and a multi-dimensional coord raised DimensionError. Bin instead when `erase` does not already cover the coord's dims, mirroring what nanhist has always done. The reordering guard added in #3949 is no longer needed: which edges come last no longer decides which dims the result has. Fixes #3958
When the coord used for histogramming is not an event coord, make_histogrammed summed the bins and let the C++ dense histogram pick the dims to replace, which always consumes all dims of the coord. Dims outside `erase` were therefore erased anyway, and a multi-dimensional coord raised DimensionError. Bin instead when `erase` does not already cover the coord's dims, mirroring what nanhist has always done. The reordering guard added in #3949 is no longer needed: which edges come last no longer decides which dims the result has. Fixes #3958
2 participants
Fixes #3948.
histwith more than one set of edges bins by all but the last edges and histograms the last one. Edges that replace an existing dim shrink that dim in the binning step, whereas a dim not touched by it survives at its original length. Deferring such edges to the final histogramming step therefore produced an intermediate with a bin count given by the product of the original and the new dim lengths — 1e6 x 200 bins for the example in the issue, which OOMs, while the same call with the edges given in the other order was fine.Edges are now ordered such that those replacing an existing dim are applied first, and the output is transposed back to the requested dim order. On
sc.data.binned_x(1e5, 1e5).hist(y=200, x=200, dim=da.dims)this goes from 4.7 s and 3964 MiB peak to 0.04 s and 19 MiB; the 1e6 example from the issue runs in 0.3 s and is bit-identical to the working argument order.Reordering is not always safe, so it is skipped in two cases: re-binning a dim drops coords defined over that dim, and histogramming by an outer coord erases that coord's dims — the latter would silently change which dims the result has, not just their order. In both cases the given order is kept.
The reordering also exposed a latent bug in the re-binning fallback added in #3839, reachable on
mainwithout any reordering: restoring the input dim order aftercombine_binsraisedDimensionErrorwhenever dims were erased or added. Fixed here.Side effect worth knowing: the output dim order now always follows the requested order. Previously
hist(y=5, x=7, z=3)could come back as('x', 'y', 'z'), sincemake_binnedcanonicalizes dim order internally. The new behavior is what the docstring examples already imply.Two classes of pre-existing problems turned up along the way and are marked as strict
xfailhere rather than fixed, so that a future fix does not go unnoticed:histremains order-dependent when none of the edges replaces an existing dim, so no ordering helps.binandgroupaccept a bin-edge outer coord that the C++ implementation rejects. Reject bin-edge outer coords in combine_bins fast path #3956 is stacked on this PR and fixes it, since doing so is a user-visible break that deserves its own change.Test plan
histfor both event-coord and outer-only-coord binning, dim order over all permutations of a 3-Dhist, and a large input that would need hundreds of GByte with the old ordering.hist,binandgroupwere cross-checked against pre-PR behaviour by a differential run over 8 data layouts x all edge combinations, argument orders anddimvalues — 820histcases and 760bin/groupcases, comparing sizes, coords, masks, unit and a position-weighted checksum, with an independent reference that broadcasts the outer coord onto the events. Previously-crashing cases now work, with no regressions. Not committed, this was a one-off check.