Core: Optimize single-column GEMV updates libeigen/eigen!3374
diff --git a/Eigen/src/Core/GeneralProduct.h b/Eigen/src/Core/GeneralProduct.h index 1ff75fd..8d31f0e 100644 --- a/Eigen/src/Core/GeneralProduct.h +++ b/Eigen/src/Core/GeneralProduct.h
@@ -408,6 +408,43 @@ } }; +// Keep the shortcut's expression out of the general GEMV caller's inlining budget. +template <bool ConjugateLhs, typename LhsScalar, typename RhsScalar, typename Dest> +EIGEN_DONT_INLINE void gemv_single_column_update(const LhsScalar* data, Index rows, Index stride, RhsScalar rhsValue, + typename Dest::Scalar alpha, Dest& dest) { + using Column = Matrix<LhsScalar, Dynamic, 1>; + // A runtime stride of one must be visible to the assignment evaluator to enable packets. + // Preserve alpha * (lhs * rhs): folding alpha into rhs can overflow before the product. + if (stride == 1) { + Map<const Column> column(data, rows); + dest.col(0).matrix() += alpha * (column.template conjugateIf<ConjugateLhs>() * rhsValue); + } else { + Map<const Column, Unaligned, InnerStride<>> column(data, rows, InnerStride<>(stride)); + dest.col(0).matrix() += alpha * (column.template conjugateIf<ConjugateLhs>() * rhsValue); + } +} + +template <bool Enable, bool ConjugateLhs, bool ConjugateRhs> +struct gemv_single_column { + template <typename Lhs, typename Rhs, typename Scalar, typename Dest> + static EIGEN_STRONG_INLINE bool run(const Lhs&, const Rhs&, const Scalar&, Dest&, bool) { + return false; + } +}; + +template <bool ConjugateLhs, bool ConjugateRhs> +struct gemv_single_column<true, ConjugateLhs, ConjugateRhs> { + template <typename Lhs, typename Rhs, typename Scalar, typename Dest> + static EIGEN_STRONG_INLINE bool run(const Lhs& lhs, const Rhs& rhs, const Scalar& alpha, Dest& dest, bool eligible) { + if (!eligible || lhs.cols() != 1) return false; + if (!numext::is_exactly_zero(alpha)) { + gemv_single_column_update<ConjugateLhs>(lhs.data(), lhs.rows(), lhs.col(0).innerStride(), + conj_if<ConjugateRhs>()(rhs.coeff(0, 0)), alpha, dest); + } + return true; + } +}; + template <> struct gemv_dense_selector<OnTheRight, ColMajor, true> { template <typename Lhs, typename Rhs, typename Dest> @@ -426,6 +463,16 @@ ResScalar actualAlpha = combine_scalar_factors(alpha, lhs, rhs); + constexpr bool DoubleScalars = std::is_same<LhsScalar, RhsScalar>::value && + std::is_same<LhsScalar, ResScalar>::value && std::is_same<ResScalar, double>::value; + // Float updates can be slower than the buffered packet kernel; bypass it only for matching double scalars. + constexpr bool EnableSingleColumn = + Lhs::ColsAtCompileTime == Dynamic && DoubleScalars && Dest::InnerStrideAtCompileTime != 1; + if (gemv_single_column<EnableSingleColumn, LhsBlasTraits::NeedToConjugate, RhsBlasTraits::NeedToConjugate>::run( + actualLhs, actualRhs, actualAlpha, dest, + Dest::InnerStrideAtCompileTime != Dynamic || dest.innerStride() != 1)) + return; + // make sure Dest is a compile-time vector type (bug 1166) using ActualDest = std::conditional_t<Dest::IsVectorAtCompileTime, Dest, typename Dest::ColXpr>; @@ -493,6 +540,15 @@ ResScalar actualAlpha = combine_scalar_factors(alpha, lhs, rhs); + // Cost heuristic: broadcasts may allocate for owning scalars. Complex shortcuts can worsen GCC's kernel spilling. + constexpr bool EnableSingleColumn = Lhs::ColsAtCompileTime == Dynamic && !NumTraits<ResScalar>::IsComplex && + std::is_trivially_copyable<LhsScalar>::value && + std::is_trivially_copyable<RhsScalar>::value && + std::is_trivially_copyable<ResScalar>::value; + if (gemv_single_column<EnableSingleColumn, LhsBlasTraits::NeedToConjugate, RhsBlasTraits::NeedToConjugate>::run( + actualLhs, actualRhs, actualAlpha, dest, true)) + return; + enum { // FIXME: find a way to allow an inner stride on the result if packet_traits<Scalar>::size==1 // on the other hand it is good for the cache to pack the vector anyways...
diff --git a/benchmarks/Core/CMakeLists.txt b/benchmarks/Core/CMakeLists.txt index d87e0e2..c5e8f58 100644 --- a/benchmarks/Core/CMakeLists.txt +++ b/benchmarks/Core/CMakeLists.txt
@@ -27,6 +27,7 @@ eigen_add_benchmark(bench_gemm_scaled_complex bench_gemm_scaled.cpp DEFINITIONS "SCALAR=std::complex<float>") eigen_add_benchmark(bench_gemm_scaled_complex_double bench_gemm_scaled.cpp DEFINITIONS "SCALAR=std::complex<double>") eigen_add_benchmark(bench_gemv bench_gemv.cpp) +eigen_add_benchmark(bench_gemv_degenerate bench_gemv_degenerate.cpp) eigen_add_benchmark(bench_vecadd bench_vecadd.cpp) foreach(scalar float double) foreach(operation abs:0 square:1 add:2 copy:3 exp:4)
diff --git a/benchmarks/Core/bench_gemv_degenerate.cpp b/benchmarks/Core/bench_gemv_degenerate.cpp new file mode 100644 index 0000000..f172b9e --- /dev/null +++ b/benchmarks/Core/bench_gemv_degenerate.cpp
@@ -0,0 +1,77 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +#include <benchmark/benchmark.h> +#include <Eigen/Core> + +template <typename Scalar, int StorageOrder = Eigen::ColMajor> +static void BM_GemvTranspose(benchmark::State& state) { + using Matrix = Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic, StorageOrder>; + using Vector = Eigen::Matrix<Scalar, Eigen::Dynamic, 1>; + const Eigen::Index rows = state.range(0), cols = state.range(1); + const Matrix a = Matrix::Random(rows, cols); + const Vector x = Vector::Random(rows); + Vector y = Vector::Zero(cols); + const Scalar alpha(0.75); + y.noalias() += alpha * a.transpose() * x; + using Wide = std::conditional_t<Eigen::NumTraits<Scalar>::IsComplex, std::complex<long double>, long double>; + using Real = typename Eigen::NumTraits<Scalar>::Real; + for (Eigen::Index j = 0; j < cols; ++j) { + Wide expected(0); + long double magnitude = 0; + for (Eigen::Index i = 0; i < rows; ++i) { + const Wide term = Wide(alpha) * Wide(a(i, j)) * Wide(x[i]); + expected += term; + magnitude += Eigen::numext::abs(term); + } + const long double bound = 8 * static_cast<long double>(rows + 1) * + static_cast<long double>(Eigen::NumTraits<Real>::epsilon()) * magnitude; + if (!(Eigen::numext::abs(Wide(y[j]) - expected) <= bound)) { + state.SkipWithError("GEMV differs from scalar reference"); + return; + } + } + benchmark::DoNotOptimize(a.data()); + benchmark::DoNotOptimize(x.data()); + for (auto _ : state) { + y.noalias() += alpha * a.transpose() * x; + benchmark::DoNotOptimize(y.data()); + benchmark::ClobberMemory(); + } +} + +BENCHMARK_TEMPLATE(BM_GemvTranspose, float)->ArgsProduct({{1, 2, 4}, {16, 256, 1024}}); +BENCHMARK_TEMPLATE(BM_GemvTranspose, double)->ArgsProduct({{1, 2, 4}, {16, 256, 1024}}); +BENCHMARK_TEMPLATE(BM_GemvTranspose, std::complex<float>)->ArgsProduct({{1, 2, 4}, {16, 256, 1024}}); +BENCHMARK_TEMPLATE(BM_GemvTranspose, float, Eigen::RowMajor)->ArgsProduct({{1, 2, 4}, {16, 256, 1024}}); +BENCHMARK_TEMPLATE(BM_GemvTranspose, double, Eigen::RowMajor)->ArgsProduct({{1, 2, 4}, {16, 256, 1024}}); +BENCHMARK_TEMPLATE(BM_GemvTranspose, std::complex<float>, Eigen::RowMajor)->ArgsProduct({{1, 2, 4}, {16, 256, 1024}}); + +template <typename Scalar> +static void BM_GemvStrided(benchmark::State& state) { + using Matrix = Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic>; + using Vector = Eigen::Matrix<Scalar, Eigen::Dynamic, 1>; + const Eigen::Index rows = state.range(0), cols = state.range(1); + const Matrix a = Matrix::Random(rows, cols); + const Vector x = Vector::Random(cols); + Vector storage = Vector::Zero(2 * rows); + Eigen::Map<Vector, Eigen::Unaligned, Eigen::InnerStride<2>> y(storage.data(), rows); + const Scalar alpha(0.75); + const Vector expected = alpha * a * x; + y.noalias() += alpha * a * x; + if (!y.isApprox(expected)) { + state.SkipWithError("Strided GEMV differs from contiguous result"); + return; + } + benchmark::DoNotOptimize(a.data()); + benchmark::DoNotOptimize(x.data()); + for (auto _ : state) { + y.noalias() += alpha * a * x; + benchmark::DoNotOptimize(y.data()); + benchmark::ClobberMemory(); + } +} + +BENCHMARK_TEMPLATE(BM_GemvStrided, float)->ArgsProduct({{16, 256, 1024}, {1, 2, 4}}); +BENCHMARK_TEMPLATE(BM_GemvStrided, double)->ArgsProduct({{16, 256, 1024}, {1, 2, 4}}); +BENCHMARK_TEMPLATE(BM_GemvStrided, std::complex<float>)->ArgsProduct({{16, 256, 1024}, {1, 2, 4}});
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 1f8c4b7..0803dd9 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt
@@ -396,6 +396,7 @@ ei_add_test(no_automatic_resizing) ei_add_test(conservative_resize) ei_add_test(product_small) +ei_add_test(gemv_degenerate) ei_add_test(product_large) ei_add_test(gemm_packing) if(CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_CXX_COMPILER_ID MATCHES "^(GNU|Clang)$")
diff --git a/test/gemv_degenerate.cpp b/test/gemv_degenerate.cpp new file mode 100644 index 0000000..61716cc --- /dev/null +++ b/test/gemv_degenerate.cpp
@@ -0,0 +1,230 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +#define EIGEN_RUNTIME_NO_MALLOC +#include "main.h" +#define EIGEN_TEST_ANNOYING_SCALAR_DONT_THROW +#include "AnnoyingScalar.h" + +template <typename Lhs, typename Rhs> +void check_degenerate_gemv(const Lhs& lhs, const Rhs& rhs) { + using Scalar = typename ScalarBinaryOpTraits<typename Lhs::Scalar, typename Rhs::Scalar>::ReturnType; + using Real = typename NumTraits<Scalar>::Real; + using Wide = std::conditional_t<NumTraits<Scalar>::IsComplex, std::complex<long double>, long double>; + using Vector = Matrix<Scalar, Dynamic, 1>; + const Scalar alpha = internal::random<Scalar>(); + const Vector initial = Vector::Random(lhs.rows()); + Vector contiguous(initial); + Vector storage = Vector::Constant(2 * lhs.rows() + 1, Scalar(7)); + Map<Vector, Unaligned, InnerStride<2>> result(storage.data(), lhs.rows()); + Vector dynamicStorage(storage); + Map<Vector, Unaligned, InnerStride<Dynamic>> dynamicResult(dynamicStorage.data(), lhs.rows(), + InnerStride<Dynamic>(2)); + for (int operation = 0; operation < 3; ++operation) { + result = initial; + contiguous = initial; + dynamicResult = initial; + auto evaluate = [&](auto& target) { + if (operation == 0) target.noalias() = alpha * lhs * rhs; + if (operation == 1) target.noalias() += alpha * lhs * rhs; + if (operation == 2) target.noalias() -= alpha * lhs * rhs; + }; + evaluate(result); + evaluate(contiguous); + evaluate(dynamicResult); + for (Index i = 0; i < lhs.rows(); ++i) { + Wide sum(0); + long double magnitude = 0; + for (Index k = 0; k < lhs.cols(); ++k) { + const Wide term = Wide(alpha) * Wide(lhs.coeff(i, k)) * Wide(rhs.coeff(k, 0)); + sum += term; + magnitude += numext::abs(term); + } + const Wide expected = operation == 0 ? sum : Wide(initial[i]) + (operation == 1 ? sum : -sum); + const long double bound = + 32 * static_cast<long double>(NumTraits<Real>::epsilon()) * (magnitude + numext::abs(Wide(initial[i]))); + VERIFY(numext::abs(Wide(result[i]) - expected) <= bound); + VERIFY(numext::abs(Wide(contiguous[i]) - expected) <= bound); + VERIFY(numext::abs(Wide(dynamicResult[i]) - expected) <= bound); + } + for (Index i = 1; i < storage.size(); i += 2) VERIFY_IS_EQUAL(storage[i], Scalar(7)); + VERIFY_IS_EQUAL(storage[storage.size() - 1], Scalar(7)); + for (Index i = 1; i < dynamicStorage.size(); i += 2) VERIFY_IS_EQUAL(dynamicStorage[i], Scalar(7)); + VERIFY_IS_EQUAL(dynamicStorage[dynamicStorage.size() - 1], Scalar(7)); + } +} + +template <typename LhsScalar, typename RhsScalar = LhsScalar> +void degenerate_gemv() { + using MatrixType = Matrix<LhsScalar, Dynamic, Dynamic>; + using RhsVector = Matrix<RhsScalar, Dynamic, 1>; + for (Index n : {0, 1, 3, 8, 17, 257}) { + for (Index depth : {0, 1, 2, 4}) { + MatrixType a = MatrixType::Random(depth, n); + RhsVector rhsStorage = RhsVector::Random(3 * depth + 1); + Map<RhsVector, Unaligned, InnerStride<3>> rhs(rhsStorage.data(), depth); + check_degenerate_gemv(a.transpose(), rhs); + check_degenerate_gemv(a.adjoint(), rhs.conjugate()); + check_degenerate_gemv(LhsScalar(0.75) * a.adjoint(), RhsScalar(0.5) * rhs); + MatrixType columnMajor = a.transpose(); + check_degenerate_gemv(columnMajor, rhs); + check_degenerate_gemv(columnMajor.conjugate(), rhs.conjugate()); + check_degenerate_gemv(LhsScalar(0.75) * columnMajor.conjugate(), RhsScalar(0.5) * rhs); + } + Matrix<LhsScalar, Dynamic, 1> lhsStorage = Matrix<LhsScalar, Dynamic, 1>::Random(3 * n + 1); + using RowMatrix = Matrix<LhsScalar, Dynamic, Dynamic, RowMajor>; + Map<RowMatrix, Unaligned, OuterStride<3>> lhs(lhsStorage.data(), n, 1); + RhsVector rhs = RhsVector::Random(1); + check_degenerate_gemv(lhs, rhs); + Map<RowMatrix, Unaligned, OuterStride<>> runtimeLhs(lhsStorage.data(), n, 1, OuterStride<>(3)); + check_degenerate_gemv(runtimeLhs, rhs); + Matrix<LhsScalar, 1, Dynamic> row = Matrix<LhsScalar, 1, Dynamic>::Random(n); + check_degenerate_gemv(row.transpose(), rhs); + Matrix<LhsScalar, 2, Dynamic> fixedDepth = Matrix<LhsScalar, 2, Dynamic>::Random(2, n); + RhsVector fixedDepthRhs = RhsVector::Random(2); + check_degenerate_gemv(fixedDepth.transpose(), fixedDepthRhs); + } +} + +template <typename Scalar, int StorageOrder> +void degenerate_gemv_zero_alpha() { + using MatrixType = Matrix<Scalar, Dynamic, Dynamic, StorageOrder>; + using Vector = Matrix<Scalar, Dynamic, 1>; + using Real = typename NumTraits<Scalar>::Real; + MatrixType lhs(17, 1); + Vector rhs(1); + Vector backing(2 * lhs.rows() + 1); + Map<Vector, Unaligned, InnerStride<2>> strided(backing.data(), lhs.rows()); + Map<Vector, Unaligned, InnerStride<Dynamic>> dynamicStrided(backing.data(), lhs.rows(), InnerStride<Dynamic>(2)); + Vector contiguous(lhs.rows()); + for (const Real exceptional : {NumTraits<Real>::quiet_NaN(), NumTraits<Real>::infinity()}) { + for (int operand = 0; operand < 2; ++operand) { + lhs.setConstant(operand == 0 ? Scalar(exceptional) : Scalar(2)); + rhs.setConstant(operand == 1 ? Scalar(exceptional) : Scalar(3)); + for (const Real zero : {Real(0), -Real(0)}) { + for (int factor = 0; factor < 3; ++factor) { + for (int operation = 0; operation < 2; ++operation) { + auto check = [&](auto& destination) { + backing.setConstant(Scalar(7)); + contiguous.setConstant(Scalar(7)); + auto update = [&](const auto& product) { + if (operation == 0) + destination.noalias() += product; + else + destination.noalias() -= product; + }; + if (factor == 0) update(Scalar(zero) * (lhs * rhs)); + if (factor == 1) update((Scalar(zero) * lhs) * rhs); + if (factor == 2) update(lhs * (Scalar(zero) * rhs)); + for (Index i = 0; i < destination.size(); ++i) VERIFY_IS_EQUAL(destination[i], Scalar(7)); + for (Index i = 1; i < backing.size(); i += 2) VERIFY_IS_EQUAL(backing[i], Scalar(7)); + VERIFY_IS_EQUAL(backing[backing.size() - 1], Scalar(7)); + }; + check(contiguous); + check(strided); + check(dynamicStrided); + } + } + } + } + } +} + +template <typename Scalar, int StorageOrder> +void degenerate_gemv_array_destinations() { + using MatrixType = Matrix<Scalar, Dynamic, Dynamic, StorageOrder>; + using Vector = Matrix<Scalar, Dynamic, 1>; + using ArrayVector = Array<Scalar, Dynamic, 1>; + const Index size = 17; + MatrixType lhs(size, 1); + ArrayVector expected(size); + for (Index i = 0; i < size; ++i) { + lhs(i, 0) = Scalar(2 * (i + 1)); + expected[i] = Scalar(3 * (i + 1)); + } + const Vector rhs = Vector::Constant(1, Scalar(3)); + const Scalar alpha(0.5); + const ArrayVector contiguous = alpha * lhs * rhs; + VERIFY((contiguous == expected).all()); + + ArrayVector backing = ArrayVector::Constant(2 * size + 1, Scalar(7)); + Map<ArrayVector, Unaligned, InnerStride<2>> strided(backing.data(), size); + Map<ArrayVector, Unaligned, InnerStride<Dynamic>> dynamicStrided(backing.data(), size, InnerStride<Dynamic>(2)); + auto check = [&](auto& destination) { + backing.setConstant(Scalar(7)); + destination = alpha * lhs * rhs; + VERIFY((destination == expected).all()); + for (Index i = 1; i < backing.size(); i += 2) VERIFY_IS_EQUAL(backing[i], Scalar(7)); + VERIFY_IS_EQUAL(backing[backing.size() - 1], Scalar(7)); + }; + check(strided); + check(dynamicStrided); + + const Array<Scalar, 1, Dynamic> row = alpha * rhs.transpose() * lhs.transpose(); + VERIFY((row.transpose() == expected).all()); + Array<Scalar, Dynamic, Dynamic> rows = Array<Scalar, Dynamic, Dynamic>::Constant(2, size + 2, Scalar(7)); + rows.row(1).segment(1, size) = alpha * rhs.transpose() * lhs.transpose(); + VERIFY((rows.row(1).segment(1, size).transpose() == expected).all()); + VERIFY((rows.row(0) == Scalar(7)).all()); + VERIFY_IS_EQUAL(rows(1, 0), Scalar(7)); + VERIFY_IS_EQUAL(rows(1, size + 1), Scalar(7)); +} + +EIGEN_DECLARE_TEST(gemv_degenerate) { + // The disabled C++14 dispatch must not require coefficient access or instantiate the update. + int placeholder = 0; + VERIFY((!internal::gemv_single_column<false, false, false>::run(placeholder, placeholder, placeholder, placeholder, + true))); + degenerate_gemv_array_destinations<float, RowMajor>(); + degenerate_gemv_array_destinations<float, ColMajor>(); + degenerate_gemv_array_destinations<double, RowMajor>(); + degenerate_gemv_array_destinations<double, ColMajor>(); + degenerate_gemv_array_destinations<std::complex<float>, RowMajor>(); + degenerate_gemv_array_destinations<std::complex<float>, ColMajor>(); + degenerate_gemv_array_destinations<std::complex<double>, RowMajor>(); + degenerate_gemv_array_destinations<std::complex<double>, ColMajor>(); + + degenerate_gemv_zero_alpha<float, RowMajor>(); + degenerate_gemv_zero_alpha<double, RowMajor>(); + degenerate_gemv_zero_alpha<std::complex<float>, RowMajor>(); + degenerate_gemv_zero_alpha<std::complex<double>, RowMajor>(); + degenerate_gemv_zero_alpha<float, ColMajor>(); + degenerate_gemv_zero_alpha<double, ColMajor>(); + STATIC_CHECK(!std::is_trivially_copyable<AnnoyingScalar>::value); + for (int repeat = 0; repeat < g_repeat; ++repeat) { + degenerate_gemv<float>(); + degenerate_gemv<double>(); + degenerate_gemv<half>(); + degenerate_gemv<bfloat16>(); + degenerate_gemv<std::complex<float>>(); + degenerate_gemv<std::complex<double>>(); + degenerate_gemv<double, std::complex<double>>(); + degenerate_gemv<std::complex<double>, double>(); + } + Matrix<double, Dynamic, Dynamic, RowMajor> lhs = MatrixXd::Constant(2, 1, 1e-200); + VectorXd rhs = VectorXd::Constant(1, 1e308); + VectorXd result = VectorXd::Zero(2); + result.noalias() += 2.0 * lhs * rhs; + for (Index i = 0; i < result.size(); ++i) { + VERIFY((numext::isfinite)(result[i])); + VERIFY(numext::abs(result[i] / 2e108 - 1.0) <= 8 * NumTraits<double>::epsilon()); + } + Matrix<AnnoyingScalar, Dynamic, Dynamic, RowMajor> custom = + Matrix<AnnoyingScalar, Dynamic, Dynamic, RowMajor>::Constant(5, 1, AnnoyingScalar(2)); + Matrix<AnnoyingScalar, Dynamic, 1> customRhs = Matrix<AnnoyingScalar, Dynamic, 1>::Constant(1, AnnoyingScalar(3)); + Matrix<AnnoyingScalar, Dynamic, 1> customResult(5); + customResult.noalias() = custom * customRhs; + for (Index i = 0; i < customResult.size(); ++i) VERIFY_IS_EQUAL(customResult[i], AnnoyingScalar(6)); + + MatrixXd column = MatrixXd::Constant(20000, 1, 2.0); + VectorXd factor = VectorXd::Constant(1, 3.0); + VectorXd backing = VectorXd::Zero(2 * column.rows()); + Map<VectorXd, Unaligned, InnerStride<2>> strided(backing.data(), column.rows()); + internal::set_is_malloc_allowed(false); + strided.noalias() += 0.75 * column * factor; + internal::set_is_malloc_allowed(true); + for (Index i = 0; i < column.rows(); ++i) { + VERIFY_IS_EQUAL(strided[i], 4.5); + VERIFY_IS_EQUAL(backing[2 * i + 1], 0.0); + } +}