Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I like to create tools for memoization since it can sometimes be useful. I recently created a generic tool for memoizing pure functions results. Here is an example og 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 anayway to improve its performance at least a little bit? And while we're 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.

share|improve this question
3  
See stackoverflow.com/q/9729212/1157100 –  200_success Nov 11 '13 at 20:51
 
@200_success Wow, that's almost the same thing :o –  Morwenn Nov 11 '13 at 21:53
 
And I optimized it even further with piecewise construction :) –  Morwenn Nov 11 '13 at 22:50
 
May I suggest that you post your revised code as an answer, and accept your own answer? –  200_success Nov 20 '13 at 0:30
 
@200_success Well, I would if was sure there isn't anything to improve. –  Morwenn Nov 20 '13 at 16:47
show 1 more comment

1 Answer

up vote 4 down vote accepted

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(std::forward<Args>(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(std::forward<Args>(args)...))).first;
    }
    return it->second;
}

While the solution above is indeed better than what I had, I managed to improve it even more by constructing the results of _func directly 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(std::forward<Args>(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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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