Tag: memory

C++ custom allocators: My first step

C++ custom allocators are a topic I don’t get around too much. They scream performance and memory usage and that’s a place I want to be. I felt a few times I might need a custom allocator to solve particular problems around dynamic memory, but it’s not something I would just jump on.

In embedded systems, dynamic memory is often replaced by static memory to get better performance and deterministic behavior. But writing custom allocators for this is not the first approach I would have. A vector can be replaced by an array and a map by a static map, and in general, memory can be allocated on the stack.

Everything has a price

This comes with costs. Not once I would’ve used dynamic polymorphism to design a feature. Even if in C++ dynamic polymorphism is not the greatest and templates can be used to achieve compile-time polymorphism, there are moments when I would choose the dynamic version for its design simplicity.

I ask myself from time to time how I could use virtual inheritance… without allocating on the heap. Some data structures from the standard library accept a custom allocator to allow me to better control how memory is managed. And this idea of controlling how an object is being allocated is bugging me more often. So I’m making a first, small, shy step. Continue reading C++ custom allocators: My first step

Map with static memory

A map dynamically allocates memory on the heap for stored objects. When new objects are added to the map, new allocations are made. Not for every added object, but there are moments when the allocated memory is not enough and more is needed.

There are systems where runtime allocations are not preferred or even forbidden because they are not predictable (they depend on how data is inserted or removed) and they take time. In these cases, an approach is to use static memory, known at compile time. For this, you need to know the size of your data.

The two approaches above are the main difference between a vector (dynamic) and an array (static) of the C++ standard library.

C++ does not provide a map that uses static memory. And I started writing one for learning purposes. It’s a concept, not ready for production, with missing features, not optimized for speed and size. I just wanted a map with static memory that would help me achieve constant lookup complexity in some algorithms. And I added some map-like features.

I started by defining the need. I have some 2D points and some types of points.

enum class PointType {
    a,
    b,
    c,
    d,
    e,
};

struct Point {
    int x;
    int y;
};

And I want a list of those points, each of them associated with a type, so I can easily find a point by a given type.

PointType::a -> Point{0, 0}
PointType::b -> Point{1, 3}
PointType::c -> Point{10, 5}

I could have reached for simple approaches like an array of points and a switch on the given type. And that’s what I kind of did but in a generalized way. I’m storing the values (Point) into an array. Then, for each map access by key, I need to find the corresponding index; this would be the hash function, which I called an indexer because it generates an index for the storage array. The default indexer that I provide does a static_cast from the key to std::size_t; a custom one can be passed.

At this point, I have a simple map that receives a Key type and a Value type, just like the standard map. Using static memory, it also needs to know the size. Continue reading Map with static memory

Explaining memory alignment and undefined behavior to myself

Memory alignment is important for the CPU to be able to read data. But it’s not always critical that the alignment is optimal.

A struct like the one below is aligned but comes with a size cost because the size of an int is larger than the size of a short and some padding is added.

struct Model {
    int a;
    short b;
    int c;
    char d;
}

Probably in critical real-time software I would need to better align it by moving the second int above the first short value. And I will get a smaller size of the struct because the padding is not needed.

struct Model {
    int a;
    int c;
    short b;
    char d;
}

I see a size of 16 bytes for the first version and 12 bytes for the second.

Another special case is serialization. When I want to transport data of a struct through a buffer, alignment is important because different compilers can handle padding in different ways. If I have a short (2 bytes) and an int (4 bytes), padding of 2 bytes will be added. But padding varies among compilers, so I should set the alignment of a struct to 1 byte, and thus memory is contiguous, with no padding. Therefore the compiler knows to read 2 bytes for the short and the following 4 bytes for the int.

#pragma pack(push, 1)
struct Model {
    short exists;
    int items[2];
} model;
#pragma pack(pop)

Continue reading Explaining memory alignment and undefined behavior to myself