6
\$\begingroup\$

I have implemented a std::function-like class,

  • that is optimized for storing lambdas,
  • that never copies the stored function,
  • that has a small buffer to store small functors, avoiding dynamic memory allocation.
  • is designed to be sized to exact multiples of a cache line, because the functors will probably be accessed from different cores.
  • stores the size of the stored object to be able to decide whether to treat it as a small-object or large-object.
  • allows one storage container to store a lot of different types of callable objects

Also,

  • Objects that are too big automatically fall back to a new, and only a pointer is stored.
  • Bare function pointers are supported, stored in the small object buffer
  • It does not use vtbl for operator() codepath. Calls are resolved at compile time.
  • It generates a helper function that "knows how" to move and dispose of the object. A pointer to that template function is stored with the object.
  • The "dispose" function for small objects explicitly calls the destructor on the object in the small object buffer. The dispose for large objects uses delete to be symmetrical with large object new.

To use it you make a map or deque to construct in place or move construct into place. You can then use the R v = it->invoke<R, T, A1, A2...>(A1, A2...) to execute R T::operator()(A1,A2...) on the stored instance.

Note that it actually allows a lot of different types of lambdas to be stored in the same container (deque/map/etc), so it is not directly comparable with std::function.

Questions:

  • Am I missing anything important? What won't work? Is there any Undefined Behaviour?

#include <unordered_map>
#include <vector>
#include <memory>
#include <cstdint>
#include <set>
#include <deque>
#include <algorithm>
#include <functional>
#include <utility>

// totalSize is the size of the entire object, not the payload
// the actual payload size is less than that by sizeof pointer
template<std::size_t totalSize = 128>
class CallableStorage
{
public:
    static constexpr std::size_t smallSize = totalSize -
            sizeof(std::size_t(*)(void*));

    using Storage =
            typename std::aligned_storage<smallSize>::type;

    template<typename T>
    CallableStorage(T&& fn)
        : CallableStorage(typename std::integral_constant<
                         bool, sizeof(T) <= smallSize>::type(),
                         std::move(fn))
    {
    }

    CallableStorage(CallableStorage const&) = delete;
    CallableStorage& operator=(CallableStorage const&) = delete;

    CallableStorage(CallableStorage&& r)
        : size(r.size)
        , helper(r.helper)
    {
        MovePair places;
        if (size <= smallSize)
        {
            places.from = &r;
            places.to = this;
            r.helper(HelperCommand::Move, &places);
        }
        else
        {
            payload.largeStorage = r.payload.largeStorage;
            r.payload.largeStorage = nullptr;
        }
    }

    CallableStorage& operator=(CallableStorage&&) = delete;

    ~CallableStorage()
    {
        if (size <= smallSize)
            helper(HelperCommand::Dispose, &payload.smallStorage);
        else
            helper(HelperCommand::Dispose, payload.largeStorage);
    }

    template<typename T>
    T* lambdaPointer()
    {
        return lambdaPointer<T>(
                    typename std::integral_constant<
                    bool, sizeof(T) <= smallSize>::type());
    }

    template<typename T>
    T const* lambdaPointer() const
    {
        return lambdaPointer<T>(
                    typename std::integral_constant<
                    bool, sizeof(T) <= smallSize>::type());
    }

    template<typename R, typename T, typename... Args>
    R invoke(Args&& ...args)
    {
        return invoke<R, T, Args...>(
                    typename std::integral_constant<
                    bool, sizeof(T) <= smallSize>::type(),
                    std::forward<Args>(args)...);
    }

private:
    enum class HelperCommand
    {
        Dispose,    // pointer to object
        Move        // pointer to MovePair
    };

    struct MovePair
    {
        void* to;
        void* from;
    };

    template<typename R, typename T, typename... Args>
    R invoke(std::true_type, Args&& ...args)
    {
        auto ptr = reinterpret_cast<T*>(&payload.smallStorage);
        return ptr->operator()(std::forward<Args>(args)...);
    }

    template<typename R, typename T, typename... Args>
    R invoke(std::false_type, Args&& ...args)
    {
        auto ptr = reinterpret_cast<T*>(payload.largeStorage);
        return ptr->operator()(std::forward<Args>(args)...);
    }

    template<typename T>
    CallableStorage(std::true_type, T&& fn)
        : size(sizeof(T))
        , helper(lambdaHelper<T>)
    {
        new (&payload.smallStorage) T(std::move(fn));
    }

    template<typename T>
    CallableStorage(std::false_type, T&& fn)
        : size(sizeof(T))
        , helper(lambdaHelper<T>)
    {
        payload.largeStorage = new T(std::move(fn));
    }

    template<typename T>
    T* lambdaPointer(std::true_type)
    {
        return reinterpret_cast<T*>(&payload.smallStorage);
    }

    template<typename T>
    T const* lambdaPointer(std::true_type) const
    {
        return reinterpret_cast<T const*>(&payload.smallStorage);
    }

    template<typename T>
    T* lambdaPointer(std::false_type)
    {
        return reinterpret_cast<T*>(payload.largeStorage);
    }

    template<typename T>
    T const* lambdaPointer(std::false_type) const
    {
        return reinterpret_cast<T const*>(payload.largeStorage);
    }

    template<typename T>
    static std::size_t lambdaHelper(HelperCommand cmd, void* p)
    {
        if (p)
        {
            using IsSmall = typename std::integral_constant<bool,
                sizeof(T) <= smallSize>::type;

            switch (cmd)
            {
            case HelperCommand::Dispose:
                lambdaDisposerImpl<T>(IsSmall(), p);
                break;

            case HelperCommand::Move:
                auto const& move = *reinterpret_cast<MovePair const*>(p);
                lambdaMoveImpl<T>(IsSmall(), move);
                break;
            }

        }

        return sizeof(T);
    }

    template<typename T>
    static void lambdaDisposerImpl(std::true_type, void* p)
    {
        reinterpret_cast<T*>(p)->~T();
    }

    template<typename T>
    static void lambdaDisposerImpl(std::false_type, void* p)
    {
        delete reinterpret_cast<T*>(p);
    }

    template<typename T>
    static void lambdaMoveImpl(std::true_type, MovePair const& p)
    {
        CallableStorage& lhs = *reinterpret_cast<CallableStorage*>(p.to);
        CallableStorage& rhs = *reinterpret_cast<CallableStorage*>(p.from);

        T* from = reinterpret_cast<T*>(&rhs.payload.smallStorage);
        T* to = reinterpret_cast<T*>(&lhs.payload.smallStorage);

        new (to) T(std::move(*from));
    }

    template<typename T>
    static void lambdaMoveImpl(std::false_type, MovePair const& )
    {
    }

    union Payload
    {
        Storage smallStorage;
        void* largeStorage;
    };

    Payload payload;
    std::size_t size;
    std::size_t (*helper)(HelperCommand, void*);
};
\$\endgroup\$
  • 1
    \$\begingroup\$ From a quick look at your code, I can't see the use of all those headers. Do you really need them all? \$\endgroup\$ – user2296177 May 13 '16 at 17:03
  • \$\begingroup\$ @user2296177 You are correct. I'll put this thing in its own file and minimize the includes. \$\endgroup\$ – doug65536 May 13 '16 at 21:14
2
\$\begingroup\$

Don't cast forwarding references to rvalue type

Here, we use std::move() on a type that could be an lvalue reference:

template<typename T>
CallableStorage(T&& fn)
    : CallableStorage(typename std::integral_constant<
                      bool, sizeof(T) <= smallSize>::type(),
                      std::move(fn))
{
}

We must use std::forward<T> instead, and/or constrain T to be an rvalue reference type:

    static_assert(std::is_rvalue_reference<T&&>::value,
                  "CallableStorage requires a moveable argument");

Is it useful to store functions with different signatures?

We've lost a lot of the convenience of operator(), as we now have to specify template arguments to invoke(). I think it would be better to have the function signature as part of the type, unless there's a demonstrated need for heterogeneous function storage. At present, it seems like we're pushing too much knowledge onto the user.

Size calculation is wrong

It looks like we've omitted the size member when computing the size for Storage. It should be

static constexpr std::size_t smallSize =
    totalSize - sizeof (helper_type) - sizeof (std::size_t);

(I shuffled things around in my copy to give helper a named type; I think that's worthwhile, to reduce accidents)

Just a note about terminology in the comment - sizeof pointer is ambiguous here, because function pointers are not necessarily the same size as object pointers in C++.

Unnecessary headers

We're including way too many Standard Library headers (but still omitting one we do need, for std::aligned_storage). I believe these are what's required:

#include <cstdint>
#include <type_traits>
#include <utility>
\$\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.