-2

谁能帮我解决这个问题？

我正在努力提高效率，这就是我尝试并行计算的原因。经过几次测试，结果告诉我没有什么比在 1 个线程上计算更快的了。在这两种情况下（1 个线程和 4 个线程），它仅占处理器负载的 25%。有人知道为什么会这样吗？我能做些什么来实现 100% 的效率（甚至 90% 比 25% 更好）？

下面你可以看到一个示例代码：


ToolsThread = class(TThread)
public
 procedure Execute(); override;
 procedure QuickSortT(var dict: TArray<AnsiString>; iLo, iHi: Integer);
 Procedure QSortT(var dict: TArray<AnsiString>);
 constructor Create();
var
 tab : TArray<AnsiString>;
 tmp1: Longint;
end;

procedure ToolsThread.QuickSortT(var dict: TArray<AnsiString>; iLo, iHi: Integer);
var
 Lo, Hi: Longint;
 Pivot: Pointer;
 T: Pointer;
begin
  Lo := iLo;
  Hi := iHi;
  Pivot := pointer(dict[(Lo + Hi) shr 1]); // shr 1 is slightly faster than div 2;
  repeat
    while dict[Lo] < AnsiString(Pivot) do Inc(Lo);
    while dict[Hi] > AnsiString(Pivot) do Dec(Hi);
    if Lo <= Hi then
    begin
      T := pointer(dict[Lo]);
      pointer(dict[Lo]) := pointer(dict[Hi]);
      pointer(dict[Hi]) := T;
      Inc(Lo) ;
      Dec(Hi) ;
    end;
  until Lo > Hi;
  if Hi > iLo then QuickSort(dict, iLo, Hi) ;
  if Lo < iHi then QuickSort(dict, Lo, iHi) ;
end;

Procedure ToolsThread.QSortT(var dict: TArray<AnsiString>);
begin
 QuickSort(dict, 0, Length(dict)-1);
end;

procedure ToolsThread.Execute();
var
 tmp1, tmp2 : Longint;
 dict: TArray<AnsiString>;
begin
 SetLength(dict, 10000000);
 for tmp1:= 0 to 10000000-1 do
  dict[tmp1] := IntToStr(Random(high(integer)));
 QSortT(dict);
end;

Procedure Main;
var
 Th1, Th2, Th3, Th4: ToolsThread;
begin

 Th1 := ToolsThread.Create();
 Th2 := ToolsThread.Create();
 Th3 := ToolsThread.Create();
 Th4 := ToolsThread.Create();

 debug('Start THR');
 Th1.Start;
 Th2.Start;
 Th3.Start;
 Th4.Start;
 th1.WaitFor;
 th2.WaitFor;
 th3.WaitFor;
 th4.WaitFor;
 debug('THR Done');
end;

根据建议更正。CPU 负载仍为 25%（每个线程 5-8%）

解决了！多处理中的一些 Delphi 内存管理存在一个普遍问题。这不是 fastMM4 问题，目前只能作为解决方法解决。

4

2 回答 2

2

首先，string到处使用。不要乱用AnsiStringandstring类型 - 除非你使用的是 Delphi 2009 之前的版本......而且你使用的是AnsiString，然后IntToStr()将返回一个平原，然后将其重新分配并在放入数组时string转换为......AnsiString

从我在您的代码中可以看到，我的猜测是大部分时间都花在了调用IntToStr()上，然后将返回的string转换为AnsiString，这将涉及堆管理器，这将在此过程中大部分被序列化。当然，这是一个快速的猜测，我的“大脑分析器”（tm）曾经是错误的。

快速排序算法是 O(n*log(n))，它比IntToStr()来自多个线程的O(n) 调用要快。

尝试只 QSortT(dict)输入Execute方法。它应该几乎是线性的。

另一个猜测是以下行不是最优的。它们将在交换字符串时涉及引用计数（分配字符串实际上是对隐藏的_UStrAsg()低函数的调用），由于引用计数器上的“锁定”，这会占用大量 CPU 资源。如果多个线程在“锁定”期间共享一些 CPU 缓存（在您的情况下可能会发生，因为IntToStr分配是并行完成的），那么这个“锁定”会产生一些缓存争用，这可能需要一些明显的时间，即使在较新的 CPU 上.

以下可能更快（待验证）：

   var T: pointer;
   ...
    if Lo <= Hi then
    begin
      T := pointer(dict[Lo]);
      pointer(dict[Lo]) := pointer(dict[Hi]);
      pointer(dict[Hi]) := T;
      Inc(Lo) ;
      Dec(Hi) ;
    end;

您也可以pivot用 a替换，pointer但它有点棘手：

var pivot: pointer;
...
  repeat
    Pivot := pointer(dict[(Lo + Hi) shr 1]); // within the 2nd repeat..until
    while dict[Lo] < string(Pivot) do Inc(Lo) ;
    while dict[Hi] > string(Pivot) do Dec(Hi) ;

在这种情况下，想法总是使用真实的分析。至少，在您要测量的代码中使用精密计时器/手表，并查看 CPU 进入的位置。

编辑：我已经使用我的建议编写了一些代码 - 请参阅https://gist.github.com/synopse/02eb142d35cb44126aed9fd3200a76d1

输出在 2 核 CPU 上：

Fill done in 3.25s
Sort done in 24.11s
  • 在填充/创建期间使用一个核心 - 正如预期的那样
  • 在排序/执行期间使用了 100% 的核心 - 正如预期的那样
于 2020-03-02T10:16:58.420 回答
0

您的行将Pivot := dict[(Lo + Hi) div 2]a 的一部分分配给AnsiStringtype 的变量String。你一遍又一遍地做。我真的不知道幕后发生了什么，但是在将所有类型更改为StringorAnsiString之后，代码将运行 100% CPU 负载，而不仅仅是使用一个内核。

您必须更加注意编译器警告

于 2020-03-02T10:18:50.867 回答