Implementation of a multi-dimensional array as a single memory buffer

Question

There is an updated version of this code with some of the recommended changes made here.

I have created an implementation of a multi-dimensional array which utilizes a single continuous memory buffer to improve cache locality. My intention is for this to behave in a similar way to a multi-dimensional vector in c++, and so I have overloaded Tensor::operator[] to return another Tensor object of dimension one less, which can then be indexed again with Tensor::operator[]. There is a base template specialization for the case where the dimension count is 1. Please give me some tips on how this implementation can be improved.

My main concerns with the code are that I use raw malloc and free statements, however I am not quite sure how I could implement this efficiently without using raw pointers and mallocs as I do not want to have to copy memory in the Tensor::operator[] function. Also I am not using the c++ equivalents of new and delete as they do not have an analogue to realloc.

#include <iostream>

template<typename Ty, size_t N>
class Tensor
{
private:
    Ty *data;
    size_t *offset;
    bool owner;
public:
    Tensor() :
        data(nullptr), offset((size_t*)malloc((N+1)*sizeof(size_t))), owner(true)
    {}
    Tensor(Ty *data, size_t *offset) :
        data(data), offset(offset), owner(false)
    {}
    ~Tensor()
    {
        if (owner)
        {
            free(offset);
            free(data);
        }
    }

    Tensor<Ty, N-1> operator[] (size_t i)
    {
        return Tensor<Ty, N-1>(&data[i*offset[N-1]], offset);
    }

    void resize(size_t* size)
    {
        if (!owner)
        {
            std::cerr << "cannot resize - memory is not owned" << std::endl;
            return;
        }
        offset[0] = 1;
        for (size_t i = 1; i <= N; ++i)
        {
            offset[i] = offset[i-1]*size[N-i];
        }
        data = (Ty*)realloc(data, offset[N] * sizeof(double));
    }
};

template<typename Ty>
class Tensor<Ty, 1>
{
private:
    Ty *data;
    size_t len;
    bool owner;
public:
    Tensor() :
        data(nullptr), len(0), owner(true)
    {}
    Tensor(Ty *data, size_t *offset) :
        data(data), len(offset[1]), owner(false)
    {}
    ~Tensor()
    {
        if (owner)
        {
            free(data);
        }
    }

    Ty &operator[](size_t i)
    {
        return data[i];
    }

    void resize(size_t* size)
    {
        if (!owner)
        {
            std::cerr << "cannot resize - memory is not owned" << std::endl;
            return;
        }
        len = size[0];
        data = (Ty*)realloc(data, len*sizeof(double));
    }
};

Answer 1

Do not use malloc() and free() in C++

My main concerns with the code are that I use raw malloc and free statements, [...] I am not using the c++ equivalents of new and delete as they do not have an analogue to realloc.

There is a good reason for that. While in C you only have so-called plain-old-data structs, in C++ a type can be a class that has constructors, destructors, copy and move operators. By using the C memory management functions, you are bypassing all these things, and can cause problems when you use this for classes that do have these things.

You should use new and delete, and indeed do realloc() by creating a new allocation, copying everything over, and deleting the old one. That might be inefficient, but it is more correct. You could specialize your class for trivial types to get performance back.

However, even better is to avoid doing your own memory management, whether it's C or C++ style. Instead, rely on existing containers to do it for you. I would use a std::vector to provide the single contiguous memory buffer for you:

template<typename Ty, size_t N>
class Tensor
{
private:
    std::vector<Ty> data;
    std::vector<size_t> offsets(N + 1);
    ...
}

This also avoids a bug in your code: when you call realloc(), you assume the size of an element is equal to sizeof(double), but you should have used sizeof(Ty). With std::vector<Ty>, you don't have to worry about this.

Create a separate view class

Instead of having class Tensor handle both the actual tensor and a lesser-dimensional view into the actual data, create two separate classes: class Tensor that owns the whole tensor, and a class TensorView that is a non-owning view into a Tensor:

template<typename Ty, size_t N>
class TensorView {
    Ty *data;
    size_t *offsets;
public:
    TensorView(Ty *data, size_t *offsets): data(datra), offsets(offsets) {}

    TensorView<Ty, N - 1> operator[](size_t i)
    {
        return {&data[i * offsets[N - 1]], offsets};
    }
};
...
template<typename Ty, size_t N>
class Tensor
{
private:
    std::vector<Ty> data;
    std::vector<size_t> offsets(N + 1);

public:
    TensorView<Ty, N - 1> operator[](size_t i)
    {
        return {&data[i * offset[N - 1]], offset};
    }

    void resize(const size_t *sizes)
    {
        offset[0] = 1;

        for (size_t i = 1; i <= N; ++i)
        {
            offset[i] = offset[i - 1] * sizes[N - i];
        }

        data.resize(offset[N]);
    }
};

This makes handling one-dimensional tensors a bit harder. Since C++17, you can use if constexpr to handle this, for example like so:

template<typename Ty, size_t N>
class Tensor
{
    ...
    auto operator[](size_t i)
    {
        if constexpr (N == 1) {
            return data[i];
        } else {
            return TensorView<Ty, N - 1>{&data[i * offset[N - 1]], offset};
        }
    }
    ...
};

Make it work like a STL container

Your class supports operator[] and resize(), but it would be much nicer if it supported all the features you would expect from a typical STL container, like std::vector. Not only does it add more member functions and operator overloads, it also handles const containers correctly, it allows iterating over the container using range-for loops.

Answer 2

I don’t agree with the answer by G. Sliepen. You created a multidimensional array specifically to work with numbers. T is a standard numeric type that doesn’t have a constructor or destructor. It is perfectly fine IMO to use std::malloc in this case. Just add a compile-time assert to verify that this is the case.

---

What I am missing are comments that explain the implementation. I gathered that offset is the stride for each dimension. But why are there N+1 values?

I am also missing a member variable that indicates the size of the array. Why does the 1D specialization have a len member? Note that you can’t derive the size of a dimension from its offset (==stride) if you want to be able to slice the array arbitrarily. For example, you might want to create an array as a view over a region of the original array. The strides remain the same, just the sizes change.

---

I would recommend making the offset array static. There is no reason to malloc that separately, given that its length is known at compile time, and it’s never very large.

---

Instead of a Boolean owner, consider using a std::shared_ptr. In the current implementation, a non-owning array can survive the array whose data it points to. This makes it really easy to use freed memory. If all arrays own the data through a shared pointer, you won’t have to worry about this. You will also not need a destructor, meaning that copy and move constructor and assignment can be automatically generate for you by the compiler.

In this version, each array would have a data shared pointer, and a second (naked) pointer pointing towards the first element of the array (so that the indexing works).

This also makes it unnecessary to separate the array from the array view, as suggested in the other answer by G. Sliepen.

---

I just realized that offsets is dynamic so that the non-owning array can reference the same offsets, avoiding copying them repeatedly in a multi-dimensional indexing expression. With the shared pointer suggestion above, you could allocate these two arrays at the same time, in the same block. One malloc is better than two.

Answer 3

Design issues

We have two-step initialization with mandatory resize call following a construction. A newly constructed but not resized Tensor object is in an invalid state. What if we forget to resize? What if a new length is not equal to N? Either way, we would get undefined behavior in the operator[]. As an alternative, consider fully constructing an object.

---

For now, Tensor objects are size-agnostic. Looks like we can assign one Tensor<int, 3> to another even if their sizes mismatch. Why should we allow it? For example, we can't assign one std::array to another of different size. Consider an alternative declaration

template<typename T, size_t... Sizes>
class Tensor {
 static constexpr size_t N = sizeof...(Sizes);
 /*...*/
};

Tensor<int, 2, 3, 4, 5> t;

Furthermore, should we allow assignment for Tensors of an arbitrary number of dimensions, like it is done for std::vectors of different sizes? If positive, we could dynamically set sizes like it has already been done.

template<typename T>
class Tensor {
public:
  explicit Tensor(std::initializer_list<size_t> tensorDimensions)
      : dimensions{tensorDimensions} { /* ... */ }  
  /* ... */

private:
  std::vector<size_t> dimensions;
  /* ... */
};

Tensor<int> t{2, 3, 4, 5};

---

We have the template specialization that must follow the main template implementation, which causes the amount of code double because any template specialization is a separate class. As an alternative, we could add a separate non-owning class like view or slice.

On using of malloc

Always check the return value, which may eventually be null. In general, prefer to avoid C-style memory management methods. Regarding your concern, I suggest checking vector class implementations that rely on allocators. A good explanation given in the book "The C++ Programming Language" by Stroustrup. There is also a related review.

If manual memory management is a burden, implement Tensor by means of another generic container like std::vector.

Define special class members for classes that manage resources

Since Tensor objects own memory, it is necessary to define special class members: Tensor(const Tensor&), Tensor& operator=(const Tensor&), Tensor(Tensor&&), Tensor& operator=(Tensor&&), ~Tensor(). Often, some undefined methods are implicitly generated and perform trivial behavior, which will likely result in undefined behavior. For example, Tensor has implicitly generated trivial copy operations. Move operations are not declared (not generated) because the destructor is explicitly defined. Any attempt to copy or move (a copy method is applied) performs shallow memberwise copy, which makes offset and data members freed multiple times (double free error). To learn more about special class members, I suggest the talk. Slides alone may be used as a cheat sheet. Also, there are related core guidelines.

Test the code

I suggest testing the to be reviewed code. The reviewed code should be ready for use. Considering the issues above, the one we have looks rather unfinished.

Also, use sanitizers for testing. They may save a lot(!) of time wasted on manual debugging. For example, gcc options: -fsanitize=address, -fsanitize=leak, -fsanitize=undefined. Visual Studio also has sanitizers.

Compiler warnings are helpful too, like -Wall -Wextra for gcc.

On the resize function implementation

Do not pass to a function a raw pointer to an array. We don't even know the size's length here.

---

Always test the realloc return value. It is not an error if realloc returns null pointer, but dereferencing null pointer is an undefined behavior.

---

Prefer C++-style casts to C-style casts. Use static_cast<Ty*>(/*...*/).

---

Typo - sizeof(double).

On using Tensor with user defined data types

Since Tensor is a generic container, we could use it with user defined data types, say std::string. Low-level memory allocation alone is insufficient to create an array of such objects. We have to manually construct them. For details, refer to the vector implementations.

Otherwise, explicitly restrict the applicability. For example, if T is meant to be an integer or floating point type,

template<typename T, size_t N, void = enable_if_t<is_arithmetic_v<T>>>
class Tensor { /* ... */ };

// or in C++20
template<typename T>
requires (is_arithmetic_v<T>)
struct Tensor { /* ... */ };

Place class' public section first

Emphasizing class interface improves readability.

Hide implementation details

Looks like the constructor Tensor(Ty*, size_t*) should not be exposed to class users.