20#ifndef NUMERICAL_TENSOR_HPP
21#define NUMERICAL_TENSOR_HPP
30#include <initializer_list>
69 const std::string&
from,
70 const std::string&
to,
71 const std::map<char, std::size_t>&
sizes,
111 const std::vector<T>& elements)
113 buffer<
T>(elements.begin(), elements.end()))
118 std::initializer_list<T> elements)
154 if (
copy_ ==
nullptr) {
157 std::size_t count {1};
158 for (
const std::size_t extent :
shape) {
181 std::vector<bool>
seen(
rank,
false);
182 for (
const std::size_t
axis :
axes) {
184 throw dimension_error(
"tensor: transposed takes a permutation of the axes");
189 throw dimension_error(
"tensor: transposed takes a permutation of the axes");
193 for (std::size_t k {0}; k <
rank; ++k) {
208 template <
typename Keep = std::vector<
bool>>
210 const std::vector<std::ptrdiff_t>& steps,
211 const std::vector<std::size_t>& counts,
212 const Keep& keep)
const
215 if (starts.size() !=
rank || steps.size() !=
rank || counts.size() !=
rank || keep.size() !=
rank) {
218 std::vector<std::size_t>
shape;
219 std::vector<std::ptrdiff_t>
strides;
222 std::ptrdiff_t offset {
static_cast<std::ptrdiff_t
>(
offset_)};
224 if (!
static_cast<bool>(keep[
axis]) && counts[
axis] != 1) {
225 throw dimension_error(
"tensor: sliced drops an axis of one index only");
228 throw index_error(
"tensor: a range of sliced leaves its axis");
230 if (counts[
axis] != 0) {
233 if (
static_cast<bool>(keep[
axis])) {
246 return tensor {std::move(
shape), std::move(elements)};
260 std::size_t length)
const
265 shape.back() = length;
267 std::size_t count {length};
274 const auto offset {
static_cast<std::size_t
>(
static_cast<std::ptrdiff_t
>(
offset_)
279 return tensor {std::move(
shape), std::move(elements)};
298 std::vector<std::size_t>
shape(order.size());
299 for (std::size_t k {0}; k < order.size(); ++k) {
309 std::iota(
axes.rbegin(),
axes.rend(), std::size_t {0});
348 return copy_ ==
nullptr;
359 if (
copy_ ==
nullptr) {
378 std::ptrdiff_t
flat {
static_cast<std::ptrdiff_t
>(
offset_)};
379 for (std::size_t
axis {0};
axis < index.size(); ++
axis) {
382 return (*
data_)[
static_cast<std::size_t
>(
flat)];
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]; });
436 std::shared_ptr<
const buffer<T>> elements)
446 std::vector<std::ptrdiff_t>
strides,
448 std::shared_ptr<
const buffer<T>> elements)
455 bool row_major {
true};
462 data_ = std::make_shared<const buffer<T>>();
469 copy_ = std::make_shared<row_major_copy>();
482 std::vector<std::size_t>
from;
483 std::vector<std::ptrdiff_t> steps;
493 for (std::size_t
to {0}, at {0};
to <
shape.size() && at <
from.size();) {
495 std::size_t
at_end {at + 1};
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]) {
512 for (std::size_t k {
to_end - 1}; k >
to; --k) {
524 std::call_once(
copy_->made, [
this] {
529 constexpr std::size_t read_directly {std::size_t {1} << 14};
537 std::vector<std::size_t>
lying;
544 std::map<char, std::size_t>
sizes;
545 std::map<std::size_t, char>
label;
551 std::stable_sort(
lying.begin(),
lying.end(), [
this](std::size_t a, std::size_t b) { return strides_[a] > strides_[b]; });
558 return copy_->elements;
564 const std::vector<std::ptrdiff_t>& strides,
571 std::size_t count {1};
572 for (
const std::size_t extent : shape) {
576 const std::size_t inner {shape.back()};
577 const auto step {strides.back()};
578 const T*
const from {data.data()};
581 auto at {
static_cast<std::ptrdiff_t
>(offset)};
583 at +=
static_cast<std::ptrdiff_t
>(
rest % shape[
axis]) * strides[
axis];
586 T*
const to {out.data() + (
row * inner)};
588 std::copy_n(
from + at, inner,
to);
591 for (std::size_t i {0}; i < inner; ++i) {
592 to[i] =
from[at + (
static_cast<std::ptrdiff_t
>(i) *
step)];
601 strides_.assign(shape_.size(), 1);
603 for (std::size_t
axis {shape_.size()};
axis-- > 0;) {
604 strides_[
axis] =
static_cast<std::ptrdiff_t
>(
acc);
607 if (data_->size() !=
acc) {
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_;
629 template <
typename T>
632 double tolerance = 1e-9)
637 for (std::size_t i {0}; i < a.
size(); ++i) {
640 if (!(a.
data()[i] == b.
data()[i]) && !(std::abs(a.
data()[i] - b.
data()[i]) <= tolerance)) {
649 [[nodiscard]]
inline std::string
shape_text(
const std::vector<std::size_t>& shape)
651 std::string out {
"("};
652 for (std::size_t i {0}; i < shape.size(); ++i) {
653 out += (i == 0 ?
"" :
", ") + std::to_string(shape[i]);
655 return out + (shape.size() == 1 ?
",)" :
")");
660 [[nodiscard]]
inline std::vector<std::size_t>
broadcast_strides(
const std::vector<std::size_t>& shape,
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;
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)
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));
689 out[i] = x == 1 ? y : x;
697 template <
typename Body>
700#ifdef NUMERICAL_X86_COMPILED
701 if (cpu_features().avx2_fma) {
702 with_fma_instruction(body, 0);
710 [[nodiscard]]
inline std::vector<std::ptrdiff_t>
row_major_strides(
const std::vector<std::size_t>& shape)
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;) {
716 stride *=
static_cast<std::ptrdiff_t
>(shape[i]);
724 const std::vector<std::ptrdiff_t>& strides)
726 std::ptrdiff_t stride {1};
727 for (std::size_t i {shape.size()}; i-- > 0;) {
728 if (shape[i] > 1 && strides[i] != stride) {
731 stride *=
static_cast<std::ptrdiff_t
>(shape[i]);
740 template <
typename T,
742 typename R = std::invoke_result_t<const Op&, const T&, const T&>>
745 const std::vector<std::size_t>& shape,
748 const std::size_t size {detail::element_count(shape.begin(), shape.end())};
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);
756 return tensor<R> {shape, std::move(out)};
766 template <
typename T,
768 typename R = std::invoke_result_t<const Op&, const T&, const T&>>
770 const std::vector<std::size_t>& a_shape,
771 const std::vector<std::ptrdiff_t>& a_strides,
773 const std::vector<std::size_t>& b_shape,
774 const std::vector<std::ptrdiff_t>& b_strides,
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);
785 for (std::size_t i {0}; i < extents.size(); ++i) {
786 out[full_rank - extents.size() + i] = extents[i] == 1 ? 0 : steps[i];
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())};
795 return tensor<R> {std::move(shape), std::move(out)};
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];
810 dims.push_back(shape[axis]);
811 sa.push_back(full_sa[axis]);
812 sb.push_back(full_sb[axis]);
814 const std::size_t rank {dims.
size()};
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;) {
836 index[axis] = 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];
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];
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)};
859 for (std::size_t i {0}; i < n; ++i) {
860 po[at + i] = op(repeated[i], whole[at + i]);
864 for (std::size_t i {0}; i < n; ++i) {
865 po[at + i] = op(whole[at + i], repeated[i]);
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]);
887 const T*
const w {whole + (at * inner)};
888 R*
const o {po + (at * inner)};
890 for (std::size_t i {0}; i < n * inner; ++i) {
891 o[i] = op(spread[i], w[i]);
895 for (std::size_t i {0}; i < n * inner; ++i) {
896 o[i] = op(w[i], spread[i]);
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]);
912 else if (step_a == 1 && step_b == 0) {
914 for (std::size_t i {0}; i < n; ++i) {
915 po[i] = op(pa[i], y);
918 else if (step_a == 0 && step_b == 1) {
920 for (std::size_t i {0}; i < n; ++i) {
921 po[i] = op(x, pb[i]);
924 else if (step_a == 0 && step_b == 0) {
925 std::fill(po, po + n, op(pa[0], pb[0]));
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]);
933 for (std::size_t axis {rank - 1}; axis-- > 0;) {
937 if (index[axis] < dims[axis]) {
940 ia -= sa[axis] *
static_cast<std::ptrdiff_t
>(dims[axis]);
941 ib -= sb[axis] *
static_cast<std::ptrdiff_t
>(dims[axis]);
946 return tensor<R> {std::move(shape), std::move(out)};
954 template <
typename T,
956 typename R = std::invoke_result_t<const Op&, const T&, const T&>>
958 const std::vector<std::size_t>& a_shape,
960 const std::vector<std::size_t>& b_shape,
972 template <
typename T>
976 return (p[0] + p[width]) + (p[2 * width] + p[3 * width]);
985 template <
typename T>
988 static constexpr std::size_t block {128};
991 [[nodiscard]]
static constexpr std::size_t
half(std::size_t count)
noexcept
998 std::size_t width = 1)
1005 template <split_complex C>
1007 static constexpr std::size_t lanes {4};
1008 static constexpr std::size_t block {64};
1012 [[nodiscard]]
static constexpr std::size_t
half(std::size_t count)
noexcept
1014 return (count - (count % 8)) / 2;
1019 std::size_t width = 1)
1029 template <
typename T>
1035 constexpr std::size_t lanes {tree::lanes};
1036 if (count < lanes) {
1038 for (std::size_t i {0}; i < count; ++i) {
1039 sum += first[i * stride];
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];
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];
1054 T
sum {tree::combine(partial.data())};
1055 for (; i < count; ++i) {
1056 sum += first[i * stride];
1060 const std::size_t half {tree::half(count)};
1070 template <
typename T>
1072 std::vector<std::size_t>& out)
1075 out.push_back(count);
1079 pairwise_leaves<T>(half, out);
1080 pairwise_leaves<T>(count - half, out);
1085 template <
typename T>
1095 return left + right;
1104 template <
typename T>
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});
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()};
1126 template <
typename 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];
1146 if (count <= block) {
1148 for (std::size_t j {0}; j < lanes; ++j) {
1149 std::copy_n(row(j), width, partial.data() + (j * width));
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) {
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);
1165 for (; i < count; ++i) {
1166 for (std::size_t q {0}; q < width; ++q) {
1167 out[q] += row(i)[q];
1172 const std::size_t half {tree::half(count)};
1176 for (std::size_t q {0}; q < width; ++q) {
1177 out[q] = out[q] + second[q];
1191 template <
typename T>
1200 const std::size_t o {task / runs};
1201 const T*
const base {data + (o * count * inner)};
1214 return std::isalpha(
static_cast<unsigned char>(ch)) != 0;
1218 [[nodiscard]]
inline std::vector<std::string>
split_inputs(
const std::string& lhs)
1220 std::vector<std::string> groups;
1221 std::string current;
1222 for (
const char ch : lhs) {
1224 groups.push_back(current);
1228 current.push_back(ch);
1231 throw einsum_error(
"einsum: invalid character in input subscripts");
1234 groups.push_back(current);
1245 template <
typename T>
1253 std::vector<std::size_t> out_shape)
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)};
1264 template <
typename T>
1265 inline constexpr std::size_t
term_work {is_complex_number<T> ? 4 : 1};
1272 template <
typename T>
1278 sum = std::fma(f, x,
sum);
1283 template <
typename T>
1295 template <std::
size_t W
idth,
bool Fused = false,
typename T>
1298 std::size_t row_step,
1299 std::size_t column_step,
1304 std::array<T, Width> sums {};
1305 for (std::size_t k {0}; k < inner; ++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]);
1312 std::copy(sums.begin(), sums.end(), y + j);
1322 template <
typename T,
bool Fused = false>
1325 std::size_t row_step,
1326 std::size_t column_step,
1330 static_assert(
strided_columns == 8,
"the switch below names each narrower last group");
1333 const std::size_t last {std::min((chunk + 1) *
vector_chunk, cols)};
1336 strided_column_group<strided_columns, Fused>(a, b, row_step, column_step, inner, j, y.data());
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;
1356 std::size_t row_step,
1357 std::size_t column_step,
1362#ifdef NUMERICAL_X86_COMPILED
1363 if (path == gemm_path::avx2 || path == gemm_path::avx512) {
1366 avx2_strided_columns(a, b, row_step, column_step, inner, chunk *
vector_chunk, std::min((chunk + 1) *
vector_chunk, cols), y.data());
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);
1376 return vector_times_columns<float>(a, b, row_step, column_step, inner, cols);
1384 std::size_t row_step,
1385 std::size_t column_step,
1390#ifdef NUMERICAL_X86_COMPILED
1391 if (path == gemm_path::avx2 || path == gemm_path::avx512) {
1394 avx2_strided_columns(a, b, row_step, column_step, inner, chunk *
vector_chunk, std::min((chunk + 1) *
vector_chunk, cols), y.data());
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);
1404 return vector_times_columns<double>(a, b, row_step, column_step, inner, cols);
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};
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");
1430 template <split_complex C>
1433 std::size_t row_step,
1434 std::size_t column_step,
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),
1452 reinterpret_cast<const R*
>(b + (first * column_step)),
1453 row_step, column_step, inner, complex_tile_depth<C>, last - first,
1454 reinterpret_cast<R*
>(y.data() + first));
1456# ifdef NUMERICAL_NEON_COMPILED
1457 if (column_step == 1) {
1458 neon_split_row_columns(a, b, row_step, inner, first, last, y.data());
1470 template <
typename T>
1487 template <
typename T>
1495 for (std::size_t k {0}; k < inner; ++k) {
1500#ifdef NUMERICAL_NEON_COMPILED
1507 inline void neon_add_row_terms(
double* y,
1514 std::vector<double> negated(inner);
1515 for (std::size_t k {0}; k < inner; ++k) {
1518 neon_subtract_products(y, negated.data(), b, ldb, inner, count);
1522 inline void neon_add_row_terms(
float* y,
1529 for (std::size_t k {0}; k < inner; ++k) {
1530 neon_scaled_add(y, b + (k * ldb), a[k], count);
1538 template <std::
floating_po
int T>
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>) {
1554 avx2_scaled_add(y, b + (k * ldb), a[k], count);
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);
1566 for (std::size_t k {0}; k < inner; ++k) {
1568 const T*
const row {b + (k * ldb)};
1569 for (std::size_t j {0}; j < count; ++j) {
1576 template <split_complex C>
1578 std::size_t count)
noexcept
1581 for (std::size_t i {0}; i < count; ++i) {
1582 finite &= std::isfinite(x[i].real()) && std::isfinite(x[i].imag());
1593 template <split_complex C>
1601 for (std::size_t k {0}; k < inner; ++k) {
1603 const C*
const row {b + (k * ldb)};
1604 if (std::isfinite(f.real()) && std::isfinite(f.imag()) &&
parts_finite(row, count)) {
1608 for (std::size_t j {0}; j < count; ++j) {
1620#if defined(__aarch64__) || defined(_M_ARM64)
1621 inline constexpr std::size_t column_sums_below {16};
1632 template <
typename T>
1640 std::vector<std::size_t> out_shape)
1642 if (cols == 1 && rows > 1 && inner != 0) {
1645 return tensor<T> {std::move(out_shape), std::move(y)};
1647 if (rows == 1 && cols > 1 && inner != 0) {
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);
1662 return tensor<T> {std::move(out_shape), std::move(y)};
1664 if (rows * cols != 1) {
1665 return tile_gemm<T>(a, lda, b, ldb, rows, inner, cols, std::move(out_shape));
1676 template <
typename T>
1678 const std::string& output,
1679 std::size_t distinct,
1680 const std::vector<std::size_t>& shape,
1683 const std::size_t rank {in.size()};
1684 if (distinct + 1 != rank || in[rank - 1] != in[rank - 2]) {
1685 return std::nullopt;
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;
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);
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))];
1702 out_shape.push_back(n);
1703 return tensor<T> {std::move(out_shape), std::move(along)};
1709 return tensor<T> {std::move(out_shape), std::move(sums)};
1719 template <
typename T>
1721 const std::string& output,
1722 const std::vector<std::size_t>& shape,
1725 const std::size_t first {in.find_first_not_of(output)};
1726 if (first == std::string::npos) {
1727 return std::nullopt;
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;
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]);
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())};
1752 return tensor<T> {std::move(out_shape), std::move(sums)};
1763 template <
typename T>
1766 const std::string& from,
1767 const std::string& to,
1768 const std::map<char, std::size_t>& sizes,
1775 const std::size_t lead {to.size() - 2};
1776 if (to.compare(0, lead, from, 0, lead) == 0) {
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};
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]; });
1798 const std::size_t rank {to.size()};
1799 std::map<char, std::size_t> source;
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]);
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]);
1813 const std::size_t inner {extent[rank - 1]};
1814 const std::size_t sweep {stride[rank - 1]};
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];
1822 for (std::size_t i {0}; i < inner; ++i) {
1823 out[(row * inner) + i] = data[offset + (i * sweep)];
1830 template <
typename T>
1832 const std::string& from,
1833 const std::string& to,
1834 const std::map<char, std::size_t>& sizes)
1836 return permuted(data.data(), data.size(), from, to, sizes);
1841 template <
typename T>
1854 template <std::
floating_po
int T>
1858 const T product {p * q};
1859#ifdef NUMERICAL_X86_COMPILED
1864 return product + (std::min(std::abs(p), std::abs(q)) == T {} ? T {} : -T {});
1866 return p == T {} || q == T {} ? product + T {} : product;
1872 template <std::
floating_po
int R>
1873 [[nodiscard]]
inline std::complex<R>
tile_product(
const std::complex<R>& p,
1874 const std::complex<R>& q)
noexcept
1878 return {R {} + re, R {} + im};
1884 template <std::
floating_po
int R>
1886 const std::complex<R>& q)
noexcept
1888 return {std::fma(-p.imag(), q.imag(),
fused_from_zero(p.real(), q.real())),
1895 template <
typename T>
1896 requires std::is_arithmetic_v<T>
1898 const std::vector<std::size_t>& x_shape,
1900 const std::vector<std::size_t>& y_shape)
1902 if constexpr (std::is_floating_point_v<T>) {
1903 if (rows_terms_fuse<T>()) {
1911 template <split_complex T>
1913 const std::vector<std::size_t>& x_shape,
1915 const std::vector<std::size_t>& y_shape)
1918#ifdef NUMERICAL_X86_COMPILED
1928 template <
typename T>
1939 template <
typename T>
1942 const std::string& sb,
1944 const std::string& output,
1945 const std::map<char, std::size_t>& sizes)
1947 const auto in_output_order {[&](
const std::string& labels,
operand_span<T> t,
buffer<T>& copy, std::vector<std::size_t>& shape) {
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);
1953 order.push_back(label);
1956 if (order == labels) {
1959 copy =
permuted(t.data, t.count, labels, order, sizes);
1960 return static_cast<const T*
>(copy.data());
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)};
1981 template <
typename T>
1984 const std::string& sb,
1986 const std::string& output,
1987 const std::string& summed,
1988 const std::map<char, std::size_t>& sizes)
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);
1998 if (batch + free_a + free_b != output && batch + free_b + free_a == output) {
2003 std::size_t inner {1};
2004 for (
const char label : summed) {
2005 inner *= sizes.at(label);
2012 if (summed.empty() && !batch.empty()) {
2016 const auto extent_of {[&sizes](
const std::string& labels) {
2017 std::size_t product {1};
2018 for (
const char label : labels) {
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};
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()};
2033 if (rows == 1 && cols == 1) {
2035 c[p] =
dot_product(left_data + (p * inner), right_data + (p * inner), inner);
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);
2044 for (std::size_t p {0}; p < batches; ++p) {
2052 std::vector<std::size_t> shape;
2053 for (
const char label : output) {
2054 shape.push_back(sizes.at(label));
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)};
2074 [[nodiscard]]
inline std::string
pair_keeps(
const std::vector<std::string>& labels,
2077 const std::string& output)
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];
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);
2094 const std::map<char, std::size_t>& sizes)
2096 double product {1.0};
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));
2108 [[nodiscard]]
inline std::vector<std::string>
after_step(
const std::vector<std::string>& labels,
2110 const std::string& output)
2112 std::vector<std::string> next;
2113 for (std::size_t k {0}; k < labels.size(); ++k) {
2115 next.push_back(labels[k]);
2125 const std::string& output,
2126 const std::map<char, std::size_t>& sizes,
2127 std::vector<contraction_step>& path,
2131 if (labels.size() < 2) {
2138 for (std::size_t i {0}; i < labels.size(); ++i) {
2139 for (std::size_t j {i + 1}; j < labels.size(); ++j) {
2141 std::vector<contraction_step> rest;
2142 double rest_cost {0.0};
2143 double rest_largest {0.0};
2145 const double here {
extent_product(labels[i] + labels[j], 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)) {
2153 path.assign(1, step);
2154 path.insert(path.end(), rest.begin(), rest.end());
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)
2172 std::vector<contraction_step> path;
2175 double largest {0.0};
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;
2182 while (labels.size() > 1) {
2184 double best_cost {-1.0};
2185 double best_size {0.0};
2186 bool connected {
false};
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);
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)) {
2197 const double here {
extent_product(labels[i] + labels[j], sizes)};
2199 if (best_cost < 0.0 || here < best_cost || (here == best_cost && size < best_size)) {
2200 best = {.first = i, .second = j};
2206 path.push_back(best);
2225 [[nodiscard]]
inline std::size_t
ellipsis_in(
const std::string& subscripts)
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");
2241 template <
typename T>
2244 const std::string& s1,
2246 const std::string& output,
2247 const std::string& summed,
2248 const std::map<char, std::size_t>& sizes)
2254 if (summed.size() == 1) {
2255 const char contracted {summed.front()};
2256 if (s0.back() == contracted && s1.front() == contracted
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]));
2263 for (std::size_t k {1}; k < s1.size(); ++k) {
2264 out_shape.push_back(sizes.at(s1[k]));
2268 if (
element_count(out_shape.begin(), out_shape.end()) == 0) {
2271 const auto split {out_shape.begin() +
static_cast<std::ptrdiff_t
>(s0.size() - 1)};
2274 return canonical_product<T>(a.
data, inner, b.
data, cols, rows, inner, cols, std::move(out_shape));
2277 return contract_pair<T>(s0, a, s1, b, output, summed, sizes);
2280 template <
typename T>
2281 [[nodiscard]]
tensor<T> einsum_impl(
const std::string& spec_in,
2282 const std::vector<
const tensor<T>*>& operands);
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);
2296 template <
typename T>
2298 const std::vector<
const tensor<T>*>& operands)
2300 const std::size_t arrow {spec.find(
"->")};
2301 std::vector<std::string> inputs {
""};
2302 for (
const char ch : spec.substr(0, arrow)) {
2304 inputs.emplace_back();
2307 inputs.back().push_back(ch);
2310 if (inputs.size() != operands.size()) {
2311 throw einsum_error(
"einsum: number of operands does not match the spec");
2313 std::vector<std::size_t> at(inputs.size());
2314 std::vector<std::size_t> under(inputs.size(), 0);
2315 std::size_t widest {0};
2316 for (std::size_t i {0}; i < inputs.size(); ++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");
2323 under[i] = operands[i]->rank() - letters;
2324 widest = std::max(widest, under[i]);
2327 static constexpr std::string_view alphabet {
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"};
2329 for (
const char letter : alphabet) {
2330 if (fresh.size() < widest && spec.find(letter) == std::string::npos) {
2331 fresh.push_back(letter);
2334 if (fresh.size() < widest) {
2335 throw einsum_error(
"einsum: too many axes under the ellipsis for the letters left");
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");
2345 broadcast = dim == 1 ? broadcast : dim;
2348 std::deque<tensor<T>> owned;
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]);
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]) {
2366 labels.push_back(fresh[axis]);
2367 shape.push_back(dim);
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]);
2376 owned.emplace_back(std::move(shape),
buffer<T>(operands[i]->data().begin(), operands[i]->data().end()));
2377 next.push_back(&owned.back());
2381 if (arrow != std::string::npos) {
2382 output = spec.substr(arrow + 2);
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");
2387 if (where != std::string::npos) {
2388 output.replace(where, 3, fresh);
2392 std::map<char, std::size_t> seen;
2393 for (
const char label : spec) {
2399 for (
const auto& [label, count] : seen) {
2401 output.push_back(label);
2405 return einsum_impl<T>(rewritten +
"->" + output, next);
2411 template <
typename To,
2415 const std::size_t count {t.
size()};
2416 const From*
const in {t.
data().data()};
2420 std::transform(in + first, in + std::min(count, first +
elementwise_chunk), out.data() + first,
2421 [](
const From& x) { return static_cast<To>(x); });
2428 template <
typename T>
2430 const std::vector<
const tensor<T>*>& operands)
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; }),
2437 if (spec.find(
'.') != std::string::npos) {
2438 return einsum_ellipsis<T>(spec, operands);
2440 if (spec.find(
"->") == std::string::npos) {
2443 std::map<char, std::size_t> seen;
2444 for (
const char label : spec) {
2450 for (
const auto& [label, count] : seen) {
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)};
2460 if (operands.size() != inputs.size()) {
2461 throw einsum_error(
"einsum: number of operands does not match the spec");
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);
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");
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);
2490 else if (found->second != dim) {
2491 throw dimension_error(
"einsum: inconsistent extent for a repeated label");
2498 for (
const char ch : rhs) {
2500 throw einsum_error(
"einsum: invalid character in output subscripts");
2502 if (sizes.find(ch) == sizes.end()) {
2503 throw einsum_error(
"einsum: output label not present in any input");
2505 if (output.find(ch) != std::string::npos) {
2508 output.push_back(ch);
2513 for (
const auto& entry : sizes) {
2514 if (output.find(entry.first) == std::string::npos) {
2515 summed.push_back(entry.first);
2525 if (operands.size() > 1) {
2526 std::deque<tensor<T>> owned;
2527 std::vector<const tensor<T>*> current;
2528 std::vector<std::string>
kept;
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];
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);
2541 if (keep == inputs[i]) {
2542 current.push_back(operands[i]);
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());
2550 kept.push_back(std::move(keep));
2552 if (operands.size() > 2 ||
reduced) {
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);
2564 return std::move(owned.back());
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));
2574 return operands[0]->transposed(axes);
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);
2588 if (operands.size() == 1) {
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);
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()};
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]);
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];
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};
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];
2645 if (has_sum_inner) {
2646 sum_step[i] = coef[i][n_labels - 1];
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]);
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) {
2659 std::size_t out_outer {1};
2660 for (std::size_t k {0}; k < free_outer_end; ++k) {
2661 out_outer *= extent[k];
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]);
2668 std::vector<std::size_t> index(n_labels, 0);
2669 std::vector<std::size_t> offset(n_ops, 0);
2671 result.reserve(out_size);
2673 for (std::size_t of {0}; of < out_outer; ++of) {
2674 for (std::size_t fe {0}; fe < inner_free; ++fe) {
2676 for (std::size_t os {0}; os < sum_outer; ++os) {
2677 for (std::size_t se {0}; se < inner_sum; ++se) {
2680 acc += operands[0]->data()[offset[0] + (fe * free_step[0]) + (se * sum_step[0])];
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];
2691 for (std::size_t i {0}; i < n_ops; ++i) {
2692 offset[i] -= coef[i][k] * (extent[k] - 1);
2696 result.push_back(acc);
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];
2707 for (std::size_t i {0}; i < n_ops; ++i) {
2708 offset[i] -= coef[i][k] * (extent[k] - 1);
2712 return tensor<T> {std::move(out_shape), std::move(result)};
2716 template <
typename T>
2718 const std::vector<
const tensor<T>*>& operands)
2720 return einsum_spec<T>(spec_in, operands);
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)
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));
2736 for (
const tensor<unsigned_type>& operand : held) {
2737 wrapped.push_back(&operand);
2739 return converted<T>(einsum_spec<unsigned_type>(spec_in, wrapped));
2759 template <
typename T,
typename ... Rest>
2762 const Rest& ... rest)
2764 const std::vector<const tensor<T>*> operands {&first, (&rest)...};
2765 return detail::einsum_impl<T>(spec, operands);
2777 template <
typename T>
2779 const std::vector<
const tensor<T>*>& operands)
2781 return detail::einsum_impl<T>(spec, operands);
2787 template <
typename T>
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");
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");
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);
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");
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);
2824 std::size_t count {1};
2825 for (
const std::size_t extent : batch) {
2826 count = detail::checked_mul(count, extent);
2828 std::vector<std::size_t> shape {batch};
2835 const std::array<std::size_t, 3> elements {count, m, n};
2836 buffer<T> c(detail::element_count(elements.begin(), elements.end()));
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)};
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; })};
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)};
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]};
2855 offset_a += index * stride_a[d];
2856 offset_b += index * stride_b[d];
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);
2863 for (std::size_t p {0}; p < count; ++p) {
2866 return tensor<T> {std::move(shape), std::move(c)};
2868 detail::parallel_for(count, m * n * k / detail::gemm_kernel_speedup, product);
2869 return tensor<T> {std::move(shape), std::move(c)};
2883 template <
typename T>
2887 return detail::stacked_matmul(a, b);
2891 template <std::
signed_
integral T>
2892 [[nodiscard]] tensor<T> matmul(
const tensor<T>& a,
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)));
A standard exception Std that numerical::error tags too, its one what answering for both bases.
Thrown when an operation's operands have incompatible shapes.
Thrown when an einsum specification is malformed or inconsistent.
einsum_error(const std::string &message)
Builds the error.
Thrown when an index or a range leaves its axis.
A dense, row-major matrix of T with value semantics.
std::size_t rows() const noexcept
The number of rows.
std::size_t cols() const noexcept
The number of columns.
A dense N-dimensional tensor of T with value semantics, read row-major. Its elements are immutable on...
std::shared_ptr< row_major_copy > copy_
A view's row-major copy; null where the elements lie row-major.
const std::vector< std::size_t > & shape() const noexcept
The size of each axis.
tensor(std::vector< std::size_t > shape, std::initializer_list< T > elements)
From a shape and a braced list of the elements, row-major.
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...
const T & operator()(const std::vector< std::size_t > &index) const
The element at a multi-index, read where it lies.
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),...
bool permutes_elements() const
Whether this view reaches every element of its buffer once, from the first: its axes longer than 1,...
std::size_t count_
The number of elements: data_'s, unless a view.
tensor(std::vector< std::size_t > shape, buffer< T > elements)
From a shape and a flat row-major buffer.
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...
tensor(const matrix< T > &m)
A rank-2 tensor from a matrix.
const buffer< T > & copied_out() const
A view's elements in row-major order, copied out on the first call.
tensor transposed() const
transposed with the axes reversed: a matrix's transpose, NumPy's .T.
void finalize()
Computes row-major strides and checks the buffer against the shape.
bool operator==(const tensor &other) const
Exact equality (same shape and equal elements).
tensor reshaped(std::vector< std::size_t > shape) const
This tensor's elements in shape, without a copy: the new tensor shares the buffer,...
const buffer< T > & data() const
The elements, row-major. A view's (transposed) are copied out by the first call, one thread copying w...
std::size_t rank() const noexcept
The number of axes (0 for a scalar).
tensor(matrix< T > &&m)
A rank-2 tensor taking over an expiring matrix's elements, without a copy.
tensor(const vector< T > &v)
A rank-1 tensor from a vector.
const T * origin() const noexcept
The first element where the elements are held (index 0 along every axis): a view (transposed,...
std::size_t offset_
Where in data_ the first element lies (a view's, sliced).
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),...
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,...
std::size_t size() const noexcept
The total number of elements.
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).
bool contiguous() const noexcept
Whether the elements lie row-major where they are held: data then copies nothing.
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,...
tensor(std::vector< std::size_t > shape, std::shared_ptr< const buffer< T > > elements)
Over the shared row-major elements elements, in shape (reshaped).
std::vector< std::size_t > lying_order() const
This view's axes from the widest stride to the narrowest, ties in their order.
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,...
tensor materialized() const
This tensor holding its own elements row-major and nothing more: itself where they lie so,...
std::vector< std::ptrdiff_t > strides_
Each axis's step from origin_: row-major unless a view.
std::shared_ptr< const buffer< T > > data_
The elements, shared with the tensors that hold them.
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),...
std::vector< std::size_t > shape_
The size of each axis.
A dense vector of T with value semantics.
std::size_t size() const noexcept
The number of elements.
The element types each_product takes: those each_rounded rounds as a product of depth one.
A complex number of float or double, which gemm_split multiplies through the real kernel and the kern...
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,...
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,...
std::vector< std::ptrdiff_t > row_major_strides(const std::vector< std::size_t > &shape)
The row-major strides of shape, in elements.
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...
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...
complex_term complex_terms() noexcept
The complex_term of the path in use.
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,...
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).
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.
bool is_label(char ch)
Is ch an ASCII letter (a valid index label)?
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...
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...
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,...
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....
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 ©)
transpose_pieces of side piece (transpose_piece's 8 or the whole tile), each side its own instance: a...
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.
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...
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...
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...
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 ...
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.
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 ...
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...
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.
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.
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...
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...
std::string shape_text(const std::vector< std::size_t > &shape)
A shape as NumPy prints it, (2, 3), for a message.
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.
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...
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),...
std::vector< std::string > split_inputs(const std::string &lhs)
Splits an einsum left-hand side into per-operand subscripts.
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...
@ 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...
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...
bool parts_finite(const C *x, std::size_t count) noexcept
Whether every part of count complex numbers from x is finite.
std::size_t ellipsis_in(const std::string &subscripts)
Evaluates a parsed einsum over its operands.
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).
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...
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 ...
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 ...
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'...
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...
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),...
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,...
T pairwise_quad(const T *p, std::size_t width)
Four partial sums at p, width apart, added pairwise: (p₀ + p₁) + (p₂ + p₃).
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 ...
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,...
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,...
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...
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...
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...
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...
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...
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),...
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,...
constexpr std::size_t column_sums_below
The columns under which canonical_product sums a vector times a matrix by vector_times_columns,...
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...
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.
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...
constexpr std::size_t strided_columns
The columns of B one task of vector_times_columns sums together: their sums' chains interleaved,...
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),...
constexpr std::size_t pairwise_lanes
The partial sums pairwise_sum interleaves, and the multiple of which its first half is long.
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,...
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...
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,...
constexpr std::size_t exhaustive_path_operands
The operands at most whose contraction order contraction_path searches exhaustively; more take the ch...
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...
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...
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...
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,...
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).
The NumericAL public API.
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...
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
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).
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.
gemm_path
The kernels a double matrix product can run on (a float one too on arm64), from the most portable....
@ 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.
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).
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...
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,...
std::size_t second
The second's, past the first.
std::size_t first
The first operand's position.
The elements of an operand of einsum_pair, row-major along its labels: a tensor's,...
const T * data
The first element.
std::size_t count
The elements, the product of the extents.
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),...
static C combine(const C *p, std::size_t width=1)
The partial sums at p, width apart, added pairwise.
The shape of NumPy's pairwise summation tree over the values of type T: below lanes values summed in ...
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.
static constexpr std::size_t half(std::size_t count) noexcept
The first half's length: half of count, less its remainder by 8.
A view's elements in row-major order, copied out by the first data call and shared with the view's co...
std::once_flag made
Set once the elements are copied out.
buffer< T > elements
The copy.
A dense, value-semantic vector over a scalar type.