NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
tensor.hpp
Go to the documentation of this file.
1
20#ifndef NUMERICAL_TENSOR_HPP
21#define NUMERICAL_TENSOR_HPP
22
23#include <algorithm>
24#include <array>
25#include <cctype>
26#include <cmath>
27#include <complex> // so std::abs resolves for a complex scalar, regardless of include order
28#include <cstddef>
29#include <deque>
30#include <initializer_list>
31#include <map>
32#include <memory>
33#include <mutex>
34#include <numeric>
35#include <optional>
36#include <ranges>
37#include <stdexcept>
38#include <string>
39#include <string_view>
40#include <type_traits>
41#include <utility>
42#include <vector>
43
44#include "gemm.hpp"
45#include "matrix.hpp"
46#include "parallel.hpp"
47#include "vector.hpp"
48
49namespace numerical {
50
52 class einsum_error : public detail::tagged<std::runtime_error>
53 {
54 public:
55
57 explicit einsum_error(const std::string& message)
58 : tagged(message)
59 {}
60 };
61
62 template <typename T>
63 class tensor;
64
65 namespace detail {
66 template <typename T>
67 [[nodiscard]] buffer<T> permuted(const T* data,
68 std::size_t count,
69 const std::string& from,
70 const std::string& to,
71 const std::map<char, std::size_t>& sizes,
72 std::size_t ld = 0);
73 } // namespace detail
74
76 inline constexpr std::size_t sliced_copy_most {512};
77
86 template <typename T>
87 class tensor
88 {
89 public:
90
97 tensor(std::vector<std::size_t> shape,
98 buffer<T> elements)
99 : shape_(std::move(shape)), data_(std::make_shared<const buffer<T>>(std::move(elements)))
100 {
101 finalize();
102 }
103
110 tensor(std::vector<std::size_t> shape,
111 const std::vector<T>& elements)
112 : tensor(std::move(shape),
113 buffer<T>(elements.begin(), elements.end()))
114 {}
115
117 tensor(std::vector<std::size_t> shape,
118 std::initializer_list<T> elements)
119 : tensor(std::move(shape),
120 buffer<T>(elements))
121 {}
122
124 explicit tensor(const vector<T>& v)
125 : tensor(std::vector<std::size_t> {v.size()},
126 buffer<T>(v.begin(), v.end()))
127 {}
128
132 explicit tensor(matrix<T>&& m)
133 : shape_ {m.rows(), m.cols()}, data_ {std::make_shared<const buffer<T>>(std::move(m).elements())}
134 {
135 finalize();
136 }
137
139 explicit tensor(const matrix<T>& m)
140 : tensor(std::vector<std::size_t> {m.rows(), m.cols()},
141 buffer<T>(m.begin(), m.end()))
142 {}
143
152 [[nodiscard]] tensor reshaped(std::vector<std::size_t> shape) const
153 {
154 if (copy_ == nullptr) {
155 return tensor {std::move(shape), data_};
156 }
157 std::size_t count {1};
158 for (const std::size_t extent : shape) {
159 count = detail::checked_mul(count, extent);
160 }
161 if (count != count_) {
162 throw dimension_error("tensor: data size does not match the shape");
163 }
164 if (auto strides {reshaped_strides(shape)}) {
165 return tensor {std::move(shape), std::move(*strides), offset_, data_};
166 }
167 // A view's copy shared as it is held, with the view's state (an aliasing pointer, which that state never holds).
168 return tensor {std::move(shape), std::shared_ptr<const buffer<T>>(copy_, &copied_out())};
169 }
170
178 [[nodiscard]] tensor transposed(const std::vector<std::size_t>& axes) const
179 {
180 const std::size_t rank {shape_.size()};
181 std::vector<bool> seen(rank, false);
182 for (const std::size_t axis : axes) {
183 if (axis >= rank || seen[axis]) {
184 throw dimension_error("tensor: transposed takes a permutation of the axes");
185 }
186 seen[axis] = true;
187 }
188 if (axes.size() != rank) {
189 throw dimension_error("tensor: transposed takes a permutation of the axes");
190 }
191 std::vector<std::size_t> shape(rank);
192 std::vector<std::ptrdiff_t> strides(rank);
193 for (std::size_t k {0}; k < rank; ++k) {
194 shape[k] = shape_[axes[k]];
195 strides[k] = strides_[axes[k]];
196 }
197 return tensor {std::move(shape), std::move(strides), offset_, data_};
198 }
199
208 template <typename Keep = std::vector<bool>>
209 [[nodiscard]] tensor sliced(const std::vector<std::size_t>& starts,
210 const std::vector<std::ptrdiff_t>& steps,
211 const std::vector<std::size_t>& counts,
212 const Keep& keep) const
213 {
214 const std::size_t rank {shape_.size()};
215 if (starts.size() != rank || steps.size() != rank || counts.size() != rank || keep.size() != rank) {
216 throw dimension_error("tensor: sliced takes one range per axis");
217 }
218 std::vector<std::size_t> shape;
219 std::vector<std::ptrdiff_t> strides;
220 shape.reserve(rank);
221 strides.reserve(rank);
222 std::ptrdiff_t offset {static_cast<std::ptrdiff_t>(offset_)};
223 for (std::size_t axis {0}; axis < rank; ++axis) {
224 if (!static_cast<bool>(keep[axis]) && counts[axis] != 1) {
225 throw dimension_error("tensor: sliced drops an axis of one index only");
226 }
227 if (!detail::range_within(starts[axis], counts[axis], steps[axis], shape_[axis])) {
228 throw index_error("tensor: a range of sliced leaves its axis");
229 }
230 if (counts[axis] != 0) {
231 offset += static_cast<std::ptrdiff_t>(starts[axis]) * strides_[axis];
232 }
233 if (static_cast<bool>(keep[axis])) {
234 // A range of one index or none takes no step: any step, PTRDIFF_MIN among them, times the stride would
235 // overflow where the range is not walked.
236 shape.push_back(counts[axis]);
237 strides.push_back(counts[axis] > 1 ? strides_[axis] * steps[axis] : strides_[axis]);
238 }
239 }
240 // Checked: a step of 0 repeats an index any number of times, whose product may pass std::size_t.
241 const std::size_t count {detail::element_count(shape.begin(), shape.end())};
242 if (count != 0 && count <= sliced_copy_most) {
243 // A few elements copied at once: a view's shared state and its later copy cost more than they spare (M1 Pro,
244 // `t[1:3] + 1` of 8 × 8 1.42 → 1.47 µs), and the copy keeps no larger buffer alive.
245 buffer<T> elements {gathered(shape, strides, static_cast<std::size_t>(offset), *data_)};
246 return tensor {std::move(shape), std::move(elements)};
247 }
248 return tensor {std::move(shape), std::move(strides), static_cast<std::size_t>(offset), data_};
249 }
250
259 std::size_t column,
260 std::size_t length) const
261 {
262 const std::size_t rank {shape_.size()};
263 std::vector<std::size_t> shape(shape_.begin(), shape_.end() - 1);
264 std::vector<std::ptrdiff_t> strides(strides_.begin(), strides_.end() - 1);
265 shape.back() = length;
266 strides.back() = strides_[rank - 2] + strides_[rank - 1];
267 std::size_t count {length};
268 for (std::size_t axis {0}; axis + 2 < rank; ++axis) {
269 count *= shape_[axis];
270 }
271 if (count == 0) {
272 return tensor {std::move(shape), buffer<T> {}};
273 }
274 const auto offset {static_cast<std::size_t>(static_cast<std::ptrdiff_t>(offset_)
275 + (static_cast<std::ptrdiff_t>(row) * strides_[rank - 2])
276 + (static_cast<std::ptrdiff_t>(column) * strides_[rank - 1]))};
277 if (count <= sliced_copy_most) {
278 buffer<T> elements {gathered(shape, strides, offset, *data_)};
279 return tensor {std::move(shape), std::move(elements)};
280 }
281 return tensor {std::move(shape), std::move(strides), offset, data_};
282 }
283
291 [[nodiscard]] std::optional<std::pair<tensor, std::vector<std::size_t>>> laid_out() const
292 {
293 if (copy_ == nullptr || !permutes_elements()) {
294 return std::nullopt;
295 }
296 // An axis of extent 1 moves nothing and lies anywhere among its ties.
297 std::vector<std::size_t> order {lying_order()};
298 std::vector<std::size_t> shape(order.size());
299 for (std::size_t k {0}; k < order.size(); ++k) {
300 shape[k] = shape_[order[k]];
301 }
302 return std::pair {tensor {std::move(shape), data_}, std::move(order)};
303 }
304
307 {
308 std::vector<std::size_t> axes(shape_.size());
309 std::iota(axes.rbegin(), axes.rend(), std::size_t {0});
310 return transposed(axes);
311 }
312
314 [[nodiscard]] std::size_t rank() const noexcept
315 {
316 return shape_.size();
317 }
318
320 [[nodiscard]] std::size_t size() const noexcept
321 {
322 return count_;
323 }
324
326 [[nodiscard]] const std::vector<std::size_t>& shape() const noexcept
327 {
328 return shape_;
329 }
330
334 {
335 return data_->data() + offset_;
336 }
337
340 [[nodiscard]] const std::vector<std::ptrdiff_t>& strides() const noexcept
341 {
342 return strides_;
343 }
344
347 {
348 return copy_ == nullptr;
349 }
350
358 {
359 if (copy_ == nullptr) {
360 return *this;
361 }
362 return tensor {shape_, std::shared_ptr<const buffer<T>>(copy_, &copied_out())};
363 }
364
370 [[nodiscard]] const buffer<T>& data() const
371 {
372 return copy_ == nullptr ? *data_ : copied_out();
373 }
374
376 [[nodiscard]] const T& operator()(const std::vector<std::size_t>& index) const
377 {
378 std::ptrdiff_t flat {static_cast<std::ptrdiff_t>(offset_)};
379 for (std::size_t axis {0}; axis < index.size(); ++axis) {
380 flat += strides_[axis] * static_cast<std::ptrdiff_t>(index[axis]);
381 }
382 return (*data_)[static_cast<std::size_t>(flat)];
383 }
384
386 [[nodiscard]] bool operator==(const tensor& other) const
387 {
388 return shape_ == other.shape_ && data() == other.data();
389 }
390
391 private:
392
394 [[nodiscard]] std::vector<std::size_t> lying_order() const
395 {
396 std::vector<std::size_t> order(shape_.size());
397 std::iota(order.begin(), order.end(), std::size_t {0});
398 std::stable_sort(order.begin(), order.end(), [this](std::size_t a, std::size_t b) { return strides_[a] > strides_[b]; });
399 return order;
400 }
401
409 {
410 if (offset_ != 0 || count_ != data_->size()) {
411 return false;
412 }
413 std::size_t acc {1};
414 for (const std::size_t axis : std::views::reverse(lying_order())) {
415 if (shape_[axis] < 2) {
416 continue;
417 }
418 if (strides_[axis] != static_cast<std::ptrdiff_t>(acc)) {
419 return false;
420 }
421 acc *= shape_[axis];
422 }
423 return true;
424 }
425
429 {
430 std::once_flag made;
432 };
433
435 tensor(std::vector<std::size_t> shape,
436 std::shared_ptr<const buffer<T>> elements)
437 : shape_(std::move(shape)), data_(std::move(elements))
438 {
439 finalize();
440 }
441
445 tensor(std::vector<std::size_t> shape,
446 std::vector<std::ptrdiff_t> strides,
447 std::size_t offset,
448 std::shared_ptr<const buffer<T>> elements)
449 : shape_(std::move(shape)), strides_(std::move(strides)), data_(std::move(elements)), offset_ {offset},
450 count_ {detail::element_count(shape_.begin(), shape_.end())}
451 {
452 // count_ checked first (an extent repeated by a stride of 0 may pass std::size_t): the products below then stay
453 // within it, and an empty shape's are never formed past its zero.
454 std::size_t acc {1};
455 bool row_major {true};
456 for (std::size_t axis {shape_.size()}; count_ != 0 && axis-- > 0;) {
457 // an axis of extent 1 moves nothing
458 row_major = row_major && (shape_[axis] < 2 || strides_[axis] == static_cast<std::ptrdiff_t>(acc));
459 acc *= shape_[axis];
460 }
461 if (count_ == 0) { // nothing to read: an empty tensor of its own
462 data_ = std::make_shared<const buffer<T>>();
463 finalize();
464 }
465 else if (row_major && offset_ == 0 && count_ == data_->size()) {
466 finalize();
467 }
468 else {
469 copy_ = std::make_shared<row_major_copy>();
470 }
471 }
472
480 [[nodiscard]] std::optional<std::vector<std::ptrdiff_t>> reshaped_strides(const std::vector<std::size_t>& shape) const
481 {
482 std::vector<std::size_t> from;
483 std::vector<std::ptrdiff_t> steps;
484 for (std::size_t axis {0}; axis < shape_.size(); ++axis) {
485 if (shape_[axis] != 1) {
486 from.push_back(shape_[axis]);
487 steps.push_back(strides_[axis]);
488 }
489 }
490 std::vector<std::ptrdiff_t> strides(shape.size(), 1);
491 // Every extent is 1 or more (an empty tensor is no view) and both hold as many elements: a run's counts meet
492 // before either side runs out.
493 for (std::size_t to {0}, at {0}; to < shape.size() && at < from.size();) {
494 std::size_t to_end {to + 1};
495 std::size_t at_end {at + 1};
496 std::size_t to_count {shape[to]};
497 std::size_t at_count {from[at]};
498 while (to_count != at_count) {
499 if (to_count < at_count) {
500 to_count *= shape[to_end++];
501 }
502 else {
503 at_count *= from[at_end++];
504 }
505 }
506 for (std::size_t k {at}; k + 1 < at_end; ++k) {
507 if (steps[k] != static_cast<std::ptrdiff_t>(from[k + 1]) * steps[k + 1]) {
508 return std::nullopt;
509 }
510 }
511 strides[to_end - 1] = steps[at_end - 1];
512 for (std::size_t k {to_end - 1}; k > to; --k) {
513 strides[k - 1] = strides[k] * static_cast<std::ptrdiff_t>(shape[k]);
514 }
515 to = to_end;
516 at = at_end;
517 }
518 return strides;
519 }
520
522 [[nodiscard]] const buffer<T>& copied_out() const
523 {
524 std::call_once(copy_->made, [this] {
525 // A view of up to 128 × 128 elements read in its order directly, row after row: detail::permuted's labels cost
526 // more than its tiles save there (M1 Pro, a transpose's copy: 8 × 8 182 against 335 ns, 96 × 96 3.5 against
527 // 3.7 µs, 128 × 128 equal); its tiles and threads pay from 256 × 256 (28 against 47 µs). They take a
528 // permutation of the whole of the elements only (\ref transposed's): a slice's rows, past it, on the threads.
529 constexpr std::size_t read_directly {std::size_t {1} << 14};
531 copy_->elements = gathered(shape_, strides_, offset_, *data_);
532 return;
533 }
534 // The strides a permutation of row-major axes leaves: the axes from the widest stride to the narrowest are
535 // the order the elements lie in, each a label for detail::permuted. An axis of extent 1 moves nothing and
536 // takes none, so the labels number at most 64 (each other axis at least doubles the elements' count).
537 std::vector<std::size_t> lying;
538 for (std::size_t axis {0}; axis < shape_.size(); ++axis) {
539 if (shape_[axis] > 1) {
540 lying.push_back(axis);
541 }
542 }
543 std::string to;
544 std::map<char, std::size_t> sizes;
545 std::map<std::size_t, char> label;
546 for (const std::size_t axis : lying) {
547 label[axis] = static_cast<char>(to.size() + 1);
548 to.push_back(label[axis]);
550 }
551 std::stable_sort(lying.begin(), lying.end(), [this](std::size_t a, std::size_t b) { return strides_[a] > strides_[b]; });
552 std::string from;
553 for (const std::size_t axis : lying) {
554 from.push_back(label[axis]);
555 }
556 copy_->elements = detail::permuted(data_->data(), data_->size(), from, to, sizes);
557 });
558 return copy_->elements;
559 }
560
563 [[nodiscard]] static buffer<T> gathered(const std::vector<std::size_t>& shape,
564 const std::vector<std::ptrdiff_t>& strides,
565 std::size_t offset,
566 const buffer<T>& data)
567 {
568 if (shape.empty()) { // a rank-0 slice: its one element
569 return buffer<T> {data[offset]};
570 }
571 std::size_t count {1};
572 for (const std::size_t extent : shape) {
573 count *= extent;
574 }
575 buffer<T> out(count);
576 const std::size_t inner {shape.back()};
577 const auto step {strides.back()};
578 const T* const from {data.data()};
579 detail::parallel_for(count / inner, detail::memory_element_weight * inner, [&](std::size_t row) {
580 // the row's first element: its index along each outer axis times that axis's stride
581 auto at {static_cast<std::ptrdiff_t>(offset)};
582 for (std::size_t axis {shape.size() - 1}, rest {row}; axis-- > 0;) {
583 at += static_cast<std::ptrdiff_t>(rest % shape[axis]) * strides[axis];
584 rest /= shape[axis];
585 }
586 T* const to {out.data() + (row * inner)};
587 if (step == 1) { // a run as it lies, copied as one
588 std::copy_n(from + at, inner, to);
589 return;
590 }
591 for (std::size_t i {0}; i < inner; ++i) {
592 to[i] = from[at + (static_cast<std::ptrdiff_t>(i) * step)];
593 }
594 });
595 return out;
596 }
597
599 void finalize()
600 {
601 strides_.assign(shape_.size(), 1);
602 std::size_t acc {1};
603 for (std::size_t axis {shape_.size()}; axis-- > 0;) {
604 strides_[axis] = static_cast<std::ptrdiff_t>(acc);
605 acc = detail::checked_mul(acc, shape_[axis]); // guard the element-count product
606 }
607 if (data_->size() != acc) {
608 throw dimension_error("tensor: data size does not match the shape");
609 }
610 offset_ = 0;
611 count_ = acc;
612 }
613
614 std::vector<std::size_t> shape_;
615 std::vector<std::ptrdiff_t> strides_;
616 std::shared_ptr<const buffer<T>> data_;
617 std::size_t offset_ {0};
618 std::size_t count_ {0};
619 std::shared_ptr<row_major_copy> copy_;
620 };
621
629 template <typename T>
630 [[nodiscard]] bool approx_equal(const tensor<T>& a,
631 const tensor<T>& b,
632 double tolerance = 1e-9)
633 {
634 if (a.shape() != b.shape()) {
635 return false;
636 }
637 for (std::size_t i {0}; i < a.size(); ++i) {
638 // Equal, or within the tolerance: a NaN is neither, so it is never close, and two equal
639 // infinities are equal although their difference is NaN.
640 if (!(a.data()[i] == b.data()[i]) && !(std::abs(a.data()[i] - b.data()[i]) <= tolerance)) {
641 return false;
642 }
643 }
644 return true;
645 }
646
647 namespace detail {
649 [[nodiscard]] inline std::string shape_text(const std::vector<std::size_t>& shape)
650 {
651 std::string out {"("};
652 for (std::size_t i {0}; i < shape.size(); ++i) {
653 out += (i == 0 ? "" : ", ") + std::to_string(shape[i]);
654 }
655 return out + (shape.size() == 1 ? ",)" : ")");
656 }
657
660 [[nodiscard]] inline std::vector<std::size_t> broadcast_strides(const std::vector<std::size_t>& shape,
661 std::size_t rank)
662 {
663 std::vector<std::size_t> strides(rank, 0);
664 std::size_t stride {1};
665 for (std::size_t i {shape.size()}; i-- > 0;) {
666 strides[rank - shape.size() + i] = shape[i] == 1 ? 0 : stride;
667 stride *= shape[i];
668 }
669 return strides;
670 }
671 } // namespace detail
672
677 [[nodiscard]] inline std::vector<std::size_t> broadcast_shape(const std::vector<std::size_t>& a,
678 const std::vector<std::size_t>& b)
679 {
680 const std::size_t rank {std::max(a.size(), b.size())};
681 std::vector<std::size_t> out(rank);
682 for (std::size_t i {0}; i < rank; ++i) {
683 const std::size_t x {i < rank - a.size() ? 1 : a[i - (rank - a.size())]};
684 const std::size_t y {i < rank - b.size() ? 1 : b[i - (rank - b.size())]};
685 if (x != y && x != 1 && y != 1) {
686 throw dimension_error("operands could not be broadcast together with shapes " + detail::shape_text(a) + " "
687 + detail::shape_text(b));
688 }
689 out[i] = x == 1 ? y : x;
690 }
691 return out;
692 }
693
694 namespace detail {
697 template <typename Body>
698 void run_fused(const Body& body)
699 {
700#ifdef NUMERICAL_X86_COMPILED
701 if (cpu_features().avx2_fma) {
702 with_fma_instruction(body, 0);
703 return;
704 }
705#endif
706 body(0);
707 }
708
710 [[nodiscard]] inline std::vector<std::ptrdiff_t> row_major_strides(const std::vector<std::size_t>& shape)
711 {
712 std::vector<std::ptrdiff_t> strides(shape.size());
713 std::ptrdiff_t stride {1};
714 for (std::size_t i {shape.size()}; i-- > 0;) {
715 strides[i] = stride;
716 stride *= static_cast<std::ptrdiff_t>(shape[i]);
717 }
718 return strides;
719 }
720
723 [[nodiscard]] inline bool lies_row_major(const std::vector<std::size_t>& shape,
724 const std::vector<std::ptrdiff_t>& strides)
725 {
726 std::ptrdiff_t stride {1};
727 for (std::size_t i {shape.size()}; i-- > 0;) {
728 if (shape[i] > 1 && strides[i] != stride) {
729 return false;
730 }
731 stride *= static_cast<std::ptrdiff_t>(shape[i]);
732 }
733 return true;
734 }
735
740 template <typename T,
741 typename Op,
742 typename R = std::invoke_result_t<const Op&, const T&, const T&>>
743 [[nodiscard]] tensor<R> pairs_into(const T* a,
744 const T* b,
745 const std::vector<std::size_t>& shape,
746 const Op& op)
747 {
748 const std::size_t size {detail::element_count(shape.begin(), shape.end())};
749 buffer<R> out(size);
750 const std::size_t chunks {(size + detail::elementwise_chunk - 1) / detail::elementwise_chunk};
751 detail::parallel_for(chunks, detail::elementwise_chunk, [&](std::size_t c) {
752 const std::size_t first {c * detail::elementwise_chunk};
753 const std::size_t last {std::min(first + detail::elementwise_chunk, size)};
754 std::transform(a + first, a + last, b + first, out.data() + first, op);
755 });
756 return tensor<R> {shape, std::move(out)};
757 }
758
766 template <typename T,
767 typename Op,
768 typename R = std::invoke_result_t<const Op&, const T&, const T&>>
769 [[nodiscard]] tensor<R> broadcast_into(const T* a,
770 const std::vector<std::size_t>& a_shape,
771 const std::vector<std::ptrdiff_t>& a_strides,
772 const T* b,
773 const std::vector<std::size_t>& b_shape,
774 const std::vector<std::ptrdiff_t>& b_strides,
775 const Op& op)
776 {
777 if (a_shape == b_shape && lies_row_major(a_shape, a_strides) && lies_row_major(b_shape, b_strides)) {
778 return pairs_into(a, b, a_shape, op);
779 }
780 std::vector<std::size_t> shape {broadcast_shape(a_shape, b_shape)};
781 const std::size_t full_rank {shape.size()};
782 const auto aligned {[full_rank](const std::vector<std::size_t>& extents,
783 const std::vector<std::ptrdiff_t>& steps) {
784 std::vector<std::ptrdiff_t> out(full_rank, 0); // a missing axis broadcasts
785 for (std::size_t i {0}; i < extents.size(); ++i) {
786 out[full_rank - extents.size() + i] = extents[i] == 1 ? 0 : steps[i];
787 }
788 return out;
789 }};
790 const std::vector<std::ptrdiff_t> full_sa {aligned(a_shape, a_strides)};
791 const std::vector<std::ptrdiff_t> full_sb {aligned(b_shape, b_strides)};
792 const std::size_t count {detail::element_count(shape.begin(), shape.end())};
793 buffer<R> out(count); // every element written below
794 if (count == 0) {
795 return tensor<R> {std::move(shape), std::move(out)};
796 }
797 // Neighbouring axes each operand steps through as one (its stride on the outer the inner's times the inner's
798 // extent, a broadcast axis 0 on both) run as one axis: the same elements in the same order.
799 std::vector<std::size_t> dims {shape[0]};
800 std::vector<std::ptrdiff_t> sa {full_sa[0]};
801 std::vector<std::ptrdiff_t> sb {full_sb[0]};
802 for (std::size_t axis {1}; axis < full_rank; ++axis) {
803 const auto extent {static_cast<std::ptrdiff_t>(shape[axis])};
804 if (sa.back() == full_sa[axis] * extent && sb.back() == full_sb[axis] * extent) {
805 dims.back() *= shape[axis];
806 sa.back() = full_sa[axis];
807 sb.back() = full_sb[axis];
808 continue;
809 }
810 dims.push_back(shape[axis]);
811 sa.push_back(full_sa[axis]);
812 sb.push_back(full_sb[axis]);
813 }
814 const std::size_t rank {dims.size()};
815 // The innermost axis runs as one loop, each operand stepping along it (1, or 0 where it broadcasts, a scalar or
816 // a row against a matrix a plain vector loop); the odometer turns only between rows. The rows go by tasks, each
817 // task's odometer set from its first row; a row longer than \ref elementwise_chunk (a vector, or a whole
818 // row-major operand against a scalar, its axes run as one) by pieces of it, each piece a task.
819 const std::size_t inner {dims[rank - 1]};
820 const std::ptrdiff_t step_a {sa[rank - 1]};
821 const std::ptrdiff_t step_b {sb[rank - 1]};
822 const std::size_t rows {count / inner};
823 const std::size_t pieces {(inner + detail::elementwise_chunk - 1) / detail::elementwise_chunk};
824 const std::size_t rows_per_task {std::max<std::size_t>(1, detail::elementwise_chunk / inner)};
825 const std::size_t tasks {pieces > 1 ? rows * pieces : (rows + rows_per_task - 1) / rows_per_task};
826 const auto row_apart {static_cast<std::ptrdiff_t>(inner)};
827 detail::parallel_for(tasks, pieces > 1 ? detail::elementwise_chunk : rows_per_task * inner, [&](std::size_t task) {
828 const std::size_t first {pieces > 1 ? task / pieces : task * rows_per_task};
829 const std::size_t last {pieces > 1 ? first + 1 : std::min(first + rows_per_task, rows)};
830 const std::size_t from {pieces > 1 ? (task % pieces) * detail::elementwise_chunk : 0};
831 const std::size_t to {pieces > 1 ? std::min(inner, from + detail::elementwise_chunk) : inner};
832 std::vector<std::size_t> index(rank, 0);
833 std::ptrdiff_t ia {0};
834 std::ptrdiff_t ib {0};
835 for (std::size_t axis {rank - 1}, rest {first}; axis-- > 0;) { // the first row's position
836 index[axis] = rest % dims[axis];
837 rest /= dims[axis];
838 ia += static_cast<std::ptrdiff_t>(index[axis]) * sa[axis];
839 ib += static_cast<std::ptrdiff_t>(index[axis]) * sb[axis];
840 }
841 // Two axes, short rows, one operand's row the same for every row (stride 0) and the other's rows
842 // together (stepping 1 along a row of two axes, its rows `inner` apart): that row repeated into
843 // a run of at least 64, the task's rows one loop against it.
844 if (rank == 2 && inner < 32 && step_a == 1 && step_b == 1 && (sa[0] == 0) != (sb[0] == 0)
845 && (sa[0] == 0 ? sb[0] : sa[0]) == row_apart) {
846 const bool a_repeats {sa[0] == 0};
847 const T* const row_of {a_repeats ? a : b};
848 const T* const whole {(a_repeats ? b : a) + (first * inner)};
849 R* const po {out.data() + (first * inner)};
850 const std::size_t span {((64 + inner - 1) / inner) * inner};
851 std::array<T, 96> repeated {};
852 for (std::size_t i {0}; i < span; ++i) {
853 repeated[i] = row_of[i % inner];
854 }
855 const std::size_t total {(last - first) * inner};
856 for (std::size_t at {0}; at < total; at += span) {
857 const std::size_t n {std::min(span, total - at)};
858 if (a_repeats) {
859 for (std::size_t i {0}; i < n; ++i) {
860 po[at + i] = op(repeated[i], whole[at + i]);
861 }
862 }
863 else {
864 for (std::size_t i {0}; i < n; ++i) {
865 po[at + i] = op(whole[at + i], repeated[i]);
866 }
867 }
868 }
869 return;
870 }
871 // Two axes, short rows, one operand a column (one element a row, stepping 0 along it, its rows
872 // together) and the other's rows together: each run of rows' column elements spread over their
873 // rows, one loop against them.
874 if (rank == 2 && inner < 32 && ((step_a == 0 && step_b == 1) || (step_a == 1 && step_b == 0))
875 && (step_a == 1 ? sb[0] : sa[0]) == 1 && (step_a == 1 ? sa[0] : sb[0]) == row_apart) {
876 const bool a_spreads {step_a == 0};
877 const T* const column {(a_spreads ? a : b) + first};
878 const T* const whole {(a_spreads ? b : a) + (first * inner)};
879 R* const po {out.data() + (first * inner)};
880 const std::size_t run {256 / inner};
881 std::array<T, 256> spread {};
882 for (std::size_t at {0}; at < last - first; at += run) {
883 const std::size_t n {std::min(run, last - first - at)};
884 for (std::size_t r {0}; r < n; ++r) {
885 std::fill_n(spread.data() + (r * inner), inner, column[at + r]);
886 }
887 const T* const w {whole + (at * inner)};
888 R* const o {po + (at * inner)};
889 if (a_spreads) {
890 for (std::size_t i {0}; i < n * inner; ++i) {
891 o[i] = op(spread[i], w[i]);
892 }
893 }
894 else {
895 for (std::size_t i {0}; i < n * inner; ++i) {
896 o[i] = op(w[i], spread[i]);
897 }
898 }
899 }
900 return;
901 }
902 const std::size_t n {to - from};
903 for (std::size_t row {first}; row < last; ++row) {
904 const T* const pa {a + ia + (static_cast<std::ptrdiff_t>(from) * step_a)};
905 const T* const pb {b + ib + (static_cast<std::ptrdiff_t>(from) * step_b)};
906 R* const po {out.data() + (row * inner) + from};
907 if (step_a == 1 && step_b == 1) {
908 for (std::size_t i {0}; i < n; ++i) {
909 po[i] = op(pa[i], pb[i]);
910 }
911 }
912 else if (step_a == 1 && step_b == 0) {
913 const T y {pb[0]};
914 for (std::size_t i {0}; i < n; ++i) {
915 po[i] = op(pa[i], y);
916 }
917 }
918 else if (step_a == 0 && step_b == 1) {
919 const T x {pa[0]};
920 for (std::size_t i {0}; i < n; ++i) {
921 po[i] = op(x, pb[i]);
922 }
923 }
924 else if (step_a == 0 && step_b == 0) {
925 std::fill(po, po + n, op(pa[0], pb[0]));
926 }
927 else { // a view's steps (reversed, or every few elements)
928 for (std::size_t i {0}; i < n; ++i) {
929 const auto at {static_cast<std::ptrdiff_t>(i)};
930 po[i] = op(pa[at * step_a], pb[at * step_b]);
931 }
932 }
933 for (std::size_t axis {rank - 1}; axis-- > 0;) { // odometer over the outer axes: carry on wrap
934 ++index[axis];
935 ia += sa[axis];
936 ib += sb[axis];
937 if (index[axis] < dims[axis]) {
938 break;
939 }
940 ia -= sa[axis] * static_cast<std::ptrdiff_t>(dims[axis]);
941 ib -= sb[axis] * static_cast<std::ptrdiff_t>(dims[axis]);
942 index[axis] = 0;
943 }
944 }
945 });
946 return tensor<R> {std::move(shape), std::move(out)};
947 }
948
954 template <typename T,
955 typename Op,
956 typename R = std::invoke_result_t<const Op&, const T&, const T&>>
957 [[nodiscard]] tensor<R> broadcast_into(const T* a,
958 const std::vector<std::size_t>& a_shape,
959 const T* b,
960 const std::vector<std::size_t>& b_shape,
961 const Op& op)
962 {
963 return broadcast_into(a, a_shape, row_major_strides(a_shape), b, b_shape, row_major_strides(b_shape), op);
964 }
965 } // namespace detail
966
967 namespace detail {
969 inline constexpr std::size_t pairwise_lanes {8};
970
972 template <typename T>
973 [[nodiscard]] T pairwise_quad(const T* p,
974 std::size_t width)
975 {
976 return (p[0] + p[width]) + (p[2 * width] + p[3 * width]);
977 }
978
985 template <typename T>
987 static constexpr std::size_t lanes {pairwise_lanes};
988 static constexpr std::size_t block {128};
989
991 [[nodiscard]] static constexpr std::size_t half(std::size_t count) noexcept
992 {
993 return (count / 2) - ((count / 2) % pairwise_lanes);
994 }
995
997 [[nodiscard]] static T combine(const T* p,
998 std::size_t width = 1)
999 {
1000 return pairwise_quad(p, width) + pairwise_quad(p + (4 * width), width);
1001 }
1002 };
1003
1005 template <split_complex C>
1006 struct pairwise_tree<C> {
1007 static constexpr std::size_t lanes {4};
1008 static constexpr std::size_t block {64};
1009
1012 [[nodiscard]] static constexpr std::size_t half(std::size_t count) noexcept
1013 {
1014 return (count - (count % 8)) / 2;
1015 }
1016
1018 [[nodiscard]] static C combine(const C* p,
1019 std::size_t width = 1)
1020 {
1021 return pairwise_quad(p, width);
1022 }
1023 };
1024
1029 template <typename T>
1030 [[nodiscard]] T pairwise_sum(const T* first,
1031 std::size_t count,
1032 std::size_t stride)
1033 {
1034 using tree = pairwise_tree<T>;
1035 constexpr std::size_t lanes {tree::lanes};
1036 if (count < lanes) {
1037 T sum {};
1038 for (std::size_t i {0}; i < count; ++i) {
1039 sum += first[i * stride];
1040 }
1041 return sum;
1042 }
1043 if (count <= tree::block) {
1044 std::array<T, lanes> partial {};
1045 for (std::size_t j {0}; j < lanes; ++j) {
1046 partial[j] = first[j * stride];
1047 }
1048 std::size_t i {lanes};
1049 for (; i < count - (count % lanes); i += lanes) {
1050 for (std::size_t j {0}; j < lanes; ++j) {
1051 partial[j] += first[(i + j) * stride];
1052 }
1053 }
1054 T sum {tree::combine(partial.data())};
1055 for (; i < count; ++i) {
1056 sum += first[i * stride];
1057 }
1058 return sum;
1059 }
1060 const std::size_t half {tree::half(count)};
1061 return pairwise_sum(first, half, stride) + pairwise_sum(first + (half * stride), count - half, stride);
1062 }
1063
1066 inline constexpr std::size_t pairwise_leaf {std::size_t {1} << 15U};
1067
1070 template <typename T>
1071 void pairwise_leaves(std::size_t count,
1072 std::vector<std::size_t>& out)
1073 {
1074 if (count <= pairwise_leaf) {
1075 out.push_back(count);
1076 return;
1077 }
1078 const std::size_t half {pairwise_tree<T>::half(count)};
1079 pairwise_leaves<T>(half, out);
1080 pairwise_leaves<T>(count - half, out);
1081 }
1082
1085 template <typename T>
1086 [[nodiscard]] T pairwise_combine(std::size_t count,
1087 const T*& next)
1088 {
1089 if (count <= pairwise_leaf) {
1090 return *next++;
1091 }
1092 const std::size_t half {pairwise_tree<T>::half(count)};
1093 const T left {pairwise_combine(half, next)};
1094 const T right {pairwise_combine(count - half, next)};
1095 return left + right;
1096 }
1097
1104 template <typename T>
1105 [[nodiscard]] T parallel_pairwise_sum(const T* first,
1106 std::size_t count)
1107 {
1108 if (count <= 4 * pairwise_leaf) {
1109 return pairwise_sum(first, count, 1);
1110 }
1111 std::vector<std::size_t> lengths;
1112 pairwise_leaves<T>(count, lengths);
1113 std::vector<std::size_t> starts(lengths.size());
1114 std::exclusive_scan(lengths.begin(), lengths.end(), starts.begin(), std::size_t {0});
1115 buffer<T> sums(lengths.size());
1116 parallel_for(lengths.size(), pairwise_leaf, [&](std::size_t leaf) { sums[leaf] = pairwise_sum(first + starts[leaf], lengths[leaf], 1); });
1117 const T* next {sums.data()};
1118 return pairwise_combine(count, next);
1119 }
1120
1126 template <typename T>
1127 void pairwise_sum_rows(const T* first,
1128 std::size_t count,
1129 std::size_t stride,
1130 std::size_t width,
1131 T* out)
1132 {
1133 using tree = pairwise_tree<T>;
1134 constexpr std::size_t lanes {tree::lanes};
1135 constexpr std::size_t block {tree::block};
1136 const auto row = [&](std::size_t i) { return first + (i * stride); };
1137 if (count < lanes) {
1138 std::fill_n(out, width, T {});
1139 for (std::size_t i {0}; i < count; ++i) {
1140 for (std::size_t q {0}; q < width; ++q) {
1141 out[q] += row(i)[q];
1142 }
1143 }
1144 return;
1145 }
1146 if (count <= block) {
1147 buffer<T> partial(lanes * width); // every element written before it is read
1148 for (std::size_t j {0}; j < lanes; ++j) {
1149 std::copy_n(row(j), width, partial.data() + (j * width));
1150 }
1151 std::size_t i {lanes};
1152 for (; i < count - (count % lanes); i += lanes) {
1153 for (std::size_t j {0}; j < lanes; ++j) {
1154 T* const sums {partial.data() + (j * width)};
1155 const T* const next {row(i + j)};
1156 for (std::size_t q {0}; q < width; ++q) {
1157 sums[q] += next[q];
1158 }
1159 }
1160 }
1161 const T* const p {partial.data()};
1162 for (std::size_t q {0}; q < width; ++q) {
1163 out[q] = tree::combine(p + q, width);
1164 }
1165 for (; i < count; ++i) {
1166 for (std::size_t q {0}; q < width; ++q) {
1167 out[q] += row(i)[q];
1168 }
1169 }
1170 return;
1171 }
1172 const std::size_t half {tree::half(count)};
1173 buffer<T> second(width);
1174 pairwise_sum_rows(first, half, stride, width, out);
1175 pairwise_sum_rows(row(half), count - half, stride, width, second.data());
1176 for (std::size_t q {0}; q < width; ++q) {
1177 out[q] = out[q] + second[q];
1178 }
1179 }
1180
1183 inline constexpr std::size_t pairwise_columns {512};
1184
1191 template <typename T>
1192 void pairwise_sums(const T* data,
1193 std::size_t outer,
1194 std::size_t count,
1195 std::size_t inner,
1196 T* out)
1197 {
1198 const std::size_t runs {(inner + pairwise_columns - 1) / pairwise_columns}; // a block's runs of columns
1199 parallel_for(outer * runs, count * std::min(inner, pairwise_columns), [&](std::size_t task) {
1200 const std::size_t o {task / runs};
1201 const T* const base {data + (o * count * inner)};
1202 if (inner == 1) {
1203 out[o] = parallel_pairwise_sum(base, count);
1204 return;
1205 }
1206 const std::size_t q {(task % runs) * pairwise_columns};
1207 pairwise_sum_rows(base + q, count, inner, std::min(pairwise_columns, inner - q), out + (o * inner) + q);
1208 });
1209 }
1210
1212 [[nodiscard]] inline bool is_label(char ch)
1213 {
1214 return std::isalpha(static_cast<unsigned char>(ch)) != 0;
1215 }
1216
1218 [[nodiscard]] inline std::vector<std::string> split_inputs(const std::string& lhs)
1219 {
1220 std::vector<std::string> groups;
1221 std::string current;
1222 for (const char ch : lhs) {
1223 if (ch == ',') {
1224 groups.push_back(current);
1225 current.clear();
1226 }
1227 else if (is_label(ch)) {
1228 current.push_back(ch);
1229 }
1230 else {
1231 throw einsum_error("einsum: invalid character in input subscripts");
1232 }
1233 }
1234 groups.push_back(current);
1235 return groups;
1236 }
1237
1245 template <typename T>
1246 [[nodiscard]] tensor<T> tile_gemm(const T* a,
1247 std::size_t lda,
1248 const T* b,
1249 std::size_t ldb,
1250 std::size_t rows,
1251 std::size_t inner,
1252 std::size_t cols,
1253 std::vector<std::size_t> out_shape)
1254 {
1255 buffer<T> c(rows * cols); // the caller routes only an output of two elements or more here
1256 gemm(rows, cols, inner, a, lda, b, ldb, c.data(), cols, c_start::zero);
1257 return tensor<T> {std::move(out_shape), std::move(c)};
1258 }
1259
1261 inline constexpr std::size_t vector_chunk {128};
1262
1264 template <typename T>
1265 inline constexpr std::size_t term_work {is_complex_number<T> ? 4 : 1};
1266
1269 inline constexpr std::size_t strided_columns {8};
1270
1272 template <typename T>
1273 void add_column_term(std::true_type /*fused*/,
1274 T& sum,
1275 const T& f,
1276 const T& x)
1277 {
1278 sum = std::fma(f, x, sum);
1279 }
1280
1283 template <typename T>
1284 void add_column_term(std::false_type /*fused*/,
1285 T& sum,
1286 const T& f,
1287 const T& x)
1288 {
1289 sum = rounded_apart_add(sum, f, x);
1290 }
1291
1295 template <std::size_t Width, bool Fused = false, typename T>
1296 void strided_column_group(const T* a,
1297 const T* b,
1298 std::size_t row_step,
1299 std::size_t column_step,
1300 std::size_t inner,
1301 std::size_t j,
1302 T* y)
1303 {
1304 std::array<T, Width> sums {};
1305 for (std::size_t k {0}; k < inner; ++k) {
1306 const T f {a[k]};
1307 const T* const row {b + (k * row_step) + (j * column_step)};
1308 for (std::size_t c {0}; c < Width; ++c) {
1309 add_column_term(std::bool_constant<Fused> {}, sums[c], f, row[c * column_step]);
1310 }
1311 }
1312 std::copy(sums.begin(), sums.end(), y + j);
1313 }
1314
1322 template <typename T, bool Fused = false>
1323 [[nodiscard]] buffer<T> vector_times_columns(const T* a,
1324 const T* b,
1325 std::size_t row_step,
1326 std::size_t column_step,
1327 std::size_t inner,
1328 std::size_t cols)
1329 {
1330 static_assert(strided_columns == 8, "the switch below names each narrower last group");
1331 buffer<T> y(cols);
1332 parallel_for((cols + vector_chunk - 1) / vector_chunk, term_work<T> * inner * vector_chunk, [&](std::size_t chunk) {
1333 const std::size_t last {std::min((chunk + 1) * vector_chunk, cols)};
1334 std::size_t j {chunk * vector_chunk};
1335 for (; j + strided_columns <= last; j += strided_columns) {
1336 strided_column_group<strided_columns, Fused>(a, b, row_step, column_step, inner, j, y.data());
1337 }
1338 switch (last - j) {
1339 case 1: strided_column_group<1, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1340 case 2: strided_column_group<2, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1341 case 3: strided_column_group<3, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1342 case 4: strided_column_group<4, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1343 case 5: strided_column_group<5, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1344 case 6: strided_column_group<6, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1345 case 7: strided_column_group<7, Fused>(a, b, row_step, column_step, inner, j, y.data()); break;
1346 default: break; // a whole number of groups
1347 }
1348 });
1349 return y;
1350 }
1351
1354 [[nodiscard]] inline buffer<float> vector_times_columns(const float* a,
1355 const float* b,
1356 std::size_t row_step,
1357 std::size_t column_step,
1358 std::size_t inner,
1359 std::size_t cols)
1360 {
1361 [[maybe_unused]] const gemm_path path {gemm_path_current()};
1362#ifdef NUMERICAL_X86_COMPILED
1363 if (path == gemm_path::avx2 || path == gemm_path::avx512) {
1364 buffer<float> y(cols);
1365 parallel_for((cols + vector_chunk - 1) / vector_chunk, inner * vector_chunk, [&](std::size_t chunk) {
1366 avx2_strided_columns(a, b, row_step, column_step, inner, chunk * vector_chunk, std::min((chunk + 1) * vector_chunk, cols), y.data());
1367 });
1368 return y;
1369 }
1370#endif
1371#ifdef NUMERICAL_NEON_COMPILED
1372 if (path == gemm_path::neon || path == gemm_path::amx) {
1373 return vector_times_columns<float, true>(a, b, row_step, column_step, inner, cols);
1374 }
1375#endif
1376 return vector_times_columns<float>(a, b, row_step, column_step, inner, cols);
1377 }
1378
1382 [[nodiscard]] inline buffer<double> vector_times_columns(const double* a,
1383 const double* b,
1384 std::size_t row_step,
1385 std::size_t column_step,
1386 std::size_t inner,
1387 std::size_t cols)
1388 {
1389 [[maybe_unused]] const gemm_path path {gemm_path_current()};
1390#ifdef NUMERICAL_X86_COMPILED
1391 if (path == gemm_path::avx2 || path == gemm_path::avx512) {
1392 buffer<double> y(cols);
1393 parallel_for((cols + vector_chunk - 1) / vector_chunk, inner * vector_chunk, [&](std::size_t chunk) {
1394 avx2_strided_columns(a, b, row_step, column_step, inner, chunk * vector_chunk, std::min((chunk + 1) * vector_chunk, cols), y.data());
1395 });
1396 return y;
1397 }
1398#endif
1399#ifdef NUMERICAL_NEON_COMPILED
1400 if (path == gemm_path::neon || path == gemm_path::amx) {
1401 return vector_times_columns<double, true>(a, b, row_step, column_step, inner, cols);
1402 }
1403#endif
1404 return vector_times_columns<double>(a, b, row_step, column_step, inner, cols);
1405 }
1406
1407#ifdef NUMERICAL_X86_COMPILED
1409 template <split_complex C>
1410 inline constexpr std::size_t complex_tile_depth {std::is_same_v<C, std::complex<double>> ? gemm_kc / 2 : gemm_kc};
1411
1412 static_assert(complex_tile_depth<std::complex<double>> == avx2_complex_tile_kernel::depth
1413 && complex_tile_depth<std::complex<double>> == avx512_complex_tile_kernel::depth
1414 && complex_tile_depth<std::complex<float>> == avx2_complex_tile_kernel_f32::depth
1415 && complex_tile_depth<std::complex<float>> == avx512_complex_tile_kernel_f32::depth,
1416 "avx2_complex_row_panels sums by the complex tiles' panels");
1417#endif
1418
1421 inline constexpr std::size_t complex_row_columns {32};
1422
1430 template <split_complex C>
1431 [[nodiscard]] buffer<C> complex_vector_times_columns(const C* a,
1432 const C* b,
1433 std::size_t row_step,
1434 std::size_t column_step,
1435 std::size_t inner,
1436 std::size_t cols)
1437 {
1438 if (inner == 0) {
1439 return buffer<C>(cols, C {});
1440 }
1441 // Columns a task: a share of them for each thread, a whole number of complex_row_columns, at most vector_chunk;
1442 // a narrow B then shared out where one chunk would keep it on one thread.
1443 const std::size_t share {(cols + max_threads() - 1) / max_threads()};
1444 const std::size_t width {std::clamp(((share + complex_row_columns - 1) / complex_row_columns) * complex_row_columns, complex_row_columns, vector_chunk)};
1445 buffer<C> y(cols);
1446 parallel_for((cols + width - 1) / width, term_work<C> * inner * width, [&](std::size_t chunk) {
1447 const std::size_t first {chunk * width};
1448 const std::size_t last {std::min(first + width, cols)};
1449#ifdef NUMERICAL_X86_COMPILED
1450 using R = typename C::value_type;
1451 avx2_complex_row_panels(reinterpret_cast<const R*>(a), // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
1452 reinterpret_cast<const R*>(b + (first * column_step)), // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
1453 row_step, column_step, inner, complex_tile_depth<C>, last - first,
1454 reinterpret_cast<R*>(y.data() + first)); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
1455#else
1456# ifdef NUMERICAL_NEON_COMPILED
1457 if (column_step == 1) {
1458 neon_split_row_columns(a, b, row_step, inner, first, last, y.data());
1459 return;
1460 }
1461# endif
1462 split_row_columns(a, b, row_step, column_step, inner, first, last, y.data());
1463#endif
1464 });
1465 return y;
1466 }
1467
1470 template <typename T>
1471 [[nodiscard]] buffer<T> vector_times_transposed(const T* a,
1472 const T* bt,
1473 std::size_t ldbt,
1474 std::size_t inner,
1475 std::size_t cols)
1476 {
1477 if constexpr (split_complex<T>) {
1478 if (complex_terms() != complex_term::compiler) {
1479 return complex_vector_times_columns(a, bt, 1, ldbt, inner, cols);
1480 }
1481 }
1482 return vector_times_columns(a, bt, 1, ldbt, inner, cols);
1483 }
1484
1487 template <typename T>
1488 void add_row_terms(T* y,
1489 const T* a,
1490 const T* b,
1491 std::size_t ldb,
1492 std::size_t inner,
1493 std::size_t count)
1494 {
1495 for (std::size_t k {0}; k < inner; ++k) {
1496 add_product(y, a[k], b + (k * ldb), count);
1497 }
1498 }
1499
1500#ifdef NUMERICAL_NEON_COMPILED
1507 inline void neon_add_row_terms(double* y,
1508 const double* a,
1509 const double* b,
1510 std::size_t ldb,
1511 std::size_t inner,
1512 std::size_t count)
1513 {
1514 std::vector<double> negated(inner);
1515 for (std::size_t k {0}; k < inner; ++k) {
1516 negated[k] = -a[k];
1517 }
1518 neon_subtract_products(y, negated.data(), b, ldb, inner, count);
1519 }
1520
1522 inline void neon_add_row_terms(float* y,
1523 const float* a,
1524 const float* b,
1525 std::size_t ldb,
1526 std::size_t inner,
1527 std::size_t count)
1528 {
1529 for (std::size_t k {0}; k < inner; ++k) {
1530 neon_scaled_add(y, b + (k * ldb), a[k], count);
1531 }
1532 }
1533
1534#endif
1535
1538 template <std::floating_point T>
1539 void add_row_terms(T* y,
1540 const T* a,
1541 const T* b,
1542 std::size_t ldb,
1543 std::size_t inner,
1544 std::size_t count)
1545 {
1546 [[maybe_unused]] const gemm_path path {gemm_path_current()};
1547#ifdef NUMERICAL_X86_COMPILED
1548 if (path == gemm_path::avx2 || path == gemm_path::avx512) {
1549 for (std::size_t k {0}; k < inner; ++k) {
1550 if constexpr (std::is_same_v<T, double>) {
1551 add_product(y, a[k], b + (k * ldb), count); // fused there, AVX-512's own where it runs
1552 }
1553 else {
1554 avx2_scaled_add(y, b + (k * ldb), a[k], count);
1555 }
1556 }
1557 return;
1558 }
1559#endif
1560#ifdef NUMERICAL_NEON_COMPILED
1561 if (path == gemm_path::neon || path == gemm_path::amx) {
1562 neon_add_row_terms(y, a, b, ldb, inner, count);
1563 return;
1564 }
1565#endif
1566 for (std::size_t k {0}; k < inner; ++k) {
1567 const T f {a[k]};
1568 const T* const row {b + (k * ldb)};
1569 for (std::size_t j {0}; j < count; ++j) {
1570 y[j] = rounded_apart_add(y[j], f, row[j]);
1571 }
1572 }
1573 }
1574
1576 template <split_complex C>
1577 [[nodiscard]] bool parts_finite(const C* x,
1578 std::size_t count) noexcept
1579 {
1580 bool finite {true};
1581 for (std::size_t i {0}; i < count; ++i) {
1582 finite &= std::isfinite(x[i].real()) && std::isfinite(x[i].imag());
1583 }
1584 return finite;
1585 }
1586
1593 template <split_complex C>
1594 void add_row_terms(C* y,
1595 const C* a,
1596 const C* b,
1597 std::size_t ldb,
1598 std::size_t inner,
1599 std::size_t count)
1600 {
1601 for (std::size_t k {0}; k < inner; ++k) {
1602 const C f {a[k]};
1603 const C* const row {b + (k * ldb)};
1604 if (std::isfinite(f.real()) && std::isfinite(f.imag()) && parts_finite(row, count)) {
1605 add_product(y, f, row, count);
1606 continue;
1607 }
1608 for (std::size_t j {0}; j < count; ++j) {
1609 y[j] = rounded_apart_add(y[j], f, row[j]);
1610 }
1611 }
1612 }
1613
1620#if defined(__aarch64__) || defined(_M_ARM64)
1621 inline constexpr std::size_t column_sums_below {16};
1622#else
1623 inline constexpr std::size_t column_sums_below {9};
1624#endif
1625
1632 template <typename T>
1633 [[nodiscard]] tensor<T> canonical_product(const T* a,
1634 std::size_t lda,
1635 const T* b,
1636 std::size_t ldb,
1637 std::size_t rows,
1638 std::size_t inner,
1639 std::size_t cols,
1640 std::vector<std::size_t> out_shape)
1641 {
1642 if (cols == 1 && rows > 1 && inner != 0) { // a matrix times a vector: each row's dot product, as "i,i->"
1643 buffer<T> y(rows);
1644 matrix_times_vector(a, lda, rows, inner, b, y.data());
1645 return tensor<T> {std::move(out_shape), std::move(y)};
1646 }
1647 if (rows == 1 && cols > 1 && inner != 0) { // a vector times a matrix: its rows scaled and added in order
1648 if constexpr (split_complex<T>) {
1649 if (complex_terms() != complex_term::compiler) { // the terms of the path's complex product
1650 return tensor<T> {std::move(out_shape), complex_vector_times_columns(a, b, ldb, 1, inner, cols)};
1651 }
1652 }
1653 if (cols < column_sums_below) { // a narrow one: its columns' sums held instead, the same bits
1654 return tensor<T> {std::move(out_shape), vector_times_columns(a, b, ldb, 1, inner, cols)};
1655 }
1656 buffer<T> y(cols, T {});
1657 parallel_for((cols + vector_chunk - 1) / vector_chunk, term_work<T> * inner * vector_chunk, [&](std::size_t chunk) {
1658 const std::size_t first {chunk * vector_chunk};
1659 const std::size_t count {std::min(vector_chunk, cols - first)};
1660 add_row_terms(y.data() + first, a, b + first, ldb, inner, count);
1661 });
1662 return tensor<T> {std::move(out_shape), std::move(y)};
1663 }
1664 if (rows * cols != 1) { // the product, an empty one included; a single element is one dot product
1665 return tile_gemm<T>(a, lda, b, ldb, rows, inner, cols, std::move(out_shape));
1666 }
1667 return tensor<T> {std::move(out_shape), buffer<T> {chunked_dot(a, b, inner)}};
1668 }
1669
1676 template <typename T>
1677 [[nodiscard]] std::optional<tensor<T>> diagonal_labels(const std::string& in,
1678 const std::string& output,
1679 std::size_t distinct,
1680 const std::vector<std::size_t>& shape,
1681 const T* data)
1682 {
1683 const std::size_t rank {in.size()};
1684 if (distinct + 1 != rank || in[rank - 1] != in[rank - 2]) { // a rank of 2 or more, its other labels once
1685 return std::nullopt;
1686 }
1687 const std::string batch {in.substr(0, rank - 2)};
1688 const bool kept {output == batch + in[rank - 1]};
1689 if (!kept && output != batch) {
1690 return std::nullopt;
1691 }
1692 const std::size_t n {shape[rank - 1]};
1693 const std::size_t outer {element_count(shape.begin(), shape.end() - 2)};
1694 std::vector<std::size_t> out_shape(shape.begin(), shape.end() - 2);
1695 buffer<T> along(outer * n);
1696 for (std::size_t b {0}; b < outer; ++b) {
1697 for (std::size_t i {0}; i < n; ++i) {
1698 along[(b * n) + i] = data[(b * n * n) + (i * (n + 1))];
1699 }
1700 }
1701 if (kept) {
1702 out_shape.push_back(n);
1703 return tensor<T> {std::move(out_shape), std::move(along)};
1704 }
1705 buffer<T> sums(outer, T {});
1706 if (n > 0) {
1707 pairwise_sums(along.data(), outer, n, 1, sums.data());
1708 }
1709 return tensor<T> {std::move(out_shape), std::move(sums)};
1710 }
1711
1719 template <typename T>
1720 [[nodiscard]] std::optional<tensor<T>> sum_over_run(const std::string& in,
1721 const std::string& output,
1722 const std::vector<std::size_t>& shape,
1723 const T* data)
1724 {
1725 const std::size_t first {in.find_first_not_of(output)};
1726 if (first == std::string::npos) {
1727 return std::nullopt; // nothing summed: a permutation, or the operand itself
1728 }
1729 const std::size_t next {in.find_first_of(output, first)};
1730 const std::size_t past {next == std::string::npos ? in.size() : next};
1731 if (in.substr(0, first) + in.substr(past) != output) {
1732 return std::nullopt;
1733 }
1734 std::vector<std::size_t> out_shape;
1735 for (std::size_t k {0}; k < in.size(); ++k) {
1736 if (k < first || k >= past) {
1737 out_shape.push_back(shape[k]);
1738 }
1739 }
1740 // The result's elements: none where a kept extent is 0, whatever the others (each part then 0); else their
1741 // checked product, which bounds the parts, and the run's with them the operand's.
1742 const std::size_t kept {element_count(out_shape.begin(), out_shape.end())};
1743 if (kept == 0) {
1744 return tensor<T> {std::move(out_shape), buffer<T> {}};
1745 }
1746 const auto begin {shape.begin()};
1747 const std::size_t outer {element_count(begin, begin + static_cast<std::ptrdiff_t>(first))};
1748 const std::size_t run {element_count(begin + static_cast<std::ptrdiff_t>(first), begin + static_cast<std::ptrdiff_t>(past))};
1749 const std::size_t inner {element_count(begin + static_cast<std::ptrdiff_t>(past), shape.end())};
1750 buffer<T> sums(kept); // the tensor's own storage, moved in
1751 pairwise_sums(data, outer, run, inner, sums.data());
1752 return tensor<T> {std::move(out_shape), std::move(sums)};
1753 }
1754
1763 template <typename T>
1764 [[nodiscard]] buffer<T> permuted(const T* data,
1765 std::size_t count,
1766 const std::string& from,
1767 const std::string& to,
1768 const std::map<char, std::size_t>& sizes,
1769 std::size_t ld)
1770 {
1771 buffer<T> out(count); // every element written below
1772 if (count == 0) {
1773 return out;
1774 }
1775 const std::size_t lead {to.size() - 2}; // the leading axes a transpose of the last two keeps
1776 if (to.compare(0, lead, from, 0, lead) == 0) { // the leading labels kept: the last two exchanged, `to` differing from `from`
1777 // A transpose of the last two axes, each slice of the leading ones by tiles, each read and written in the cache;
1778 // the slices' bands of rows shared among the threads.
1779 const std::size_t rows {sizes.at(from[lead])};
1780 const std::size_t cols {sizes.at(from[lead + 1])};
1781 const std::size_t apart {ld == 0 ? cols : ld}; // the elements between one row of a slice and the next
1782 const std::size_t slices {count / (rows * cols)};
1783 const std::size_t bands {(rows + transpose_tile - 1) / transpose_tile};
1784 const std::size_t piece {transpose_piece(cols * sizeof(T), rows * sizeof(T))};
1785 parallel_for(slices * bands, transpose_tile * cols, [&](std::size_t task) {
1786 const std::size_t slice {task / bands};
1787 const std::size_t r0 {(task % bands) * transpose_tile};
1788 const std::size_t r1 {std::min(r0 + transpose_tile, rows)};
1789 const T* const in {data + (slice * rows * apart)};
1790 T* const into {out.data() + (slice * rows * cols)};
1791 for (std::size_t c0 {0}; c0 < cols; c0 += transpose_tile) {
1792 transpose_walk(r0, r1, c0, std::min(c0 + transpose_tile, cols), piece,
1793 [&](std::size_t r, std::size_t c) { into[(c * rows) + r] = in[(r * apart) + c]; });
1794 }
1795 });
1796 return out;
1797 }
1798 const std::size_t rank {to.size()};
1799 std::map<char, std::size_t> source; // each label's stride in data
1800 std::size_t step {1};
1801 for (std::size_t axis {from.size()}; axis-- > 0;) {
1802 source[from[axis]] = step;
1803 step *= sizes.at(from[axis]);
1804 }
1805 std::vector<std::size_t> stride(rank);
1806 std::vector<std::size_t> extent(rank);
1807 for (std::size_t axis {0}; axis < rank; ++axis) {
1808 stride[axis] = source.at(to[axis]);
1809 extent[axis] = sizes.at(to[axis]);
1810 }
1811 // Each row of the result along its last label from its own index (its outer labels' strides summed), a strided
1812 // sweep; the rows shared among the threads.
1813 const std::size_t inner {extent[rank - 1]};
1814 const std::size_t sweep {stride[rank - 1]};
1815 parallel_for(count / inner, memory_element_weight * inner, [&](std::size_t row) {
1816 std::size_t rest {row};
1817 std::size_t offset {0};
1818 for (std::size_t axis {rank - 1}; axis-- > 0;) {
1819 offset += (rest % extent[axis]) * stride[axis];
1820 rest /= extent[axis];
1821 }
1822 for (std::size_t i {0}; i < inner; ++i) {
1823 out[(row * inner) + i] = data[offset + (i * sweep)];
1824 }
1825 });
1826 return out;
1827 }
1828
1830 template <typename T>
1831 [[nodiscard]] buffer<T> permuted(const buffer<T>& data,
1832 const std::string& from,
1833 const std::string& to,
1834 const std::map<char, std::size_t>& sizes)
1835 {
1836 return permuted(data.data(), data.size(), from, to, sizes);
1837 }
1838
1841 template <typename T>
1843 {
1844 const T* data;
1845 std::size_t count;
1846 };
1847
1854 template <std::floating_point T>
1855 [[nodiscard]] inline T fused_from_zero(T p,
1856 T q) noexcept
1857 {
1858 const T product {p * q};
1859#ifdef NUMERICAL_X86_COMPILED
1860 // One comparison, then −0 added (which leaves every number as it is) or +0 (which turns a zero +0): GCC
1861 // vectorizes it, where it kept `p == 0 || q == 0` a branch per element (einsum `ij,j->ij` of 30 × 134 on eight
1862 // AVX2 cores, 9.8 → 5.5 µs). On arm64 the two comparisons are the faster (Clang, 40 200 elements: 9.8 µs
1863 // against 12.8).
1864 return product + (std::min(std::abs(p), std::abs(q)) == T {} ? T {} : -T {});
1865#else
1866 return p == T {} || q == T {} ? product + T {} : product;
1867#endif
1868 }
1869
1872 template <std::floating_point R>
1873 [[nodiscard]] inline std::complex<R> tile_product(const std::complex<R>& p,
1874 const std::complex<R>& q) noexcept
1875 {
1876 const R re {fused_from_zero(p.real(), q.real()) - fused_from_zero(p.imag(), q.imag())};
1877 const R im {fused_from_zero(p.real(), q.imag()) + fused_from_zero(p.imag(), q.real())};
1878 return {R {} + re, R {} + im};
1879 }
1880
1884 template <std::floating_point R>
1885 [[nodiscard]] inline std::complex<R> split_product(const std::complex<R>& p,
1886 const std::complex<R>& q) noexcept
1887 {
1888 return {std::fma(-p.imag(), q.imag(), fused_from_zero(p.real(), q.real())),
1889 std::fma(-p.imag(), -q.real(), fused_from_zero(p.real(), q.imag()))};
1890 }
1891
1895 template <typename T>
1896 requires std::is_arithmetic_v<T>
1897 [[nodiscard]] tensor<T> each_rounded(const T* x,
1898 const std::vector<std::size_t>& x_shape,
1899 const T* y,
1900 const std::vector<std::size_t>& y_shape)
1901 {
1902 if constexpr (std::is_floating_point_v<T>) { // gemm_rows fuses no integer's terms
1903 if (rows_terms_fuse<T>()) {
1904 return broadcast_into(x, x_shape, y, y_shape, [](T p, T q) { return fused_from_zero(p, q); });
1905 }
1906 }
1907 return broadcast_into(x, x_shape, y, y_shape, [](T p, T q) { return rounded_apart_add(T {}, p, q); });
1908 }
1909
1911 template <split_complex T>
1912 [[nodiscard]] tensor<T> each_rounded(const T* x,
1913 const std::vector<std::size_t>& x_shape,
1914 const T* y,
1915 const std::vector<std::size_t>& y_shape)
1916 {
1917 if (complex_terms() != complex_term::compiler) {
1918#ifdef NUMERICAL_X86_COMPILED
1919 return broadcast_into(x, x_shape, y, y_shape, [](const T& p, const T& q) { return tile_product(p, q); });
1920#else
1921 return broadcast_into(x, x_shape, y, y_shape, [](const T& p, const T& q) { return split_product(p, q); });
1922#endif
1923 }
1924 return broadcast_into(x, x_shape, y, y_shape, [](const T& p, const T& q) { return rounded_apart_add(T {}, p, q); });
1925 }
1926
1928 template <typename T>
1929 concept element_product = std::is_arithmetic_v<T> || split_complex<T>;
1930
1939 template <typename T>
1940 [[nodiscard]] tensor<T> each_product(const std::string& sa,
1942 const std::string& sb,
1944 const std::string& output,
1945 const std::map<char, std::size_t>& sizes)
1946 {
1947 const auto in_output_order {[&](const std::string& labels, operand_span<T> t, buffer<T>& copy, std::vector<std::size_t>& shape) {
1948 std::string order;
1949 for (const char label : output) {
1950 const bool carried {labels.find(label) != std::string::npos};
1951 shape.push_back(carried ? sizes.at(label) : 1);
1952 if (carried) {
1953 order.push_back(label);
1954 }
1955 }
1956 if (order == labels) {
1957 return t.data;
1958 }
1959 copy = permuted(t.data, t.count, labels, order, sizes);
1960 return static_cast<const T*>(copy.data());
1961 }};
1962 buffer<T> a_copy;
1963 buffer<T> b_copy;
1964 std::vector<std::size_t> a_shape;
1965 std::vector<std::size_t> b_shape;
1966 const T* const x {in_output_order(sa, a, a_copy, a_shape)};
1967 const T* const y {in_output_order(sb, b, b_copy, b_shape)};
1968 return each_rounded(x, a_shape, y, b_shape);
1969 }
1970
1981 template <typename T>
1982 [[nodiscard]] tensor<T> contract_pair(const std::string& sa,
1984 const std::string& sb,
1986 const std::string& output,
1987 const std::string& summed,
1988 const std::map<char, std::size_t>& sizes)
1989 {
1990 std::string batch;
1991 std::string free_a;
1992 std::string free_b;
1993 for (const char label : output) {
1994 const bool in_a {sa.find(label) != std::string::npos};
1995 const bool in_b {sb.find(label) != std::string::npos};
1996 (in_a && in_b ? batch : (in_a ? free_a : free_b)).push_back(label);
1997 }
1998 if (batch + free_a + free_b != output && batch + free_b + free_a == output) {
1999 // The other operand first lays the result out in the output's order: the same terms in the same order
2000 // (each a product of the same two numbers), with no permutation of the result.
2001 return contract_pair(sb, b, sa, a, output, summed, sizes);
2002 }
2003 std::size_t inner {1};
2004 for (const char label : summed) {
2005 inner *= sizes.at(label);
2006 }
2007 if constexpr (element_product<T>) {
2008 // A batch of such products (ij,j->ij: one of depth one per row; ij,ij->ij: one per element) element by
2009 // element; a single one (i,j->ij, an outer product) stays one product of depth one, whose kernel the
2010 // processor's vectors run (four AVX2 cores, 200 by 200: 21 µs, 25 element by element in code built for any
2011 // x86-64).
2012 if (summed.empty() && !batch.empty()) {
2013 return each_product(sa, a, sb, b, output, sizes);
2014 }
2015 }
2016 const auto extent_of {[&sizes](const std::string& labels) {
2017 std::size_t product {1};
2018 for (const char label : labels) {
2019 product = checked_mul(product, sizes.at(label));
2020 }
2021 return product;
2022 }};
2023 const std::size_t batches {extent_of(batch)};
2024 const std::size_t rows {extent_of(free_a)};
2025 const std::size_t cols {extent_of(free_b)};
2026 const std::string left_order {batch + free_a + summed};
2027 const std::string right_order {batch + summed + free_b};
2028 const buffer<T> left {sa == left_order ? buffer<T> {} : permuted(a.data, a.count, sa, left_order, sizes)};
2029 const buffer<T> right {sb == right_order ? buffer<T> {} : permuted(b.data, b.count, sb, right_order, sizes)};
2030 const T* const left_data {sa == left_order ? a.data : left.data()};
2031 const T* const right_data {sb == right_order ? b.data : right.data()};
2032 buffer<T> c(checked_mul(batches, checked_mul(rows, cols)));
2033 if (rows == 1 && cols == 1) { // a dot product per batch, as `chunked_dot` sums each chunk
2034 parallel_for(batches, inner, [&](std::size_t p) {
2035 c[p] = dot_product(left_data + (p * inner), right_data + (p * inner), inner);
2036 });
2037 }
2038 else {
2039 const auto product {[&](std::size_t p) {
2040 gemm(rows, cols, inner, left_data + (p * rows * inner), inner, right_data + (p * inner * cols), cols,
2041 c.data() + (p * rows * cols), cols, c_start::zero);
2042 }};
2043 if (batches < max_threads()) { // fewer than the threads: one after another, each on all of them
2044 for (std::size_t p {0}; p < batches; ++p) {
2045 product(p);
2046 }
2047 }
2048 else {
2049 parallel_for(batches, rows * cols * inner / gemm_kernel_speedup, product);
2050 }
2051 }
2052 std::vector<std::size_t> shape;
2053 for (const char label : output) {
2054 shape.push_back(sizes.at(label));
2055 }
2056 const std::string order {batch + free_a + free_b};
2057 return tensor<T> {std::move(shape), order == output ? std::move(c) : permuted(c, order, output, sizes)};
2058 }
2059
2062 inline constexpr std::size_t exhaustive_path_operands {4};
2063
2067 {
2068 std::size_t first;
2069 std::size_t second;
2070 };
2071
2074 [[nodiscard]] inline std::string pair_keeps(const std::vector<std::string>& labels,
2075 std::size_t i,
2076 std::size_t j,
2077 const std::string& output)
2078 {
2079 std::string elsewhere {output};
2080 for (std::size_t k {0}; k < labels.size(); ++k) {
2081 elsewhere += k == i || k == j ? std::string {} : labels[k];
2082 }
2083 std::string keep;
2084 for (const char label : labels[i] + labels[j]) {
2085 if (elsewhere.find(label) != std::string::npos && keep.find(label) == std::string::npos) {
2086 keep.push_back(label);
2087 }
2088 }
2089 return keep;
2090 }
2091
2093 [[nodiscard]] inline double extent_product(const std::string& labels,
2094 const std::map<char, std::size_t>& sizes)
2095 {
2096 double product {1.0};
2097 std::string seen;
2098 for (const char label : labels) {
2099 if (seen.find(label) == std::string::npos) {
2100 seen.push_back(label);
2101 product *= static_cast<double>(sizes.at(label));
2102 }
2103 }
2104 return product;
2105 }
2106
2108 [[nodiscard]] inline std::vector<std::string> after_step(const std::vector<std::string>& labels,
2109 contraction_step step,
2110 const std::string& output)
2111 {
2112 std::vector<std::string> next;
2113 for (std::size_t k {0}; k < labels.size(); ++k) {
2114 if (k != step.first && k != step.second) {
2115 next.push_back(labels[k]);
2116 }
2117 }
2118 next.push_back(pair_keeps(labels, step.first, step.second, output));
2119 return next;
2120 }
2121
2124 inline void cheapest_path(const std::vector<std::string>& labels,
2125 const std::string& output,
2126 const std::map<char, std::size_t>& sizes,
2127 std::vector<contraction_step>& path,
2128 double& cost,
2129 double& largest)
2130 {
2131 if (labels.size() < 2) {
2132 path.clear();
2133 cost = 0.0;
2134 largest = 0.0;
2135 return;
2136 }
2137 bool found {false};
2138 for (std::size_t i {0}; i < labels.size(); ++i) {
2139 for (std::size_t j {i + 1}; j < labels.size(); ++j) {
2140 const contraction_step step {.first = i, .second = j};
2141 std::vector<contraction_step> rest;
2142 double rest_cost {0.0};
2143 double rest_largest {0.0};
2144 cheapest_path(after_step(labels, step, output), output, sizes, rest, rest_cost, rest_largest);
2145 const double here {extent_product(labels[i] + labels[j], sizes)};
2146 const double size {extent_product(pair_keeps(labels, i, j, output), sizes)};
2147 const double total {here + rest_cost};
2148 const double peak {std::max(size, rest_largest)};
2149 if (!found || total < cost || (total == cost && peak < largest)) {
2150 found = true;
2151 cost = total;
2152 largest = peak;
2153 path.assign(1, step);
2154 path.insert(path.end(), rest.begin(), rest.end());
2155 }
2156 }
2157 }
2158 }
2159
2168 [[nodiscard]] inline std::vector<contraction_step> contraction_path(std::vector<std::string> labels,
2169 const std::string& output,
2170 const std::map<char, std::size_t>& sizes)
2171 {
2172 std::vector<contraction_step> path;
2173 if (labels.size() <= exhaustive_path_operands) {
2174 double cost {0.0};
2175 double largest {0.0};
2176 cheapest_path(labels, output, sizes, path, cost, largest);
2177 return path;
2178 }
2179 const auto shares {[&labels](std::size_t i, std::size_t j) {
2180 return labels[i].find_first_of(labels[j]) != std::string::npos;
2181 }};
2182 while (labels.size() > 1) {
2183 contraction_step best {.first = 0, .second = 1};
2184 double best_cost {-1.0};
2185 double best_size {0.0};
2186 bool connected {false}; // a pair sharing a label exists: an outer product waits
2187 for (std::size_t i {0}; i < labels.size(); ++i) {
2188 for (std::size_t j {i + 1}; j < labels.size(); ++j) {
2189 connected = connected || shares(i, j);
2190 }
2191 }
2192 for (std::size_t i {0}; i < labels.size(); ++i) {
2193 for (std::size_t j {i + 1}; j < labels.size(); ++j) {
2194 if (connected && !shares(i, j)) {
2195 continue;
2196 }
2197 const double here {extent_product(labels[i] + labels[j], sizes)};
2198 const double size {extent_product(pair_keeps(labels, i, j, output), sizes)};
2199 if (best_cost < 0.0 || here < best_cost || (here == best_cost && size < best_size)) {
2200 best = {.first = i, .second = j};
2201 best_cost = here;
2202 best_size = size;
2203 }
2204 }
2205 }
2206 path.push_back(best);
2207 labels = after_step(labels, best, output);
2208 }
2209 return path;
2210 }
2211
2225 [[nodiscard]] inline std::size_t ellipsis_in(const std::string& subscripts)
2226 {
2227 const std::size_t at {subscripts.find("...")};
2228 const auto dots {static_cast<std::size_t>(std::count(subscripts.begin(), subscripts.end(), '.'))};
2229 if (dots != (at == std::string::npos ? 0U : 3U)) {
2230 throw einsum_error("einsum: '.' stands only as one ellipsis, '...', per subscript");
2231 }
2232 return at;
2233 }
2234
2241 template <typename T>
2242 [[nodiscard]] tensor<T> einsum_pair(const std::string& s0,
2244 const std::string& s1,
2246 const std::string& output,
2247 const std::string& summed,
2248 const std::map<char, std::size_t>& sizes)
2249 {
2250 // Fast path: a plain two-operand single contraction in canonical layout —
2251 // `A` ending with the contracted label, `B` starting with it, and the
2252 // output being A's leading free labels then B's trailing ones — is exactly
2253 // a matrix product, routed to the packed kernel (gemm.hpp).
2254 if (summed.size() == 1) {
2255 const char contracted {summed.front()};
2256 if (s0.back() == contracted && s1.front() == contracted // the contracted label in both, so neither empty
2257 && output == s0.substr(0, s0.size() - 1) + s1.substr(1)) {
2258 const std::size_t inner {sizes.at(contracted)};
2259 std::vector<std::size_t> out_shape;
2260 for (std::size_t k {0}; k + 1 < s0.size(); ++k) {
2261 out_shape.push_back(sizes.at(s0[k]));
2262 }
2263 for (std::size_t k {1}; k < s1.size(); ++k) {
2264 out_shape.push_back(sizes.at(s1[k]));
2265 }
2266 // The result's elements, 0 where one of its extents is 0 whatever the others (an empty contraction's
2267 // operands may hold any number along their other axes); else checked, and the rows and columns within.
2268 if (element_count(out_shape.begin(), out_shape.end()) == 0) {
2269 return tensor<T> {std::move(out_shape), buffer<T> {}};
2270 }
2271 const auto split {out_shape.begin() + static_cast<std::ptrdiff_t>(s0.size() - 1)};
2272 const std::size_t rows {element_count(out_shape.begin(), split)};
2273 const std::size_t cols {element_count(split, out_shape.end())};
2274 return canonical_product<T>(a.data, inner, b.data, cols, rows, inner, cols, std::move(out_shape));
2275 }
2276 }
2277 return contract_pair<T>(s0, a, s1, b, output, summed, sizes);
2278 }
2279
2280 template <typename T>
2281 [[nodiscard]] tensor<T> einsum_impl(const std::string& spec_in,
2282 const std::vector<const tensor<T>*>& operands);
2283
2284 template <std::signed_integral T>
2285 [[nodiscard]] tensor<T> einsum_impl(const std::string& spec_in,
2286 const std::vector<const tensor<T>*>& operands);
2287
2296 template <typename T>
2297 [[nodiscard]] tensor<T> einsum_ellipsis(const std::string& spec,
2298 const std::vector<const tensor<T>*>& operands)
2299 {
2300 const std::size_t arrow {spec.find("->")};
2301 std::vector<std::string> inputs {""};
2302 for (const char ch : spec.substr(0, arrow)) {
2303 if (ch == ',') {
2304 inputs.emplace_back();
2305 }
2306 else {
2307 inputs.back().push_back(ch);
2308 }
2309 }
2310 if (inputs.size() != operands.size()) {
2311 throw einsum_error("einsum: number of operands does not match the spec");
2312 }
2313 std::vector<std::size_t> at(inputs.size());
2314 std::vector<std::size_t> under(inputs.size(), 0); // the axes each operand's ellipsis stands for
2315 std::size_t widest {0};
2316 for (std::size_t i {0}; i < inputs.size(); ++i) {
2317 at[i] = ellipsis_in(inputs[i]);
2318 if (at[i] != std::string::npos) {
2319 const std::size_t letters {inputs[i].size() - 3};
2320 if (operands[i]->rank() < letters) {
2321 throw einsum_error("einsum: operand rank does not match its subscripts");
2322 }
2323 under[i] = operands[i]->rank() - letters;
2324 widest = std::max(widest, under[i]);
2325 }
2326 }
2327 static constexpr std::string_view alphabet {"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"};
2328 std::string fresh;
2329 for (const char letter : alphabet) {
2330 if (fresh.size() < widest && spec.find(letter) == std::string::npos) {
2331 fresh.push_back(letter);
2332 }
2333 }
2334 if (fresh.size() < widest) {
2335 throw einsum_error("einsum: too many axes under the ellipsis for the letters left");
2336 }
2337 std::vector<std::size_t> extent(widest, 1);
2338 for (std::size_t i {0}; i < inputs.size(); ++i) {
2339 for (std::size_t d {0}; d < under[i]; ++d) {
2340 const std::size_t dim {operands[i]->shape()[at[i] + d]};
2341 std::size_t& broadcast {extent[widest - under[i] + d]};
2342 if (dim != 1 && broadcast != 1 && dim != broadcast) {
2343 throw dimension_error("einsum: the axes under the ellipsis do not broadcast");
2344 }
2345 broadcast = dim == 1 ? broadcast : dim;
2346 }
2347 }
2348 std::deque<tensor<T>> owned; // the operands with axes dropped (a deque keeps their addresses)
2349 std::vector<const tensor<T>*> next;
2350 std::string rewritten;
2351 for (std::size_t i {0}; i < inputs.size(); ++i) {
2352 rewritten += i == 0 ? "" : ",";
2353 if (at[i] == std::string::npos) {
2354 rewritten += inputs[i];
2355 next.push_back(operands[i]);
2356 continue;
2357 }
2358 std::string labels {inputs[i].substr(0, at[i])};
2359 std::vector<std::size_t> shape(operands[i]->shape().begin(), operands[i]->shape().begin() + static_cast<std::ptrdiff_t>(at[i]));
2360 for (std::size_t d {0}; d < under[i]; ++d) {
2361 const std::size_t axis {widest - under[i] + d};
2362 const std::size_t dim {operands[i]->shape()[at[i] + d]};
2363 if (dim != extent[axis]) { // 1 where another operand's is longer: repeated, its letter dropped
2364 continue;
2365 }
2366 labels.push_back(fresh[axis]);
2367 shape.push_back(dim);
2368 }
2369 labels += inputs[i].substr(at[i] + 3);
2370 shape.insert(shape.end(), operands[i]->shape().begin() + static_cast<std::ptrdiff_t>(at[i] + under[i]), operands[i]->shape().end());
2371 rewritten += labels;
2372 if (shape.size() == operands[i]->rank()) {
2373 next.push_back(operands[i]);
2374 }
2375 else {
2376 owned.emplace_back(std::move(shape), buffer<T>(operands[i]->data().begin(), operands[i]->data().end()));
2377 next.push_back(&owned.back());
2378 }
2379 }
2380 std::string output;
2381 if (arrow != std::string::npos) {
2382 output = spec.substr(arrow + 2);
2383 const std::size_t where {ellipsis_in(output)};
2384 if (where == std::string::npos && widest > 0) {
2385 throw einsum_error("einsum: the output keeps the axes under the ellipsis: '...' in it, as NumPy requires");
2386 }
2387 if (where != std::string::npos) {
2388 output.replace(where, 3, fresh);
2389 }
2390 }
2391 else { // implicit: the broadcast axes, then the letters that appear once, in order
2392 std::map<char, std::size_t> seen;
2393 for (const char label : spec) {
2394 if (is_label(label)) {
2395 ++seen[label];
2396 }
2397 }
2398 output = fresh;
2399 for (const auto& [label, count] : seen) {
2400 if (count == 1) {
2401 output.push_back(label);
2402 }
2403 }
2404 }
2405 return einsum_impl<T>(rewritten + "->" + output, next);
2406 }
2407
2411 template <typename To,
2412 typename From>
2413 [[nodiscard]] tensor<To> converted(const tensor<From>& t)
2414 {
2415 const std::size_t count {t.size()};
2416 const From* const in {t.data().data()};
2417 buffer<To> out(count);
2419 const std::size_t first {c * elementwise_chunk};
2420 std::transform(in + first, in + std::min(count, first + elementwise_chunk), out.data() + first,
2421 [](const From& x) { return static_cast<To>(x); });
2422 });
2423 return tensor<To> {t.shape(), std::move(out)};
2424 }
2425
2428 template <typename T>
2429 [[nodiscard]] tensor<T> einsum_spec(const std::string& spec_in,
2430 const std::vector<const tensor<T>*>& operands)
2431 {
2432 // Tolerate whitespace anywhere in the spec, the way NumPy does ("ij, jk -> ik").
2433 std::string spec {spec_in};
2434 spec.erase(std::remove_if(spec.begin(), spec.end(),
2435 [](unsigned char ch) { return std::isspace(ch) != 0; }),
2436 spec.end());
2437 if (spec.find('.') != std::string::npos) {
2438 return einsum_ellipsis<T>(spec, operands);
2439 }
2440 if (spec.find("->") == std::string::npos) {
2441 // Implicit mode, as NumPy reads it: the output is every label that appears once, in ASCII order (`"ij,jk"`
2442 // is `"ij,jk->ik"`, `"ii"` the trace, `"ba"` the transpose).
2443 std::map<char, std::size_t> seen;
2444 for (const char label : spec) {
2445 if (label != ',') {
2446 ++seen[label];
2447 }
2448 }
2449 spec += "->";
2450 for (const auto& [label, count] : seen) {
2451 if (count == 1) {
2452 spec += label;
2453 }
2454 }
2455 }
2456 const std::size_t arrow {spec.find("->")};
2457 const std::vector<std::string> inputs {split_inputs(spec.substr(0, arrow))};
2458 const std::string rhs {spec.substr(arrow + 2)};
2459
2460 if (operands.size() != inputs.size()) {
2461 throw einsum_error("einsum: number of operands does not match the spec");
2462 }
2463
2464 // A transposed matrix read where its elements lie, as the binding's borrowed einsum reads it: summed over one
2465 // axis (ij->j, ij->i), its diagonal (ii->i, ii->) or permuted (ij->ji), the einsum of the matrix laid out
2466 // under it (tensor::laid_out) with its labels reversed, the view never copied out (one AVX2 core, ij->j of
2467 // order 256 84 → 16 µs, 1024 2.4 → 0.22 ms). Each element the same terms in the same order, so the same bits; a
2468 // sum of every element (ij->), another rank and a pair would take theirs in another order, and keep the copy.
2469 if (operands.size() == 1 && inputs[0].size() == 2 && (!rhs.empty() || inputs[0][0] == inputs[0][1])) {
2470 if (std::optional<std::pair<tensor<T>, std::vector<std::size_t>>> lying {operands[0]->laid_out()}) {
2471 const std::string reversed {inputs[0][1], inputs[0][0]};
2472 const std::vector<const tensor<T>*> base {&lying->first};
2473 return einsum_spec<T>(reversed + "->" + rhs, base);
2474 }
2475 }
2476
2477 // Each label's extent, checked for consistency across every axis it labels.
2478 std::map<char, std::size_t> sizes;
2479 for (std::size_t i {0}; i < operands.size(); ++i) {
2480 if (inputs[i].size() != operands[i]->rank()) {
2481 throw einsum_error("einsum: operand rank does not match its subscripts");
2482 }
2483 for (std::size_t axis {0}; axis < inputs[i].size(); ++axis) {
2484 const char label {inputs[i][axis]};
2485 const std::size_t dim {operands[i]->shape()[axis]};
2486 const auto found {sizes.find(label)};
2487 if (found == sizes.end()) {
2488 sizes.emplace(label, dim);
2489 }
2490 else if (found->second != dim) {
2491 throw dimension_error("einsum: inconsistent extent for a repeated label");
2492 }
2493 }
2494 }
2495
2496 // Output (free) labels: each must be present in the inputs and appear once.
2497 std::string output;
2498 for (const char ch : rhs) {
2499 if (!is_label(ch)) {
2500 throw einsum_error("einsum: invalid character in output subscripts");
2501 }
2502 if (sizes.find(ch) == sizes.end()) {
2503 throw einsum_error("einsum: output label not present in any input");
2504 }
2505 if (output.find(ch) != std::string::npos) {
2506 throw einsum_error("einsum: repeated output label");
2507 }
2508 output.push_back(ch);
2509 }
2510
2511 // Summed labels: those that do not survive into the output (sorted, by map).
2512 std::string summed;
2513 for (const auto& entry : sizes) {
2514 if (output.find(entry.first) == std::string::npos) {
2515 summed.push_back(entry.first);
2516 }
2517 }
2518
2519 // Two operands or more: first sum each one over the labels no other operand and not the output carries
2520 // (`ijk,jl->il` sums k in `ijk->ij` first: I·J·K + I·J·L terms, where one loop over every label ran I·J·K·L),
2521 // then contract them two at a time in the cheapest order (\ref contraction_path), each intermediate keeping
2522 // only the labels still to come. One loop over every label of `ij,jk,kl->il` runs n⁴ terms; pairs run 2·n³, and
2523 // `i,j,k,l,m->` over 65 536 ones each runs five sums of 65 536 instead of 2⁸⁰. A repeated label kept is read
2524 // once, on its diagonal (`ii,i->i` takes `ii->i`).
2525 if (operands.size() > 1) {
2526 std::deque<tensor<T>> owned; // the reductions and intermediates (a deque keeps their addresses)
2527 std::vector<const tensor<T>*> current;
2528 std::vector<std::string> kept;
2529 bool reduced {false};
2530 for (std::size_t i {0}; i < operands.size(); ++i) {
2531 std::string elsewhere {output};
2532 for (std::size_t j {0}; j < operands.size(); ++j) {
2533 elsewhere += j == i ? std::string {} : inputs[j];
2534 }
2535 std::string keep;
2536 for (const char label : inputs[i]) {
2537 if (elsewhere.find(label) != std::string::npos && keep.find(label) == std::string::npos) {
2538 keep.push_back(label);
2539 }
2540 }
2541 if (keep == inputs[i]) { // nothing of its own to sum: the operand itself
2542 current.push_back(operands[i]);
2543 }
2544 else {
2545 const std::vector<const tensor<T>*> alone {operands[i]};
2546 owned.push_back(einsum_impl<T>(inputs[i] + "->" + keep, alone));
2547 current.push_back(&owned.back());
2548 reduced = true;
2549 }
2550 kept.push_back(std::move(keep));
2551 }
2552 if (operands.size() > 2 || reduced) { // a pair with nothing of its own to sum is contracted below
2553 for (const contraction_step step : contraction_path(kept, output, sizes)) {
2554 const std::string keep {kept.size() == 2 ? output : pair_keeps(kept, step.first, step.second, output)};
2555 const std::vector<const tensor<T>*> pair {current[step.first], current[step.second]};
2556 owned.push_back(einsum_impl<T>(kept[step.first] + "," + kept[step.second] + "->" + keep, pair));
2557 current.erase(current.begin() + static_cast<std::ptrdiff_t>(step.second));
2558 current.erase(current.begin() + static_cast<std::ptrdiff_t>(step.first));
2559 kept.erase(kept.begin() + static_cast<std::ptrdiff_t>(step.second));
2560 kept.erase(kept.begin() + static_cast<std::ptrdiff_t>(step.first));
2561 current.push_back(&owned.back());
2562 kept.push_back(keep);
2563 }
2564 return std::move(owned.back()); // the last contraction's, the output
2565 }
2566 }
2567
2568 // Fast path: one operand, nothing summed, each label once: a permutation of its axes (a transpose), a view.
2569 if (operands.size() == 1 && summed.empty() && inputs[0].size() == output.size()) {
2570 std::vector<std::size_t> axes;
2571 for (const char label : output) {
2572 axes.push_back(inputs[0].find(label));
2573 }
2574 return operands[0]->transposed(axes);
2575 }
2576
2577 // Fast path: one operand, each label once, its summed labels one run of its axes and the output the others in
2578 // order (ij->i, ij->, ij->j, ijk->ik): sum_over_run.
2579 if (operands.size() == 1 && sizes.size() == inputs[0].size()) {
2580 if (std::optional<tensor<T>> sums {sum_over_run(inputs[0], output, operands[0]->shape(), operands[0]->data().data())}) {
2581 return *std::move(sums);
2582 }
2583 }
2584
2585 // Fast path: one operand whose last two labels are one (…ii), each other label once and the output those in
2586 // order, with the diagonal's label (…ii->…i: the diagonal) or without (…ii->…: its sum, pairwise as sum() adds,
2587 // so the same bits as trace()). The general loop below added the diagonal's terms one after another.
2588 if (operands.size() == 1) {
2589 if (std::optional<tensor<T>> diagonal {diagonal_labels(inputs[0], output, sizes.size(), operands[0]->shape(), operands[0]->data().data())}) {
2590 return *std::move(diagonal);
2591 }
2592 }
2593
2594 if (operands.size() == 2) {
2595 return einsum_pair<T>(inputs[0], {operands[0]->data().data(), operands[0]->size()}, inputs[1],
2596 {operands[1]->data().data(), operands[1]->size()}, output, summed, sizes);
2597 }
2598
2599 // One operand from here (pairs and more are contracted above), its labels repeated (a diagonal) or summed in
2600 // no run. Every distinct label, output (free) first then summed: this fixes the
2601 // index space and the row-major order of the result.
2602 const std::string labels {output + summed};
2603 const std::size_t n_labels {labels.size()};
2604 const std::size_t n_free {output.size()};
2605 const std::size_t n_ops {operands.size()};
2606
2607 std::vector<std::size_t> extent(n_labels);
2608 for (std::size_t k {0}; k < n_labels; ++k) {
2609 extent[k] = sizes.at(labels[k]);
2610 }
2611
2612 // coef[i][k]: operand i's flat-offset change per unit of label k — the sum
2613 // of its row-major strides over the axes carrying that label (so a label
2614 // repeated within one operand, e.g. "ii", walks that operand's diagonal).
2615 std::vector<std::vector<std::size_t>> coef(n_ops, std::vector<std::size_t>(n_labels, 0));
2616 for (std::size_t i {0}; i < n_ops; ++i) {
2617 const std::vector<std::size_t>& shape {operands[i]->shape()};
2618 std::size_t stride {1};
2619 for (std::size_t axis {inputs[i].size()}; axis-- > 0;) {
2620 coef[i][labels.find(inputs[i][axis])] += stride;
2621 stride *= shape[axis];
2622 }
2623 }
2624
2625 // Fast path: peel the innermost label of each group — the last free label
2626 // and the last summed label — into a tight unit-of-stride inner loop, and
2627 // run the odometer only over the *remaining* (outer) labels. The innermost
2628 // axis is then a contiguous sweep amortising one odometer step over its
2629 // whole extent: a strided write for a transpose/broadcast, a strided
2630 // multiply-accumulate for a contraction — both auto-vectoriser-friendly.
2631 const bool has_free_inner {n_free > 0};
2632 const bool has_sum_inner {n_labels > n_free};
2633 const std::size_t inner_free {has_free_inner ? extent[n_free - 1] : 1};
2634 const std::size_t inner_sum {has_sum_inner ? extent[n_labels - 1] : 1};
2635 const std::size_t free_outer_end {has_free_inner ? n_free - 1 : 0};
2636 const std::size_t sum_outer_end {has_sum_inner ? n_labels - 1 : n_free};
2637
2638 // Per-operand stride of each peeled axis (0 when that axis is absent).
2639 std::vector<std::size_t> free_step(n_ops, 0);
2640 std::vector<std::size_t> sum_step(n_ops, 0);
2641 for (std::size_t i {0}; i < n_ops; ++i) {
2642 if (has_free_inner) {
2643 free_step[i] = coef[i][n_free - 1];
2644 }
2645 if (has_sum_inner) {
2646 sum_step[i] = coef[i][n_labels - 1];
2647 }
2648 }
2649
2650 std::size_t out_size {1};
2651 for (std::size_t k {0}; k < n_free; ++k) {
2652 out_size = detail::checked_mul(out_size, extent[k]); // guard the result allocation size
2653 }
2654 std::vector<std::size_t> out_shape(extent.begin(),
2655 extent.begin() + static_cast<std::ptrdiff_t>(n_free));
2656 if (out_size == 0) { // an empty result computes nothing, whatever its other extents multiply to
2657 return tensor<T> {std::move(out_shape), buffer<T> {}};
2658 }
2659 std::size_t out_outer {1}; // bounded by out_size
2660 for (std::size_t k {0}; k < free_outer_end; ++k) {
2661 out_outer *= extent[k];
2662 }
2663 std::size_t sum_outer {1};
2664 for (std::size_t k {n_free}; k < sum_outer_end; ++k) {
2665 sum_outer = detail::checked_mul(sum_outer, extent[k]); // a wrapped count would sum nothing, silently
2666 }
2667
2668 std::vector<std::size_t> index(n_labels, 0); // value of each outer label
2669 std::vector<std::size_t> offset(n_ops, 0); // each operand's flat offset (outer labels only)
2670 buffer<T> result;
2671 result.reserve(out_size);
2672
2673 for (std::size_t of {0}; of < out_outer; ++of) {
2674 for (std::size_t fe {0}; fe < inner_free; ++fe) {
2675 T acc {};
2676 for (std::size_t os {0}; os < sum_outer; ++os) {
2677 for (std::size_t se {0}; se < inner_sum; ++se) {
2678 // The element itself: a complex 1 times it was no identity (0 · inf is a NaN, and −0 − (−0) a +0), so a
2679 // trace or a sum of complex infinities or signed zeros went wrong.
2680 acc += operands[0]->data()[offset[0] + (fe * free_step[0]) + (se * sum_step[0])];
2681 }
2682 // Step the outer-summed odometer (labels [n_free, sum_outer_end)).
2683 for (std::size_t k {sum_outer_end}; k-- > n_free;) {
2684 if (++index[k] < extent[k]) {
2685 for (std::size_t i {0}; i < n_ops; ++i) {
2686 offset[i] += coef[i][k];
2687 }
2688 break;
2689 }
2690 index[k] = 0;
2691 for (std::size_t i {0}; i < n_ops; ++i) {
2692 offset[i] -= coef[i][k] * (extent[k] - 1);
2693 }
2694 }
2695 }
2696 result.push_back(acc);
2697 }
2698 // Step the outer-free odometer (labels [0, free_outer_end)).
2699 for (std::size_t k {free_outer_end}; k-- > 0;) {
2700 if (++index[k] < extent[k]) {
2701 for (std::size_t i {0}; i < n_ops; ++i) {
2702 offset[i] += coef[i][k];
2703 }
2704 break;
2705 }
2706 index[k] = 0;
2707 for (std::size_t i {0}; i < n_ops; ++i) {
2708 offset[i] -= coef[i][k] * (extent[k] - 1);
2709 }
2710 }
2711 }
2712 return tensor<T> {std::move(out_shape), std::move(result)};
2713 }
2714
2716 template <typename T>
2717 [[nodiscard]] tensor<T> einsum_impl(const std::string& spec_in,
2718 const std::vector<const tensor<T>*>& operands)
2719 {
2720 return einsum_spec<T>(spec_in, operands);
2721 }
2722
2725 template <std::signed_integral T>
2726 [[nodiscard]] tensor<T> einsum_impl(const std::string& spec_in,
2727 const std::vector<const tensor<T>*>& operands)
2728 {
2729 using unsigned_type = std::make_unsigned_t<T>;
2730 std::vector<tensor<unsigned_type>> held;
2731 std::vector<const tensor<unsigned_type>*> wrapped;
2732 held.reserve(operands.size());
2733 for (const tensor<T>* operand : operands) {
2734 held.push_back(converted<unsigned_type>(*operand));
2735 }
2736 for (const tensor<unsigned_type>& operand : held) {
2737 wrapped.push_back(&operand);
2738 }
2739 return converted<T>(einsum_spec<unsigned_type>(spec_in, wrapped));
2740 }
2741 } // namespace detail
2742
2759 template <typename T, typename ... Rest>
2760 [[nodiscard]] tensor<T> einsum(const std::string& spec,
2761 const tensor<T>& first,
2762 const Rest& ... rest)
2763 {
2764 const std::vector<const tensor<T>*> operands {&first, (&rest)...};
2765 return detail::einsum_impl<T>(spec, operands);
2766 }
2767
2777 template <typename T>
2778 [[nodiscard]] tensor<T> einsum(const std::string& spec,
2779 const std::vector<const tensor<T>*>& operands)
2780 {
2781 return detail::einsum_impl<T>(spec, operands);
2782 }
2783
2784 namespace detail {
2787 template <typename T>
2788 [[nodiscard]] tensor<T> stacked_matmul(const tensor<T>& a,
2789 const tensor<T>& b)
2790 {
2791 const std::vector<std::size_t>& sa {a.shape()};
2792 const std::vector<std::size_t>& sb {b.shape()};
2793 if (sa.empty() || sb.empty()) {
2794 throw dimension_error("matmul: a rank-0 operand has no matrix to multiply");
2795 }
2796 const bool row {sa.size() == 1};
2797 const bool column {sb.size() == 1};
2798 const std::size_t m {row ? 1 : sa[sa.size() - 2]};
2799 const std::size_t k {sa.back()};
2800 const std::size_t n {column ? 1 : sb.back()};
2801 if ((column ? sb[0] : sb[sb.size() - 2]) != k) {
2802 throw dimension_error("matmul: the inner extents of the operands differ");
2803 }
2804 const std::size_t lead_a {sa.size() - (row ? 1 : 2)};
2805 const std::size_t lead_b {sb.size() - (column ? 1 : 2)};
2806 const std::size_t rank {std::max(lead_a, lead_b)};
2807 std::vector<std::size_t> batch(rank);
2808 std::vector<std::size_t> stride_a(rank, 0); // 0 along an axis the operand repeats
2809 std::vector<std::size_t> stride_b(rank, 0);
2810 std::size_t step_a {m * k};
2811 std::size_t step_b {k * n};
2812 for (std::size_t d {rank}; d-- > 0;) {
2813 const std::size_t da {d + lead_a >= rank ? sa[d + lead_a - rank] : 1};
2814 const std::size_t db {d + lead_b >= rank ? sb[d + lead_b - rank] : 1};
2815 if (da != db && da != 1 && db != 1) {
2816 throw dimension_error("matmul: the leading axes of the operands do not broadcast");
2817 }
2818 batch[d] = da == 1 ? db : da;
2819 stride_a[d] = da == 1 ? 0 : step_a;
2820 stride_b[d] = db == 1 ? 0 : step_b;
2821 step_a = detail::checked_mul(step_a, da);
2822 step_b = detail::checked_mul(step_b, db);
2823 }
2824 std::size_t count {1};
2825 for (const std::size_t extent : batch) {
2826 count = detail::checked_mul(count, extent);
2827 }
2828 std::vector<std::size_t> shape {batch};
2829 if (!row) {
2830 shape.push_back(m);
2831 }
2832 if (!column) {
2833 shape.push_back(n);
2834 }
2835 const std::array<std::size_t, 3> elements {count, m, n};
2836 buffer<T> c(detail::element_count(elements.begin(), elements.end()));
2837 if (rank == 0) { // no stack: one product
2838 detail::gemm(m, n, k, a.data().data(), k, b.data().data(), n, c.data(), n, detail::c_start::zero);
2839 return tensor<T> {std::move(shape), std::move(c)};
2840 }
2841 // B shared by the whole stack and A's matrices one after another: one product of all A's rows, B packed once
2842 // (1000 × 3 by 3 × 64 matrices times 64 × 64, ten AVX-512 cores, 165 → 87 µs). Each element of C the same.
2843 const bool shared_b {std::ranges::all_of(stride_b, [](std::size_t s) { return s == 0; }) && std::ranges::none_of(stride_a, [](std::size_t s) { return s == 0; })};
2844 if (shared_b) {
2845 detail::gemm(count * m, n, k, a.data().data(), k, b.data().data(), n, c.data(), n, detail::c_start::zero);
2846 return tensor<T> {std::move(shape), std::move(c)};
2847 }
2848 const auto product {[&](std::size_t p) {
2849 std::size_t rest {p};
2850 std::size_t offset_a {0};
2851 std::size_t offset_b {0};
2852 for (std::size_t d {batch.size()}; d-- > 0;) {
2853 const std::size_t index {rest % batch[d]};
2854 rest /= batch[d];
2855 offset_a += index * stride_a[d];
2856 offset_b += index * stride_b[d];
2857 }
2858 detail::gemm(m, n, k, a.data().data() + offset_a, k, b.data().data() + offset_b, n, c.data() + (p * m * n), n, detail::c_start::zero);
2859 }};
2860 // Fewer products than threads: one after another, each on all of them, where the stack's products in parallel held
2861 // each to one (two products of order 1000, ten AVX-512 cores: 28.0 → 7.2 ms); else the stack's products in parallel.
2862 if (count < max_threads()) {
2863 for (std::size_t p {0}; p < count; ++p) {
2864 product(p);
2865 }
2866 return tensor<T> {std::move(shape), std::move(c)};
2867 }
2868 detail::parallel_for(count, m * n * k / detail::gemm_kernel_speedup, product);
2869 return tensor<T> {std::move(shape), std::move(c)};
2870 }
2871 } // namespace detail
2872
2883 template <typename T>
2884 [[nodiscard]] tensor<T> matmul(const tensor<T>& a,
2885 const tensor<T>& b)
2886 {
2887 return detail::stacked_matmul(a, b);
2888 }
2889
2891 template <std::signed_integral T>
2892 [[nodiscard]] tensor<T> matmul(const tensor<T>& a,
2893 const tensor<T>& b)
2894 {
2895 using unsigned_type = std::make_unsigned_t<T>;
2896 return detail::converted<T>(detail::stacked_matmul(detail::converted<unsigned_type>(a), detail::converted<unsigned_type>(b)));
2897 }
2898} // namespace numerical
2899
2900#endif // NUMERICAL_TENSOR_HPP
A standard exception Std that numerical::error tags too, its one what answering for both bases.
Definition vector.hpp:61
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
Thrown when an einsum specification is malformed or inconsistent.
Definition tensor.hpp:53
einsum_error(const std::string &message)
Builds the error.
Definition tensor.hpp:57
Thrown when an index or a range leaves its axis.
Definition vector.hpp:98
A dense, row-major matrix of T with value semantics.
Definition matrix.hpp:36
std::size_t rows() const noexcept
The number of rows.
Definition matrix.hpp:108
std::size_t cols() const noexcept
The number of columns.
Definition matrix.hpp:114
A dense N-dimensional tensor of T with value semantics, read row-major. Its elements are immutable on...
Definition tensor.hpp:88
std::shared_ptr< row_major_copy > copy_
A view's row-major copy; null where the elements lie row-major.
Definition tensor.hpp:619
const std::vector< std::size_t > & shape() const noexcept
The size of each axis.
Definition tensor.hpp:326
tensor(std::vector< std::size_t > shape, std::initializer_list< T > elements)
From a shape and a braced list of the elements, row-major.
Definition tensor.hpp:117
std::optional< std::pair< tensor, std::vector< std::size_t > > > laid_out() const
Where this view reaches each of its elements once from the first (a transpose's, transposed): its axe...
Definition tensor.hpp:291
const T & operator()(const std::vector< std::size_t > &index) const
The element at a multi-index, read where it lies.
Definition tensor.hpp:376
std::optional< std::vector< std::ptrdiff_t > > reshaped_strides(const std::vector< std::size_t > &shape) const
The strides that read this view's elements, in row-major order, under shape (as many elements),...
Definition tensor.hpp:480
bool permutes_elements() const
Whether this view reaches every element of its buffer once, from the first: its axes longer than 1,...
Definition tensor.hpp:408
std::size_t count_
The number of elements: data_'s, unless a view.
Definition tensor.hpp:618
tensor(std::vector< std::size_t > shape, buffer< T > elements)
From a shape and a flat row-major buffer.
Definition tensor.hpp:97
static buffer< T > gathered(const std::vector< std::size_t > &shape, const std::vector< std::ptrdiff_t > &strides, std::size_t offset, const buffer< T > &data)
The elements of data in shape, read along strides from offset, in row-major order: row after row alon...
Definition tensor.hpp:563
tensor(const matrix< T > &m)
A rank-2 tensor from a matrix.
Definition tensor.hpp:139
const buffer< T > & copied_out() const
A view's elements in row-major order, copied out on the first call.
Definition tensor.hpp:522
tensor transposed() const
transposed with the axes reversed: a matrix's transpose, NumPy's .T.
Definition tensor.hpp:306
void finalize()
Computes row-major strides and checks the buffer against the shape.
Definition tensor.hpp:599
bool operator==(const tensor &other) const
Exact equality (same shape and equal elements).
Definition tensor.hpp:386
tensor reshaped(std::vector< std::size_t > shape) const
This tensor's elements in shape, without a copy: the new tensor shares the buffer,...
Definition tensor.hpp:152
const buffer< T > & data() const
The elements, row-major. A view's (transposed) are copied out by the first call, one thread copying w...
Definition tensor.hpp:370
std::size_t rank() const noexcept
The number of axes (0 for a scalar).
Definition tensor.hpp:314
tensor(matrix< T > &&m)
A rank-2 tensor taking over an expiring matrix's elements, without a copy.
Definition tensor.hpp:132
tensor(const vector< T > &v)
A rank-1 tensor from a vector.
Definition tensor.hpp:124
const T * origin() const noexcept
The first element where the elements are held (index 0 along every axis): a view (transposed,...
Definition tensor.hpp:333
std::size_t offset_
Where in data_ the first element lies (a view's, sliced).
Definition tensor.hpp:617
tensor transposed(const std::vector< std::size_t > &axes) const
This tensor with its axes in the order axes (axis k of the result is axis axes[k] of this one),...
Definition tensor.hpp:178
const std::vector< std::ptrdiff_t > & strides() const noexcept
Each axis's step, in elements, from the first element (origin), row-major unless a view,...
Definition tensor.hpp:340
std::size_t size() const noexcept
The total number of elements.
Definition tensor.hpp:320
tensor(std::vector< std::size_t > shape, const std::vector< T > &elements)
From a shape and a flat row-major std::vector, copied into the storage (a buffer moves in instead).
Definition tensor.hpp:110
bool contiguous() const noexcept
Whether the elements lie row-major where they are held: data then copies nothing.
Definition tensor.hpp:346
tensor sliced(const std::vector< std::size_t > &starts, const std::vector< std::ptrdiff_t > &steps, const std::vector< std::size_t > &counts, const Keep &keep) const
The elements starts[a] + i·steps[a] for i < counts[a] along each axis a, without a copy,...
Definition tensor.hpp:209
tensor(std::vector< std::size_t > shape, std::shared_ptr< const buffer< T > > elements)
Over the shared row-major elements elements, in shape (reshaped).
Definition tensor.hpp:435
std::vector< std::size_t > lying_order() const
This view's axes from the widest stride to the narrowest, ties in their order.
Definition tensor.hpp:394
tensor(std::vector< std::size_t > shape, std::vector< std::ptrdiff_t > strides, std::size_t offset, std::shared_ptr< const buffer< T > > elements)
Over the shared elements elements, read along strides from the element at offset (transposed,...
Definition tensor.hpp:445
tensor materialized() const
This tensor holding its own elements row-major and nothing more: itself where they lie so,...
Definition tensor.hpp:357
std::vector< std::ptrdiff_t > strides_
Each axis's step from origin_: row-major unless a view.
Definition tensor.hpp:615
std::shared_ptr< const buffer< T > > data_
The elements, shared with the tensors that hold them.
Definition tensor.hpp:616
tensor diagonal_view(std::size_t row, std::size_t column, std::size_t length) const
The length elements from (row, column) down the diagonal of each matrix (the last two axes),...
Definition tensor.hpp:258
std::vector< std::size_t > shape_
The size of each axis.
Definition tensor.hpp:614
A dense vector of T with value semantics.
Definition vector.hpp:171
std::size_t size() const noexcept
The number of elements.
Definition vector.hpp:194
The element types each_product takes: those each_rounded rounds as a product of depth one.
Definition tensor.hpp:1929
A complex number of float or double, which gemm_split multiplies through the real kernel and the kern...
Definition simd.hpp:188
The matrix product kernel behind matrix * matrix and the einsum matmul path.
A dense, row-major, value-semantic matrix over a scalar type.
constexpr std::size_t pairwise_columns
The columns pairwise_sum_rows sums at once: its partial sums of eight rows, 32 KiB of doubles,...
Definition tensor.hpp:1183
tensor< T > stacked_matmul(const tensor< T > &a, const tensor< T > &b)
numerical::matmul of a type whose sums and products are defined past its range: a float,...
Definition tensor.hpp:2788
std::vector< std::ptrdiff_t > row_major_strides(const std::vector< std::size_t > &shape)
The row-major strides of shape, in elements.
Definition tensor.hpp:710
T fused_from_zero(T p, T q) noexcept
std::fma(p, q, +0) without the instruction (in code built for any x86-64, std::fma is a call to the l...
Definition tensor.hpp:1855
void pairwise_sum_rows(const T *first, std::size_t count, std::size_t stride, std::size_t width, T *out)
pairwise_sum of width neighbouring columns at once, into out: column q's sum that of pairwise_sum(fir...
Definition tensor.hpp:1127
complex_term complex_terms() noexcept
The complex_term of the path in use.
Definition gemm.hpp:2318
buffer< T > vector_times_transposed(const T *a, const T *bt, std::size_t ldbt, std::size_t inner, std::size_t cols)
vector_times_columns of a matrix given as its transpose bt (cols × inner, its rows ldbt apart,...
Definition tensor.hpp:1471
T pairwise_sum(const T *first, std::size_t count, std::size_t stride)
Sum of count values from first at stride stride, by NumPy's pairwise summation (pairwise_tree).
Definition tensor.hpp:1030
tensor< T > tile_gemm(const T *a, std::size_t lda, const T *b, std::size_t ldb, std::size_t rows, std::size_t inner, std::size_t cols, std::vector< std::size_t > out_shape)
Matrix product C(M×N) = A(M×K) · B(K×N), row-major.
Definition tensor.hpp:1246
bool is_label(char ch)
Is ch an ASCII letter (a valid index label)?
Definition tensor.hpp:1212
tensor< T > einsum_pair(const std::string &s0, operand_span< T > a, const std::string &s1, operand_span< T > b, const std::string &output, const std::string &summed, const std::map< char, std::size_t > &sizes)
einsum of two operands a (labels s0) and b (s1) into output, summed the labels neither the output car...
Definition tensor.hpp:2242
bool lies_row_major(const std::vector< std::size_t > &shape, const std::vector< std::ptrdiff_t > &strides)
Whether elements strides apart along the axes of shape lie row-major from the first (an axis of fewer...
Definition tensor.hpp:723
tensor< R > pairs_into(const T *a, const T *b, const std::vector< std::size_t > &shape, const Op &op)
op(a, b) element by element of the row-major a and b, both of shape shape, in op's result type R,...
Definition tensor.hpp:743
constexpr bool range_within(std::size_t first, std::size_t count, std::ptrdiff_t step, std::size_t extent) noexcept
Whether count indices from first, step apart, all lie in [0, extent): none is out for a count of 0....
Definition vector.hpp:115
void transpose_walk(std::size_t i0, std::size_t i1, std::size_t j0, std::size_t j1, std::size_t piece, const Copy &copy)
transpose_pieces of side piece (transpose_piece's 8 or the whole tile), each side its own instance: a...
Definition simd.hpp:142
tensor< T > einsum_impl(const std::string &spec_in, const std::vector< const tensor< T > * > &operands)
Einstein summation of operands as spec_in reads it (einsum): einsum_spec.
Definition tensor.hpp:2717
void run_fused(const Body &body)
body(0), where std::fma is the instruction (with_fma_instruction) on an x86-64 processor with AVX2 an...
Definition tensor.hpp:698
constexpr std::size_t gemm_kernel_speedup
The multiply-adds the register tile does in the time of one in work_per_thread's dependent chain (abo...
Definition gemm.hpp:893
tensor< R > broadcast_into(const T *a, const std::vector< std::size_t > &a_shape, const std::vector< std::ptrdiff_t > &a_strides, const T *b, const std::vector< std::size_t > &b_shape, const std::vector< std::ptrdiff_t > &b_strides, const Op &op)
op(a, b) element by element of a, of shape a_shape, its elements a_strides apart along each axis from...
Definition tensor.hpp:769
constexpr std::size_t complex_row_columns
The columns of a task of complex_vector_times_columns divide: the most its kernels hold in registers ...
Definition tensor.hpp:1421
std::vector< std::string > after_step(const std::vector< std::string > &labels, contraction_step step, const std::string &output)
The list after a contraction step: the two operands' labels removed, their result's appended.
Definition tensor.hpp:2108
buffer< T > vector_times_columns(const T *a, const T *b, std::size_t row_step, std::size_t column_step, std::size_t inner, std::size_t cols)
canonical_product's vector a (inner) times a matrix b whose element B[k][j] is b[(k · row_step) + (j ...
Definition tensor.hpp:1323
void add_row_terms(T *y, const T *a, const T *b, std::size_t ldb, std::size_t inner, std::size_t count)
y[j] += Σₖ a[k] · b[(k · ldb) + j] for count columns, B's inner rows added in order to a vector times...
Definition tensor.hpp:1488
void add_product(double *y, const double &f, const double *x, std::size_t count)
y[i] += f · x[i] for double, as subtract_product.
Definition gemm.hpp:648
constexpr std::size_t term_work
The real multiply-adds of a term a · b of T, as parallel_for counts work: four for a complex one.
Definition tensor.hpp:1265
void cheapest_path(const std::vector< std::string > &labels, const std::string &output, const std::map< char, std::size_t > &sizes, std::vector< contraction_step > &path, double &cost, double &largest)
The cheapest order of contraction from labels, and its cost and largest intermediate: every order tri...
Definition tensor.hpp:2124
tensor< T > canonical_product(const T *a, std::size_t lda, const T *b, std::size_t ldb, std::size_t rows, std::size_t inner, std::size_t cols, std::vector< std::size_t > out_shape)
The product of the row-major rows × inner a and inner × cols b, shaped out_shape: the canonical two-o...
Definition tensor.hpp:1633
std::string shape_text(const std::vector< std::size_t > &shape)
A shape as NumPy prints it, (2, 3), for a message.
Definition tensor.hpp:649
void add_column_term(std::true_type, T &sum, const T &f, const T &x)
sum += f · x of strided_column_group, one fused multiply-add.
Definition tensor.hpp:1273
constexpr std::size_t elementwise_chunk
The elements one task of an element-wise operation takes, a quarter of a thread's work: a tensor of a...
Definition parallel.hpp:734
tensor< T > each_rounded(const T *x, const std::vector< std::size_t > &x_shape, const T *y, const std::vector< std::size_t > &y_shape)
The products that sum nothing of each_product, x and y broadcast against each other (broadcast_into),...
Definition tensor.hpp:1897
std::vector< std::string > split_inputs(const std::string &lhs)
Splits an einsum left-hand side into per-operand subscripts.
Definition tensor.hpp:1218
T parallel_pairwise_sum(const T *first, std::size_t count)
pairwise_sum of count contiguous values on the threads, to the bit: the tree's subtrees of at most pa...
Definition tensor.hpp:1105
@ split
arm64's real kernel's (gemm_split): Re a·Re b from zero, −Im a·Im b fused into it; Re a·Im b,...
std::string pair_keeps(const std::vector< std::string > &labels, std::size_t i, std::size_t j, const std::string &output)
The labels of labels[i] and labels[j] that the output or another operand carries, in their order of a...
Definition tensor.hpp:2074
T rounded_apart_add(T sum, T a, T b) noexcept
sum + a·b as the vector tile rounds it (vector_tile_kernel), so that the plain loop's elements are it...
Definition gemm.hpp:1717
bool parts_finite(const C *x, std::size_t count) noexcept
Whether every part of count complex numbers from x is finite.
Definition tensor.hpp:1577
std::size_t ellipsis_in(const std::string &subscripts)
Evaluates a parsed einsum over its operands.
Definition tensor.hpp:2225
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
Definition parallel.hpp:790
buffer< T > permuted(const T *data, std::size_t count, const std::string &from, const std::string &to, const std::map< char, std::size_t > &sizes, std::size_t ld=0)
The elements of data, whose axes carry the labels from (extents in sizes), laid out row-major along t...
Definition tensor.hpp:1764
void matrix_times_vector(const T *a, std::size_t lda, std::size_t rows, std::size_t cols, const T *x, T *y)
y = A x for the row-major rows × cols a, its rows lda apart: each element the dot product of its row ...
Definition gemm.hpp:5153
std::size_t transpose_piece(std::size_t from_bytes, std::size_t to_bytes) noexcept
The side of the square pieces a transposing copy walks a tile by, from the bytes between rows of its ...
Definition simd.hpp:100
gemm_path gemm_path_current() noexcept
The path the next double product takes: the most capable one under the cap that runs here (each path'...
Definition gemm.hpp:148
std::optional< tensor< T > > diagonal_labels(const std::string &in, const std::string &output, std::size_t distinct, const std::vector< std::size_t > &shape, const T *data)
einsum of one row-major operand data (shape, labelled in, distinct labels in all) whose last two labe...
Definition tensor.hpp:1677
std::complex< R > split_product(const std::complex< R > &p, const std::complex< R > &q) noexcept
0 + p·q of complex numbers as arm64's real kernel rounds it (complex_term::split),...
Definition tensor.hpp:1885
tensor< To > converted(const tensor< From > &t)
A copy of t, each element converted to To (between a signed integer type and its unsigned one,...
Definition tensor.hpp:2413
T pairwise_quad(const T *p, std::size_t width)
Four partial sums at p, width apart, added pairwise: (p₀ + p₁) + (p₂ + p₃).
Definition tensor.hpp:973
tensor< T > each_product(const std::string &sa, operand_span< T > a, const std::string &sb, operand_span< T > b, const std::string &output, const std::map< char, std::size_t > &sizes)
A batch of two-operand products that sum nothing (ij,j->ij, ijk,ik->ijk), each element of the output ...
Definition tensor.hpp:1940
tensor< T > einsum_spec(const std::string &spec_in, const std::vector< const tensor< T > * > &operands)
einsum_impl of a type whose sums and products are defined past its range: a float,...
Definition tensor.hpp:2429
double dot_product(const double *x, const double *y, std::size_t count)
Σ x[i] · y[i] for double, as subtract_product chooses its units (in another order of summation there,...
Definition gemm.hpp:715
std::size_t checked_mul(std::size_t a, std::size_t b)
a * b, throwing numerical::dimension_error if the product overflows std::size_t. Guards dimension/sha...
Definition vector.hpp:135
std::vector< contraction_step > contraction_path(std::vector< std::string > labels, const std::string &output, const std::map< char, std::size_t > &sizes)
The order in which to contract operands labelled labels into output, as opt_einsum chooses it: the ch...
Definition tensor.hpp:2168
void strided_column_group(const T *a, const T *b, std::size_t row_step, std::size_t column_step, std::size_t inner, std::size_t j, T *y)
Columns j to j + Width of vector_times_columns into y, their sums held through the rows: each term on...
Definition tensor.hpp:1296
tensor< T > einsum_ellipsis(const std::string &spec, const std::vector< const tensor< T > * > &operands)
einsum_impl of a spec with ellipses, as NumPy reads them: each ... stands for an operand's axes its l...
Definition tensor.hpp:2297
void pairwise_sums(const T *data, std::size_t outer, std::size_t count, std::size_t inner, T *out)
The pairwise sums of outer blocks of count rows of inner elements (row-major), each column of a block...
Definition tensor.hpp:1192
std::vector< std::size_t > broadcast_strides(const std::vector< std::size_t > &shape, std::size_t rank)
The row-major strides of shape, with a stride of 0 on each axis of extent 1 (it broadcasts),...
Definition tensor.hpp:660
std::size_t element_count(It first, It last)
The elements a shape's extents [first, last) hold: 0 where one of them is 0, whatever the others,...
Definition vector.hpp:151
constexpr std::size_t column_sums_below
The columns under which canonical_product sums a vector times a matrix by vector_times_columns,...
Definition tensor.hpp:1623
std::complex< R > tile_product(const std::complex< R > &p, const std::complex< R > &q) noexcept
0 + p·q of complex numbers as the x86-64 complex tiles round it (complex_term::tiles): each part's pr...
Definition tensor.hpp:1873
constexpr std::size_t vector_chunk
The columns a thread takes of a vector times a matrix: each of its rows added to them in order.
Definition tensor.hpp:1261
std::optional< tensor< T > > sum_over_run(const std::string &in, const std::string &output, const std::vector< std::size_t > &shape, const T *data)
einsum of one row-major operand data (shape, its axes labelled in, each label once) into the labels o...
Definition tensor.hpp:1720
constexpr std::size_t strided_columns
The columns of B one task of vector_times_columns sums together: their sums' chains interleaved,...
Definition tensor.hpp:1269
tensor< T > contract_pair(const std::string &sa, operand_span< T > a, const std::string &sb, operand_span< T > b, const std::string &output, const std::string &summed, const std::map< char, std::size_t > &sizes)
A two-operand contraction as matrix products: the labels both operands and the output carry (batch),...
Definition tensor.hpp:1982
constexpr std::size_t pairwise_lanes
The partial sums pairwise_sum interleaves, and the multiple of which its first half is long.
Definition tensor.hpp:969
void pairwise_leaves(std::size_t count, std::vector< std::size_t > &out)
The lengths of pairwise_sum's subtrees of at most pairwise_leaf values of type T over count,...
Definition tensor.hpp:1071
constexpr std::size_t pairwise_leaf
The longest subtree of pairwise_sum's tree parallel_pairwise_sum sums on one thread: 256 KiB of doubl...
Definition tensor.hpp:1066
T chunked_dot(const T *a, const T *b, std::size_t count, const Dot &dot)
Σ a[i] · b[i] for a plain dot product: chunks of dot_chunk elements in parallel, each by dot,...
Definition gemm.hpp:5066
constexpr std::size_t exhaustive_path_operands
The operands at most whose contraction order contraction_path searches exhaustively; more take the ch...
Definition tensor.hpp:2062
void split_row_columns(const C *a, const C *b, std::size_t row_step, std::size_t column_step, std::size_t inner, std::size_t first, std::size_t last, C *y, bool kept=false)
Columns first to last of the complex vector a (inner) times B (B[k][j] at b[(k · row_step) + (j · col...
Definition gemm.hpp:3895
T pairwise_combine(std::size_t count, const T *&next)
The subtrees' sums from next on (pairwise_leaves' order) added as pairwise_sum's tree over count valu...
Definition tensor.hpp:1086
buffer< C > complex_vector_times_columns(const C *a, const C *b, std::size_t row_step, std::size_t column_step, std::size_t inner, std::size_t cols)
The complex vector a (inner) times a matrix b whose element B[k][j] is b[(k · row_step) + (j · column...
Definition tensor.hpp:1431
constexpr std::size_t memory_element_weight
The weight of an element a pass bound by the memory writes or moves, against a multiply-add,...
Definition parallel.hpp:760
double extent_product(const std::string &labels, const std::map< char, std::size_t > &sizes)
The product of the extents of labels' distinct labels, as a double (a cost: it may pass size_t).
Definition tensor.hpp:2093
The NumericAL public API.
Definition amx.hpp:44
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
Definition buffer.hpp:443
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
Definition parallel.hpp:995
T sum(const tensor< T > &t)
The sum of every element, by pairwise halving (0 for an empty tensor), on the threads where they are ...
constexpr std::size_t sliced_copy_most
The most elements tensor::sliced copies at once rather than viewing (4 KiB of doubles).
Definition tensor.hpp:76
std::vector< std::size_t > broadcast_shape(const std::vector< std::size_t > &a, const std::vector< std::size_t > &b)
The shape two shapes broadcast to, as NumPy's broadcast_shapes.
Definition tensor.hpp:677
gemm_path
The kernels a double matrix product can run on (a float one too on arm64), from the most portable....
Definition gemm.hpp:83
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
@ reduced
Q is m × k, R k × n, k = min(m, n): NumPy's default.
tensor< T > einsum(const std::string &spec, const tensor< T > &first, const Rest &... rest)
Einstein summation over one or more tensor operands.
Definition tensor.hpp:2760
tensor< T > diagonal(const tensor< T > &t, std::ptrdiff_t offset)
The offset diagonal of each matrix of t (its last two axes), as numpy.linalg.diagonal: above the main...
bool approx_equal(const matrix< T > &a, const matrix< T > &b, double tolerance=1e-9)
Element-wise closeness within a tolerance (for inexact scalars).
Definition matrix.hpp:276
tensor< T > matmul(const tensor< T > &a, const tensor< T > &b)
The matrix product of two tensors, as NumPy's matmul: each operand a stack of matrices along its lead...
Definition tensor.hpp:2884
A minimal std::thread parallel-for for the hot kernels.
One step of a contraction path: the operands at first and second of the current list,...
Definition tensor.hpp:2067
std::size_t second
The second's, past the first.
Definition tensor.hpp:2069
std::size_t first
The first operand's position.
Definition tensor.hpp:2068
The elements of an operand of einsum_pair, row-major along its labels: a tensor's,...
Definition tensor.hpp:1843
const T * data
The first element.
Definition tensor.hpp:1844
std::size_t count
The elements, the product of the extents.
Definition tensor.hpp:1845
static constexpr std::size_t half(std::size_t count) noexcept
The first half's length: NumPy's half of the parts (count of them, less their remainder by 8),...
Definition tensor.hpp:1012
static C combine(const C *p, std::size_t width=1)
The partial sums at p, width apart, added pairwise.
Definition tensor.hpp:1018
The shape of NumPy's pairwise summation tree over the values of type T: below lanes values summed in ...
Definition tensor.hpp:986
static T combine(const T *p, std::size_t width=1)
The partial sums at p, width apart, added pairwise: its two fours, then the two.
Definition tensor.hpp:997
static constexpr std::size_t half(std::size_t count) noexcept
The first half's length: half of count, less its remainder by 8.
Definition tensor.hpp:991
A view's elements in row-major order, copied out by the first data call and shared with the view's co...
Definition tensor.hpp:429
std::once_flag made
Set once the elements are copied out.
Definition tensor.hpp:430
buffer< T > elements
The copy.
Definition tensor.hpp:431
A dense, value-semantic vector over a scalar type.