std::pair<int, int> vs struct with two int's

c++ performance std-pair
Etan picture Etan · Oct 22, 2009 · Viewed 14k times · Source

In an ACM example, I had to build a big table for dynamic programming. I had to store two integers in each cell, so I decided to go for a std::pair<int, int>. However, allocating a huge array of them took 1.5 seconds:

std::pair<int, int> table[1001][1001];

Afterwards, I have changed this code to

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

and the allocation took 0 seconds.

What explains this huge difference in time?

Answer

sharptooth picture sharptooth · Oct 22, 2009

std::pair<int, int>::pair() constructor initializes the fields with default values (zero in case of int) and your struct Cell doesn't (since you only have an auto-generated default constructor that does nothing).

Initializing requires writing to each field which requires a whole lot of memory accesses that are relatively time consuming. With struct Cell nothing is done instead and doing nothing is a bit faster.

Related questions

Why is processing a sorted array faster than processing an unsorted array?

Here is a piece of C++ code that shows some very peculiar behavior. For some strange reason, sorting the data miraculously makes the code almost six times faster: #include <algorithm> #include <ctime> #include <iostream> …

Read More
C++ performance vs. Java/C#

My understanding is that C/C++ produces native code to run on a particular machine architecture. Conversely, languages like Java and C# run on top of a virtual machine which abstracts away the native architecture. Logically it would seem impossible …

Read More
Static linking vs dynamic linking

Are there any compelling performance reasons to choose static linking over dynamic linking or vice versa in certain situations? I've heard or read the following, but I don't know enough on the subject to vouch for its veracity. 1) The difference …

Read More