Class: CAMeld

Inherits:
Object
  • Object
show all
Defined in:
lib/carray/meld_reduce.rb

Overview

CAMeld reduce fast paths (per-parent decompose family).

All decomposable reductions along the meld axis land at eager-entity parity via the identity op(concat_k p_k) = combine_k op(p_k) where op is sum/min/max/mean/etc. and combine_k is +, min, max, or the Welford update (variance/stddev). Each per-parent op runs on an entity, hitting the fastest kernel_iterator path, and dodges the whole-view SRC_ATTACH materialise (K per-parent xfer_all GET into scratch).

Reductions along a non-meld axis (memo §7.4) also decompose: each parent independently reduces the non-meld axis, and the K results are concatenated back along the meld axis via CArray.meld. Result is materialised (.copy) to preserve the entity-returning semantic of CArray#sum/#mean/etc.

Fast path activates when:

  • axis kwarg is a single Integer (or absent for flat reduce)
  • no mask on CAMeld or any parent (skipna needs per-cell dispatch; the decompose would not see correct mask propagation across parents)
  • no non-:axis kwargs (min_count / fill_value / keep_axis / etc. punt to super; those change finalisation semantics) When any condition fails the method falls through to super, landing on the kernel_iterator SRC_ATTACH path (correct, just slower).

Order statistics (median / percentile / quantile) do NOT decompose — per-parent medians are not a function of the overall median — so those stay on the SRC_ATTACH path, which is already essentially parity because the sort cost dominates.

See docs/objects/CAMeld.md and devel/bench_cameld_*.rb for numbers.

Instance Method Summary collapse

Instance Method Details

#max(*args, **kw) ⇒ CArray, Numeric

Same result as CArray#max, obtained by reducing each parent and combining, so the melded array is never materialised. Falls back to the generic path when the decomposition does not apply.

Returns:



100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/carray/meld_reduce.rb', line 100

def max(*args, **kw)
  return super unless args.empty? && meld_reduce_fast_path_ok?(kw)
  axis = kw[:axis]
  if axis.nil?
    return super if parents.all? { |p| p.elements == 0 }
    parents.reject { |p| p.elements == 0 }.map(&:max).max
  elsif meld_axis_normalized?(axis)
    return super if parents.all? { |p| p.dim[meld_axis] == 0 }
    nonempty = parents.reject { |p| p.dim[meld_axis] == 0 }
    CArray.stack(nonempty.map { |p| p.max(axis: axis) }).max(axis: 0)
  else
    non_meld_axis_decompose(:max, axis)
  end
end

#mean(*args, **kw) ⇒ CArray, Numeric

Same result as CArray#mean, obtained by reducing each parent and combining, so the melded array is never materialised. Falls back to the generic path when the decomposition does not apply.

Returns:



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/carray/meld_reduce.rb', line 53

def mean(*args, **kw)
  return super unless args.empty? && meld_reduce_fast_path_ok?(kw)
  axis = kw[:axis]
  # `mean` has no identity: an empty set of contributors has no defined
  # mean (0/0 = NaN).  Punt to super, which returns UNDEF: a reduction
  # with no contributors yields the identity where one exists and UNDEF
  # where none does, and never raises.
  if axis.nil?
    return super if parents.all? { |p| p.elements == 0 }
    total_sum = parents.map(&:sum).inject(:+)
    total_count = parents.map(&:elements).inject(:+)
    total_sum / total_count.to_f
  elsif meld_axis_normalized?(axis)
    return super if parents.all? { |p| p.dim[meld_axis] == 0 }
    total_sum = parents.map { |p| p.sum(axis: axis) }.inject(:+)
    total_count = parents.map { |p| p.dim[meld_axis] }.inject(:+)
    total_sum / total_count.to_f
  else
    non_meld_axis_decompose(:mean, axis)
  end
end

#min(*args, **kw) ⇒ CArray, Numeric

Same result as CArray#min, obtained by reducing each parent and combining, so the melded array is never materialised. Falls back to the generic path when the decomposition does not apply.

Returns:



79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/carray/meld_reduce.rb', line 79

def min(*args, **kw)
  return super unless args.empty? && meld_reduce_fast_path_ok?(kw)
  axis = kw[:axis]
  # `min` has no identity — empty parent list / all-empty parents punt to
  # super for UNDEF.
  if axis.nil?
    return super if parents.all? { |p| p.elements == 0 }
    parents.reject { |p| p.elements == 0 }.map(&:min).min
  elsif meld_axis_normalized?(axis)
    return super if parents.all? { |p| p.dim[meld_axis] == 0 }
    nonempty = parents.reject { |p| p.dim[meld_axis] == 0 }
    CArray.stack(nonempty.map { |p| p.min(axis: axis) }).min(axis: 0)
  else
    non_meld_axis_decompose(:min, axis)
  end
end

#stddev(*args, **kw) ⇒ CArray, Numeric

Same result as CArray#stddev, obtained by reducing each parent and combining, so the melded array is never materialised. Falls back to the generic path when the decomposition does not apply.

Returns:



148
149
150
 
# File 'lib/carray/meld_reduce.rb', line 148

def stddev(*args, **kw)
  variance_family(args, kw, sample: true, sqrt: true) { super }
end

#stddevp(*args, **kw) ⇒ CArray, Numeric

Same result as CArray#stddevp, obtained by reducing each parent and combining, so the melded array is never materialised. Falls back to the generic path when the decomposition does not apply.

Returns:



156
157
158
 
# File 'lib/carray/meld_reduce.rb', line 156

def stddevp(*args, **kw)
  variance_family(args, kw, sample: false, sqrt: true) { super }
end

#sum(*args, **kw) ⇒ Object

---------- monoid reductions (sum / mean / min / max) ----------



37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/carray/meld_reduce.rb', line 37

def sum(*args, **kw)
  return super unless args.empty? && meld_reduce_fast_path_ok?(kw)
  axis = kw[:axis]
  if axis.nil?
    parents.map(&:sum).inject(:+)
  elsif meld_axis_normalized?(axis)
    parents.map { |p| p.sum(axis: axis) }.inject(:+)
  else
    non_meld_axis_decompose(:sum, axis)
  end
end

#variance(*args, **kw) ⇒ Object

---------- variance family (Welford combine along meld axis) ----------

Chan / Welford parallel merge: each parent contributes (n_k, mean_k, M2_k = Σ (x - mean_k)^2). Combine two chunks (n1, m1, M1) + (n2, m2, M2): n = n1 + n2 δ = m2 - m1 mean = m1 + δ * n2 / n M2 = M1 + M2 + δ² * (n1 * n2 / n) sample variance = M2 / (n - 1) population variance = M2 / n

M2 per parent is recovered from CArray's variance: M2_k = variance_k * (n_k - 1) [sample-variance CArray path] This inherits CArray's ε-close SIMD reduce contract (memo: reduction is ε-close, not bit-exact). Falls through to super when any parent has n <= 1 along the axis (sample variance undefined).



132
133
134
 
# File 'lib/carray/meld_reduce.rb', line 132

def variance(*args, **kw)
  variance_family(args, kw, sample: true, sqrt: false) { super }
end

#variancep(*args, **kw) ⇒ CArray, Numeric

Same result as CArray#variancep, obtained by reducing each parent and combining, so the melded array is never materialised. Falls back to the generic path when the decomposition does not apply.

Returns:



140
141
142
 
# File 'lib/carray/meld_reduce.rb', line 140

def variancep(*args, **kw)
  variance_family(args, kw, sample: false, sqrt: false) { super }
end