A custom, highly-specialized, special-purpose standard-compliant C++ allocator

Question

Brief Preface

I recognize that there are many nuances and requirements for a standard-compatible allocator. There are a number of questions here covering a range of topics associated with allocators. I realize that the requirements set out by the standard are critical to ensuring that the allocator functions correctly in all cases, doesn't leak memory, doesn't cause undefined-behaviour, etc. This is particularly true where the allocator is meant to be used (or at least, can be used) in a wide range of use cases, with a variety of underlying types and different standard containers, object sizes, etc.

In contrast, I have a very specific use case where I personally strictly control all of the conditions associated with its use, as I describe in detail below. Consequently, I believe that what I've done is perfectly acceptable given the highly-specific nature of what I'm trying to implement.

I'm hoping someone with far more experience and understanding than me can either confirm that the description below is acceptable or point out the problems (and, ideally, how to fix them too).

Overview / Specific Requirements

In a nutshell, I'm trying to write an allocator that is to be used within my own code and for a single, specific purpose:

• I need "a few" std::vector (probably uint16_t), with a fixed (at runtime) number of elements. I'm benchmarking to determine the best tradeoff of performance/space for the exact integer type[1]
• As noted, the number of elements is always the same, but it depends on some runtime configuration data passed to the application
• The number of vectors is also either fixed or at least bounded. The exact number is handled by a library providing an implementation of parallel::for(execution::par_unseq, ...)
• The vectors are constructed by me (i.e. so I know with certainty that they will always be constructed with N elements)

[1] The value of the vectors are used to conditionally copy a float from one of 2 vectors to a target: c[i] = rand_vec[i] < threshold ? a[i] : b[i] where a, b, c are contiguous arrays of float, rand_vec is the std::vector I'm trying to figure out here, and threshold is a single variable of type integer_tbd. The code compiles as SSE SIMD operations. I do not remember the details of this, but I believe that this requires additional shifting instructions if the ints are smaller than the floats.

On this basis, I've written a very simple allocator, with a single static boost::lockfree::queue as the free-list. Given that I will construct the vectors myself and they will go out of scope when I'm finished with them, I know with certainty that all calls to alloc::deallocate(T*, size_t) will always return vectors of the same size, so I believe that I can simply push them back onto the queue without worrying about a pointer to a differently-sized allocation being pushed onto the free-list.

As noted in the code below, I've added in runtime tests for both the allocate and deallocate functions for now, while I've been confirming for myself that these situations cannot and will not occur. Again, I believe it is unquestionably safe to delete these runtime tests. Although some advice would be appreciated here too -- considering the surrounding code, I think they should be handled adequately by the branch predictor so they don't have a significant runtime cost (although without instrumenting, hard to say for 100% certain).

In a nutshell - as far as I can tell, everything here is completely within my control, completely deterministic in behaviour, and, thus, completely safe. This is also suggested when running the code under typical conditions -- there are no segfaults, etc. I haven't yet tried running with sanitizers yet -- I was hoping to get some feedback and guidance before doing so.

I should point out that my code runs 2× faster than using std::allocator, which is at least qualitatively to be expected.

---

CR_Vector_Allocator.hpp

class CR_Vector_Allocator {

  using T = CR_Range_t; // probably uint16_t or uint32_t, set elsewhere.

private:
  using free_list_type = boost::lockfree::queue>;

  static free_list_type free_list;

public:
  T* allocate(size_t);
  void deallocate(T* p, size_t) noexcept;

  using value_type = T;
  using pointer = T*;
  using reference = T&;

  template  struct rebind { using other = CR_Vector_Allocator;};
};

CR_Vector_Allocator.cc

CR_Vector_Allocator::T* CR_Vector_Allocator::allocate(size_t n) {

  if (n <= 1)
    throw std::runtime_error("Unexpected number of elements to initialize: " +
                         std::to_string(n));

  T* addr_;
  if (free_list.pop(addr_)) return addr_;

  addr_ = reinterpret_cast<T*>(std::malloc(n * sizeof(T)));
  return addr_;
}

void CR_Vector_Allocator::deallocate(T* p, size_t n) noexcept {
  if (n <= 1) // should never happen. but just in case, I don't want to leak
    free(p);
  else
    free_list.push(p);
}

CR_Vector_Allocator::free_list_type CR_Vector_Allocator::free_list;

---

It is used in the following manner:

using CR_Vector_t = std::vector<uint16_t, CR_Vector_Allocator>;

CR_Vector_t Generate_CR_Vector(){

  /* total_parameters is a member of the same class
     as this member function and is defined elsewhere */
  CR_Vector_t cr_vec (total_parameters); 
  std::uniform_int_distribution<uint16_t> dist_;

  /* urng_ is a member variable of type std::mt19937_64 in the class */
  std::generate(cr_vec.begin(), cr_vec.end(), [this, &dist_](){
     return dist_(this->urng_);});
     return cr_vec; 
}

void Prepare_Next_Generation(...){
  /* 
     ... 
  */
  using hpx::parallel::execution::par_unseq;
  hpx::parallel::for_loop_n(par_unseq, 0l, pop_size, [this](int64_t idx){
    auto crossovers = Generate_CR_Vector();
    auto new_parameters = Generate_New_Parameters(/* ... */, std::move(crossovers));
  }
}

Any feedback, guidance or rebukes would be greatly appreciated.

Answer 1

This only works if n is never changes between calls.

T* addr_;
if (free_list.pop(addr_)) return addr_;

IF you can guarantee this then its fine. Otherwise you need a free list for every different value of n. otherwise an allocation for 10 could be done then deallocated (thus you have a block of ten on the list). Now an allocation comes in for 20 (you will give it the block on the free list which has a size of 10).

If you know that n never changes then:

if (n <= 1)
  throw std::runtime_error("Unexpected number of elements to initialize: " +
                       std::to_string(n));

and

if (n <= 1) // should never happen. but just in case, I don't want to leak
  free(p);

Are a waste of time. You have already guaranteed that n is consistent.

This is particularly bad practice for something that needs optimal work.

if (n <= 1) // should never happen. but just in case, I don't want to leak
  free(p);

Branching is the single most problematic thing in degradation of performance. If the CPU branch prediction is off then you always pay the price. I would put that check in an assert() that way you can validate when testing but in production you don't need to perform the test.

Undefined Behavior.

This will not work:

static free_list_type free_list;

If you have any std::vector<> that use your allocator that is in the global scope (or any constructors for static storage duration objects that create vectors directly or indirectly with your allocator).

You will need to convert this to a static function:

   static free_list_type getFreeList() {
        static free_list_type free_list;
        return free_list;
   }