在我的程序中,我处理了数百万个具有特殊字符的字符串,例如 "|" 来分隔每个字符串中的标记。我有一个函数来返回第n个标记,这就是它:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
var
I, P, P2: integer;
begin
P2 := Pos(Delim, Line);
if TokenNum = 1 then begin
if P2 = 0 then
Result := Line
else
Result := copy(Line, 1, P2-1);
end
else begin
P := 0; { To prevent warnings }
for I := 2 to TokenNum do begin
P := P2;
if P = 0 then break;
P2 := PosEx(Delim, Line, P+1);
end;
if P = 0 then
Result := ''
else if P2 = 0 then
Result := copy(Line, P+1, MaxInt)
else
Result := copy(Line, P+1, P2-P-1);
end;
end; { GetTok }
我开发了这个函数,当时我使用的是Delphi 4。它调用了非常高效的PosEx例程,它最初是由Fastcode开发的,现在包含在Delphi的StrUtils库中。
我最近升级到了Delphi 2009,并且我的字符串都是Unicode。这个GetTok函数仍然可以工作,并且仍然很好地工作。
我已经浏览了Delphi 2009中的新库,其中有许多新的函数和增强功能。
但我在任何新的Delphi库中都没有看到我需要的GetToken函数,在各种fastcode项目中也找不到任何东西,除了Zarko Gajic的:Delphi Split / Tokenizer Functions,但它没有我已经拥有的那么优化。
即使改进10%,在我的程序中也会明显。我知道另一种方法是使用StringLists并始终保持标记分开,但这在内存方面有很大的开销,并且我不确定如果我做了所有的转换工作,它是否会更快。
哎呀。所以在这篇漫长的文章之后,我的问题真的是:
您是否知道任何非常快速实现GetToken例程的方法?汇编优化版本将是理想的吗?
如果没有,您能否看到上面的代码中有任何优化可能会改善情况?
后续:Barry Kelly提到了我一年前关于优化文件中行的解析的问题。那时我甚至没想到我的GetTok例程,因为它并未用于读取或解析。直到我看到了我的GetTok例程的开销,才引发了这个问题。在Carl Smotricz和Barry的回答之前,我从未想过将两者联系起来。这太显而易见了,但我没有意识到。感谢指出这一点。
是的,我的Delim是一个单字符,所以显然我可以做出一些重大的优化。我在GetTok例程中使用Pos和PosEx(上面),这使我对使用字符搜索忽视了一些更快的方法,例如使用以下代码片段:
while (cp^ > #0) and (cp^ <= Delim) do
Inc(cp);
我将逐一查看每个人的答案,尝试不同的建议并进行比较。然后我会发布结果。
困惑:好吧,现在我真的很困惑。
我采用了卡尔和巴里的建议选择使用PChars,这是我的实现:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://dev59.com/s-o6XIcBkEYKwwoYTzEw }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
在实际情况下,我认为这已经是最好的了。
因此,我将两个例程都用于任务,并使用AQTime查看发生了什么。我的运行包括1,108,514次对GetTok的调用。
AQTime计时原始例程为0.40秒。一百万次Pos的调用花费了0.10秒。五十万个TokenNum = 1的副本花费了0.10秒。六十万个PosEx调用只花费了0.03秒。
然后,我使用AQTime为相同的运行和完全相同的调用计时了我的新例程。AQTime报告说,我的新“快速”例程需要3.65秒,即比原来慢9倍。根据AQTime的说法,罪魁祸首是第一个循环:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
这个 while 循环被执行了 1800 万次,耗时 2.66 秒。而 inc 行则被执行了 1600 万次,用时为 0.47 秒。
我原以为自己知道这里发生了什么。去年我在一个问题中使用 AQTime 遇到了类似的问题:为什么 CharInSet 比 Case 语句快?
再次感谢 Barry Kelly 提供了线索。基本上,像 AQTime 这样的插装分析器并不一定适合进行微优化。它会给每一行代码都增加开销,这可能会淹没结果,正如这些数字所显示的那样。在我的新“优化代码”中执行的 3400 万行代码压倒了原始代码的数百万行,Pos 和 PosEx 程序显然几乎没有任何开销。
Barry 给了我一个使用 QueryPerformanceCounter 的代码示例来证明他是正确的,在那个例子中他是对的。
好的,现在让我们使用 QueryPerformanceCounter 来证明我的新程序更快,而不是 AQTime 所说的慢了 9 倍。所以这就是我要做的:
function TimeIt(const Title: string): double;
var i: Integer;
start, finish, freq: Int64;
Seconds: double;
begin
QueryPerformanceCounter(start);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 1);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 2);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 3);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 4);
QueryPerformanceCounter(finish);
QueryPerformanceFrequency(freq);
Seconds := (finish - start) / freq;
Result := Seconds;
end;
这将测试1,000,000次对GetTok的调用。
我的旧过程使用Pos和PosEx调用,耗时0.29秒。 使用PChars的新过程需要2.07秒。
现在我完全困惑了!有人能告诉我为什么PChar过程不仅更慢,而且慢8至9倍吗?
谜底揭开了!Andreas在他的回答中说将Delim参数从字符串更改为Char。我将始终只使用Char,因此至少对于我的实现来说,这是非常可能的。我对发生的事情感到惊讶。
100万次调用的时间从1.88秒降至0.22秒。
令人惊讶的是,当我将原始的Pos / PosEx例程的Delim参数更改为Char时,其时间从0.29秒上升到0.44秒。
坦白地说,我对Delphi的优化器感到失望。Delim是一个常量参数。优化器应该注意到在循环中发生了相同的转换,并应该将其移出,以便只进行一次。
双重检查我的代码生成参数,是的,我有优化开启,字符串格式检查关闭。
底线是,经过Andrea的修复,新的PChar例程大约比我的原始例程快25%(.22与.29)。
我仍然想跟进这里的其他评论并测试它们。
关闭优化并打开字符串格式检查仅将时间从.22增加到.30。它对原始内容增加的约相同。
使用汇编代码或调用用汇编语言编写的例程(如Pos或PosEx)的优点在于它们不受您设置的代码生成选项的影响。它们始终以预优化和非膨胀的方式运行。
在过去的几天中,我已经确认了微优化代码的最佳方法是查看和比较CPU窗口中的汇编代码。如果Embarcadero能够使该窗口更加方便,并允许我们将部分复制到剪贴板或打印部分,则会很好。
此外,在此帖子中,我不公平地抨击了AQTime,认为它添加的额外时间仅是因为它添加的仪器。现在我回头检查Char参数而不是String时,while循环的时间从2.66降至.30秒,而inc行的时间从.47降至.14秒。奇怪的是,inc行的时间也会下降。但我已经筋疲力尽地进行了所有这些测试
function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string;
{ LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://dev59.com/s-o6XIcBkEYKwwoYTzEw }
var
I, CurToken: Integer;
PLine, PStart: PChar;
begin
CurToken := 1;
PLine := PChar(Line);
PStart := PLine;
for I := 1 to length(Line) do begin
if PLine^ = Delim then begin
if CurToken = TokenNum then
break
else begin
CurToken := CurToken + 1;
inc(PLine);
PStart := PLine;
end;
end
else
inc(PLine);
end;
if CurToken = TokenNum then
SetString(Result, PStart, PLine - PStart)
else
Result := '';
end;
可能还有一些小的优化可以进行,比如CurToken = Tokennum这个比较,应该使用相同类型的Integer或Byte,以速度更快的那个为准。
但是现在我很满意了。
再次感谢StackOverflow Delphi社区。