Skip to content

Instantly share code, notes, and snippets.

@baileyparker baileyparker/Makefile Secret
Last active Mar 4, 2020

Embed
What would you like to do?
Benchmark for cartesian_product vs nested for loop
#pragma once
#include <tuple>
template<typename... Ts>
class product_iterator;
template<typename... Ts>
class product;
template<typename T>
class product<T> {
public:
explicit product(const T &x) : m_x(x) {}
product_iterator<T> begin() const;
product_iterator<T> end() const;
protected:
const T &m_x;
};
template<typename T, typename... Ts>
class product<T, Ts...> {
public:
product(const T &x, const Ts&... xs) : m_x(x), m_xs(product<Ts...>(xs...)) {}
product_iterator<T, Ts...> begin() const;
product_iterator<T, Ts...> end() const;
protected:
const T &m_x;
product<Ts...> m_xs;
};
template<typename T>
class product_iterator<T> {
friend class product<T>;
public:
std::tuple<typename T::value_type> operator*() const {
return std::make_tuple(*m_it);
}
const product_iterator<T> &operator++() {
m_it++;
return *this;
}
bool operator==(const product_iterator &other) const {
return m_it == other.m_it;
}
bool operator!=(const product_iterator &other) const {
return !(*this == other);
}
protected:
typedef typename T::const_iterator t_iterator;
product_iterator(t_iterator it, t_iterator end) : m_it(it), m_end(end) {}
t_iterator m_it;
t_iterator m_end;
};
template<typename T, typename... Ts>
class product_iterator<T, Ts...> {
friend class product<T, Ts...>;
public:
decltype(auto) operator*() const {
return std::tuple_cat(std::make_tuple(*m_x), *m_xs);
}
const product_iterator<T, Ts...> &operator++() {
if (++m_xs == m_xs_end && ++m_x != m_x_end) {
m_xs = m_xs_begin;
}
return *this;
}
bool operator==(const product_iterator &other) const {
return m_x == other.m_x && m_xs == other.m_xs;
}
bool operator!=(const product_iterator &other) const {
return !(*this == other);
}
protected:
typedef typename T::const_iterator t_iterator;
typedef product_iterator<Ts...> ts_iterator;
product_iterator(t_iterator x, t_iterator x_end, ts_iterator xs,
ts_iterator xs_begin, ts_iterator xs_end)
: m_x(x), m_x_end(x_end), m_xs(xs), m_xs_begin(xs_begin), m_xs_end(xs_end) {}
t_iterator m_x;
t_iterator m_x_end;
ts_iterator m_xs;
ts_iterator m_xs_begin;
ts_iterator m_xs_end;
};
template<typename T>
product_iterator<T> product<T>::begin() const {
return product_iterator<T>(m_x.begin(), m_x.end());
}
template<typename T>
product_iterator<T> product<T>::end() const {
return product_iterator<T>(m_x.end(), m_x.end());
}
template<typename T, typename... Ts>
product_iterator<T, Ts...> product<T, Ts...>::begin() const {
return product_iterator<T, Ts...>(m_x.begin(), m_x.end(), m_xs.begin(),
m_xs.begin(), m_xs.end());
}
template<typename T, typename... Ts>
product_iterator<T, Ts...> product<T, Ts...>::end() const {
return product_iterator<T, Ts...>(m_x.end(), m_x.end(), m_xs.end(), m_xs.begin(),
m_xs.end());
}
template<typename... Ts>
product<Ts...> cartesian_product(Ts&... xs) {
return product<Ts...>(xs...);
}
#include <cstdint>
#include <vector>
#include "cartesian_product.hpp"
#include "dummy.hpp"
void dot(const std::vector<uint32_t> &as, const std::vector<uint32_t> &bs) {
for (auto [a, b] : cartesian_product(as, bs)) {
dummy(a, b);
}
}
#include <cstdint>
#include <vector>
#include "cartesian_product.hpp"
#include "dummy.hpp"
void dot(const std::vector<uint32_t> &as, const std::vector<uint32_t> &bs) {
for (auto a : as) {
for (auto b : bs) {
dummy(a, b);
}
}
}
#include <cstdint>
#include <algorithm>
uint32_t largest;
void dummy(uint32_t a, uint32_t b) {
largest = std::max(std::max(a, b), largest);
}
#pragma once
#include <cstdint>
extern void dummy(uint32_t a, uint32_t b);
CXXFLAGS=-O3 -Wall -pedantic -MMD -std=c++1z
all: run_cartesian run_loop
run_cartesian: dot_cartesian.o run.o dummy.o
$(CXX) $(LDFLAGS) -o $@ $^
run_loop: dot_loop.o run.o dummy.o
$(CXX) $(LDFLAGS) -o $@ $^
benchmark: run_cartesian run_loop
time ./run_cartesian
time ./run_loop
clean:
rm -f run_cartesian run_loop *.d *.o
.PHONY: all benchmark
#include <cstdint>
#include <vector>
extern void dot(const std::vector<uint32_t> &as, const std::vector<uint32_t> &bs);
int main(int argc, char **argv) {
std::vector<uint32_t> as(4096);
std::vector<uint32_t> bs(4096);
for (size_t i = 0; i < 1024; i++) {
dot(as, bs);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.