8
\$\begingroup\$

Here's a trick for preallocating some memory for some type T. Do there exist similar tricks? Improvements?

#include <cassert>

#include <cstdlib>

#include <atomic>

#include <limits>

#include <new>

#include <thread>

#include <utility>

namespace
{
  template <typename T, typename A = unsigned>
  struct static_store
  {
    static constexpr auto const max_instances =
      ::std::numeric_limits<unsigned char>::digits * sizeof(A);

    static void cleanup() { delete [] store_; }

#ifdef __GNUC__
    template <typename U>
    static int ffz(U const v)
    {
      return __builtin_ctzll(~v);
    }
#elif _MSC_VER && !__INTEL_COMPILER
    template <typename U>
    static int ffz(U const v)
    {
      return ::std::numeric_limits<unsigned char>::digits * sizeof(v) -
        __lzcnt64(v & -v);
    }
#elif __INTEL_COMPILER
    template <typename U>
    static int ffz(U const v)
    {
      return _bit_scan_forward(~v);
    }
#else
    template <typename U>
    static int ffz(U v)
    {
      decltype(ffz()) b{};

      for (; (v & 1); ++b)
      {
        v >>= 1;
      }

      return b;
    }
#endif

    static ::std::atomic_flag lock_;

    static A memory_map_;

    static typename ::std::aligned_storage<sizeof(T),
      alignof(T)>::type* store_;
  };

  template <typename T, typename A>
  ::std::atomic_flag static_store<T, A>::lock_;

  template <typename T, typename A>
  A static_store<T, A>::memory_map_;

  template <typename T, typename A>
  typename ::std::aligned_storage<sizeof(T), alignof(T)>::type*
    static_store<T, A>::store_{(::std::atexit(static_store<T, A>::cleanup),
      new typename ::std::aligned_storage<sizeof(T),
        alignof(T)>::type[static_store<T, A>::max_instances])};

  template <typename T, typename ...A>
  inline T* static_new(A&& ...args)
  {
    using static_store = static_store<T>;

    while (static_store::lock_.test_and_set(::std::memory_order_acquire))
    {
      ::std::this_thread::yield();
    }

    auto const i(static_store::ffz(static_store::memory_map_));

    auto p(new (&static_store::store_[i]) T(::std::forward<A>(args)...));

    static_store::memory_map_ |= 1ull << i;

    static_store::lock_.clear(::std::memory_order_release);

    return p;
  }

  template <typename T>
  inline void static_delete(T* const p)
  {
    using static_store = static_store<T>;

    auto const i(p - static_cast<T*>(static_cast<void*>(
      static_store::store_)));
    //assert(!as_const(static_store::memory_map_)[i]);

    while (static_store::lock_.test_and_set(::std::memory_order_acquire))
    {
      ::std::this_thread::yield();
    }

    static_store::memory_map_ &= ~(1ull << i);

    static_cast<T*>(static_cast<void*>(&static_store::store_[i]))->~T();

    static_store::lock_.clear(::std::memory_order_release);
  }
}

Usage:

auto const p(static_new<int>());
*p = 10;
static_delete(p);

The code uses an integral type (A), as a bit mask, where each cleared bit means, that a corresponding slot in the store_ is not occupied, and a set bit means it is occupied. This is done to minimize the storage requirements for the allocation mechanism. To find a free slot, the ffz function (find first zero) is used: it is compiled into a single instruction on many platforms. The same thing could have been done with an array of bools, but with greatly increased storage requirements.

\$\endgroup\$
12
  • \$\begingroup\$ Let teh editz commence? ;-) \$\endgroup\$
    – Jamal
    Commented Sep 15, 2013 at 17:19
  • 1
    \$\begingroup\$ @Jamal nay, let the comments begin! \$\endgroup\$ Commented Sep 15, 2013 at 17:20
  • \$\begingroup\$ That, too. But what about the answers? \$\endgroup\$
    – Jamal
    Commented Sep 15, 2013 at 17:20
  • \$\begingroup\$ @Jamal Hmmm, that too, I hope especially for alternative trickery, that one might use. \$\endgroup\$ Commented Sep 15, 2013 at 17:27
  • 1
    \$\begingroup\$ If you have tricks. Ask on stackoverflow. There are many more experienced C++ users there that can tell you if it is a good idea or not. \$\endgroup\$ Commented Sep 15, 2013 at 22:26

1 Answer 1

8
\$\begingroup\$

I still have trouble understanding how the whole works, but there are still some small things that could be improved:

  • In your comments, you say that A is an integer type used as a bitmask. The safest bitmask types are unsigned types or std::bitset. You should make this condition clear in your code, write

      template <typename T, typename BitmaskType=unsigned>
      struct static_store { /* ... */ };
    

    You could even make it an error to use a nonconforming type and create a is_bitmask trait, which would allow you to create a meaningful error message:

    static_assert(is_bitmask<BitmaskType>::value,
                  "the BitmaskType requirements are not satisfied");
    
  • I got confused with these lines:

    template <typename T, typename ...A>
    inline T* static_new(A&& ...args)
    

    It is once again a naming problem: I had in mind the template parameter A from static_store. Since it represents arguments to be forwarding, you should just use the common convetion and name it Args instead. I don't know whether there are written guidelines to name variadic parameter packs, but Args is probably the name that I saw the most often.

  • You could probably slightly hide details and reduce the visual burden by using a typedef for the type of store_:

    using store_type = typename ::std::aligned_storage<sizeof(T), alignof(T)>::type;
    
\$\endgroup\$
2
  • \$\begingroup\$ new has to be fast, that's why no ::std::bitset. \$\endgroup\$ Commented Apr 24, 2014 at 19:53
  • \$\begingroup\$ @user1095108 That makes sense :) \$\endgroup\$
    – Morwenn
    Commented Apr 24, 2014 at 22:04

Your Answer

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

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