Year: 2019

There is an interesting set of articles at Fluent{C++} discussing AoS vs SoA.
I decided to do my own performance test: to iterate and accumulate data over an array of 10,000,000 structures that describe a person:

Versus a structure of arrays of the same data:

Below are the numbers measured on my 2012 MacBook Pro 2.3 GHz Intel Core i7. The code was compiled with maximum optimizations using latest GCC, Apple Clang, and LLVM compilers available for Mac OS:

GCC -Ofast -march=native -lstdc++
AoS duration 108.039 ms
SoA duration 42.228 ms

Apple CLANG -Ofast -march=native -lc++
AoS duration 64.001 ms
SoA duration 24.916 ms

LLVM CLANG -Ofast -march=native -lc++
AoS duration 67.579 ms
SoA duration 22.620 ms

Conclusion: locality of reference matters 🙂

Complete listing:

P.S. I had to do the sum += and return sum; hack. Otherwise the compilers kept optimizing away the averageXXX calls!

Let us take a look at what the C++ compiler generates for us when we use the keywords new, new[], delete, and delete[](I will skip over std::nothrow versions in this post).

new

When you write this:

The compiler really generates this:

First, using operator new the memory for T is allocated. If the allocation fails it will throw std::bad_alloc exception. Next (line 4) the object of type T is being constructed in the memory address t2 (this is called placement new). This however may fail due to T’s constructor throwing an exception. The language guarantees that if that happens, the allocated memory will be freed. The code in line 6 will catch any exception emitted by T’s constructor. Line 8 will then free the memory, and finally line 9 will re-throw the exception.

delete

This one-liner:

Becomes this:

In line 1 T’s destructor is called, and in line 2 the memory is freed using operator delete. All is good until T’s destructor throws an exception. Noticed the lack of try-catch block? If T’s destructor throws, line 2 will never be executed. This is a memory leak and reason why you should never throw exceptions from destructors; see Effective C++ by Scott Meyers, Item #8.

new[]

Things are about to get interesting. This innocent looking snippet of code:

Becomes (gasp), more or less 😉 , this:

So what happens when we allocate an array of objects on the heap? Where do we store the number of objects allocated which needs to be referenced later when deleting the array?
The compiler will generate code that allocates enough space for HOW_MANY instances of T, plus sizeof(size_t) bytes to store the number of objects created and will place the object count at offset 0 of the allocated memory block. Moreover the language guarantees that it will either allocate and construct ALL instances of T, or none. So what happens if halfway through constructing the objects in the array one of the constructors throws an exception? The compiler will generate proper cleanup code to deal with this scenario. This is what the above code illustrates. Let’s go through it line by line.
Line 1 allocates enough space for HOW_MANY objects plus sizeof(size_t) bytes for the number of objects in the array.
Line 2 stores the number of objects at offset 0 of the memory block.
Line 3 advances the pointer t4 by sizeof(size_t) bytes to where the first T will be created.
Line 4 is the loop inside which we’ll be creating the instances of T one by one.
Line 8 creates an instance of T at the right memory location inside the array using placement new (same as when constructing a single instance of T).
Line 10 catches any possible exception from T’s constructor and begins the cleanup block of partially constructed array.
Line 12 defines the loop that will destroy all instances of T created up to the point of exception being thrown.
Line 13 calls the destructor of T.
Line 14 moves the pointer t4 back by sizeof(size_t) bytes to the beginning of the memory block allocated for the array.
Line 15 frees the previously allocated memory block.
Line 16, after having done all the cleanup, re-throws the exception.

delete[]

The following array delete statement:

Is turned into something like this:

The compiler now has to generate code to first destroy all the instances of T stored in the array before deallocating the memory. After allocating the array of T’s the t4 pointed at the first object in the array, not at the beginning of the memory block. That’s why…
Line 1 subtracts sizeof(size_t) bytes from t4 and retrieves the number of objects in the array.
Line 2 starts the loop that will call every T’s destructor.
Line 3 destroys each instance of T.
Line 4 moves the t4 pointer back by sizeof(size_t) bytes to point at the beginning of the memory block.
Line 5, after all T’s have been destroyed, frees the memory block.
Due to a lack of try-catch block the same principle of not throwing exceptions from destructors applies here as well.

Complete listing:

Thanks to Sebastian Mestre (who commented on my previous post) I learned something new today 🙂 The X macro makes the enum to string code much… well, perhaps not cleaner, but shorter 😉 It also solves the problem of having to update the code in 2 places: 1st in the enum itself, 2nd in the enum to string map.
Without further ado I present to you the X macro:

And the complete implementation goes something like this:

In this version we only have to update the MY_ENUM macro. The rest is taken care of by the preprocessor.

UPDATE

Here’s the same approach that works with strongly typed enums:

UPDATE 2

Here’s the same approach that works with strongly typed enums, custom enum values, and enum values outside of the defined ones:

A fellow engineer at work asked me today how to convert an enum to a string value. This is what I came up with:

MyEnumToString function has a static map of MyEnum to const char*. In the assert it checks that the MyEnum::SIZE is equal to the size of the map: so you don’t forget to update the map when you update MyEnum with a new entry 😉

For larger enums would unordered_map be a better choice for the mapping data structure in terms of performance? Probably.

UPDATE

Several people on here and reddit suggested that the use of std::map or even std::unordered_map is an overkill. I agree. Though it is a must for non continuous enums (ones that do not start at 0 and do not increment by 1). Below is an updated MyEnumToString function which offers much faster conversion. It uses std::array to hold the string values.

Lesson learned the hard way: trust the implementation to do the right thing! Everything else has been strikethrough’ed because my approach was flowed from the beginning. See the quoted comments at the bottom of this post.

Thanks everyone who commented! Looks like this blogging thing will be a great learning exercise for me 🙂

From https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

It is a non-binding request to reduce capacity() to size(). It depends on the implementation whether the request is fulfilled.

In other words, it can do absolutely nothing! Now what?
Let’s test programmatically what the implementation of STL is actually doing, and in case it does nothing let’s shrink the vector another way.

The test:

Self explanatory I hope 🙂 we create a vector of 1 std::byte, reserve space for 2 entries, then call shrink_to_fit. Finally we test the capacity; if it’s now 1 instead of 2, the call worked. Great! But what if it failed to shrink the vector?

shrink_to_fit that works:

We first test (once, thanks to static) if shrink_to_fit works, if it does, we invoke it. Otherwise we fallback onto a temporary -> swap trick. This works because the temporary vector created from v will have capacity equal to v‘s size. See here: https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Shrink-to-fit

Test of our solution:

Output of the program from my Xcode console:

10
5
Program ended with exit code: 0

Complete listing:

UPDATE!

I shared my blog on Reddit CPP as well as comp.lang.c++ and received many comments about my shrink_to_fit approach:

Ouch 😉 Very constrictive critique of my implementation. Thank you sakarri and Joerg! So I decided to rewrite the initial shrink_to_fit function, here it is:

In this approach we skip the shrink_to_fit_test and go straight to the vector’s call. If it doesn’t do what we want we do the temporary -> swap trick.

Here’s the complete listing again:

Below are some of the comments I received:

Just figured I’d comment on your post about how  shrink_to_fit sucks. It’s your solution that is significantly inferior in every possible way whereas the standard’s approach is optimal. That may seem blunt but it’s worth understanding why.
First your  shrink_to_fit_test is too pessimistic since it assumes that an implementation either always performs the shrink or never performs it when actually the situation is a lot more complex than that. The whole purpose of the standard leaving it up to the implementation is that for small vectors, forcing a  shrink_to_fit potentially wastes a lot more memory than not doing anything at all. The reason is two fold, first because the default allocator doesn’t allocate memory less than 16 bytes to begin with. In other words a vector of 10 bytes takes up just as much memory as a vector of 1 byte so forcing a  shrink_to_fit in that situation doesn’t save you anything. Furthermore with your implementation it actually ends up potentially causing you to waste 4 kilobytes of RAM because your solution forces a new memory allocation and given how virtual memory works, that allocation can result in having to fetch a new page, so you’ve now wasted 4 kilobytes of physical RAM for nothing.
In situations where something like this seems fishy, it’s best to review the literature on the issue to understand why the committee made the decision they did. Sometimes they do screw up, but that’s not the initial conclusion you should jump to. Take a look at how GCC implements  shrink_to_fit, it delegates the operation to the allocator so the allocator can decide whether to carry it out since the allocator knows more about the memory system than  vector does. It also implements the operation in a way that can avoid any reallocation period and it does its best to provide the strong exception guarantee.
The standard didn’t make this part of the STL non-binding so that the people who work incredibly hard to implement it could be lazy, the standard made it non-binding so that if there are potential optimizations that save more memory and consume fewer CPU cycles by avoiding it, the implementation would be free to leverage them. This is explicitly noted in the standard as follows:
Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note
Basically there is no situation where you would want to use your implementation of  shrink_to_fit over the one provided by the standard library.

In particular, the January 27 posting “shrink_to_fit that doesn’t suck” 
still provides only solutions (to a non-existing problem) that do suck…