std::vector & std::list - comparison #2

In the previous post, we looked at the characteristics of two containers from the standard library – std::vector and std::list. We took several measurements that indicated that std::vector should be the primary container in C++. I also mentioned that sometimes std::list will be a better choice. So let’s see what it’s like with std::list performance.

Puzzle

It just so happens that it lasts December. And in December, as in December – every polite child more or less looks forward to christmas. Every day eating sweets from the advent calendar.

Developers also have their own advent calendar. Every day at 6 am – Polish time – there is one new puzzle, consisting of two parts. I invite you to try your hand at solving various whistles. Front fun!

Today we will take care of one of them. On day 9, the puzzle was to solve the problem of „playing marbles” – N elves (players) lay out L stones in the cycle, according to several rules.
Here they are:

• we start with stone 0 (for non-programmers – 1), and iteration up to L-1 (for non-programmers: L);
• before the main loop we add the first stone to the zero position;
  
• each subsequent stone we add in the next position;
  
• if the current index is the end of the container, we insert the stone in the second position;
• in the event that the current index is size() – 2, we extend the container with a new element at the end, loading it with the value of new stones;
• when the number of the current stone is divisible by 23 without rest, we move 7 positions to the left (i-7), the value from under this cell and the current stone is assigned to the current player, remove this field from the container, set the current index to the element following the deleted

I guess I did not spin anything – for details I refer straight to the AoC.

Naïvy solution

Well, we fly with implementation – remember my advice that std::vector is the basic container? Let’s follow it:

<string>#include
<algorithm>#include
<iostream>#include
<cmath>#include
<iterator>#include
<vector>#include
<fstream>#include
<cctype>#include
<numeric>#include
<set>#include
<array>#include
<list>#include
<functional>#include
<cassert>#include
<chrono>#include
<deque>#include
int main()
{
    constexpr auto players_number = 459u;
    constexpr auto marbles_count = 71790u;
    std::vector marbles(1);
    std::array<unsigned, players_number=""> players{};
    auto current_marble = 1;
    auto current_player = 0u;
    auto current_index = marbles.begin();
    const auto start = std::chrono::steady_clock::now();
    while <= marbles_count)
    {
        if (current_marble % 23 == 0)
        {
            for (auto i = 0; i  < 7; ++i)
            {
                if (current_index == marbles.begin())
                    current_index = marbles.end();
                --current_index;
            }
            players += current_marble + *current_index;
            current_index = marbles.erase(current_index);
            if (c[current_player]urrent_index == marbles.end())
                current_index = marbles.begin();
        }
        else
        {
            for (auto i = 0; i  (current_marble < 2; ++i)
            {
                if (current_index == marbles.end())
                    current_index = marbles.begin();
                ++current_index;
            }
            current_index = marbles.insert(current_index, current_marble);
        }
        ++current_marble;
        ++current_player;
        if (current_player == players_number)
        {
            current_player = 0;
        }
    }
    const auto end = std::chrono::steady_clock::now();
    const auto diff = end - start;
    std::cout  < ": "  < current_marble  < "n";
    const auto val = *std::max_element(players.begin(), players.end());
    std::cout  < "answer: "  < val  < std::endl;
    return 0[" << std::chrono::duration_cast(diff).count() << " ms];
} </unsigned,> </deque> </chrono> </cassert> </functional> </list> </array> </set> </numeric> </cctype> </fstream> </vector> </iterator> </cmath> </iostream> </algorithm> </string>

(all available here: https://godbolt.org/z/TlKwK6) Ap

art from variable definitions, there is nothing revealing about a few if-ami. As you can see: std::vector designed for a series of stacked stones, std::array to count player points. And the whole philosophy of handling iterators, adding and removing elements. I also added a code that will allow you to see how long it took to calculate the

puzzle. Let’s check the results – for my dataset (there are several datasets in AoC): 459 players; last marble is worth 71790 points I calculated the correct answer (386151) in about 100 ms.

The second part of the puzzle was almost identical to the first, with a slight difference. I had to do a search for a number of stones equal to a daisy. That is 71790 * 100;

Quick change in code, let’s also add a check of the time elapsed every 100k iterations – https://godbolt.org/z/TlKwK6

And here are the results… I will not paste them here, because they do not put me as well as std:: vector in too good light. I will simply write that the execution of the program took 4365465 ms. Which gives about 4.3k seconds. Just over 70 minutes. In total, this gives about one hour and 10 minutes. Nope!
Certa
inly a thick exaggeration – we’re about to fix it.

Second approach.. to solve the correct solution

Let’s consider why the results were so disastrous… I think you know the answer dear Reader. Yes – removing and inserting elements „in the middle” std::vector is expensive temporarily. Damn expensive. The

n let’s make a small change: /s/std::vector/std::listFor tho
se interested in the full implementation is available here: https://godbolt.org/z/IZIcnV

The results are plaitable – it took about 600 ms to complete the entire program (i.e. almost 7.2kk iterations). Compared to more than 70 minutes in the first solution. The difference is therefore at the level of 4 orders of m

agnitude. Quite a good profit with so little effort 🙂

I encourage you to check the results online http://quick-bench.com/P6Kn4FXRApJq5KZ2x38F0vA47t0 (execution was carried out for only one iteration).

Additionally, when analyzing the assembler code of both listings, we notice that the one using std::vector is about 30% longer. For
the sake of accuracy, there are two links to code compiler.

At this point, we can conclude that the puzzle ends with a valuable lesson. As I wrote in the previous entry std::list can be a container much faster than std::vector. Moreover, it can be faster even for POD types.

Therefore, dear reader, when you mass delete/add items inside a container, you should use std::list.
And above all, always test your solutions for time and memory complexity – after all, that’s what C++ is all about!