5
\$\begingroup\$

I wrote a math vector implementation using expression templates to add a little boost to "chain operations" like:

tnt::vector res = -v * 2 + d / 2 - 4 * c; // v, d, c are some vectors.

by avoiding the creation of the temporaries. The implementation uses C++20's concepts for safer and more readable code, generic lambda's explicit template parameters to avoid having "implementation/private functions" inside struct vector and other C++20 features like three way comparison and conditional explicit as well. Here's the code:

#include <algorithm> // std::lexicographical_compare_three_way, std::ranges::equal
#include <utility> // std::index_sequence

namespace tnt
{
    namespace detail
    {
        template <typename T>
        concept arithmetic = std::integral<T> or std::floating_point<T>;

        template <typename T>
        concept expression = requires {
            typename T::value_type;
            { T::size() } -> std::same_as<std::size_t>;
        } and requires (T const& t) {
            requires std::same_as<std::remove_cvref_t<decltype(t[0])>,
                typename T::value_type>;
        };

        // vector_sum
        template <detail::expression Left, detail::expression Right>
            requires (Left::size() == Right::size())
        struct vector_sum final
        {
            using value_type = decltype(std::declval<Left>()[0] + std::declval<Right>()[0]);

            static constexpr std::size_t size() noexcept
            {
                return Left::size();
            }

            constexpr auto operator[](std::size_t i) const noexcept(noexcept(lhs[i] + rhs[i]))
            {
                return lhs[i] + rhs[i];
            }

            Left const& lhs;
            Right const& rhs;
        };

        template <typename Left, typename Right>
        vector_sum(Left, Right) -> vector_sum<Left, Right>;

        // vector_diff
        template <detail::expression Left, detail::expression Right>
            requires (Left::size() == Right::size())
        struct vector_diff final
        {
            using value_type = decltype(std::declval<Left>()[0] - std::declval<Right>()[0]);

            static constexpr std::size_t size() noexcept
            {
                return Left::size();
            }

            constexpr auto operator[](std::size_t i) const noexcept(noexcept(lhs[i] - rhs[i])) { return lhs[i] - rhs[i]; }

            Left const& lhs;
            Right const& rhs;
        };

        template <typename Left, typename Right>
        vector_diff(Left, Right) -> vector_diff<Left, Right>;

        // vector_prod
        template <detail::expression Left, detail::arithmetic Right>
        struct vector_prod final
        {
            using value_type = decltype(std::declval<Left>()[0] * std::declval<Right>());

            static constexpr std::size_t size() noexcept { return Left::size(); }

            constexpr auto operator[](std::size_t i) const noexcept(noexcept(lhs[i] * rhs)) { return lhs[i] * rhs; }

            Left const& lhs;
            Right const& rhs;
        };

        template <typename Left, typename Right>
        vector_prod(Left, Right) -> vector_prod<Left, Right>;

        // vector_ratio
        template <detail::expression Left, detail::arithmetic Right>
        struct vector_ratio final
        {
            using value_type = decltype(std::declval<Left>()[0] / std::declval<Right>());

            static constexpr std::size_t size() noexcept { return Left::size(); }

            constexpr auto operator[](std::size_t i) const noexcept(noexcept(lhs[i] / rhs)) { return lhs[i] / rhs; }

            Left const& lhs;
            Right const& rhs;
        };

        template <typename Left, typename Right>
        vector_ratio(Left, Right) -> vector_ratio<Left, Right>;
    }

    // math operators
    constexpr auto operator+(detail::expression auto const& lhs, detail::expression auto const& rhs) noexcept
    {
        return detail::vector_sum{lhs, rhs};
    }

    constexpr auto operator-(detail::expression auto const& lhs, detail::expression auto const& rhs) noexcept
    {
        return detail::vector_diff{lhs, rhs};
    }

    constexpr auto operator*(detail::expression auto const& lhs, detail::arithmetic auto const& rhs) noexcept
    {
        return detail::vector_prod{lhs, rhs};
    }

    constexpr auto operator*(detail::arithmetic auto const& lhs, detail::expression auto const& rhs) noexcept
    {
        return detail::vector_prod{rhs, lhs};
    }

    constexpr auto operator/(detail::expression auto const& lhs, detail::arithmetic auto const& rhs) noexcept
    {
        return detail::vector_ratio{lhs, rhs};
    }

    // vector
    template <detail::arithmetic T, std::size_t N>
        requires (N > 0u)
    struct vector final
    {
        using value_type = T;

        template <std::convertible_to<T> ...Ts>
            requires (sizeof...(Ts) <= N)
        explicit(sizeof...(Ts) == 1) constexpr vector(Ts &&... ts) noexcept
            : data{std::forward<T>(ts)...} {}

        // copy stuff
        template <std::convertible_to<T> U, std::size_t S>
            requires (S <= N)
        constexpr vector(vector<U, S> const& rhs) noexcept
        {
            [this, &rhs]<std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] = rhs.data[I]), ...);
            }(std::make_index_sequence<S>{});
        }

        template <std::convertible_to<T> U, std::size_t S>
            requires (S <= N)
        constexpr vector& operator=(vector<U, S> const& rhs) noexcept
        {
            [this, &rhs]<std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] = rhs.data[I]), ...);
            }(std::make_index_sequence<S>{});
            return *this;
        }

        // move operators
        template <std::convertible_to<T> U, std::size_t S>
            requires (S <= N)
        constexpr vector(vector<U, S> &&rhs) noexcept
        {
            [this, rhs = std::move(rhs)]<std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] = std::exchange(rhs.data[I], U(0))), ...);
            }(std::make_index_sequence<S>{});
        }

        template <std::convertible_to<T> U, std::size_t S>
            requires (S <= N)
        constexpr vector& operator=(vector<U, S> &&rhs) noexcept
        {
            if (this != &rhs)
                [this, rhs = std::move(rhs)]<std::size_t... I>(std::index_sequence<I...>) noexcept {
                    ((data[I] = std::exchange(rhs.data[I], U(0))), ...);
                }(std::make_index_sequence<S>{});
            return *this;
        }

        // detail::expression logic
        template <detail::expression E>
            requires std::convertible_to<typename E::value_type, T>
        constexpr vector(E &&rhs) noexcept
        {
            [this, rhs = std::move(rhs)]
                <std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] = rhs[I]), ...);
            }(std::make_index_sequence<N>{});
        }

        template <detail::expression E>
            requires (E::size() <= N and std::convertible_to<typename E::value_type, T>)
        constexpr vector& operator=(E &&rhs) noexcept
        {
            [this, rhs = std::move(rhs)]
                <std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] = rhs[I]), ...);
            }(std::make_index_sequence<N>{});
            return *this;
        }

        // math operators
        template <detail::expression E>
            requires (E::size() <= N and std::convertible_to<typename E::value_type, T>)
        constexpr vector& operator +=(E &&rhs) noexcept
        {
            [this, rhs = std::move(rhs)]
                <std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] += rhs[I]), ...);
            }(std::make_index_sequence<N>{});
            return *this;
        }

        template <detail::expression E>
            requires (E::size() <= N and std::convertible_to<typename E::value_type, T>)
        constexpr vector& operator -=(E &&rhs) noexcept
        {
            [this, rhs = std::move(rhs)]
                <std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] -= rhs[I]), ...);
            }(std::make_index_sequence<N>{});
            return *this;
        }

        template <detail::arithmetic A>
        constexpr vector& operator *=(A const& rhs) noexcept
        {
            [this, &rhs]
                <std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] *= rhs), ...);
            }(std::make_index_sequence<N>{});
            return *this;
        }

        template <detail::arithmetic A>
        constexpr vector& operator /=(A const& rhs) noexcept
        {
            [this, &rhs]
                <std::size_t... I>(std::index_sequence<I...>) noexcept {
                ((data[I] /= rhs), ...);
            }(std::make_index_sequence<N>{});
            return *this;
        }

        // operator []
        constexpr T& operator[](std::size_t i) noexcept { return data[i]; }
        constexpr const T& operator[](std::size_t i) const noexcept { return data[i]; }

        // size
        static constexpr std::size_t size() noexcept { return N; }

        // operator ==, operator <=>
        template <std::equality_comparable_with<T> A>
        friend constexpr bool operator==(vector const& lhs, vector<A, N> const& rhs) noexcept
        {
            return std::ranges::equal(lhs.data, lhs.data + N, &rhs[0], &rhs[N]);
        }

        template <std::three_way_comparable_with<T> A>
        friend constexpr auto operator <=>(vector const& lhs, vector<A, N> const& rhs) noexcept
        {
            return std::lexicographical_compare_three_way(lhs.data, lhs.data + N, rhs.data, rhs.data + N);
        }

    private:
        T data[N]{};
    };

    // deduction guides
    template <detail::arithmetic T, std::convertible_to<T>... U>
    vector(T, U...) -> vector<T, sizeof...(U) + 1>;

    template <detail::expression E>
    vector(E) -> vector<typename E::value_type, E::size()>;

    // vector constants
    template <detail::arithmetic T, std::size_t N>
        requires (N > 0)
    inline constexpr vector<T, N> vector_zero{};

    // unary operator -
    template <detail::arithmetic T, std::size_t N>
        requires (N > 0)
    constexpr auto operator -(vector<T, N> const& vec) noexcept
    {
        return detail::vector_diff{vector_zero<T, N>, vec};
    }
} // namespace tnt

And here is a small demonstration

#include <iostream>

int main()
{
    constexpr tnt::vector v{1, 2, 3.};
    constexpr tnt::vector d{2., 4, 6};
    constexpr tnt::vector r = -v * 2 + d / 2; // no tnt::vector temporary created
    std::cout << '{' << r[0] << ", " << r[1] << ", " << r[2] << '}'; // prints {-1, -2, -3}
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

It looks like very good code in general, good use of C++20 features, constexpr all the things. There is one issue I see with this code though:

Is it worth avoiding temporary tnt::vectors?

Are you sure that avoiding temporary tnt::vectors is worth creating expression types? Because those expressions themselves are now going to be the temporaries, and each of those expression types has storage of its own: most of them store two pointers. So is trading in three doubles for two pointers worth it? Because now there is indirection involved, and expressions themselves can be complex and thus need a lot of temporary storage.

Temporaries might not have any overhead at all, depending on whether the compiler can see it doesn't need to create them. So the problem you are trying to fix might not even exist in practice.

Another issue is that you change the order in which data is accessed. Instead of accessing all the elements of two vectors to create a third vector, when converting a detail::expression to a tnt::vector, you first access the first element of all the vectors involved in the expression, then the second, and so on. This means you are less likely to benefit from locality of data. For small vectors and expressions, it will probably not matter as long as everything fits into the CPU's cache, but if you are working with much larger vectors this might be an issue.

I would create a version that doesn't use expression types, and then look at the resulting assembler code generated by the compiler, and benchmark the code, to see if it really was worth it or not.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thank you. I will try to benchmark both approaches and check the assembly as well. \$\endgroup\$ Mar 13, 2021 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.