Linux C++ new 运算符非常慢

Question

我有双启动 PC，Debian 8 64 位和 Windows 10 64 位。我在 C++ 中键入了两个代码，使用 DSW 算法和 deap 堆实现 BST 树。在这两个代码中，都有使用 new 运算符添加 100000 个数据（结构）节点的功能。在 Windows 上，代码是使用最新的 TDM GCC 编译器 (Dev C++) 编译的，它们运行时间不超过 1 秒，但在 Linux 上，它们是使用默认的 GCC 编译器编译的他们运行时间超过 20 秒。为什么差异如此之大？是编译器的错还是 OS 的错？我注意到添加功能太慢了。我读到 new operator is "thread safe" on Linux 这可能会减慢它的速度，但我不知道这实际上是这个原因。在另一台装有 Win7 的电脑上运行时间也短于 1 秒。我相信 Linux 程序应该运行比 Windows 程序快。那怎么了？可以在 Linux?

上加快运行时间

我的BST+DSW代码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;
}

你需要一个inlab04.txt到运行它，它包含数字：255 100000

Answer 1

鉴于 98% 的时间花在该函数上，我重写了您的 "get a number" 函数：

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

现在，在我的机器上，根据程序自己的测量，使用 clang++（大约 4 周前的 3.7 版）需要 0.0839 秒，根据 Linux 的 time 命令需要 0.089 秒.

如果我让X2再大一个0，程序运行需要12s，93%的时间都在Add_Node，int_malloc最后变成0.17总执行时间的百分比，以及 operator new 0.03%。

我相当确定我们可以最终说 new 不是这里的问题...（即使在我改进了随机函数之后，获取随机数功能也占了大约 2%总执行时间的一部分——换句话说，计算一个随机数大约需要 operator new 时间的 10 倍）。

Linux C++ new 运算符非常慢

Linux C++ new operator incredibly slow

c++

linux

performance

operator-keyword

allocation