C ++ code optimization (C ++ 11) using a specific task as an example

I would like to tell you a little about the optimization of C / C ++ programs, because there is not enough information on the Internet. In the post there will be explanations of some optimizations on the example of the task that I was given to solve at the institute (the task is implemented in C ++ 11, the explanation is given only for 64 bit systems).
The first article was written to learn more about optimization, tips on which, I hope, you leave in the comments.

The condition of the task and purpose

The task is rather trivial:

In the city of M, N new microdistricts are being built, between which M main roads are planned. Each road has its own construction cost Pij. Last year, the municipality managed to build K of these M roads. Unfortunately, this year it was decided to reduce the financing of construction, and now from the planned but not built MK roads, it is necessary to leave such that at least one way exists from any neighborhood to any other, but the cost of their construction is minimal (guaranteed that such a set exists).
What is the minimum cost P of the completion of the road network construction under the new plan, and how many new roads on it are to be built?

and is solved by the Kruskal algorithm (building the minimum spanning tree). Initially, the contest was limited to 2 seconds for execution and 24 MB of memory. Not serious. I set myself the goal to optimize the program as much as possible and to keep within 100ms for the most difficult test, I want to note that you can only use the STL library and the fixed compiler settings (as this is in any way a problem from the contest). The task was not fully accomplished - I managed to fit 122 ms and 11mb of memory. For the most impatient I quote the program code:

Data alignment

You can learn more about what data alignment is, here , I will just explain with specific examples. Unfortunately, this is not explicitly used anywhere in my code, but let's look at this structure:

 struct A { char a; long int b; int c; }; 

This structure is 24 bytes (for this we will display the result of sizeof (A)).
Now consider the following structure:

 struct B { char a; int c; long int b; }; 

It takes only 16 bytes. Why is that? The fact is that on a 64-bit OS, the memory is read in chunks of 8 bytes and to speed up processing by the processor, the data is aligned, specifically for class A, the structure of the memory location looks like this:
(1 byte for a + 7 empty bytes) + (8 byte for b) + (4 bytes for c + 4 empty bytes) = 24 bytes.
Not very economical, right? For class B, the memory occupied is as follows:
(1 byte for a + 3 empty bytes + 4 bytes for c) + (8 bytes for b) = 16 bytes.
It is worth paying attention to such a trifle, because moving data “back and forth” costs time, and the less data moves, the faster your program accelerates, and then, swapping a couple of lines is not the most difficult optimization.

Initialization lists

Why a constructor should look like this:

 UF_element(T id) : size(1) , parent(id) { } 

Not so:

 UF_element(T id) { size = 1; parent = id; } 

You can read here . When using initialization lists, the constructor is called with the passed values, in contrast to the second case, when the default constructor is called for the class fields and the assignment is made in the body of the class constructor.
')

Register specifier

A bit of theory:

register is an automatic memory class specifier. Applies to objects located in local memory by default. It is a “request” (optional for execution) to the compiler about placing the values ​​of objects declared with the register specifier in one of the available registers, and not in the local memory.

In my code I used the following structure:

 for (register T i = 1; i < n + 1; ++i) { idElements[i] = UF_element<T>(i); } 

It is necessary to use this specifier correctly.
If you need to score an array with numbers from 1 to n (almost as I have in the example above), then using the specifier will increase in speed, if the loop body is not so trivial, then most likely register will not only not change performance, but may reduce it, allocating a variable case.

Work with memory

Very short and well written here . In general, when you begin to understand how the program uses memory and, in particular, you are looking for leaks, some rules are developed.

For myself, I realized one thing: until the programmer is able to tell straight away when and where the memory allocated using the new operator is freed and how convenient it is for the memory manager to access the free memory after calling delete, it should be beat with rags for use new / delete. Therefore, in order not to be beaten, I got rid of the use of these operators architecturally:

  UnionFind(T n) : Elements(n + 1) //        { for (register T i = 1; i < n + 1; ++i) { Elements[i] = UF_element<T>(i); //    } } 

Input and output data

Guided by this article , input was greatly accelerated. Since in this task only 2 numbers are output, the use of putchar (putchar_unlocked) does not bring a large profit, but for those who do not believe, until they check, I give below the output implementation using putchar_unlocked.