blob: e5814324099fa86e4a5f1f132e01c48bcf2a01e3 [file] [edit]
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// setFromTriplets: a counting sort of the triplets into the transposed storage order, duplicate collapsing, then a
// storage-order change.
#include <benchmark/benchmark.h>
#include <Eigen/Sparse>
#include <algorithm>
#include <random>
#include <vector>
using namespace Eigen;
using Scalar = double;
using SpMat = SparseMatrix<Scalar>;
using Triplets = std::vector<Triplet<Scalar, SpMat::StorageIndex>>;
struct TripletCase {
Index rows, cols;
Triplets triplets;
};
// 5-point Laplacian on an n x n grid, every entry repeated `copies` times.
static TripletCase laplacian2d(int n, int copies) {
TripletCase c{n * n, n * n, {}};
for (int k = 0; k < copies; ++k)
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x) {
int i = y * n + x;
c.triplets.emplace_back(i, i, 4);
if (x > 0) c.triplets.emplace_back(i, i - 1, -1);
if (x + 1 < n) c.triplets.emplace_back(i, i + 1, -1);
if (y > 0) c.triplets.emplace_back(i, i - n, -1);
if (y + 1 < n) c.triplets.emplace_back(i, i + n, -1);
}
return c;
}
// count triplets at uniformly random positions.
static TripletCase randomPositions(int rows, int cols, int count, unsigned seed) {
std::mt19937 g(seed);
std::uniform_int_distribution<int> row(0, rows - 1), col(0, cols - 1);
TripletCase c{rows, cols, {}};
for (int k = 0; k < count; ++k) c.triplets.emplace_back(row(g), col(g), Scalar(k % 7 + 1));
return c;
}
// Banded, scattered, hypersparse (most vectors empty), and a banded assembly in which every entry occurs four times.
static const TripletCase& tripletCase(int c) {
static const TripletCase cases[] = {laplacian2d(500, 1), randomPositions(200000, 200000, 1600000, 1),
randomPositions(1000000, 1000000, 200000, 2), laplacian2d(500, 4)};
return cases[c];
}
static void BM_SetFromTriplets(benchmark::State& state) {
const TripletCase& c = tripletCase(int(state.range(0)));
SpMat m(c.rows, c.cols);
for (auto _ : state) {
m.setFromTriplets(c.triplets.begin(), c.triplets.end());
benchmark::DoNotOptimize(m.valuePtr());
}
// Reference through the sorted-triplet path, which shares no code with the unsorted one.
Triplets sorted = c.triplets;
std::sort(sorted.begin(), sorted.end(), [](const Triplets::value_type& a, const Triplets::value_type& b) {
return a.col() != b.col() ? a.col() < b.col() : a.row() < b.row();
});
SpMat reference(c.rows, c.cols);
reference.setFromSortedTriplets(sorted.begin(), sorted.end());
if (m.nonZeros() != reference.nonZeros() || !m.isApprox(reference) || !m.isCompressed())
state.SkipWithError("wrong result");
static const char* names[] = {"lap2d500", "random200k_1.6M", "hyper1M_200k", "lap2d500_dup4"};
state.SetLabel(names[state.range(0)]);
state.counters["triplets"] = double(c.triplets.size());
state.counters["nnz"] = double(m.nonZeros());
state.SetItemsProcessed(state.iterations() * Index(c.triplets.size()));
}
BENCHMARK(BM_SetFromTriplets)->DenseRange(0, 3)->Unit(benchmark::kMillisecond);