7
\$\begingroup\$

I like to create tools for memoization since it can sometimes be useful. I recently created a generic tool for memoizing the results of pure functions.

Here is an example of how it works:

// Dummy function
auto func(int a, bool b)
    -> std::string
{
    // Some heavy computations
}

int main()
{
    auto memof_f = memoized(func);
    auto a = memo_f(5, true);
    auto b = memo_f(8, false);
    // ...
}

In this example, memo_f is a wrapper that calls func and memoizes its results. When called, it checks whether the result for the given arguments is in cache and computes it only if it is not.

Here is the implementation of memoized:

template<typename Ret, typename... Args>
class MemoizedFunction
{
    public:
        MemoizedFunction(const std::function<Ret(Args...)>& func):
            _func(func)
        {}

        auto operator()(Args... args)
            -> Ret
        {
            auto tuple_args = std::make_tuple(args...);
            if (not _memory.count(tuple_args))
            {
                auto res = _func(args...);
                _memory[tuple_args] = res;
                return res;
            }
            return _memory[tuple_args];
        }

    private:
        // Stored function
        std::function<Ret(Args...)> _func;
        // Map containing the pairs args/return
        std::unordered_map<std::tuple<Args...>, Ret> _memory;
};

template<typename Ret, typename... Args>
auto memoized(Ret (*func)(Args...))
    -> MemoizedFunction<Ret, Args...>
{
    return { std::function<Ret(Args...)>(func) };
}

Also, it's not of utmost importance, but I need these little functions in order to hash a tuple:

template<typename First, typename... Rest>
auto hash_all(First first, Rest... rest)
    -> std::size_t
{
    auto seed = std::hash<First>()(first);
    seed ^= hash_all(rest...);
    return seed;
}

template<typename First, typename Second>
auto hash_all(First first, Second second)
    -> std::size_t
{
    return std::hash<First>()(first) ^ std::hash<Second>()(second);
}

namespace std
{
    // Hash function for tuples
    template<typename... Args>
    struct hash<std::tuple<Args...>>
    {
        auto operator()(const std::tuple<Args...>& args) const
            -> std::size_t
        {
            return apply(hash_all<Args...>, args);
        }
    };
}

Note: the function apply is a function that uses the elements of a tuple as parameters for a given function, as proposed in N3802.

My question is simple: since this a low-level tool, which could be used in several contexts, is there any way to improve its performance at least a little bit? And while we are at it, do not hesitate to give tips for that construct to be more versatile too :)

Note: this class is only intended to work for pure (or "well-behaved" as of N3744) functions.

\$\endgroup\$
7
\$\begingroup\$

Thanks to an answer to a similar question on StackOverflow (thanks @200_success), I improved the implementation of operator(). Using _memory.count is pretty inefficient compared to _memory.find since the latter will stop once the first corresponding key is found:

auto operator()(Args... args)
    -> Ret
{
    const auto t_args = std::make_tuple(args...);
    auto it = _memory.find(t_args);
    if (it == _memory.cend())
    {
        using val_t = typename std::unordered_map<std::tuple<Args...>, Ret>::value_type;
        it = _memory.insert(val_t(t_args, _func(args...))).first;
    }
    return it->second;
}

While the solution above is indeed better than what I had, I managed to improve it even more: the results of _func should be directly constructed into _memory thanks to the piecewise construction of std::pair:

template<typename Ret, typename... Args>
auto MemoizedFunction<Ret, Args...>::operator()(Args... args)
    -> Ret
{
    const auto t_args = std::make_tuple(args...);
    auto it = _memory.find(t_args);
    if (it == _memory.cend())
    {
        it = _memory.emplace(std::piecewise_construct,
                             std::forward_as_tuple(t_args),
                             std::forward_as_tuple(_func(args...))
                        ).first;
    }
    return it->second;
}

Now, operator() is far better than it originally was. I don't know whether it is still possible to improve it or not though.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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