Linux C++ new operator incredibly slow

Question

I have dual boot PC, Debian 8 64-bit and Windows 10 64-bit. I've typed two codes in C++ implementing BST tree with DSW algorithm and deap heap. In both codes there is function adding 100000 nodes of data (structures) using new operator. On Windows the codes are compiled using latest TDM GCC compiler (Dev C++) and they runtimes aren't longer than 1 sec, but on Linux they're compiled using default GCC compiler and they runtimes are longer than 20 sec. Why the difference is so huge? It is fault of the compilator or the OS? I've noticed that adding functions are so slow. I've read that new operator is "thread safe" on Linux which may be slowing it so much, but I don't know it is actually this reason. On another PC with Win7 runtimes were also shorter than 1 sec. I believe Linux programs should run faster than Windows ones. So what's wrong? It is possible to speed up runtime on Linux?

My BST+DSW code https://ideone.com/tFvxbt

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <stdio.h>

using namespace std;

struct Node
{
int Key;
Node* Left_Child;
Node* Right_Child;
Node* Father;
};

void Initialization(Node* &Ref_Root)
{
Ref_Root = 0;
}

Node* Find_Node(Node* &Ref_Root, int Key)
{
if (!Ref_Root) return 0;
Node* Temp = Ref_Root;
while (true)
{
if (Temp->Key == Key) return Temp;
if (Key < Temp->Key)
{
if (!Temp->Left_Child) return 0;
Temp = Temp->Left_Child;
continue;
}
if (Key > Temp->Key)
{
if (!Temp->Right_Child) return 0;
Temp = Temp->Right_Child;
continue;
}
}
}

int Ten_To_One_Million_Ten(void)
{
int Number = 0;
while (Number > 1000010 || Number < 10)
{
Number = (rand() << 5) + rand()%32;
}
return Number;
}

bool Add_Node(Node* &Ref_Root, int Key)
{
if (!Ref_Root)
{
Ref_Root = new Node;
Ref_Root->Left_Child = 0;
Ref_Root->Right_Child = 0;
Ref_Root->Father = 0;
Ref_Root->Key = Key;
return true;
}
if (Find_Node(Ref_Root, Key) != 0) return false;
Node* Temp;
Temp = Ref_Root;
while (true)
{
if (Key < Temp->Key)
{
if (Temp->Left_Child)
{
Temp = Temp->Left_Child;
continue;
}
if (!Temp->Left_Child)
{
Temp->Left_Child = new Node;
Temp->Left_Child->Left_Child = 0;
Temp->Left_Child->Right_Child = 0;
Temp->Left_Child->Father = Temp;
Temp->Left_Child->Key = Key;
return true;
}
}
if (Key > Temp->Key)
{
if (Temp->Right_Child)
{
Temp = Temp->Right_Child;
continue;
}
if (!Temp->Right_Child)
{
Temp->Right_Child = new Node;
Temp->Right_Child->Left_Child = 0;
Temp->Right_Child->Right_Child = 0;
Temp->Right_Child->Father = Temp;
Temp->Right_Child->Key = Key;
return true;
}
}
}
}

void Create_Tree(Node* &Ref_Root, int X)
{
int i = X;
while (i > 0)
{
if (Add_Node(Ref_Root, Ten_To_One_Million_Ten())) --i;
}
}

bool Delete_Node(Node* &Ref_Root, int Key)
{
if (!Ref_Root) return false;
Node* Temp;
Node* Father;
if (Ref_Root->Key == Key)
{
if (!Ref_Root->Left_Child && !Ref_Root->Right_Child)
{
delete Ref_Root;
Ref_Root = 0;
return true;
}
if (Ref_Root->Left_Child && !Ref_Root->Right_Child)
{
Temp = Ref_Root;
Ref_Root = Ref_Root->Left_Child;
delete Temp;
return true;
}
if (!Ref_Root->Left_Child && Ref_Root->Right_Child)
{
Temp = Ref_Root;
Ref_Root = Ref_Root->Right_Child;
delete Temp;
return true;
}
if (Ref_Root->Left_Child && Ref_Root->Right_Child)
{
if (!Ref_Root->Left_Child->Right_Child)
{
Temp = Ref_Root->Left_Child;
Temp->Right_Child = Ref_Root->Right_Child;
delete Ref_Root;
Ref_Root = Temp;
return true;
}
Temp = Ref_Root->Left_Child;
Father = Ref_Root;
while (Temp->Right_Child)
{
Father = Temp;
Temp = Temp->Right_Child;
}
if (!Temp->Left_Child)
{
Father->Right_Child = 0;
Temp->Left_Child = Ref_Root->Left_Child;
Temp->Right_Child = Ref_Root->Right_Child;
delete Ref_Root;
Ref_Root = Temp;
return true;
}
if (Temp->Left_Child)
{
Father->Right_Child = Temp->Left_Child;
Temp->Left_Child = Ref_Root->Left_Child;
Temp->Right_Child = Ref_Root->Right_Child;
delete Ref_Root;
Ref_Root = Temp;
return true;
}
}
}
Temp = Find_Node(Ref_Root, Key);
if (Temp == 0) return false;
Father = Temp->Father;
if (!Temp->Left_Child && !Temp->Right_Child)
{
if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = 0;
if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = 0;
delete Temp;
return true;
}
if (Temp->Left_Child && !Temp->Right_Child)
{
if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp->Left_Child;
if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp->Left_Child;
delete Temp;
return true;
}
if (!Temp->Left_Child && Temp->Right_Child)
{
if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp->Right_Child;
if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp->Right_Child;
delete Temp;
return true;
}
if (Temp->Left_Child && Temp->Right_Child)
{
if (!Temp->Left_Child->Right_Child)
{
Temp->Left_Child->Right_Child = Temp->Right_Child;
if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp->Left_Child;
if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp->Left_Child;
delete Temp;
return true;
}
if (Temp->Left_Child->Right_Child)
{
Node* Temp2 = Temp->Left_Child;
Node* Temp3 = Temp->Left_Child->Right_Child;
while (Temp3->Right_Child)
{
Temp2 = Temp3;
Temp3 = Temp3->Right_Child;
}
if (!Temp3->Left_Child)
{
if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp3;
if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp3;
Temp2->Right_Child = 0;
Temp3->Right_Child = Temp->Right_Child;
Temp3->Left_Child = Temp->Left_Child;
delete Temp;
return true;
}
if (Temp3->Left_Child)
{
if (Father->Left_Child && Father->Left_Child->Key == Temp->Key) Father->Left_Child = Temp3;
if (Father->Right_Child && Father->Right_Child->Key == Temp->Key) Father->Right_Child = Temp3;
Temp2->Right_Child = Temp3->Left_Child;
Temp3->Right_Child = Temp->Right_Child;
Temp3->Left_Child = Temp->Left_Child;
delete Temp;
return true;
}
}
}
}

void Rotate_Left(Node* &Ref_Root, Node* Ref_Node)
{
if (!Ref_Root) return;
if (!Ref_Node->Right_Child) return;
Node* Right_Child = Ref_Node->Right_Child;
if (!Ref_Node->Father)
{
Ref_Node->Right_Child = Right_Child->Left_Child; //
if (Right_Child->Left_Child) Right_Child->Left_Child->Father = Ref_Node; //
Right_Child->Left_Child = Ref_Node; //
Right_Child->Father = 0;
Ref_Node->Father = Right_Child; //
Ref_Root = Right_Child;
}
else
{
Node* Father = Ref_Node->Father;
bool Is_Left_Child = true;
if (Father->Right_Child && Father->Right_Child->Key == Ref_Node->Key) Is_Left_Child = false;
Ref_Node->Right_Child = Right_Child->Left_Child; //
if (Right_Child->Left_Child) Right_Child->Left_Child->Father = Ref_Node; //
Right_Child->Left_Child = Ref_Node; //
Ref_Node->Father = Right_Child; //
Right_Child->Father = Father;
if (Is_Left_Child == true) Father->Left_Child = Right_Child;
else Father->Right_Child = Right_Child;
}
}

void Rotate_Right(Node* &Ref_Root, Node* Ref_Node)
{
if (!Ref_Root) return;
if (!Ref_Node->Left_Child) return;
Node* Left_Child = Ref_Node->Left_Child;
if (!Ref_Node->Father)
{
Ref_Node->Left_Child = Left_Child->Right_Child;
if (Left_Child->Right_Child) Left_Child->Right_Child->Father = Ref_Node;
Left_Child->Right_Child = Ref_Node;
Left_Child->Father = 0;
Ref_Node->Father = Left_Child;
Ref_Root = Left_Child;
}
else
{
Node* Father = Ref_Node->Father;
bool Is_Left_Child = true;
if (Father->Right_Child && Father->Right_Child->Key == Ref_Node->Key) Is_Left_Child = false;
Ref_Node->Left_Child = Left_Child->Right_Child;
if (Left_Child->Right_Child) Left_Child->Right_Child->Father = Ref_Node;
Left_Child->Right_Child = Ref_Node;
Ref_Node->Father = Left_Child;
Left_Child->Father = Father;
if (Is_Left_Child == true) Father->Left_Child = Left_Child;
else Father->Right_Child = Left_Child;
}
}

int Log2(int N)
{
int T = 1;
while (T < N) T <<= 1;
if (T > N) T >>= 1;
return T;
}

void DSW(Node* &Ref_Root)
{
if (!Ref_Root) return;
int Nodes_Counter = 1;
while (Ref_Root->Left_Child) Rotate_Right(Ref_Root, Ref_Root);
Node* Ref_Node = Ref_Root->Right_Child;
if (!Ref_Node) return;
while (Ref_Node)
{
if (Ref_Node->Left_Child)
{
Rotate_Right(Ref_Root, Ref_Node);
Ref_Node = Ref_Node->Father;
}
else
{
++Nodes_Counter;
Ref_Node = Ref_Node->Right_Child;
}
}
int N = Nodes_Counter + 1 - Log2(Nodes_Counter + 1);
Ref_Node = Ref_Root;
for (int i = 0; i < N; ++i)
{
Rotate_Left(Ref_Root,Ref_Node);
Ref_Node = Ref_Node->Father->Right_Child;
}
int X = Nodes_Counter - N;
while(X > 1)
{
X >>= 1;
Ref_Node = Ref_Root;
for(int i = 0; i < X; ++i)
{
Rotate_Left(Ref_Root,Ref_Node);
Ref_Node = Ref_Node->Father->Right_Child;
}
}
}

void Print_In_Order(Node* &Ref_Root)
{
if (!Ref_Root) return;
if (Ref_Root->Left_Child) Print_In_Order(Ref_Root->Left_Child);
cout << Ref_Root->Key << endl;
if (Ref_Root->Right_Child) Print_In_Order(Ref_Root->Right_Child);
}

int Calculate_Height(Node* &Ref_Node)
{
int Left_Height = 0;
int Right_Height = 0;
if (Ref_Node->Left_Child) Left_Height = Calculate_Height(Ref_Node->Left_Child);
if (Ref_Node->Right_Child) Right_Height = Calculate_Height(Ref_Node->Right_Child);
if (Left_Height > Right_Height)
{
++Left_Height;
return Left_Height;
}
if (Left_Height <= Right_Height)
{
++Right_Height;
return Right_Height;
}
}

int main()
{
int X1, X2;

FILE* fp = fopen("inlab04.txt", "r");
if (fp == NULL) return -1;
fscanf (fp, "%d %d", &X1, &X2);
fclose(fp);

clock_t begin, end;
double time_spent;
begin = clock();
srand(time(NULL));

Node* Root;
Initialization(Root);
Create_Tree(Root, X1);
cout << "Wysokosc drzewa dla X1 przed wykonaniem DSW: " << Calculate_Height(Root) << endl;
DSW(Root);
cout << "Wysokosc drzewa dla X1 po wykonaniu DSW: " << Calculate_Height(Root) << endl;
while (Root) Delete_Node(Root, Root->Key);
Create_Tree(Root, X2);
cout << "Wysokosc drzewa dla X2 przed wykonaniem DSW: " << Calculate_Height(Root) << endl;
DSW(Root);
cout << "Wysokosc drzewa dla X2 po wykonaniu DSW: " << Calculate_Height(Root) << endl;

end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Program wykonal sie w: " << time_spent << " sekund" << endl;
return 0;
}  

You need a inlab04.txt to run it, it contains numbers: 255 100000

Answer 1

Given that 98% of the time is spent in that function, I rewrote your "get a number" function:

int Ten_To_One_Million_Ten(void)
{
    unsigned Number = (((unsigned)rand() << 5) + (unsigned)rand()%32) % 1000000 + 10;
    assert(Number >= 10 && Number <= 1000010);
    return Number;
}

Now, on my machine, using clang++ (Version 3.7 from about 4 weeks ago) takes 0.0839 seconds according to the program's own measurement, and 0.089s according to Linux's time command.

If I make X2 larger by another zero, it takes 12s to run the program, and 93% of the time is in Add_Node, and int_malloc ends up being 0.17% of the total execution time, and operator new 0.03%.

I'm fairly sure we can conclusively say that new is not the problem here... (Even after my improved random function, the get-a-random-number functionality accounts for about 2% of the total execution time - in other words, the calculating of a random number takes about 10x the time of operator new).