Tag: c++

Entries for tag "c++", ordered from most recent. Entry count: 144.

Pages: 1 2 3 ... 18 >

# Intrusive Linked List in C++

Tue
25
May 2021

A doubly linked list is one of the most fundamental data structures. Each element contains, besides the value we want to store in this container, also a pointer to the previous and next element. This may not be the best choice for indexing i-th element or even traversing all elements quickly (as they are scattered in memory, performance may suffer because of poor cache utilization), but inserting an removing an element from any place in the list is quick.


Source: Doubly linked list at Wikipedia.

Inserting and removing elements is quick, but not necessarily very simple in terms of code complexity. We have to change pointers in the current element, previous and next one, as well as handle special cases when the current element is the first one (head/front) or the last one (tail/back) – a lot of special cases, which may be error-prone.

Therefore it is worth to encapsulate the logic inside some generic, container class. This authors of STL library did by defining List class inside #include <list>. It is a template, where each item of the list will contain our type T plus additional data needed – most likely pointer to the next and previous item.

struct MyStructure {
int MyNumber;
};
std::list<MyStructure> list;
list.push_back(MyStructure{3});

In other words, our structure is contained inside one that is defined internally by STL. After resolving template, it may look somewhat like this:

struct STL_ListItem {
STL_ListItem *Prev, *Next;
MyStructure UserData;
};

What if we want to do the opposite – to contain “utility” pointers needed to implement the list inside our custom structure? Maybe we have a structure already defined and cannot change it or maybe we want each item to be a member of two different lists, e.g. sorted by different criteria, and so to contain two pairs of previous-next pointers? A definition of such structure is easy to imagine, but can we still implement some generic class of a list to hide all the complex logic of inserting and removing elements, which would work on our own structure?

struct MyStructure {
int MyNumber = 0;
MyStructure *Prev = nullptr, *Next = nullptr;
};

If we could do that, such data structure could be called an “intrusive linked list”, just like an “intrusive smart pointer” is a smart pointer which keeps reference counter inside the pointed object. Actually, all that our IntrusiveLinkedList class needs to work with our custom item structure, besides the type itself, is a way to access the pointer to the previous and next element. I came up with an idea to provide this access using a technique called “type traits” – a separate structure that exposes specific interface to deliver information on some other type. In our case, it is to read (for const pointer) or access by reference (for non-const pointer) the previous and next pointer.

The traits structure for MyStructure may look like this:

struct MyStructureTypeTraits {
typedef MyStructure ItemType;
static ItemType* GetPrev(const ItemType* item) { return item->Prev; }
static ItemType* GetNext(const ItemType* item) { return item->Next; }
static ItemType*& AccessPrev(ItemType* item) { return item->Prev; }
static ItemType*& AccessNext(ItemType* item) { return item->Next; }
};

By having this, we can implement a class IntrusiveLinkedList<ItemTypeTraits> that will hold a pointer to the first and last item on the list and be able to insert, remove, and do other operations on the list, using a custom structure of an item, with custom pointers to previous and next item inside.

IntrusiveLinkedList<MyStructureTypeTraits> list;

list.PushBack(new MyStructure{1});
list.PushBack(new MyStructure{2});

for(MyStructure* i = list.Front(); i; i = list.GetNext(i))
printf("%d\n", i->MyNumber); // prints 1, 2

while(!list.IsEmpty())
delete list.PopBack();

I know this is nothing special, there are probably many such implementations on the Internet already, but I am happy with the result as it fulfilled my specific need elegantly.

To see the full implementation of my IntrusiveLinkedList class, go to D3D12MemAlloc.cpp file in D3D12 Memory Allocator library. One caveat is that the class doesn't allocate or free memory for the list items – this must be done by the user.

Comments | #algorithms #c++ Share

# Book Review: C++ Lambda Story

Wed
13
Jan 2021

C++ Lambda Story book

Courtesy its author BartÅ‚omiej Filipek, I was given an opportunity to read a new book “C++ Lambda Story”. Here is my review.

A book with 149 pages would be too short to teach entire C++, even in its basics, but this one is about a specific topic, just one feature of the language – lambda expressions. For this, it may seem like even too many, depending on how deeply the author goes into the details. To find out, I read the book over 3 evenings.

The book starts from the very beginning – the description of the problem in C++98/03, where lambdas were not available in the language, so we had to write functors - structs or classes with overloaded operator(). Then he moves on to describing lambdas as introduced in C++11, their syntax and all the features. Every feature described is accompanied by a short and clear example. These examples also have links to the same code available in online compilers like Wandbox, Compiler Explorer, or Coliru.

In the next chapters, the author describes what has been added to lambdas in new language revisions – C++14, C++17, C++20, and how other new features introduced to the language interact with lambdas – e.g. consteval and concepts from C++20.

Not only features of lambda expressions are described but also some quirks that every programmer should know. What if a lambda outlives the scope where it was created? What may happen when it is called on multiple threads in parallel? The book answers all these questions, illustrating each with a short, yet complete example.

Sometimes the author describes tricks that may seem too sophisticated. It turns out you can make a recursive call of your lambda, despite not directly supported, by defining a helper generic lambda inside your lambda. You can also derive your class from the implicit class defined by a lambda, or many of them, to have your operator() overloaded for different parameter types.

Your tolerance to such tricks depends on whether you are a proponent of “modern C++” and using all its features, or you prefer simple code, more like “C with classes”. Nonetheless, lambda expressions by themselves are a great language feature, useful in many cases. The book mentions some of these cases, as it ends with a chapter “Top Five Advantages of C++ Lambda Expressions”.

Overall, I like the book a lot. It describes this specific topic of lambda expressions in C++ comprehensively, but still in a concise and clear way. I recommend it to every C++ programmer. Because it is not very long, you shouldn’t hesitate with reading it like it was a new project you need to find time for. You should rather treat it like an additional, valuable learning resource, as if you read several blog articles or watched some YouTube videos about a topic of your interest.

You can buy the book on Leanpub. I also recommend visiting authors blog: C++ Stories (new blog converted from bfilipek.com). See also my review of his previous book: “C++17 in Detail”. There is a discount for “C++ Lambda Story” ($5.99 instead of $8.99) here, as well as for both books ($19.99 instead of $23.99) here - valid until the end of February 2021.

Comments | #books #c++ Share

# On Debug, Release, and Other Project Configurations

Sun
17
May 2020

Foreword: I was going to write a post about #pragma optimize in Visual Studio, which I learned recently, but later I decided to describe the whole topic more broadly. As a result, this blog post can be useful or inspiring to every programmer coding in C++ or even in other languages, although I give examples based on just C++ as used in Microsoft Visual Studio on Windows.

When we compile a program, we often need to choose one of possible "configurations". Visual Studio creates two of those for a new C++ project, called "Debug" and "Release". As their names imply, the first one is mostly intended to be used during development and debugging, while the other should be used to generate the final binary of the program to be distributed to the external users. But there is more to it. Each of these configurations actually sets multiple parameters of the project and you can change them. You can also define your custom configurations and have over 2 of them, which can be very useful, as you will see later.

First, let's think about the specific settings that are defined by a project configuration. They can be divided into two broad categories. First one is all the parameters that control the compiler and linker. The difference between Debug and Release is mostly regarding optimizations. Debug configuration is all about having the optimizations disabled (which allows full debugging functionality and also makes the compilation time short), while Release has the optimizations enabled (which obviously makes the program run faster). For example, Visual Studio sets these options in Release:

Visual Studio also inserts an additional code in Debug configuration to fill memory with some bit pattern that helps with debugging low-level memory access errors, which are plaguing C and C++ programmers. For example, seeing 0xCCCCCCCC in the debugger usually means uninitialized memory on the stack, 0xCDCDCDCD - allocated but uninitialized memory on the heap, and 0xFEEEFEEE - memory that was already freed and should no longer be used. In Release, memory under such incorrectly used pointers will just hold its previous data.

The second category of things controlled by project configurations are specific features inside the code. In case of C and C++ these are usually enabled and disabled using preprocessor macros, like #ifdef, #if. Such macros can not only be defined inside the code using #define, but also passed from the outside, among the parameters of the compiler, and so they can be set and changed depending on the project configuration.

The features controlled by such macros can be very diverse. Probably the most canonical example is the standard assert macro (or your custom equivalent), which we define to some error logging, instruction to break into the debugger, or even complete program termination in Debug config, and to an empty macro in Release. In case of C++ in Visual Studio, the macro defined in Debug is _DEBUG, in Release - NDEBUG, and depending on the latter, standard macro assert is doing "something" or is just ignored.

There are more possibilities. Depending on these standard pre-defined macros or your custom ones, you can cut out different functionalities from the code. One example is any instrumentation that lets you analyze and profile its execution (like calls to Tracy). You probably don't want it in the final client build. Same with detailed logging functionality, any hidden developer setting or cheat codes (in case of games). On the other hand, you may want to include in the final build something that's not needed during development, like checking user's license, some anti-piracy or anti-cheat protection, and generation of certificates needed for the program to work on non-developer machines.

As you can see, there are many options to consider. Sometimes it can make sense to have over 2 project configurations. Probably the most common case is a need for a "Profile" configuration that allows to measure the performance accurately - has all the compiler optimizations enabled, but still keeps the instrumentation needed for profiling in the code. Another idea would be to wrap the super low level, frequently called checks like (index < size()) inside vector::operator[] into some separate macro called HEAVY_ASSERT and have some configuration called "SuperDebug" that we know works very slowly, but has all those checks enabled. On the other end, remember that the "FinalFinal" configuration that you will use to generate the final binary for the users should be build and tested in your Continuous Integration during development, not only one week before the release date. Bugs that occur in only one configuration and not in the others are not uncommon!

Some bugs just don't happen in Debug, e.g. due to uninitialized memory containing consistent 0xCCCCCCCC instead of garbage data, or a race condition between threads not occurring because of a different time it takes to execute certain functions. In some projects, the Debug configuration works so slowly that it's not even possible to test the program on a real, large data set in this configuration. I consider it a bad coding practice and I think it shouldn't happen, but it happens quite often, especially when STL is used, where every reference to myVector[i] element in the unoptimized code is a function call with a range check instead of just pointer dereferecence. In any case, sometimes we need to investigate bugs occurring in Release configuration. Not all hope is lost then, because in Visual Studio the debugger still works, just not as reliably as in Debug. Because of optimizations made by the compiler, the instruction pointer (yellow arrow) may jump across the code inconsistently, and some variables may be impossible to preview.

Here comes the trick that inspired me to write this whole blog post. I recently learned that there is this custom Microsoft preprocessor macro:

#pragma optimize("", off)

that if you put at the beginning of a .cpp file or just before your function of interest, disables all the compiler optimizations from this point until the end of the file, making its debugging nice and smooth, while the rest of the program behaves as before. (See also its documentation.) A nice trick!

Comments | #c++ #visual studio Share

# Book review: C++17 in Detail

Sun
06
Oct 2019

Courtesy its author Bartłomiej Filipek, I was given an opportunity to read a new book "C++17 in Detail". Here is my review:

When I am about to read or decide whether to buy a book, I first look at two things. These are not the looks of the cover or the description on the back. Instead, I check the table of contents and the number of pages. It gives me a good overview of the topics covered and the estimation of chances they are sufficiently covered. "C++17 in Detail" with its 361 pages looks good as for a book describing what's new in C++17 standard, considering the additions to the standard are not as extensive as they were in C++11. The author is undoubtedly an expert in this field, as seen from entries on his Bartek's coding blog.

Author claims to describe all the significant additions to the language. However, this is not a dull, difficult to read documentation of the new language elements, like you can find on cppreference.com. Instead, the book describes each of them by giving some background and rationale, and showing real-life examples. It makes them easy to understand and to appreciate their usefulness. Each addition to the standard is also accompanied with a reference to the official documents by C++ standard committee and a table showing which versions of the most popular C++ compilers (GCC, Clang, Microsoft Visual C++) support it. Spoiler: They already support almost all of them :)

The book doesn't teach everything from scratch. That would be impossible in that number of pages, considering how big and complex C++ is. It assumes the reader already knows the language quite well, including some features from C++11 like unique_ptr or r-value reference + move semantics. It explains however few topics needed for the book in more details, like the concept of "reduce" and "scan" parallel algorithms, which C++17 adds to the standard library.

The contents of the book is grouped into 3 parts. Part 1 describes additions to the C++ language itself, including init statement for if and switch (e.g. if(int i = Calculate(); i > 0) ...), additions to templates like if constexpr, and attributes like [[nodiscard]], [[maybe_unused]]. Part 2 describes what has been added to its standard library, including std::optional, variant, any, string_view, filesystem. Finally, part 3 shows more extensive code examples that combine multiple new C++ features to refactor existing code into more clean and more efficient one. The author also mentions what parts of the language have been deprecated or removed in the new standard (like auto_ptr).

To summarize, I recommend this book to any C++ developer. It's a good one, and it lets you stay up-to-date with the language standard. You will learn all new features of the language and its standard library from it in a more pleasing way than by reading documents from the C++ committee. Even if you won't be able to use these new features in your current project because your old compiler not upgraded for many years or the coding standard imposed by your team lead doesn't let you, I think it's worth learning those things. Who knows if you won't be asked about them on your next job interview?

You can buy printed version of the book on Amazon.com and electronic version on Leanpub. Bartek, the author of the book, also agreed to give all of the readers of my blog a nice discount - 30%. It's valid till the end of October, and to use it just visit this link.

Comments | #C++ #books Share

# Weirdest rules from coding standards

Sat
28
Sep 2019

Earlier this month I asked on Twitter "what is the weirdest and the most stupid rule you had to follow because of the "Coding Standard"?" I've got some interesting responses. Thinking about it more, I concluded that coding standards are complex. Having one in your project is a good thing because it imposes a consistent style, which is a value by itself. But specific rules are of various types. Some carry universally recognized good practices, like "use std::unique_ptr, don't use std::auto_ptr". Some serve good code performance, like "pass large structures as const& parameters, not by value". Others are purely a matter of subjective preference of its authors, e.g. to use CamelCaseIdentifiers rather than snake_case_identifiers or spaces instead of tabs for indentation. Even the division between those categories is no clear though. For example, there is a research showing that Developers Who Use Spaces Make More Money Than Those Who Use Tabs.

But some rules are simply ridiculous and hard to explain in a rational way. Here are two examples from my experience:

Number 2: Lengthy ASCII-art comment required before every function. In that project we couldn't write an inline function even for the simplest getters, like:

class Element
{
private:
    int identifier;
public:
    int GetIdentifier() { return identifier; } // Illegal!

We had to only declare member functions in the header file, while definition had to contain a specific comment that repeats the name of the function (which is a nonsense and a bad practice by itself, as it introduces duplication and may go out of sync with actual code), and its description (even if the name is self-descriptive), description of all its parameters (even if their names are self-descriptive), return value etc. Example:

/*****************************************************************************\

Function:
    Element::GetIdentifier

Description:
    Returns identifier.

Input:
    None.

Output:
    Identifier of the current element.

\*****************************************************************************/ 
int Element::GetIdentifier()
{
    return identifier;
}

I like comments. I believe they are useful to explain and augment information carried by function and variable names, especially when they document valid usage of a library interface. For example, a comment may say that a pointer can be null and what that means, a uint may have special value UINT32_MAX and what happens then, or that a float is expressed in seconds. But the comment as shown above doesn't add any useful information. It's just more symbols to type, developer's time wasted, makes code bloated and less readable. It's not even in any standard format that could automatically generate documentation, like with Doxygen. It's just custom, arbitrary rule.

What was the reason behind this rule? A colleague once told me that many years ago the architect of this whole program hoped that they would develop a tool to parse all this code and those comments and generate documentation. Decades have passed, and it didn't happen, but developers still had to write those comments.

The effect was that everyone avoided adding new functions as much as possible or splitting their code into small functions. They were just adding more and more code to the existing ones, which could grow to hundreds of lines. That also caused one of the most obscure bugs I've met in my life (bug number 2).

Number 1: Don't use logical negation operator '!', like: if(!isEnabled). Always compare with false instead, like: if(isEnabled == false).

I understand a requirement to always compare pointers and numbers to some value like nullptr instead of treating them as booleans, although I don't like it. But banning one of the fundamental operators, also when used with bool variables, is hard to justify for me.

Why would anyone come up with something like this? Is it because a single '!' symbol is easy to omit when writing or reading and not so explicit as == false? Then, if the author of this rule suffers from bad sight or dyslexia and a single dash here and there doesn't make a difference to him, maybe he should also define functions Add(), Subtract(), and tell developers to use them instead of operators '+' and '-', because they too are so easy to confuse? Or maybe not... He should rather go do something other than programming :)

Comments | #software engineering #c++ Share

# How to design API of a library for Vulkan?

Fri
08
Feb 2019

In my previous blog post yesterday, I shared my thoughts on graphics APIs and libraries. Another problem that brought me to these thoughts is a question: How do you design an API for a library that implements a single algorithm, pass, or graphics effect, using Vulkan or DX12? It may seem trivial at first, like a task that just needs to be designed and implemented, but if you think about it more, it turns out to be a difficult issue. They are few software libraries like this in existence. I don’t mean here a complex library/framework/engine that “horizontally” wraps the entire graphics API and takes it to a higher level, like V-EZ, Nvidia Falcor, or Google Filament. I mean just a small, “vertical”, plug-in library doing one thing, e.g. implementing ambient occlusion effect, efficient texture mipmap down-sampling, rendering UI, or simulating particle physics on the GPU. Such library needs to interact efficiently with the rest of the user’s code to be part of a large program or game. Vulkan Memory Allocator is also not a good example of this, because it only manages memory, implements no render passes, involves no shaders, and it interacts with a command buffer only in its part related to memory defragmentation.

I met this problem at my work. Later I also discussed it in details with my colleague. There are multiple questions to consider:

This is a problem similar to what we have with any C++ libraries. There is no consensus about the implementation of various basic facilities, like strings, containers, asserts, mutexes etc., so every major framework or game engine implements its own. Even something so simple as min/max function is defined is multiple places. It is defined once in <algorithm> header, but some developers don’t use STL. <Windows.h> provides its own, but these are defined as macros, so they break any other, unless you #define NOMINMAX before the include… A typical C++ nightmare. Smaller libraries are better just configurable or define their own everything, like the Vulkan Memory Allocator having its own assert, vector (can be switched to standard STL one), and 3 versions of read-write mutex.

All these issues make it easier for developers to just write a paper, describe their algorithm, possibly share a piece of code, pseudo-code or a shader, rather than provide ready to use library. This is a very bad situation. I hope that over time patterns emerge of how the API of a library implementing a single pass or effect using Vulkan/DX12 should look like. Recently my colleague shared an idea with me that if there was some higher-level API that would implement all these interactions between various parts (like resource allocation, image barriers) and we all commonly agreed on using it, then authoring libraries and stitching them together on top of it would be way easier. That’s another argument for the need of such new, higher-level graphics API.

Comments | #gpu #vulkan #directx #libraries #graphics #c++ Share

# Two most obscure bugs in my life

Wed
14
Nov 2018

Fixing bugs is a significant part of software development, and a very emotional one - from frustration when you have no idea what is happening to euphoria when you find the cause and you know how to fix it. There are many different kinds of bugs and reasons why they are introduced to the code. (Conducting a deep investigation of how each bug happened might be an interesting idea - I will write a separate blog post about it someday...) But the most frustrating ones are probably these that occur only in some specific conditions, like only on one of many supported platforms or only in "Release" and not in "Debug" configuration. Below you will find description of the two most obscure bugs I've found and fixed in my life, for your education and amusement :) Both were in large, multiplatform, C++ codebases.

1. There was this bug reported causing incorrect program behavior, occurring on only one of many platforms where the program was built and used. It was probably Mac, but I can't remember exactly. It was classified as a regression - it used to work before and stopped working, caught by automated tests, after some specific code change. The strange thing was that the culprit submit to the code repository introduced only new comments and nothing else. How can change in a code comment introduce a new bug?!

It turned out that the author of this change wanted to draw a nice "ASCII art" in his comment, so he's put something like this:

// HERE STARTS AN IMPORTANT SECTION
//==================================================================\\
Function1();
Function2();
(...)

Have you noticed anything suspicious?...

A backslash '\' at the end of line in C/C++ means that the logical line is continued to next line. This feature is used mostly when writing complex preprocessor macros. But a code starting from two slashes '//' begins a comment that spans until the end of line. Now the question is: Does the single-line comment span to next line as well? In other words: Is the first function call commented out, or not?

I don't know and I don't really care that much about what would "language lawyers" read from the C++ specification and define as a proper behavior. The real situation was that compilers used on some platforms considered the single-line comment to span to the next line, thus commenting out call to Function1(), while others didn't. That caused the bug to occur on some platforms only.

The solution was obviously to change the comment not to contain backslash at the end of line, even at the expense of aesthetics and symmetry of this little piece of art :)

2. I was assigned a "stack overflow" bug occurring only in "Debug" and not in "Release" configuration of a Visual Studio project. At first, I was pretty sure it would be easy to find. After all, "stack overflow" usually means infinite recursion, right? The stack is the piece of memory where local function variables are allocated, along with return addresses from nested function calls. They tend not to be too big, while the stack is 1 MB by default, so there must be unreasonable call depth involved to hit that error.

It turned out not to be true. After few debugging sessions and reading the code involved, I understood that there was no infinite recursion there. It was a traversal of a tree structure, but the depth of its hierarchy was not large enough to be of a concern. It took me a while to realize that the stack was bloated to the extent that exceeded its capacity by one function. It was a very long function - you know, this kind of function that you can see in corporate environment which defies any good practices, but no one feels responsible to refactor. It must have grown over time with more and more code added gradually until it reached many hundreds of lines. It was just one big switch with lots of code in each case.

void Function(Option op)
{
  switch(op)
  {
  case OPTION_FIRST:
    // Lots of code, local variables, and stuff...
    break;
  case OPTION_SECOND:
    // Lots of code, local variables, and stuff...
    break;
  case OPTION_THIRD:
    // Lots of code, local variables, and stuff...
    break;
  ...
  }
}

What really caused the bug was the number and size of local variables used in this function. Each of the cases involved many variables, some big like fixed-size arrays or objects of some classes, defined by value on the stack. It was enough to call this function recursively just few times to exhaust the stack capacity.

Why "stack overflow" occurred in "Debug" configuration only and not in "Release"? Apparently Visual Studio compiler can lazily allocate or alias local variables used in different cases of a switch instruction, while "Debug" configuration has all the optimizations disabled and so it allocates all these variables with every function call.

The solution was just to refactor this long function with a switch - to place the code from each case in a separate, new function.

What are the most obscure bugs you've met in your coding practice? Let me know in the comments below.

Comments | #debugger #visual studio #c++ Share

# Efficient way of using std::vector

Sat
22
Sep 2018

Some people say that C++ STL is slow. I would rather say it's the way we use it. Sure, there are many potential sources of slowness when using STL. For example, std::list or std::map tends to allocate many small objects and dynamic allocation is a time-consuming operation. Making many copies of your objects like std::string is also costly - that's why I created str_view project. But std::vector is just a wrapper over a dynamically allocated array that also remembers its size and can reallocate when you add new elements. Without STL, you would need to implement the same functionality yourself.

When it comes to traversing elements of the vector (e.g. to sum the numerical values contained in it), there are many ways to do it. STL is notoriously known for working very slow in Debug project configuration, but as it turns out, this heavily depends on what method do you choose for using it.

Here is a small experiment that I've just made. In this code, I create a vector of 100,000,000 integers, then sum its elements using 5 different methods, calculating how much time does it take for each of them. Results (averaged over 5 iterations for each method) are as follows. Notice logarithmic scale on horizontal axis.

Here is the full source code of my testing program:

#include <cstdio>
#include <cstdint>
#include <vector>
#include <chrono>
#include <numeric>

typedef std::chrono::high_resolution_clock::time_point time_point;
typedef std::chrono::high_resolution_clock::duration duration;
inline time_point now() { return std::chrono::high_resolution_clock::now(); }
inline double durationToMilliseconds(duration d) { return std::chrono::duration<double, std::milli>(d).count(); }

int main()
{
    printf("Iteration,Method,Sum,Time (ms)\n");
    
    for(uint32_t iter = 0; iter < 5; ++iter)
    {
        std::vector<int> numbers(100000000ull);
        numbers[0] = 1; numbers[1] = 2; numbers.back() = 3;

        {
            time_point timeBeg = now();

            // Method 1: Use STL algorithm std::accumulate.
            int sum = std::accumulate(numbers.begin(), numbers.end(), 0);

            printf("%u,accumulate,%i,%g\n", iter, sum, durationToMilliseconds(now() - timeBeg));
        }

        {
            time_point timeBeg = now();

            // Method 2: Use the new C++11 range-based for loop.
            int sum = 0;
            for(auto value : numbers)
                sum += value;

            printf("%u,Range-based for loop,%i,%g\n", iter, sum, durationToMilliseconds(now() - timeBeg));
        }

        {
            time_point timeBeg = now();

            // Method 3: Use traditional loop, traverse vector using its iterator.
            int sum = 0;
            for(auto it = numbers.begin(); it != numbers.end(); ++it)
                sum += *it;

            printf("%u,Loop with iterator,%i,%g\n", iter, sum, durationToMilliseconds(now() - timeBeg));
        }

        {
            time_point timeBeg = now();

            // Method 4: Use traditional loop, traverse using index.
            int sum = 0;
            for(size_t i = 0; i < numbers.size(); ++i)
                sum += numbers[i];

            printf("%u,Loop with indexing,%i,%g\n", iter, sum, durationToMilliseconds(now() - timeBeg));
        }

        {
            time_point timeBeg = now();

            // Method 5: Get pointer to raw array and its size, then use a loop to traverse it.
            int sum = 0;
            int* dataPtr = numbers.data();
            size_t count = numbers.size();
            for(size_t i = 0; i < count; ++i)
                sum += dataPtr[i];

            printf("%u,Loop with pointer,%i,%g\n", iter, sum, durationToMilliseconds(now() - timeBeg));
        }
    }
}

As you can see, some methods are slower than the others in Debug configurations by more than 3 orders of magnitude! The difference is so big that if you write your program or game like this, it may not be possible to use its Debug version with any reasonably-sized input data. But if you look at disassembly, it should be no surprise. For example, method 4 calls vector methods size() and operator[] in every iteration of the loop. We know that in Debug configuration functions are not inilined and optimized, so these are real function calls:

On the other hand, method 5 that operates on raw pointer to the vector's underlying data is not that much slower in Debug configuration comparing to Release. Disassembly from Debug version:

So my conclusion is: Using std::vector to handle memory management and reallocation and using raw pointer to access its data is the best way to go.

My testing environment was:

CPU: Intel Core i7-6700K 4.00 GHz
RAM: DDR4, Dual-Channel, current memory clock 1066 MHz
OS: Windows 10 Version 1803 (OS Build 17134.285)
Compiler: Microsoft Visual Studio Community 2017 Version 15.4.8
Configuration options: x64 Debug/Release
Windows SDK Version 10.0.16299.0

Comments | #stl #c++ #optimization Share

Pages: 1 2 3 ... 18 >

[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2021