This is not your typical "Hello World" to say the least. Recently, I have been learning C++ for programming microcontrollers. However, the ability to make fast, dynamic libraries for VBA and more also appeals to me. Normally, I learn code through books, but I primarily learned C++ from this video series.
Learning Experience
I have an intermediate book on programming microcontrollers, Real-Time C++. So, the goal of watching that playlist was to get me started rather than to rely on it entirely. However, the depth far exceeded my expectations and matched what I expect from a good book, although some of the very basics were skipped over. I strongly recommend it.
I learn code differently than most. I study for many hours until I have a solid understanding of how the language works. Then, I write code to apply and refine what I learned. As a result, I watched that playlist without having actually written any C++ code before, not even "Hello World" test. So, I decided it was time to install an editor and write some code.
The Problem
When I put effort towards something, I prefer it to be something productive. So, instead of a test script, I wanted to make something that would be useful to me. I want to implement my weight tracker in C++. However, that was too ambitious at all once. Instead, I decided to make a library tool for that project as well as others. I decided to make a class for multi-dimensional arrays. This array would need to be allocated during runtime so that the lengths may be determined by data in a file or database.
Traditionally, multi-dimensional arrays would be implemented through using arrays of arrays of arrays of... you get the idea. Consider the example below. You would access single data elements using the notation Array[x][y]. The main array would contain an array of pointers. And, each pointer would contain an array of values in the y-dimension. The video below explains the traditional implementation of multi-dimensional arrays in C++.
The following video discusses static multi-dimensional arrays while covering pointers in detail.
Memory fragmentation may be avoided with different techniques, but there would still be a considerable storage overhead. Consider an array of the form Array[x][y][z] with dimension lengths of X=10, Y=4, and Z=4. That may be a realistic situation for storing transformation matrices as used in 3D graphics. The X array would consist of 10 pointers. The Y array would consist of 4 pointers, and there would be X number of them, 10. That means there would be X + X * Y + 1 = 51 pointers, counting the main pointer.
Consider the overhead as a percentage of the size of pointers versus the size of the data elements. The size for each data element in bytes may be represented as a multiple, k, of the size of a pointer in bytes. The percentage would be (X + X * Y + 1) / (k * X * Y * Z). This may be significantly reduced by bypassing the arrays of pointers and accessing the data directly.
The Solution
Data in memory is not stored in multiple dimensions; it is stored in just one dimension. So, it makes sense to simply allocate all the needed data in a single dimension, a single array. Then, any data within that array of data may be accessed with a single pointer, or index. This is not different from how arrays access memory to begin with.
A pointer has a datatype. The pointer increments its memory address in multiples of the size of its datatype. An integer point may be 4 bytes, so incrementing the pointer by 2 will point to a memory address 8 bytes "away." Following the matrix example above, one could create a 16 element transformation matrix struct. Then, an array of those structs could be heap allocated. When the array index is incremented by 1, the pointer is moved in memory by the size of the struct such that it point to the next struct. Then, accessing an element within the struct accesses the memory at a given offset from the address of the struct.
This concept may be generalized. One could heap allocate a single array of data. Then, matrices may be virtually grouped by a controller. The controller would access the data by manipulating the index that it uses the access the array. Consider the following.
It shows two 4x4 matrices of incremental data. Dimension X holds the matrices, as if they were a struct or class. Dimension Y holds the rows of the matrices. Dimension Z holds the values within each row. At the bottom, it lists all the data in memory, in an array. Above that, it lists the index of such an array. Above that it lists the corresponding x, y, z coordinates of the elements in that array as if they were in a 3D array.
As shown, the index location of the 3D data inside the 1D array may be determined with an equation based upon the element counts of each matrix and each row. More generally speaking, an equation based upon the lengths of the virtual dimensions may specify the index of any data element.
So, the multi-dimensional arrays may be stored as normal arrays. And, a controller class may access the data by calculating an index value for a given set of input coordinates. Now, this concept needs implemented, and it presents some challenges.
The Implementation
Several challenges present themselves while coding this. First, as far as I could tell, the number of arguments that a function requires may not be varied by a template. So, either every case must be programmed or the function must accept however many arguments in a parameter pack. At the time of writing this, that playlist did not contain a video focusing on parameter packs and variadic functions.
Second, chaining bracket operators is complicated. The bracket operator of the controller class must return an object that also returns an object with its bracket operator to chain the operators. Sure, simply using a function that accepts indices as arguments would work, but I really wanted something that would behave similarly to the nested arrays in that one could chain bracket operators. However, this was challenging since C++ only allows functions to return a single datatype. Below is an illustration of the issue and the solution.
Because a class cannot have multiple return types for a given function, the controller object must only return another object, of the Dimension class in this example, or a data reference. It cannot return either depending upon the number of dimensions specified through the template. Likewise, an instance of the Dimension class can only return another Dimension class object or a data reference. The MultArray class could return a Dimension class which returns a data reference, but that is for strictly two dimensions. However, different classes may be chained together for as many dimensions as one needs as long as the end of the chain always returns a data reference.
From this, let a Dimension <1> object always return a data reference. And, let a Dimension <2> object always return a Dimension <1> object. However, if the MultArray may only return Dimension <2> class objects. This chain will only allow for various dimensions if the MultAray object could return any Dimension <N> object at the beginning of the chain.
Thankfully, this can be done using templates. A template parameter may be used for the MultArray class which specifies how many dimensions the class will have and which Dimension class object it will return. A MultArray<5> class object could always return a Dimension<4> class object. The Dimension class may be templated such that a Dimension<N> class object always returns a Dimension<N-1> class object. However, such a structure would have a chain of infinite Dimension class objects chained together.
This chain may be ended by manually defining the Dimension <1> class. Although the return datatype cannot be varied by a template, classes with different template arguments may return different datatypes as if they were different classes entirely, because they actually are different class types. So, this limitation may be worked around by customizing the Dimension<1> class. Similarly, the MultArray<1> class may be defined specifically to return a data reference as well as to omit most of the control structures since it would be only a single dimension array.
Code
Here is the commented code. It includes a DEBUG flag to add some extra checks for when debugging. It could use some extra features such as being able to change the lengths of dimensions, but this is a very solid starting point.
The code worked before, but a mistake may have crept in while formatting it for this post.
#define DEBUG 1
//Declaration for MultArrayDimension to see
template<typename T, const size_t _Dims> class MultArray;
//MultArrayDimension<T, _Dims, _Dim>
//Templated class that chains together to enable a chain of []
// operators to select data from a MultArray.
template<typename T, const size_t _Dims, const size_t _Dim>
class MultArrayDimension
{
private:
//Next object in the chain
MultArrayDimension<T, _Dims, _Dim - 1U> returnObj;
//Reference to the parent MultArray object
MultArray<T, _Dims>* m_MultArray;
public:
//Constructor takes a pointer to the parent MultArray object
// to store it for its own reference and to construct the
// next MultArrayDimension in the chain.
MultArrayDimension(MultArray<T, _Dims>* MultArray)
: m_MultArray(MultArray), returnObj(MultArray) {}
~MultArrayDimension()
{
//This prevents the parent MultArray from being deleted with
// the referencing MultArrayDimension child objects.
m_MultArray = nullptr;
}
//Overload the [] operator to return the next MultArrayDimension
// in the chain.
MultArrayDimension<T, _Dims, _Dim – 1U>& operator[](size_t index)
{
//Increment the target index of the MultArray for the index
// passed in the brackets.
m_MultArray->addIndex(_Dims - _Dim + 1U, index);
return returnObj;
}
};
//MultArrayDimension<T, _Dims, 1>
//The last MultArrayDimension in the chain (_Dim = 1) must
// be specially defined to return something different.
template<typename T, const size_t _Dims>
class MultArrayDimension<T, _Dims, 1U>
{
private:
//Reference to the parent MultArray object
MultArray<T, _Dims>* m_MultArray;
public:
//Constructor takes a pointer to the parent MultArray object
// to store it for its own reference
MultArrayDimension(MultArray<T, _Dims>* MultArray)
: m_MultArray(MultArray) {}
~MultArrayDimension()
{
//This prevents the parent MultArray from being deleted
// the referencing MultArrayDimension child objects.
m_MultArray = nullptr;
}
//Overload the [] operator to return a reference to the data
// selected from all the specified indecies.
T& operator[](size_t index)
{
//Increment the target index of the MultArray for the last index
m_MultArray->addIndex(_Dims, index);
//Return the data in the array at the composite index
return m_MultArray->getData(m_MultArray->getIndex());
}
};
//MultArray<T, _Dims>
//Creates an array and overlays controls to use it as if it was
// a multi-dimensional array.
template<typename T, const size_t _Dims>
class MultArray
{
private:
//Stores which index of the array is being requested
size_t m_index = 0U;
//Pointer for the array
T* m_data = nullptr;
//Stores the element count of each dimension
size_t m_dimLengths[_Dims];
//Holds products of dimension element counts for indexing
size_t m_dimElementProducts[_Dims + 1U];
//MultArrayDimension for overloading additinoal [] overloads
MultArrayDimension<T, _Dims, (_Dims - 1U)> returnObj;
public:
//Constructor constructs the child MultArrayDimension with a
// pointer to itself so that the child can call various methods.
MultArray()
: returnObj(this) {}
~MultArray()
{
//Delete the heap-allocated array when this object is destroyed
delete[] m_data;
}
private:
//These functions are only needed in debug mode for checks.
#if DEBUG
//Unpacks and counts the number of packed parameters. This
// function runs once for each argument, returning 1U each time.
template<typename Arg, typename... Args>
const size_t countArgs(Arg dim, Args... dims) const
{
size_t count = 1;
//Run this method recursively for each argument, summing the
// returned 1Us. This gives the number of times the function ran.
count+=countArgs(dims...);
return count;
}
//After the final argument, this intercepts the recursive call
// to end the recursion and to return a 0U instead of a 1U.
const size_t countArgs() const { return 0U; }
//Check that a specified dimension or index is not out of bounds
bool isIndexInBounds(size_t dim, size_t index)
{
if (dim > _Dims)
{
//Error implementation
return false;
}
if (index > m_dimLengths[dim - 1U] - 1U)
{
//Error implementation
return false;
}
return true;
}
//Check that a specified index is not out of bounds of m_data
bool isIndexInBounds(size_t index)
{
if (index > m_dimElementProducts[0] - 1U)
{
//Error implementation
return false;
}
return true;
}
#endif
//This accepts numbers representing the length of each
// dimension and stores them in an array.
template<typename Arg, typename... Args>
void setDimArray(Arg dim, Args... dims)
{
//Strip out the first argument and add it to m_dimLengths
m_dimLengths[m_index] = dim;
//Misuse m_index as an incrementing index for m_dimLengths
m_index++;
//Recursively call this function, stripping off and adding
// an argument each time.
setDimArray(dims...);
//Reset m_index to avoid errors since 0U is its initial value.
m_index = 0U;
}
//Runs when the arguments are all used to end the recursion
void setDimArray() {}
//Multiplies the lengths of the dimensions to get the number
// of elements inside each dimension and stores them in
// m_dimElementProducts.
void setElementProducts()
{
size_t multiplier = 1U;
//m_dimElementProducts[_Dims] is the # of sub-elements in
// dimension _Dims, corresponding to m_dimLengths[_Dims - 1].
m_dimElementProducts[_Dims] = multiplier;
// m_dimElementProducts[0] is the length of m_data.
// The products are stored backwards, as they are multiplied.
for (int i = _Dims-1; i > -1; i--) {
multiplier *= m_dimLengths[i];
m_dimElementProducts[i] = multiplier;
}
}
public:
//Dimension the MultArray; it cannot be used without running
// this, and the constructor cannot use packed parameters.
template<typename... Args>
void setDimLengths(Args... dimSizes)
{
//This check is only needed in debugging. More checking could be
// done, like checking that no lengths are 0. This checks for the
// correct number of arguments and that it has not been run before.
#if DEBUG
//This checks for the correct number of arguments and
//that it has not been run previously.
size_t argCount = countArgs(dimSizes...);
if ((argCount == _Dims) && (m_data == nullptr)) {
#endif
//Set the lengths of the dimensions into m_dimLengths[]
setDimArray(dimSizes...);
//Compute the number of elements per dimension
setElementProducts();
//Allocate m_data based upon the total # of elements
m_data = new T[m_dimElementProducts[0U]];
#if DEBUG
}
else
{
//Error implementation
}
#endif
}
//Overwrites m_index with the beginning of an index
//For setDimLengths(100,2,4), the value of [i][j][k] is stored
void setIndex(size_t dim, size_t index)
{
//This check is only needed in debugging.
#if DEBUG
if (isIndexInBounds(dim, index))
#endif
m_index = index * m_dimElementProducts[dim];
}
//Same as setIndex except it adds the next part of the index
// to m_index. From the previous example, m_index += j*4
void addIndex(size_t dim, size_t index)
{
//This check is only needed in debugging.
#if DEBUG
if (isIndexInBounds(dim, index))
#endif
m_index += index * m_dimElementProducts[dim];
}
//Returns the value of m_index for the last MultArrayDimension
// to use in calling MultArray::getData
const size_t getIndex() const
{
return m_index;
}
//Returns the length of a specified dimension
const size_t getLength(size_t dim) const
{
//This check is only needed in debugging.
#if DEBUG
if (isIndexInBounds(dim, 0U))
#endif
return m_dimLengths[dim];
}
//Returns the total number of elements
const size_t getDataLength() const
{
return m_dimElementProducts[0U];
}
//Allows referencing m_data[index] with getData(index)
T& getData(size_t index)
{
//This check is only needed in debugging.
#if DEBUG
if (isIndexInBounds(index))
#endif
return m_data[index];
}
//Overloads the [] operator to set the first part of the index
// and to return the first MultArrayDimension in the chain.
MultArrayDimension<T, _Dims, _Dims - 1>& operator[](size_t index)
{
setIndex(1U, index);
return returnObj;
}
};
//MultArray<T, 1U>
//Specialization for a single dimension array
template<typename T>
class MultArray<T, 1U>
{
private:
//Pointer for the array
T* m_data = nullptr;
//Stores the number of elements in the array
size_t m_dimLength;
public:
//To behave as the multi-dimensional arrays, the constructor
// doesn't have anything to do anything.
MultArray() {}
~MultArray()
{
//Delete the heap-allocated array when this object is destroyed
delete[] m_data;
}
//Sets the size of the array.
void setDimLength(size_t dimLength)
{
//This check is only needed in debugging. The input arguments
// ensure that only one length is given.
#if DEBUG
if (m_data == nullptr) {
#endif
//Set the length of the dimension
m_dimLength = dimLength;
//Allocate m_data based upon the total # of elements
m_data = new T[m_dimLength];
#if DEBUG
}
else
{
//Error message implementation
}
#endif
}
//Returns the length of a specified dimension
const size_t getLength() const
{
return m_dimLength;
}
//Allows referencing m_data[index] with getData(index)
T& getData(size_t index)
{
//This check is only needed in debugging.
#if DEBUG
if (index < m_dimLength)
{
#endif
return m_data[index];
#if DEBUG
}
else
{
//Error implementation
}
#endif
}
//Overloads the [] operator to reference m_data[index]
T& operator[](size_t index)
{
//This check is only needed in debugging.
#if DEBUG
if (index < m_dimLength)
{
#endif
return m_data[index];
#if DEBUG
}
else
{
//Error implementation
}
#endif
}
};Overhead
The overhead of this code depends upon the number of dimensions, but the lengths of those dimensions do not matter. The case of a single dimension is the simplest and only has the overhead of 1 pointer and 1 integer. Two dimensions and greater have a greater overhead.
The case of two dimensions has 6 integers and 2 pointers. In the Visual Studio compiler for 32-bit systems, this amounts to 32 bytes of overhead, 4 bytes for each pointer and 4 bytes for each integer. Each additional dimension increases the overhead by 2 integers and 1 pointer, or 12 bytes in this case. So, the overhead may be expressed as 2 integers + N * (2 integers + 1 pointer) where N is the number of dimensions.
In the example of matrices, the overhead percentage was (X + X * Y + 1) / (k * X * Y * Z) where X=10, Y=4, and Z=4. Assuming k=2 for float elements of 8 bytes each, that would be 16%. For the MultArray, the overhead percentage is 3.4%. That is a significant improvement.
This does not come free. There is a performance overhead for calculating the index. Looking at the assembly output of MultArray[1][1][1] = 8 as shown below, it required 8 simple instructions. For MultArray[0][0][0] = 1, there were only 5 instructions.
Numbers[1][1][1] = 8;
00191159 mov eax,dword ptr [ebp-24h]
0019115C mov dword ptr [Numbers],eax
0019115F mov ecx,dword ptr [ebp-14h]
00191162 mov eax,dword ptr [ecx+1Ch]
00191165 add dword ptr [ecx],eax
00191167 mov ecx,dword ptr [ebp-18h]
0019116A mov eax,dword ptr [ecx+20h]
0019116D add dword ptr [ecx],eax This is in contrast the assembly instructions produced using nested arrays. While the storage efficiency is impressive, the performance penalty is unfortunate. The block of code above is the same number of lines as the block below, but it is for a single operation while the bottom block is for two operations!
Numbers[0][0][0] = 1;
00CC104F mov ecx,dword ptr [Numbers]
00CC1052 mov eax,dword ptr [ecx]
00CC1054 mov eax,dword ptr [eax]
00CC1056 mov dword ptr [eax],1
Numbers[1][1][1] = 8;
00CC10A1 mov eax,dword ptr [ecx+4]
00CC10A4 mov eax,dword ptr [eax+4]
00CC10A7 mov dword ptr [eax+4],8 For frequent operations, such overhead may be a problem... or it may not be. Maybe I will create some loops to perform hundreds or millions of operations on a larger dataset and run some benchmarks to see how much of a difference this really makes.
Going Forward
I am pleased with this code enough to move forward using it. But, I will be looking into improving it. Currently, I think that I can setup a templated struct to have the size of each dimension. Perhaps having structs of structs instead of arrays of arrays would be quite efficient while using some of the techniques used here. And, in the end, the greatest performance optimization may come from using a single function like MultArray(x, y, z) to reference the data instead of chaining bracket operations.
That said, part of the challenge was to make the bracket operation chaining work, and I succeeded. Now, I will be focusing on performance optimization and potentially further size reduction. However, the greatest prize is that I am confident enough in my knowledge of C++ to begin reading Real-Time C++: Efficient Object-Oriented and Template Microcontroller Programming. That may have some great advice on optimizations that may even be useful for setting up multi-dimensional arrays.
Comments