Solved

[Impossible] A speed challenge.

Posted on 2004-10-12
98
785 Views
Last Modified: 2010-04-05
In http://www.experts-exchange.com/Programming/Programming_Languages/Delphi/Q_21164802.html I posted this routine:


type
  TSkipChars = set of char;

function StripChars( const Value: string; SkipChars: TSkipChars ): string;
var
  I, J: Integer;
  Max: Integer;
begin
  Result := Value;
  Max := Length( Value ); // Avoids recalculating the length.
  I := 1;
  while ( I <= Max ) and not ( Result[ I ] in SkipChars ) do
    Inc( I );
  if ( I <= Max ) then begin
    J := I + 1;
    while ( J <= Max ) do begin
      if not ( Result[ J ] in SkipChars ) then begin
        Result[ I ] := Result[ J ];
        Inc( I );
      end;
      Inc( J );
    end;
  end;
  SetLength( Result, I - 1 );
end;

Then someone posted a different version that's slightly faster than mine. However, the challenge is as follows:
Create a function with the same parameters as the one above that is at least twice as fast as my solution above. Use any means possible. :-)

Yeah, Impossible? Maybe. But it's a honorable challenge for the real speed-maniacs here. (Probably ends up becoming something in assembler...)
Now, once we have a lightning-fast solution, let no one ever ask how to strip characters from a string from this point on!
0
Comment
Question by:Wim ten Brink
  • 30
  • 18
  • 16
  • +7
98 Comments
 
LVL 6

Expert Comment

by:vadim_ti
ID: 12288547
but i think it is not worked, try please
value := AB,+CD:UE
set := ,+_:
0
 
LVL 6

Expert Comment

by:vadim_ti
ID: 12288799
sorry , my fault
it is worked
can do it 30% faster
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12289717
Did a little test of 500000 times executing StripChars using yadim_ti's value and set.
That results in 560 ticks. My version of StripChars uses 250 ticks.
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12290003
ok, test my code against your benchmark too? I posted it in the previous Q, hehe.
0
 
LVL 1

Assisted Solution

by:Bart_Thomas
Bart_Thomas earned 90 total points
ID: 12290247
Allriight, Workshop Alex, 560 ticks
DragonSlayer 300 ticks
Me 350 ticks

  function StripChars2 (const Value: string; SkipChars: TSkipChars): string;
  var
    p,q: PChar;
  begin
    SetLength (Result, length(Value));
    q := PChar(Result);
    p := PChar(Value);
    while p^ <> #0 do
    begin
      if not(p^ in SkipChars) then
      begin
        q^ := p^;
        inc (q);
        q^ := #0;
      end;
      inc (p);
    end;
  end;
0
 
LVL 14

Assisted Solution

by:DragonSlayer
DragonSlayer earned 90 total points
ID: 12291340
Bart, yours could perhaps be a bit more optimised:

function Stripper(const s: string; SkipChars: TSkipChars): string;
var
  p, q: PChar;
  Max: Integer;
  lastIndex: PChar;
begin
  Max := Length(s);
  SetLength(Result, Max + 1);
  q := PChar(Result);
  p := PChar(s);
  lastIndex := p + Max - 1;
  while p <= lastIndex do
  begin
    if not (p^ in SkipChars) then
    begin
      q^ := p^;
      Inc(q);
    end;
    Inc(p);
  end;
  q^ := #0;
end;

Notice that you can make do with assigning #0 to q^ at the very end of the loop, that should shave off some ticks ;-)
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12291698
There's not that much difference :(
(5000000 iterations)

============================================
StripChars AB,+CD:UE = ABCDUE
StripChars2 AB,+CD:UE = ABCDUE
MyStrip AB,+CD:UE = ABCDUE
Stripper AB,+CD:UE = ABCDUE
StripChars 5625 ticks
StripChars2 2531 ticks
MyStrip 3110 ticks
Stripper 2640 ticks
============================================

Is there an alternative for: if not (p^ in SkipChars) then ??

Regards,
Bart
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12291789
well, the above test is not really that conclusive (increase the size of the tested text, perhaps?)... but at least, 2640 and 2531 are already 50% the time of 5625 ticks =p
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12291936
Indeed, the testdata could be better. Anyways, it is quite interesting that PChar's are that much quicker. That makes me wonder how much faster this code can be?

Regards,
Bart
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12291972
Oh oh... do I sense some asm coding coming? ;-)
0
 
LVL 33

Expert Comment

by:Slick812
ID: 12292304
hey all, this is what I came up with -

function razChars( const Value: string; SkipChars: TSkipChars ): string;
var
  I, Max: Integer;
begin
Result := Value;
Max := Length(Value)+1;
I := 1;
while I < Max do
  begin
  if Result[I] in SkipChars  then
    begin
    MoveMemory(@Result[I], @Result[I+1], Max-I);
    Dec(Max);
    end else
    Inc(I);
  end;
end;

seems to run faster than StripChars?
0
 
LVL 33

Expert Comment

by:Slick812
ID: 12292332
there's an asm function in sysUtils called   StrScan  whichseems like it has the asm code that might could be modified to for this
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12292377
LoLx, I hate slick :p

Was coming up with my version using MoveMemory too... lol
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12292378
I was thinking about it, but I doubt the compiler can be beaten that easily.  This is the asm version of StripChar2:

;SetLength (Result, length(Value));
  mov eax, ebx
  call @StrLen
  mov edx, eax
  mov eax, esi
  call @LStrSetLength
;q := PChar(Result);
  mov eax, [esi]
  call @LStrToPChar
  mov esi, eax
;p := PChar(Value);
  mov eax, ebx
  call @LStrToPChar
  jmp +$12
;if not(p^ in SkipChars) then
  mov ecx, edx
  and ecx, @000000ff
  bt [esp], ecx
  jb +$03
;q^ := p^
  mov [esi], dl
;inc (q);
  inc esi
;inc (p);
  inc eax
;while p^ <> #0 do
  mov dl, [eax]
  test dl,dl
  jnz -$18

This is no rocket science code, but the "bt [esp], ecx" is unkown to me. Anyone?

Regards,
Bart
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12292416
I'm quite sure bt doesn't stand for Bart Thomas =p

Slick, would it be better to end your function with a

SetLength(Result, Max)?
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12293309
Lol, I know it cannot be optimized too much, so asking for something twice as fast is a real challenge. :-) That's why it's worth 500 points.

@Bart_Thomas, your solution seems quite fast but the problem might be that the result string will technically be larger than the string it contains. If you use:

SetLength(AString, 100);
AString[10] := #0;

Then the string is still 100 characters in size. The Delphi string type can store null characters without any problem. Thus, your method still needs a bit of code to set the proper length. :-)

Okay, since we need some specific test data for this routine, we will yse this string constant (without the quotes): "the quick brown fox jumps over the lazy poodle". And the characters we're going to strip are the vowels aeiouy and the space. It should be case-sensitive but since both data as stripchars are lower-case in the first place, this should not be a problem.

Now, to test the stuff, I used the following code:

program Strip;

uses
  Windows, SysUtils;

type
  TSkipChars = set of char;
  TStripChars = function(const Value: string; SkipChars: TSkipChars): string;
  TStatistics = record
    StripChars: TStripChars;
    Ticks: Cardinal;
    Count: Integer;
    Name: string;
  end;

function WA_StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  I, J: Integer;
  Max: Integer;
begin
  Result := Value;
  Max := Length(Value); // Avoids recalculating the length.
  I := 1;
  while (I <= Max) and not (Result[I] in SkipChars) do
    Inc(I);
  if (I <= Max) then begin
    J := I + 1;
    while (J <= Max) do begin
      if not (Result[J] in SkipChars) then begin
        Result[I] := Result[J];
        Inc(I);
      end;
      Inc(J);
    end;
  end;
  SetLength(Result, I - 1);
end;

function Slick_StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  I, Max: Integer;
begin
  Result := Value;
  Max := Length(Value) + 1;
  I := 1;
  while I < Max do begin
    if Result[I] in SkipChars then begin
      MoveMemory(@Result[I], @Result[I + 1], Max - I);
      Dec(Max);
    end
    else begin
      Inc(I);
    end;
  end;
end;

function Dragon_StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  p, q: PChar;
  Max: Integer;
  lastIndex: PChar;
begin
  Max := Length(Value);
  SetLength(Result, Max + 1);
  q := PChar(Result);
  p := PChar(Value);
  lastIndex := p + Max - 1;
  while p <= lastIndex do begin
    if not (p^ in SkipChars) then begin
      q^ := p^;
      Inc(q);
    end;
    Inc(p);
  end;
  q^ := #0;
end;

function Bart_StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  p, q: PChar;
begin
  SetLength(Result, length(Value));
  q := PChar(Result);
  p := PChar(Value);
  while p^ <> #0 do begin
    if not (p^ in SkipChars) then begin
      q^ := p^;
      inc(q);
      q^ := #0;
    end;
    inc(p);
  end;
end;

procedure TestEverything;
const
  MaxCount = 100;
  MaxInnerLoop = 100000;
  AString: string = 'the quick brown fox jumps over the lazy poodle';
  SkipChars: TSkipChars = ['a', 'e', 'i', 'o', 'u', 'y'];
var
  Statistics: array[0..3] of TStatistics;
  I, J, K: Integer;
  Ticks: Cardinal;
  StripChar: TStripChars;
  Tmp: string;
  Report: TextFile;
begin
  AssignFile(Report, 'Report.txt');
  Rewrite(Report);
  Statistics[0].StripChars := WA_StripChars;
  Statistics[0].Ticks := 0;
  Statistics[0].Count := 0;
  Statistics[0].Name := 'Workshop Alex';

  Statistics[1].StripChars := Bart_StripChars;
  Statistics[1].Ticks := 0;
  Statistics[1].Count := 0;
  Statistics[1].Name := 'Bart Thomas';

  Statistics[2].StripChars := Dragon_StripChars;
  Statistics[2].Ticks := 0;
  Statistics[2].Count := 0;
  Statistics[2].Name := 'DragonSlayer';

  Statistics[3].StripChars := Slick_StripChars;
  Statistics[3].Ticks := 0;
  Statistics[3].Count := 0;
  Statistics[3].Name := 'Slick812';

  // Do the tests a maximum number of times.
  for I := 1 to MaxCount do begin
    // // Loop through all different methods.
    for J := Low(Statistics) to High(Statistics) do begin
      // Get the address of the function. (Increases speed a bit.)
      StripChar := Statistics[J].StripChars;
      // Get start ticks.
      Ticks := GetTickCount;
      // Execute function.
      for K := 1 to MaxInnerLoop do
        Tmp := StripChar(AString, SkipChars);
      // Calculate total ticks used.
      Ticks := GetTickCount - Ticks;
      // If ticks <= 0 then something went wrong...
      if (Ticks > 0) then begin
        // Write what the function returned.
        WriteLn(Report, I: 4, '': 1, Tmp, ' - ', Statistics[J].Name, ' took ', Ticks, ' Ticks.');
        // Add to the statistics.
        Statistics[J].Ticks := Statistics[J].Ticks + Ticks;
        Statistics[J].Count := Statistics[J].Count + 1;
      end;
    end;
  end;
  // Now we're done testing. Display the results.
  for J := Low(Statistics) to High(Statistics) do begin
    with Statistics[J] do begin
      if (Count = 0) then begin
        WriteLn(Report, Name, ': No loop took longer than 0 ticks.');
      end
      else begin
        WriteLn(Report, Name, ': Average ticks: ', Ticks / Count: 0: 1, ' (Total ', Ticks, ' ticks for ', Count, ' tries.');
      end;
    end;
  end;
  CloseFile(Report);
end;

begin
  TestEverything;
  MessageBox(GetDesktopWindow, 'View the report now.', 'Done', MB_OK);
end.

Now, I ran above code, and guess what, guys... Your code all contains a nasty bug. :-P
As I said, the Delphi string type allows the #0 to be part of a string. Thus, if you add it to a string, it still doesn't change the string length. The WriteLn() I used therefore writes just a few more bytes. In above code I write the strings to a textfile and it shows me the additional garbage.

The result of just one loop:
Workshop Alex: Average ticks: 502.8 (Total 50277 ticks for 100 tries.
Bart Thomas: Average ticks: 439.3 (Total 43928 ticks for 100 tries.
DragonSlayer: Average ticks: 349.8 (Total 34983 ticks for 100 tries.
Slick812: Average ticks: 630.8 (Total 63079 ticks for 100 tries.

I added breakpoints in every method while testing above code and skipped every result where the ticks were 0. All methods are properly called so no problem there. It took a while but so far, DragonSlayer seems to be closest to the correct solution. Unfortunately, still not twice as fast as my code. And it has a bug...

If you disagree with above testing method, please let me know. :-) It seems reasonable fair to me, though.

Oh, and "bt [esp], ecx" is the trick Delphi uses to check if a value is in the set, I think. The parameters are passed through the registers so edx probably contains a reference to the set.
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12293324
  1 th qck brwn fx jmps vr th lz pdl - Workshop Alex took 431 Ticks.
   1 th qck brwn fx jmps vr th lz pdl e lazy poodle - Bart Thomas took 431 Ticks.
   1 th qck brwn fx jmps vr th lz pdl e lazy poodle  - DragonSlayer took 330 Ticks.
   1 th qck brwn fx jmps vr th lz pdl               - Slick812 took 581 Ticks.

Above you can see what the real result strings are... There's a #0 character after every pdl, except in my own version. ;-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12293387
One more thing. I ran it again, with optimization turned on and without any debug information. This almost doubled the speed by itself!

Workshop Alex: Average ticks: 283.8 (Total 28377 ticks for 100 tries.
Bart Thomas: Average ticks: 287.8 (Total 28782 ticks for 100 tries.
DragonSlayer: Average ticks: 239.1 (Total 23911 ticks for 100 tries.
Slick812: Average ticks: 393.3 (Total 39333 ticks for 100 tries.

Or maybe my system was less busy... But it made a big difference, though. DragonSlayer is still the fastest, but I'm in second-place and that's not a good sign... :-) It might just be impossible to improve the speed to double of my method, though. In that case, I'll divide the points between the three experts who gave the fastest versions. (Even if they are mucl slower than mine, Slick!) 250 for number 1, 150 for number 2 and 100 for number 3. So come on, guys! Go, earn those points!
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12294333
Let me try....

Give me a bit of time

Hypoviax
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12294441
I give up.... can't beat you guys ;-)

Hypoviax

0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12294459
Hmmmm... i may rise to the challenge again if i can spare the time
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12295151
I wonder, would the "nasty bug" be solved by a final

SetLength(Result, Length(Result));

at the end of the function? ;-)
0
 
LVL 20

Assisted Solution

by:Madshi
Madshi earned 90 total points
ID: 12295253
I win!   :-)

This function is directly taken from my freeware unit "madStrings.pas". I've only changed the parameters a bit so that it uses the same parameter logic as your functions. According to my tests it's faster than Alex' code and it doesn't have the string length bug.

function madshi_StripChars(const Value: string; SkipChars: TSkipChars) : string;
var cursor1, cursor2, lastChar : pchar;
begin
  result := Value;
  UniqueString(result);
  cursor1 := pchar(result);
  cursor2 := cursor1;
  lastChar := cursor1 + Length(result) - 1;
  while cursor2 <= lastChar do begin
    if not (cursor2^ in SkipChars) then begin
      cursor1^ := cursor2^;
      inc(cursor1);
    end;
    inc(cursor2);
  end;
  if cursor1 <> cursor2 then
    SetLength(result, cursor1 - pchar(result));
end;
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12295283
madshi, just a little curious... why is there a need for UniqueString?
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12295436
Strings are reference counted. When I do "result := Value", both point to the very same memory location. Now if I change the string by doing "result[1] := 'x'" or by doing "SetLength(result, ...)" or by doing "Delete(result, ...)" then Delphi automatically makes sure that the "result" string gets its own memory location, so that no harm to the other string references happens. But if you manipulate the string by using pointers, Delphi can't detect string changes and so we would change both strings at the same time. E.g. test this:

procedure TestStr;
var str1, str2 : string;
begin
  str1 := 'test' + IntToStr(1);
  str2 := str1;
  UniqueString(str1);
  pchar(str1)^ := 'T';
  ShowMessage(str2);
end;

Try it with and without the UniqueString and you'll see what it is good for.
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12295613
Yea, I understand about UniqueString, but in your code above... UniqueString for Result is to do ... what? Because if you want to retain cursor1's separation with Result, UniqueString should've been called after the cursor1 := PChar(Result) statement?

Of course, I also noticed that if I removed the UniqueString statement, an exception is raised when I changed the content of the PChar? strange...

Sorry if this sounds like a weak effort to get some free pchar tutorials, madshi, hehe, but I will give u some points later... thanks again.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12295654
> UniqueString for Result is to do ... what?

It is to make sure that our manipulation only affects the result string and not the source string.

> an exception is raised

Hmmm... When calling such a function with a string constant, "Value" and "result" both point directly to the string constant which is stored in the exe file. Trying to change this constant via pchar would result in changing the data section of the exe image in memory. That results in an access violation. UniqueString makes sure that the string is allocated (and thus changeable) instead.
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12295702
Ahh... so I must've misunderstood UniqueString...

since the codes

str1 := 'Hello';
str2 := str1;
UniqueString(str1);

will essentially "separate" str1 and str2, I would've thought that your UniqueString(Result) above would be to separate Result and cursor1/2... but then again, your call to UniqueString was done *before* the cursor1/2 assignments, so yea, guess my eyes are failing me ;-)

Btw, posted points for you at http://www.experts-exchange.com/Programming/Programming_Languages/Delphi/Q_21166295.html
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12295763
I reckon you are more active now Madshi despite what you said in that other question... :-)

Hypoviax
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12295798
Heh, it's always hard for me to resist a speed challenge. Plus, in this specific case I already had that fine tuned function sitting in my own strings unit, so...   :-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12296041
Well, now Madshi entered the battle, I guess everyone is curious to the new scorelist, of course. :-)
Oh, well. I'm at work now and have a faster PC here but since I keep testing and comparing ALL versions, it should still be quite fair.
The difference however is that at home I run the test application on a Pentium 3, 866 MHz, 512 MB memory and the application is compiled with Delphi 7. At work, I'm using a Pentium IV at 2.4 GHz, 512 MB memory but I've downgraded to Delphi 5 here. I expected faster results, but the results did amaze me, though. (For the final score, the system at home will be used, though!)

Workshop Alex: Average ticks: 121.7 (Total 12174 ticks for 100 tries.
Bart Thomas: Average ticks: 58.0 (Total 5801 ticks for 100 tries.
DragonSlayer: Average ticks: 60.6 (Total 6061 ticks for 100 tries.
Slick812: Average ticks: 168.5 (Total 16853 ticks for 100 tries.
Madshi: Average ticks: 94.6 (Total 9455 ticks for 100 tries.

And suddenly both Bart and Dragon seem to have a (flawed) function that is twice as fast as mine. And Madshi? A bit disappointing, though. It's faster, but definitely not the fastest. If Bart or Dragon provide an improved version that sets the proper string length then they probably win! Oh, well... If you add:
  SetLength( Result, Integer( q ) - Integer( PChar( Result ) ) );
at the end of their functions, the length is set to the correct value. And for Slick the following line:
  SetLength( Result, Max - 1 );
will solve the bug in his version.

I ran it again, this time without debug information (but optimization has been turned on for both tests) and with the bugs "fixed":
Workshop Alex: Average ticks: 115.4 (Total 11540 ticks for 100 tries.
Bart Thomas: Average ticks: 67.1 (Total 6706 ticks for 100 tries.
DragonSlayer: Average ticks: 67.5 (Total 6750 ticks for 100 tries.
Slick812: Average ticks: 175.2 (Total 17518 ticks for 100 tries.
Madshi: Average ticks: 94.9 (Total 9486 ticks for 100 tries.

The new test application is uploaded to http://www.workshop-alex.org/Sources/Strip.dpr and the complete report is at http://www.workshop-alex.org/Sources/Report.txt in case someone is interested.

Madshi is just about 20% faster while Bart and Dragon are almost twice as fast! (With the fixed bug!) But the real test will be done on my Pentium 3 at home, though. But it's interesting to see how the P4 seems to be able to improve the PChar operations... Their solutions are quite similar but the biggest difference is that Bart will stop if a #0 is encountered while Dragon looks at the real string length. Thus, they're not completely equal and Dragon's version therefore is slightly better, but also slower.

And Madshi, I'm amazed that your solution actually seems slower than the fixed versions of these two guys... :-P Guess you'll need to improve the MadStrings unit then. :-)
You're on the third place now, with Dragon and Bart sharing the first place. (Their code just isn't twice as fast as mine.) ;-)

About the UniqueString usage, Slick and I don't need it because we access the characters through the string index. ( Result[I] ) Dragon and Bart don't need it because they reserve the space for a new string. They don't copy the reference to Value. Only Madshi needs it because he assigns a reference to the Value string first, then has to make sure the string is unique. But Madshi, like me, is then just copying the characters from inside the result string only, ignoring Value. Madshi's code also has another time-consuming problem, though. What if the first 20 characters don't need to be stripped? Then cursor1 and cursor2 keep pointing at the same position. Still he copies those characters in those cases. A bit like: A := A;
I solved it by first searching for the first character that needed to be stripped. If no character needs to be stripped, nothing is done.

It's funny how a simple function can seem so perfect yet still it could be optimized a lot...
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12296049
@Madshi
> Plus, in this specific case I already had that fine tuned function sitting in my own strings unit, so...

Not finetuned enough, apparantly... ;-) Your solution is slow!... :-P
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12296101
Well, I expected the "bugfix" to cost more performance. Hmmmm...
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12296236
So did I. But apparantly my fix is still fast enough to let them beat your code. :-)

As I said, a function might still look so perfect, yet someone might still show it's not optimal.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12296374
There are 2 possible situations:

(1)
We need both the original and the modified string. So we use:

function StripChars(const Value: string; SkipChars: TSkipChars): string;

Example code:
strVar1 := 'test';
strVar2 := StripChars(strVar1, ['e']);
ShowMessage(strVar1 + ' -> ' + strVar2);

(2)
We don't need the original string, we only need the modified string. So we use:

procedure StripChars(var Value: string; SkipChars: TSkipChars);

Example code:
strVar1 := 'test';
StripChars(strVar1, ['e']);
ShowMessage(strVar1);

-------------------------

Why am I saying this? Because (2) can be made much faster than (1), because you can save some allocations. The string doesn't need to be reallocated. We can just mess with the original string buffer. My original code was doing (2), and it's doing it quite fast. I've changed the code to (1), because all your functions worked that way. But when comparing my code to DragonSlayer's code I can see that my code is not really well suited for (1). The main loop of DragonSlayer's code and my code are more or less identical. The top of the function (string allocation etc) is what makes the time difference.

If anyone is interested: Try benching all functions in mode (2). Then my function will look much better in comparison...   :-)

Here's how my original code looks like:

function KillChars(var str: string; killChrs: TSChar) : boolean;
var cursor1, cursor2, lastChar : pchar;
begin
  UniqueString(str);
  cursor1 := pchar(str);
  cursor2 := cursor1;
  lastChar := cursor1 + Length(str) - 1;
  while cursor2 <= lastChar do begin
    if not (cursor2^ in killChrs) then begin
      cursor1^ := cursor2^;
      inc(cursor1);
    end;
    inc(cursor2);
  end;
  result := cursor1 <> cursor2;
  if result then SetLength(str, cursor1 - pchar(str));
end;
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12296708
True, [2] is faster but I guess that all other functions might become faster too with this new rule. :-) Then again, their solutions would start to look a lot like yours in those cases. Just compare your version with the one Dragon made:

function Dragon_StripChars( const Value: string; SkipChars: TSkipChars ): string;
var
  p, q: PChar;
  Max: Integer;
  lastIndex: PChar;
begin
  Max := Length( Value );
  SetLength( Result, Max + 1 );
  q := PChar( Result );
  p := PChar( Value );
  lastIndex := p + Max - 1;
  while p <= lastIndex do begin
    if not ( p^ in SkipChars ) then begin
      q^ := p^;
      Inc( q );
    end;
    Inc( p );
  end;
  q^ := #0;
  SetLength( Result, Integer( q ) - Integer( PChar( Result ) ) );
end;

They appear to be very similar... The difference is that Dragon doesn't need to call UniqueString, while you must call it. Basically, you're copying the data in the string too many times. First it's copied to the result string. Then they are copied within the result string and with a bit of bad luck, they are copied to their original position, which wastes a bit of time. Sorry, but it does seem  a bit less efficient. :-)

And that function doesn't fit in my benchmark application... :-( Needs a "big" rewrite for that. Even worse, since you overwrite the value in str, I need to re-assign the original value every time to this string. And unfortunately, these routines are a bit too fast to get the ticks calculated over just a single run. If I would run every solution only once, instead of the 100.000 times I do now, they would all tell me they used 0 ticks... :-)
And re-assigning the str value every time would just slow down the benchmark test. I guess I would get the same result as I do now.

Besides, for this test I decided we need to maintain the original string.

I did optimize Dragon's code a bit, but it didn't matter much:

function Improved_Dragon_StripChars( const Value: string; SkipChars: TSkipChars ): string;
var
  p, q, r: PChar;
  Count: Integer;
begin
  Count := Length( Value );
  SetLength( Result, Count );
  q := PChar( Result );
  p := PChar( Value );
  r := p;
  inc( r, Count );
  while ( p < r ) do begin
    if not ( p^ in SkipChars ) then begin
      q^ := p^;
      Inc( q );
    end;
    Inc( p );
  end;
  SetLength( Result, Integer( q ) - Integer( PChar( Result ) ) );
end;

Looking at the CPU window, the whole assembler source fits on my screen now. (1280x1024) http://www.workshop-alex.org/Sources/Strip.gif for the greyed image. It just makes me wonder if there's much room for improvement here... It only does 5 different string-handling calls. And none of them within the loop that moves the data around. It just doesn't leave much room for improvements. And of course, you could end the function with
  Value := Result;
if you've passed Value as a var parameter instead. Assignments aren't that slow, especially since it just moves the reference... (No need for UniqueString either.)

So far, Bart and Dragon seem to share the first place and Madshi the third place. :-) Too bad I had to fix their code. :-P
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12296754
so... just using plain SetLength alone to create the memory allocation, and then copying the chars as necessary, should be faster than a string to variable assignment.

I wonder, if we remove the not in the IF statement, would things run faster? My own test resulted in mixed results:

function Dragon_StripChars2(const Value: string; SkipChars: TSkipChars): string;
var
  p, q: PChar;
  Max: Integer;
  lastChar: PChar;
begin
  Max := Length(s);
  SetLength(Result, Max + 1);
  p := PChar(Result);
  q := PChar(s);
  lastChar := q + Max - 1;
  while q <= lastChar do
  begin
    if (q^ in SkipChars) then
      Inc(q)
    else begin
      p^ := q^;
      Inc(p);
      Inc(q);
    end;
  end;
  p^ := #0;
  SetLength(Result, Integer(p - PChar(Result)));
end;
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12296953
>> True, [2] is faster but I guess that all other functions might become faster too with this new rule. :-)

Yes, and that's why my strings unit is using [2] most of the time!   :-)

>> The difference is that Dragon doesn't need to call UniqueString, while you must call it. Basically, you're copying the data in the string too many times. Sorry, but it does seem  a bit less efficient. :-)

Absolutely correct. But this is only the case because I did a quick convert from mode [2] to mode [1]. As I said, my code is not really suited well for mode [1], because it was originally written for mode [2].

>> And that function doesn't fit in my benchmark application... :-(

Absolutely correct.

--------------------

The big question for me is: What will be needed in actual daily programming work? Will you need mode [1] or mode [2]? I think mode [2] should be just fine for normal programming work - and it would be faster. So if we're really searching for the fastest way to kill specific chars from a string, we should go mode [2]...   :-)
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12297062
Just for reference, here's the disasm of the latest "Dragon" function. There's surely some potential for optimization left. But I don't have the time to do that... Another question is if it's really worth the pain. AND if a future Borland compiler improves performance, it might end up faster than if we try to manually tweak the asm.

0054349c       public Dragon_StripChars:        ; function entry point
0054349c 18543   push    ebx
0054349d         push    esi
0054349e         push    edi
0054349f         push    ebp
005434a0         add     esp, -$2c
005434a3         mov     esi, edx
005434a5         lea     edi, [esp+$c]
005434a9         push    ecx
005434aa         mov     ecx, 8
005434af         rep movsd
005434b1         pop     ecx
005434b2         mov     ebx, ecx
005434b4         mov     edi, eax
005434b6         mov     ebp, esp
005434b8 18544   mov     eax, edi
005434ba         call    -$13e58f ($404f30)     ; @LStrLen
005434ba
005434bf         mov     esi, eax
005434c1 18545   mov     eax, ebx
005434c3         mov     edx, esi
005434c5         call    -$13e20e ($4052bc)     ; @LStrSetLength
005434c5
005434ca 18546   mov     eax, [ebx]
005434cc         call    -$13e3a1 ($405130)     ; @LStrToPChar
005434cc
005434d1         mov     [esp+4], eax
005434d5 18547   mov     eax, edi
005434d7         call    -$13e3ac ($405130)     ; @LStrToPChar
005434d7
005434dc         mov     [ebp], eax
005434df 18548   mov     eax, [ebp]
005434e2         mov     [esp+8], eax
005434e6 18549   add     [esp+8], esi
005434ea 18550   mov     eax, [ebp]
005434ed         cmp     eax, [esp+8]
005434f1         jnb     loc_54351f
005434f1
005434f3       loc_5434f3:
005434f3 18551   mov     eax, [ebp]
005434f6         mov     al, [eax]
005434f8         mov     edx, eax
005434fa         and     edx, $ff
00543500         bt      [esp+$c], edx
00543505         jb      loc_543512
00543505
00543507 18552   mov     edx, [esp+4]
0054350b         mov     [edx], al
0054350d 18553   add     dword ptr [esp+4], 1
0054350b 18552
00543512       loc_543512:
00543512 18555   add     dword ptr [ebp], 1
00543516 18550   mov     eax, [ebp]
00543519         cmp     eax, [esp+8]
0054351d         jb      loc_5434f3
0054351d
0054351f       loc_54351f:
0054351f 18557   mov     eax, [ebx]
00543521         call    -$13e3f6 ($405130)     ; @LStrToPChar
00543521
00543526         mov     edx, [esp+4]
0054352a         sub     edx, eax
0054352c         jno     loc_543533
0054352c
0054352e         call    -$13f8c7 ($403c6c)     ; @IntOver
0054352e
00543533       loc_543533:
00543533         mov     eax, ebx
00543535         call    -$13e27e ($4052bc)     ; @LStrSetLength
00543535
0054353a 18558   add     esp, $2c
0054353d         pop     ebp
0054353e         pop     edi
0054353f         pop     esi
00543540         pop     ebx
00543541         ret
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12297080
I checked the assember code that you get when you remove the 'not' from the comparison. All it does is change the jump instruction from "jb Address" to "jnb Address".  Thus it doesn't make any difference.
I thought it might make any difference if I would just skip a'' lower-case letters ['a'..'z'] but the performance didn't change much. Only Slick's version becomes much SLOWER in that case. (He's moving around too much data.)
I also checked the assembler code of my routine and now knows why it's slightly slower than the others. It's calling Uniquestring within the inner loop where values are assigned. Removing this piece of code will improve the speed a bit, but not much. I've tested it by rewriting my version to:

function Improved_WA_StripChars( const Value: string; SkipChars: TSkipChars ): string;
var
  I, J: Integer;
  Max: Integer;
  P, Q: PChar;
begin
  Result := Value;
  Max := Length( Value ); // Avoids recalculating the length.
  I := 1;
  while ( I <= Max ) and not ( Result[ I ] in SkipChars ) do
    Inc( I );
  if ( I <= Max ) then begin
    J := I + 1;
    Q := PChar( Result );
    P := Q;
    inc( P, I - 1 );
    while ( J <= Max ) do begin
      if not ( Result[ J ] in SkipChars ) then begin
        P^ := Result[ J ];
        Inc( P );
      end;
      Inc( J );
    end;
    SetLength( Result, Integer( P ) - Integer( Q ) );
  end;
end;

Now, the pointer management is avoiding the calls to UniqueString, making it about as fast as Madshi's version. ;-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12297614
@Madshi,
> But this is only the case because I did a quick convert from mode [2] to mode [1].

Actually your [2] version does copy the original string to a new string value, just like Dragon and Bart are doing. But you're using UniqueString to make this copy of the string. Actually, your version will only be faster if the string is unique BEFORE the function is called. If the string isn't unique then yours is slower. UniqueString checks the reference counter of a string and if it's bigger than 1, it will make a copy of the string and fill it with the original string data. And then you copy it around again. Both DragonSlayer and Bart Thomas make sure the data is only copied once.
If the string is unique, though, then your version might be just as fast, since the code is quite similar to the others.

And no, further optimization by using ASM isn't worth the trouble. Delphi already makes highly efficient code of most of these routines. (Even my own, which actually suprised me!)

I have uploaded the latest version of the strip application to my site (see link above) with the new report. There are 7 versions in this benchmark application. The current score is:

1) Bart Thomas: Average ticks: 77.6 (Total 7764 ticks for 100 tries.)
*) DragonSlayer (Improved by WA): Average ticks: 79.7 (Total 7972 ticks for 100 tries.)
2) DragonSlayer: Average ticks: 79.8 (Total 7983 ticks for 100 tries.)
3) Madshi: Average ticks: 112.1 (Total 11212 ticks for 100 tries.)
*) Workshop Alex (Improved): Average ticks: 113.1 (Total 11313 ticks for 100 tries.)
*) Workshop Alex: Average ticks: 137.8 (Total 13781 ticks for 100 tries.)
4) Slick812: Average ticks: 192.1 (Total 19208 ticks for 100 tries.)

But the final score will be determined tonight, when I'm back home. (In about 6 hours.) I did have to fix the versions of Bart and DragonSlayer a bit but won't hold it against them. Bart's version does have a minor flaw, though. He stops when he encounters a #0 but this could be a legitimate character in a string variable. If it's fixed, it would be identical to DragonSlayers solution. DragonSlayers improved version just avoids one more call to a string-handling function. The same for my own improved version where I used a pointer instead of Result[I] to keep track of positions.
It seems the best way to improve performance is by avoiding as many calls to the string-handling routines that Delphi has.

Oh, one other thing that helps improve speed. I used SkipChars:= [ ] for a change and ran the tests again. This time, my own improved version just beats ALL other versions! :-)

Workshop Alex (Improved): Average ticks: 81.7 (Total 8166 ticks for 100 tries.)
Madshi: Average ticks: 82.2 (Total 8216 ticks for 100 tries.)
DragonSlayer: Average ticks: 83.5 (Total 8353 ticks for 100 tries.)
Bart Thomas: Average ticks: 83.6 (Total 8360 ticks for 100 tries.)
DragonSlayer (Improved by WA): Average ticks: 84.6 (Total 8457 ticks for 100 tries.)
Slick812: Average ticks: 97.9 (Total 9792 ticks for 100 tries.)
Workshop Alex: Average ticks: 100.6 (Total 10063 ticks for 100 tries.)

And Madshi's version is the fastest now of all your solutions. So I needed to set up a test that's more fair... What I do now is use several sets of chars that need to be stripped. This version is at http://www.workshop-alex.org/Sources/Strip2.dpr and now the bad news, guys...
<bad news>Whenever all characters [ #0..#255 ] are stripped, all routines become ten times slower.</bad news> Even worse, the speed difference between the fastest (Bart Thomas, 487.8) and the slowest (Slick812, 665.4) is relatively small. It really suprised me to see this be so slow.
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12297736
well, of course, we could've cheated again and added checks such as "if (Value = '') or (SkipChars = []) then Exit"
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12297913
@DragonSlayer, the problem exists when ALL characters are stripped away from the result. With my benchmark code, I would only have to use the set [#32, 'a'..'z'] and it would strip all characters away, but the routine would take ten times longer...

Weird, isn't it? Maybe because the string gets deallocated and the memory is freed but if that's the case, freeing strings is quite expensive, code-wise.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12298170
>> your version will only be faster if the string is unique BEFORE the function is called

That's right. The big question is how often a string in everyday life is unique or not. I'm not sure about that. What do you think?

>> If the string is unique, though, then your version might be just as fast, since the code is quite similar to the others.

"Just as fast" is wrong. It's much faster in that situation. Here are my test results:

Dragon mode [1] non-unique: 1891 ms
madshi mode [2] non-unique: 2016 ms
Dragon mode [1] unique: 1968 ms
madshi mode [2] unique: 1344 ms

Benchmark code:

const CKillChars : TSChar = ['a', 'e', 'i', 'o', 'u', 'y'];

procedure GetUniqueStr(var str: string);
begin
  str := 'the quick brown fox jumps over the lazy poodle';
  UniqueString(str);
end;

var s1, s2         : string;
    c1, c2, c3, c4 : dword;
    i1             : integer;
initialization
  MessageBox(0, 'start', 'info', 0);
  c1 := GetTickCount;
  for i1 := 1 to 1000000 do begin
    GetUniqueStr(s1);
    s2 := s1;
    Dragon_StripChars2(s2, CKillChars);
  end;
  c1 := GetTickCount - c1;
  c2 := GetTickCount;
  for i1 := 1 to 1000000 do begin
    GetUniqueStr(s1);
    s2 := s1;
    KillChars(s2, CKillChars);
  end;
  c2 := GetTickCount - c2;
  c3 := GetTickCount;
  for i1 := 1 to 1000000 do begin
    GetUniqueStr(s1);
    Dragon_StripChars2(s1, CKillChars);
  end;
  c3 := GetTickCount - c3;
  c4 := GetTickCount;
  for i1 := 1 to 1000000 do begin
    GetUniqueStr(s1);
    KillChars(s1, CKillChars);
  end;
  c4 := GetTickCount - c4;
  MessageBox(0, pchar('Dragon mode [1] non-unique: ' + IntToStr(c1) + #$D#$A +
                      'madshi mode [2] non-unique: ' + IntToStr(c2) + #$D#$A +
                      'Dragon mode [1] unique: ' + IntToStr(c3) + #$D#$A +
                      'madshi mode [2] unique: ' + IntToStr(c4)), 'info', 0);
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12298222
>> Whenever all characters [ #0..#255 ] are stripped, all routines become ten times slower.

Not on my PC! Actually Dragon's code needs 1700ms on my PC with ['a', 'e', 'i', 'o', 'u', 'y'], while it only needs 1450ms with [#0..#255]. Something strange on your PC, it seems to me!
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12299065
OK you experts fight it out, I will just *watch* ... heheheh ;-)
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12299069
Oh, funny though... meikl hasn't been seen around...
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12299070
> Something strange on your PC, it seems to me!
Which is why I'll be doing the final benchmark on my home computer. :-)

> That's right. The big question is how often a string in everyday life is unique or not. I'm not sure about that. What do you think?
That depends, I guess. If the string is passed from some component to your code, then it might be possible that the component also has a copy of this string. If you read the string from a file, it's unlikely that it's NOT unique. But if the string has been passed from one function to the other, to the third, etc, then it is likely that it's not unique;

Somethin like:

procedure A(Str1:string);
begin
  if B(Str1) then ...
end;
function B(Str2: string): Boolean;
begin
  C(Str2);
end;
procedure C(var Str3:string);
begin
end;

In above code, Str3 is not unique. And similar constructions can exist. In above example, A might read a string from a file and pass it to B. B then lets C do something with it before B e.g. writes the string to a logfile or whatever.

I have benchmarked your solution, btw. And indeed, in that case your solution is really faster. :-)
Dragon mode [1] non-unique: 1843
madshi mode [2] non-unique: 1625
Dragon mode [1] unique: 1563
madshi mode [2] unique: 1109

Faster in both cases. The reason for this big difference could be related to the release of unused strings. So I've done it a bit different. :-)

var
  c1, c2, c3, c4: dword;
  I: integer;
  List1: array[ 0..1000000 ] of string;
  List2: array[ 0..1000000 ] of string;

procedure CleanLists( Unique: Boolean );
var
  I: Integer;
begin
  if Unique then begin
    for I := Low( List1 ) to High( List1 ) do begin
      GetUniqueStr( List1[ I ] );
      List2[ I ] := '';
    end;
  end
  else begin
    for I := Low( List1 ) to High( List1 ) do begin
      GetUniqueStr( List1[ I ] );
      List2[ I ] := List1[ I ];
    end;
  end;
end;

begin
  //                                                                            
  CleanLists( True );
  c1 := GetTickCount;
  for I := Low( List1 ) to High( List1 ) do List2[ I ] := Dragon_StripChars2( List1[ I ], CKillChars );
  c1 := GetTickCount - c1;
  //                                                                            
  CleanLists( True );
  c2 := GetTickCount;
  for I := Low( List1 ) to High( List1 ) do KillChars( List1[ I ], CKillChars );
  c2 := GetTickCount - c2;
  //                                                                            
  CleanLists( False );
  c3 := GetTickCount;
  for I := Low( List1 ) to High( List1 ) do List2[ I ] := Dragon_StripChars2( List1[ I ], CKillChars );
  c3 := GetTickCount - c3;
  //                                                                            
  CleanLists( False );
  c4 := GetTickCount;
  for I := Low( List1 ) to High( List1 ) do KillChars( List1[ I ], CKillChars );
  c4 := GetTickCount - c4;
  //                                                                            
  WriteLn( 'Dragon mode [1] unique: ', c1 );
  WriteLn( 'madshi mode [2] unique: ', c2 );
  WriteLn( 'Dragon mode [1] not unique: ', c3 );
  WriteLn( 'madshi mode [2] not unique: ', c4 );
  MessageBox( 0, 'Done!', 'Info', 0 );
end.

Result:
Dragon mode [1] unique: 1016
madshi mode [2] unique: 640
Dragon mode [1] not unique: 1172
madshi mode [2] not unique: 1110

However, if I would change:
    List2[ I ] := Dragon_StripChars2( List1[ I ], CKillChars );
into:
    List1[ I ] := Dragon_StripChars2( List1[ I ], CKillChars );
The result becomes:
Dragon mode [1] unique: 2171
madshi mode [2] unique: 640
Dragon mode [1] not unique: 1235
madshi mode [2] not unique: 937

Madshi, since I haven't changed anything affecting your code, I think it's a bit strange that this change actually improved the speed of YOUR routine. For whatever reason, your code is slower whenever I let Dragon's code assign the results to List2 instead of List1. But his code actually improved when assigned to List2. Almost twice as fast. The performance gain must be related to the release of old string values. So, testing this by replacing:
  for I := Low( List1 ) to High( List1 ) do List2[ I ] := Dragon_StripChars2( List1[ I ], CKillChars );
with:
  for I := Low( List1 ) to High( List1 ) do Dragon_StripChars2( List1[ I ], CKillChars );
And guess what? Since we're discarding the result in these cases, Dragon is actually beating you again in performance! But not much:

Dragon mode [1] unique: 656
madshi mode [2] unique: 672
Dragon mode [1] not unique: 782
madshi mode [2] not unique: 828

So where does the slow performance come from? Right! from releasing old string values and references... The only reason your code is faster is probably because you have to release less string values.

This just proves that if you want to strip characters from an existing string, your code is faster. If you want to assign the result to a new string instead, other methods might perform just as well. Too bad this challenge is about the latter. ;-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12299086
I could wait for meikl though, give him a chance too to try and improve this all. ;-)
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 20

Expert Comment

by:Madshi
ID: 12299181
Well, it's really quite complicated to do proper benchmarking. I was also stumbling about strange effects which seem to be related to hidden string discarding. E.g. if you do "result := ''" in the first line of DragonSlayer's code, it becomes much slower for me. So it seems that Delphi somehow keeps the result string in memory and reuses it when the function is called in a loop. Do the benches show real life performance then? I'm not sure, it's really difficult to say...
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12299214
>> OK you experts fight it out

Hey, your function is one of the fastest (under specific circumstances it's the fastest). So who is the expert here?   :-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12299310
I must say that Borland makes it quite difficult for us this way. :-) We're trying to find the fastest solution and then it doesn't seem to matter much because in the code behind it things are slowing down again.

And no, Dragon is on the second place. Bart is the one with the fastest solution! (Even though he doesn't allow the #0 character to be part of the string, which in most cases won't be part of the string in the first place. I think the speed increase here comes from the hard-coded comparison with 0, instead of comparing two values. The CPU has always been slightly faster when comparing with 0.
But Dragon's code is faster than Madshi's version, if you forget about the part where the result is assigned to some other string value. :-) The code itself is faster, but the stuff around it that Delphi is doing just slows it down again. And no one here ever expected the code itself to be faster. ;-)
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12299397
>> Hey, your function is one of the fastest

Oh hey, but when it comes to real critical processing involving tonnes of threads and critical sections, guess madshi and alex are much much much more experienced than me! Oh, and Slick too!
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12300208
Hey! Critical processing also includes getting the best performance out of string handling routines. Especially when you're trying to build your own parser or import routines, it is very good to know how to get the best results. What I've seen here is that even a very small change to the code might increase the speed of a process.
Besides, did anyone expect that assigning one string value to another string value would cost that much processing time?

I have been trying to find a way to increase the speed but most of the speed loss comes from the string handling stuff. In general, you will need 5 calls if you want to return ia string result:
* To get the length
* To get a pointer to the original value
* To get a pointer to the result
* To initialize the result with the original value length
* To adjust the result length to it's shorter length.

Madshi's solution also have 5 calls:
* To make the string unique
* To get a pointer to the value
* To get the length of the value
* To get a pointer to the value again (!)
* To adjust the value length to it's shorter length.

Okay, if he just stores the start address of the value a bit better, it saves a single assignment. But this doesn't improve speed much, though. The SetLength() and Length() functions slows it down considerably.

The following version is slightly faster than Madshi's version because, like Bart, I'm not retrieving the length:

procedure StripChars2( var Value: string; SkipChars: TSChar );
var
  Start: PChar;
  P1, P2: PChar;
begin
  UniqueString( Value );
  Start := PChar( Value );
  P1 := Start;
  while ( P1^ <> #0 ) and not ( PChar( P1 )^ in SkipChars ) do
    inc( P1 );
  P2 := P1;
  inc( P1 );
  while ( P1^ <> #0 ) do begin
    if not ( P1^ in SkipChars ) then begin
      P2^ := P1^;
      inc( P2 );
    end;
    inc( P1 );
  end;
  SetLength( Value, P2 - Start );
end;

But it's only faster with unique strings. Slower with non-unique strings, because it has to make it unique again. It's also faster if there are more characters at the start that can be skipped. ;-)

(I also discovered that a while-do might be faster than repeat-until...)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12300234
Using:
  procedure StripChars2( var Value: string; SkipChars: TSChar ); register;
makes it even faster, since it's using the registers now to pass on the parameters. It saves about 10% in speed...
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12300295
"register" is the default calling convention!
0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12300600
so... where does that leave us?
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12300725
That means, it doesn't matter whether we write "register" or not. It's all the same.
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12300838
What bothers me is that PChars are really that much quicker than Strings.
I always thought that the compiler converted them to PChars. Weird...
This is why I didn't resize the result-string in my function after "stripping"
it.

Regards,
Bart Thomas

0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12300872
Come to think of it, this is so cool... Delphi 2005 is announced, and yet, a couple of us Delphi old-timers are still fretting over issues of PChars, hehehehe ;-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12301089
register is standard? I thought pascal was standard... Just checked. You're right. Just shows that measuring the time this way isn't very reliable...

Am at home now. Compiled Strip2.dpr since it should give a more reliable result. Results will be here in about half an hour, with the final grades. :-)
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12301126
It is a bit odd indeed :-) But it is quite annoying that there is a difference between them and why is a repeat-until slower than a while-do.

Here's yet another stripchars function. Not quicker, but with regular strings.

function YASCF (const Value: string; SkipChars: TSkipChars): string;
var
  i,j: Integer;
begin
  SetLength (Result, length(Value));
  j := 1;
  for i := 1 to length(Value) do
  begin
    if not(Value[i] in SkipChars) then
    begin
      Result[j] := Value[i];
      inc (j);
    end;
  end;
  SetLength (Result, j-1);
end;

Regards,
Bart Thomas
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12301209
Repeat-until just seemed a bit slower in one case where I replaced a while do with a repeat-until.

And I seem to have some "technical" problems. :-) On my PIII-866 it seems that no solution is really a lot faster...

Workshop Alex: Average ticks: 257.0 (Total 15422 ticks for 60 tries.)
Bart Thomas: Average ticks: 265.5 (Total 15930 ticks for 60 tries.)
DragonSlayer: Average ticks: 234.5 (Total 14070 ticks for 60 tries.)
Slick812: Average ticks: 499.5 (Total 29968 ticks for 60 tries.)
Madshi: Average ticks: 293.3 (Total 17599 ticks for 60 tries.)
DragonSlayer (Improved by WA): Average ticks: 243.2 (Total 14594 ticks for 60 tries.)
Workshop Alex (Improved): Average ticks: 248.7 (Total 14923 ticks for 60 tries.)

Sorted by speed:

DragonSlayer: Average ticks: 234.5 (Total 14070 ticks for 60 tries.)
DragonSlayer (Improved by WA): Average ticks: 243.2 (Total 14594 ticks for 60 tries.)
Workshop Alex (Improved): Average ticks: 248.7 (Total 14923 ticks for 60 tries.)
Workshop Alex: Average ticks: 257.0 (Total 15422 ticks for 60 tries.)
Bart Thomas: Average ticks: 265.5 (Total 15930 ticks for 60 tries.)
Madshi: Average ticks: 293.3 (Total 17599 ticks for 60 tries.)
Slick812: Average ticks: 499.5 (Total 29968 ticks for 60 tries.)

Darn. I hate these speed tests... :-) Even amazing that Madshi seems to be slower than my own solution... :P
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12301321
Testing is indeed quite difficult.
My first testloop produced some weird results aswell. Your original was the first one, mine was second.
Somehow yours always was quicker. This is why I switched to PChars. When I commented the testing
of yours it gave entirely different results.

This is my current loop and it gives quite "statisfying" results.

var
  S: String;
  R: String;
  C: TSkipChars;
  i: Integer;
  T: Cardinal;
  sl: TStringList;
begin
  S := 'the quick brown fox jumps over the lazy poodle';
  C := ['a', 'e', 'i', 'o', 'u', 'y'];;

  sl := TStringList.Create;
  try
    T := GetTickCount;
    for i := 0 to 5000000 do
    begin
      R := YASCF (S,C);
      if sl.IndexOf (R) = -1 then
        sl.Add (R);
      R := StringOfChar ('=', length(R));
    end;
    memo1.Lines.Add(Format ('YASCF used %d ticks and had %d unique results in stripping %s to %s',[GetTickCount-T,sl.Count,S,sl[0]]));
  finally
    sl.Free;
  end;

Regards,
Bart Thomas
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12301886
Well, ran another test just now, with more tries this time... Result (ordered):

DragonSlayer (Improved by WA): Average ticks: 325.5 (Total 195286 ticks for 600 tries.)
DragonSlayer: Average ticks: 326.9 (Total 196151 ticks for 600 tries.)
Workshop Alex: Average ticks: 341.8 (Total 205074 ticks for 600 tries.)
Workshop Alex (Improved): Average ticks: 342.1 (Total 205278 ticks for 600 tries.)
Bart Thomas: Average ticks: 371.8 (Total 223079 ticks for 600 tries.)
Madshi: Average ticks: 387.9 (Total 232726 ticks for 600 tries.)
Slick812: Average ticks: 570.2 (Total 342115 ticks for 600 tries.)

I used six different sets with this test: [ ], [ #32 ], [ 'a', 'e', 'i', 'o', 'u', 'y' ], [ #0..#255 ] - [ 'a', 'e', 'i', 'o', 'u', 'y' ], [ 'a'..'e', 'i'..'o', 'u'..'y' ], [ #0..#255 ] - [ 'a'..'e', 'i'..'o', 'u'..'y' ]
Every test-set is used 100 times for all seven functions. In the inner-loop each function is called 100.000 times.

There could be a difference in the processor here, causing this difference between what I get at home and at work. The test application isn't using much memory so no swap issues. I guess the P4 is optimizing a lot better than the P3 with string-handling stuff. Still, quite a lot of people might be using P3's so it's difficult to say who has won. I'd say that DragonSlayer, Bart Thomas and Madshi all get 160 points, since the results aren't very far away from the others. Since DragonSlayer seems to have the fastest solution, he will be marked as the one who answered it. This leaves 20 points for Slick812 for his nice attempt. But Slick812's method has never been faster.

Anyone who disagrees? Then post a faster solution within the next 12 hours. I'll accept it tomorrow when I'm back at work.
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12303138
Ok, before you accept, can you test mine. It'll probably be slow as but you never know ;-). i'll post it up soon

Hypoviax
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12303227
Ok, here it is... don't laugh. I changed the parameter to use a string if that's alright. Just because i'm not as pro as you guys are please don't laugh:

function StripChars(const Value: string; SkipChars: string): string;
var
  X,y: Integer;
  Max,maxskips: Integer;
  CurrentChr,CurrentSkip:String;
  foundskipchar:boolean;
begin
max:=length(value);
maxskips:=length(SkipChars);
   For X:=1 to max do
   begin
   foundskipchar:=false;
   CurrentChr:=copy(value,x,1);
    For Y:=0 to maxskips do
      begin
         CurrentSkip:=copy(skipchars,y,1);
        if CurrentChr=CurrentSkip then
          begin
              foundskipchar:=true;
          end;
      end;
      if foundskipchar<>true then
        begin
          result:=result+CurrentChr
        end;
   end;
end;

:-)

Hypoviax
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12303318
oh, with the string parameter works just like:

StripChars("the quick brown fox jumps over the lazy poodle","aeiouy");
0
 
LVL 14

Assisted Solution

by:Pierre Cornelius
Pierre Cornelius earned 110 total points
ID: 12303520
Howzit Alex.

Wow, this topic has attracted quite a bit of attention...

Bart:
the previous code you posted (the function YASCF) is exactly my code from the previous thread (http://www.experts-exchange.com/Programming/Programming_Languages/Delphi/Q_21164802.html )

Here is my stab at it:

function PC_StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  I, ps: Integer;
  Max: pInteger;
  p: pchar;
begin
  Max:= pointer(Value);
  Dec(Max);
  SetLength(result, Max^);
  ps:= integer(result);
  p:= PChar(Result);

  for i:= 1 to Max^ do
    if NOT (Value[i] in SkipChars)
    then begin
      p^ := Value[i];
      Inc(p);
    end;
  ps:= integer(p)-ps;
  Max:= pointer(result);
  Dec(Max);
  Max^:= ps;
end;

Instead of using Length and SetLength, I read and write the values in memory directly. It results in some speed improvements. Anyone see something wrong with it? It is based on the following:
- A long-string variable is a pointer occupying four bytes of memory
- The eight bytes before the location contain a 32-bit length indicator and a 32-bit reference count.

Regards
Pierre
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12303539
This basically isn't bad. You just need some knowledge of sets and accessing chars in strings directly.

A set is quite simple. Just like a set of cards. The Delphi equivalent of checking if a certain card is part of the whole deck is:

if CertainCard in WholeDeck then DoSomething;

Since your your inner-loop:

#      For Y:=0 to maxskips do
#      begin
#         CurrentSkip:=copy(skipchars,y,1);
#        if CurrentChr=CurrentSkip then
#          begin
#              foundskipchar:=true;
#          end;
#      end;
#      if foundskipchar<>true then
#        begin
#          result:=result+CurrentChr
#        end;

Is a simular check, it translates to:

if not(CurrentChr in SkipChars) then // CurrentChr not part of set SkipChars
  result := result + CurrentChr;

A string is basically a array of chars. So your line:

# CurrentChr:=copy(value,x,1);

Translates to:

CurrentChr := value[x];

With this knowledge your function is:

function StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  X: Integer;
  Max: Integer;
  CurrentChr: Char;
begin
  max:=length(value);
   For X:=1 to max do
   begin
     CurrentChr := value[x];
     if not(CurrentChr in SkipChars) then
       result := result + CurrentChr
   end;
end;

Which can be shortened to:

function StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  X: Integer;
  Max: Integer;
begin
  max:=length(value);
   For X:=1 to max do
   begin
     if not(value[x] in SkipChars) then
       result := result + CurrentChr
   end;
end;

The "result := result + CurrentChr" is slow operation. Use SetLength function to "size" the Result-string in advance. That means you can access it as an array. Set the length of Result to the length of Value before you remove the skipchars and correct the size after "removing" the skipchars.

function StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  X,Y: Integer;
  Max: Integer;
begin
  max:=length(value);
  SetLength (Result, max);
  Y := 1;  
  For X:=1 to max do
   begin
     if not(value[X] in SkipChars) then
     begin
       result[Y] := Value[X] ;
       inc (Y);
   end;
   SetLength (Result,Y-1);
end;

StripChars("the quick brown fox jumps over the lazy poodle",['a','e','i','o','u','y']);

Regards,
Bart.
0
 
LVL 1

Expert Comment

by:Bart_Thomas
ID: 12303576
PierreC: OOPS...  It just popped up in my head as I was debugging some sql-thingy :-)

Regards,
Bart
0
 
LVL 14

Expert Comment

by:Pierre Cornelius
ID: 12303594
No problem.

How do they say, again: Great minds think alike (and fools never differ hehe...)
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12304210
Thanks for your comments Bart. I would like to know how my original code performed anyway compared to the adjusted version:

function StripChars(const Value: string; SkipChars: TSkipChars): string;
var
  X,Y: Integer;
  Max: Integer;
begin
  max:=length(value);
  SetLength (Result, max);
  Y := 1;  
  For X:=1 to max do
   begin
     if not(value[X] in SkipChars) then
     begin
       result[Y] := Value[X] ;
       inc (Y);
   end;
   SetLength (Result,Y-1);
end;

Best Regards,

Hypoviax

0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12304239
I'll challenge you guys soon (after my exams) to a speed competition in sorting an array of data

If you're up for it post your comments here and i'll make a question around the 4-5th November.

Hypoviax
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12306837
@Hypoviax, your version looks a bit slow and doesn't fit well in my benchmark tool. (The function template is different.) But I worked around it. :-) A quick test already showed me your's is about 100 times slower than Slicks solution! And yes, I said Oops too when I noticed it.
And after I included your code in my benchmark application, it decided to crash because the system ran out of memory. Without your version, the system never needed more than about 15 MB of RAM and VM. With your version, I saw the memory usage run up to 512 MB ram and over one GB of VM. So your solution isn't just slow. It also eats up a large amount of memory. I hate to say it but it's the WORST solution so far. ;-)
Hypoviax, your challenge will be interesting, though. But make sure to set up good specifications and build a simple benchmark tool to test every method in a fair way.

@PierreC, it seems a bit of a nasty hack and if Borland ever decides to change it's string implementation then it will fail. Then again, none of the methods used here will work correctly in Delphi 8 anyway... :-)

I decided to make the test a bit more interesting too. Something more like this:

var
  List: array[ 1..100000 ] of string;
  ...And more...
begin
  ...code...
  for K := Low( List ) to High( List ) do
    List[ K ] := '';
  Ticks := GetTickCount;
  for K := Low( List ) to High( List ) do
    List[ K ] := Hypoviax_StripChars( AString, SkipStrings );
  Ticks := GetTickCount - Ticks;
  ...code...
end;

The difference here is that I am assigning every function result to a DIFFERENT string variable. Which would be more logical in a real-world situation.
I've dropped the solution from Hypoviax because it's way too slow and eats too much memory. (Especially compared to the other solutions.) I've included the solution from PierreC and will do the performance check at work first, since it shows a clearer difference.

Run 1:
PierreC: Average ticks: 214.8 (Total 12888 ticks for 60 tries.)
Bart Thomas: Average ticks: 229.4 (Total 13761 ticks for 60 tries.)
DragonSlayer: Average ticks: 233.2 (Total 13989 ticks for 60 tries.)
DragonSlayer (Improved by WA): Average ticks: 239.6 (Total 14377 ticks for 60 tries.)
Madshi: Average ticks: 250.0 (Total 15002 ticks for 60 tries.)
Workshop Alex (Improved): Average ticks: 255.5 (Total 15327 ticks for 60 tries.)
Workshop Alex: Average ticks: 299.1 (Total 17947 ticks for 60 tries.)
Slick812: Average ticks: 580.7 (Total 34841 ticks for 60 tries.)

Run 2:
PierreC: Average ticks: 211.4 (Total 12686 ticks for 60 tries.)
Bart Thomas: Average ticks: 225.5 (Total 13529 ticks for 60 tries.)
DragonSlayer: Average ticks: 229.2 (Total 13750 ticks for 60 tries.)
DragonSlayer (Improved by WA): Average ticks: 231.0 (Total 13861 ticks for 60 tries.)
Madshi: Average ticks: 247.6 (Total 14857 ticks for 60 tries.)
Workshop Alex (Improved): Average ticks: 249.4 (Total 14966 ticks for 60 tries.)
Workshop Alex: Average ticks: 291.1 (Total 17468 ticks for 60 tries.)
Slick812: Average ticks: 568.7 (Total 34124 ticks for 60 tries.)

PierreC does have a pretty good speed increase here. Maybe not the neatest way, but it works! But I wonder if it leaks memory since changing the result length to a shorter value instead of using SetLength() might leave some bytes that aren't freed. Then again, Borland's string handling routines might be like the definition of a TList, where you have a count (length) and a capacity, which tells how much memory is reserved for possible overhead. Considering the fact that Borland adds a #0 to a string if you use PChar(AString) which is NOT included in the length of the string, this could even be quite likely.

I tried to improve PierreC's version and with a bit of succes. This version has only one string-handling call:

function Improved_PierreC_StripChars( const Value: string; SkipChars: TSkipChars ): string;
var
  Len: PInteger;
  PValue, PResult, Loop: PChar;
begin
  Len := PInteger( Value );
  PValue := PChar( Len );
  Dec( Len );
  SetLength( Result, Len^ );
  PResult := Pointer( Result );
  Loop := PResult;
  while ( PValue^ <> #0 ) do begin
    if not ( PValue^ in SkipChars ) then begin
      Loop^ := PValue^;
      Inc( Loop );
    end;
    Inc( PValue );
  end;
  Len := PInteger( PResult );
  Dec( Len );
  Len^ := Loop - PResult;
end;

The difference?
PierreC: Average ticks: 209.6 (Total 12573 ticks for 60 tries.)
PierreC (Improved by WA): Average ticks: 205.0 (Total 12300 ticks for 60 tries.)

Yes, I needed 273 less ticks. Still, a good idea from PierreC. But okay, back to the current score...

First of all, I cannot use any code that has been improved by me, because that would not be fair. DragonSlayer and Bart Thomas provided fast, working solutions with a minor bug. (a minor penalty is given for this.) Madshi showed that a different approach also improves speed so it makes it difficult to see a clear winner. Thus, in my opinion, DragonSlayer, Bart Thomas and Madshi are all on a shared second place. PierreC is number one! (Makes the point division 260/80/80/80 in my opinion.)
But okay, a new solution has been added so I'll test again at home this evening...

I've put the source for the new benchmark application at http://www.workshop-alex.org/Sources/Strip2.dpr and there's a new report at http://www.workshop-alex.org/Sources/Report.txt showing the current results. To make the test a bit more reliable, I give the process a very high thread and process priority, so other applications can't barely breathe. I also re-order the list of functions after every test based on the best results. Thus, the fastest routine gets executed first. (It also makes it easier for me to see the scores.)

Scores so far:
PierreC (Improved by WA): Average ticks: 188.1 (Total 15045 ticks for 80 tries.)
PierreC: Average ticks: 198.1 (Total 15848 ticks for 80 tries.)
DragonSlayer (Improved by WA): Average ticks: 211.5 (Total 16919 ticks for 80 tries.)
Bart Thomas: Average ticks: 213.9 (Total 17110 ticks for 80 tries.)
DragonSlayer: Average ticks: 216.2 (Total 17297 ticks for 80 tries.)
Workshop Alex (Improved): Average ticks: 228.0 (Total 18237 ticks for 80 tries.)
Madshi: Average ticks: 229.6 (Total 18365 ticks for 80 tries.)
Workshop Alex: Average ticks: 261.8 (Total 20941 ticks for 80 tries.)
Slick812: Average ticks: 527.4 (Total 42189 ticks for 80 tries.)

Btw, Slick812... If no characters are stripped, your code is as fast as Madshi's. But if all characters must be stripped, yours is the slowest. However, Madshi's code is as fast in stripping no characters as it is at stripping ALL characters. :-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12307441
Okay, added a few more improvements to the benchmark routine...

First of all, added this function:

function RDTSC: Int64;
asm
  dw $310F  {BASM doesn't support RDTSC}
end;

This is a more precise version of GetTickCount since it counts processor steps. (Or whatever.) It is perfect for extremely fast routines. Thus I could lower the number of times that I call the inner loop where the StripChar functions are called. (Reducing the memory usage for the list a bit.) I increased the number of tests to 10 different sets of chars. The Inner loop runs 2500 times. All tests are repeated 500 times. At the moment I have 9 different functions to test. The results don't differ much from what we've seen before but the measurement is just a bit more precise.
Oh, andf I generated a new layout that you can see better with a fixed font. Unfortunately EE doesn't allow me to use one...

 # Name                             Average  Difference       % Tries
 1 PierreC (Improved by WA)         5100.54           0  147.31  5000
 2 PierreC                          5182.84   411469052  144.97  5000
 3 Bart Thomas                      6369.06  6342565224  117.97  5000
 4 DragonSlayer (Improved by WA)    6378.88  6391693812  117.79  5000
 5 DragonSlayer                     6378.94  6392007964  117.79  5000
 6 Workshop Alex (Improved)         6462.60  6810272616  116.26  5000
 7 Madshi                           6773.47  8364646872  110.93  5000
 8 Workshop Alex                    7513.70 12065792408  100.00  5000
 9 Slick812                        14111.50 45054808396   53.25  5000

A percentage is shown too now, comparing all speeds with the speed of the original option. The higher, the better, but no one managed to get 200% or more. (Or even 150%.) Average is the average time used. Difference is the difference in clockticks with the top solution. Tries is the number of times the loop of 2500 iterations has been called, and thus the speed measured.

The % colums shows a clear difference in speed between PierreC and all others.
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12308634
Okay, a slightly improved benchmark tool (again) at http://www.workshop-alex.org/Sources/Strip4.dpr is available. This version scared me since it showed me that if run once, PierreC's version is THREE TIMES faster than mine. No other version is even twice at fast, unfortunately. The score, if run once:

 # Name                             Average  Difference       % Tries
 1 PierreC (Improved by WA)         4802.29           0  366.72    10
 2 PierreC                          4973.26     1709712  354.11    10
 3 Bart Thomas                     16096.42   112941304  109.41    10
 4 DragonSlayer                    17095.15   122928572  103.02    10
 5 Workshop Alex                   17611.00   128087088  100.00    10
 6 DragonSlayer (Improved by WA)   19850.84   150485512   88.72    10
 7 Madshi                          20404.58   156022928   86.31    10
 8 Workshop Alex (Improved)        20465.86   156635696   86.05    10
 9 Slick812                        28272.06   234697696   62.29    10

Apparantly, the string system in Delphi needs to warm up a bit. PierreC's score gets down if the benchmark is run multiple times and finally stabilizes at being 150% faster. But technically, he did create a version that was twice as fast as my solution so technically, he wins. In some conditions his solution was even 4 times faster. Quite amazing.

But it seems that Delphi is learning after several runs. In the Strip4.dpr source, search for the MaxCount constant. If set to 1, PierreC is lightning-fast. If set to 10 then all other methods manage to gain some speed. It's not PierreC's solution getting slower. No, it's the other solutions getting faster, somehow. Or maybe it's related to some other problem...
This is real nasty from Borland...
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12309427
Alex, I don't think that Delphi is "learning". I think that while doing all this string stuff some hidden string instances are flying around. Delphi has a strange (unpredictable) way to clear them. That's why you get sudden unexpected speedups or slowdowns.

Just try this: In all the functions add a "result := ''" in the first line. Theoretically I would expect that this has only a minor impact on performance. But instead the impact is quite big. Why? Because Delphi seems to cache the return string instance and reuse it if you call the same function multiple times. This saves allocations big time. When doing "result := ''" in the first line you break this caching more or less.

I noticed this in my normal programming life. Once there was a time when I expected that result strings are initialized to '' in the beginning of a function. But that's not true. If you run through the same function a 2nd time, the result string often begins with the content of the first run through. So I had to add a "result := ''" to some functions.

I'm not sure whether this caching stuff doesn't somehow invalidate some of the benches, cause the caching has quite a big impact on the benches, while in real life I think the caching will help less.
0
 
LVL 26

Accepted Solution

by:
Russell Libby earned 120 total points
ID: 12312028

It would also appear (at least on my P4 system), that the BT assembly instruction is actually slower than doing the bit testing by hand. So, here is "another" version that, on my system at least, runs faster than all others.

Anyways, I take no credit for the base routine, as PierreC wrote it;... I do take credit for the bit testing though. I have also cleaned it up so that it won't choke if an empty string is passed as the source, and it also works with the actual string length (vs the #0 null check which MAY not be the end of the string).

Just my 2 cents,
Russell

const
  SlotSet:          Array [0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);

type
  PByteArray        =  ^TByteArray;
  TByteArray        =  Array [0..Pred(MaxInt)] of Byte;

function Improved_PierreC_StripChars2(const Value: string; SkipChars: TSkipChars ): String;
var  lpSkip:        PByteArray;
     lpszValue:     PChar;
     lpszResult:    PChar;
     dwLength:      Integer;
     dwIndex:       Integer;
begin

  // Cast source as pchar
  lpszValue:=PChar(Value);

  // Check pointer
  if Assigned(lpszValue) then
  begin
     // Get the source length
     dwLength:=PInteger(lpszValue-4)^;
     // Allocate result pointer
     SetLength(result, dwLength);
     // Get dest pointer
     lpszResult:=PChar(result);
     // Get the set, which is 32 bytes (8 bits/byte * 32 bytes = 256 items in set)
     lpSkip:=@SkipChars;
     // Walk the source string
     for dwIndex:=0 to Pred(dwLength) do
     begin
        // Check set data
        if ((lpSkip[Byte(lpszValue^) div 8] and SlotSet[Byte(lpszValue^) mod 8]) = 0) then
        begin
           // Append to dest
           lpszResult^:=lpszValue^;
           Inc(lpszResult);
        end;
        Inc(lpszValue);
     end;
     // Update result string length
     PInteger(PChar(result)-4)^:=lpszResult-PChar(result);
  end
  else
     // Dest = Source
     result:=Value;

end;

0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12313161
Workshop_Alex,

I knew my solution would be slow (very slow it seems ;-) ), i was just wondering how it performed against the others. I havn't that much experience in this particular area, and so, for me it's more of a learning experience. I'll make my challenge (in early november) worth 500 points. However, i may need assistance from you or others in writing a testing script.

Regards,

Hypoviax
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12316328
Wow, installed NAV 2005 (upgrade) on my system yesterday. And of course it does a full system scan. So starting at 9 PM I decided to go to bed early since the scan would take a while. Not fair to run a benchmark when NAV is eating away clockticks. It's now & AM and NAV is just finished, finding 24 Beagles in some old archive folder of mine full emails that I never bothered to read anyway. Oh, well. I knew it would be slow because it had to scan 160 GB out of 200 GB total. :-) But now it's time for the benchmark.

@Hypoviax, when I ran your version once, it was over 100 times slower than my own solution. Thus it performed quite badly. When I ran it as often as I ran all others, I noticed that the system was eating up all available memory, then continued eating up my swapfile to finally run out of memory. You actually made my benchmark tool crash! :-)
For a good testing script, it is important that you avoid measuring unneeded code. In my Strip4 source you can see that I actually just test the call to the function and the loop counting only. Everything else like filling the variables and getting the right function is done outside the time-measuring part. I also used RDTSC to get a more precise time counter. Actually, RDTSC doesn't measure time but real processor ticks, thus this value won't change much between computers of different speeds.
It is funny though, that some solution on my P3 require less ticks than on the P4 at work. Others require more ticks. The times on my P3 are much closer to each other than on the P4. An interesting discovery. Thus, when you are going to do a benchmark, specify the type of computer(s) that will be involved for your test, including clock speed and RAM.
Furthermore, to try avoiding that another process is stealing ticks away when one solution happens to run, I made sure that each test itself is quite short and that all tests are repeated quite often. (I also re-order the tests based on speed with a simple bubble-sort routine, which is fast enough for such a short list.
And when I run the benchmark, the process and current thread is at it's highest priority which should help a lot too.

@Russell, I've included your solution too now and if it's indeed an improvement, you will end on a SHARED first place with PierreC. (Which is only fair since you came up with an interesting new addition. However, a quick glance on your code shows me that you're using two string-handling functions too many. This part:
    PInteger(PChar(result) - 4)^ := lpszResult - PChar(result);
should not be needed because you've calculated the address of result before!

@Madshi, True. Delphi has an unpredictable way of cleaning trings. The solution by Hypoviax already showed this since it kept eating up memory, clearly showing that Delphi "forgot" to free strings. Shows that the copy() command in this case might be highly inefficient. However, in the benchmark it does have an interesting effect. It speeds things up considerably. (And the whole application never needs more than 1.5 MB of RAM.) Delphi seems to make the code highly efficient once it's run more often.
But still, unpredictable... :-)
I know result strings are not initialized to '' to begin with, which just makes it all so extremely interesting. Especially when creating parsers and import routines this is, of course, extremely powerful. (However, when I create a parser, I try to avoid the use of strings, relying on PChar's and memory mapped files most of the time.)

I'll include Russells version too, compile without debug information and with optimization on. Results should be here shortly...
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12316414
Any prize for last place?

Oh well at least i found out a way of crashing your benchmark tool ... maybe you'll have to change it so that it can accomodate greedy versions like mine ;-)

Best Regards,

Hypoviax
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12316652
ARGL! I HATE BENCHMARKS! The results will show you why...

Start list order (sorted by simple speed check).
 # Name                             Average  Difference       % Tries
 1 Russell                          3569.15           0  143.85    10
 2 Russell (Improved by WA)         3650.28      811291  140.65    10
 3 PierreC                          4635.85    10666960  110.75    10
 4 Workshop Alex (Improved)         5032.18    14630260  102.03    10
 5 Workshop Alex                    5134.19    15650395  100.00    10
 6 PierreC (Improved by WA)         5253.65    16844971   97.73    10
 7 DragonSlayer                     5603.88    20347335   91.62    10
 8 DragonSlayer (Improved by WA)    5674.52    21053751   90.48    10
 9 Madshi                           5763.70    21945494   89.08    10
10 Bart Thomas                      6262.37    26932253   81.98    10
11 Slick812                        10900.03    73308768   47.10    10

Final score:
 # Name                             Average  Difference       % Tries
 1 Russell (Improved by WA)         3791.31           0  138.76   100
 2 Russell                          3822.29     3097952  137.64   100
 3 PierreC                          4775.75    98444720  110.16   100
 4 Workshop Alex (Improved)         5186.11   139480296  101.44   100
 5 Workshop Alex                    5260.95   146964441  100.00   100
 6 PierreC (Improved by WA)         5357.47   156616746   98.20   100
 7 DragonSlayer                     5701.42   191011253   92.27   100
 8 DragonSlayer (Improved by WA)    5743.52   195221475   91.60   100
 9 Madshi                           5930.72   213941574   88.71   100
10 Bart Thomas                      6336.12   254480911   83.03   100
11 Slick812                        10883.25   709193932   48.34   100

Yes, it's true. My solution is apparantly faster than most others. Only PierreC and Russell are faster. This is plain silly! I'm considering searching for a heavy club and hit myself on the head several times because I just cannot understand this increase in performance... Tested it again and again:
 1 Russell took 3698544 Ticks.
 2 Russell (Improved by WA) took 3718778 Ticks.
 3 PierreC took 4776563 Ticks.
 4 PierreC (Improved by WA) took 5146508 Ticks.
 5 Workshop Alex (Improved) took 6918230 Ticks.
 6 Workshop Alex took 6925355 Ticks.
 7 DragonSlayer took 7426829 Ticks.
 8 DragonSlayer (Improved by WA) took 7488393 Ticks.
 9 Madshi took 7568672 Ticks.
10 Bart Thomas took 8017432 Ticks.

But my code has never changed a bit here! It's just a different processor.

The Optimization compiler flag also seems to make a big difference.
Final score with Optimization off:
 # Name                             Average  Difference       % Tries
 1 Russell (Improved by WA)         4158.77           0  151.93   100
 2 Russell                          4216.35     5758455  149.86   100
 3 PierreC                          5337.27   117850425  118.38   100
 4 PierreC (Improved by WA)         5579.99   142121931  113.24   100
 5 DragonSlayer (Improved by WA)    5695.27   153649842  110.94   100
 6 DragonSlayer                     5765.25   160647694  109.60   100
 7 Workshop Alex (Improved)         5912.57   175380255  106.87   100
 8 Madshi                           6059.55   190078066  104.27   100
 9 Workshop Alex                    6318.50   215973239  100.00   100
10 Bart Thomas                      6529.19   237042199   96.77   100
11 Slick812                        11491.45   733268466   54.98   100

Final score with Optimization on:
 # Name                             Average  Difference       % Tries
 1 Russell                          3764.94           0  139.11   100
 2 Russell (Improved by WA)         3838.13     7318794  136.46   100
 3 PierreC                          4780.93   101599271  109.55   100
 4 PierreC (Improved by WA)         5119.02   135407952  102.31   100
 5 Workshop Alex (Improved)         5174.08   140914287  101.22   100
 6 Workshop Alex                    5237.39   147244818  100.00   100
 7 DragonSlayer                     5815.11   205016563   90.07   100
 8 DragonSlayer (Improved by WA)    5891.20   212625894   88.90   100
 9 Madshi                           5923.60   215865879   88.42   100
10 Bart Thomas                      6313.19   254825264   82.96   100
11 Slick812                        10679.23   691429299   49.04   100

Apparantly, my own version gets a lot of speed increase from this optimization flag. So, okay. It could be because the starting string value never changes. So I decide to use a slightly different string value for every new testloop. Solething like this:

  for I := 0 to Pred(MaxCount) do begin
    WriteLn('Run ', I + 1, ':');
    Tmp := IntToStr(I) + AString + IntToStr(I);
    for SkipIndex := Low(SkipCharList) to High(SkipCharList) do begin
      for J := Low(Statistics) to High(Statistics) do begin
        UniqueString(Tmp);
        Statistics[J].Ticks := Statistics[J].Ticks + GetLoopTicks(Statistics[J].StripChars, Tmp, SkipCharList[SkipIndex], Statistics[J].List);
        Statistics[J].Count := Statistics[J].Count + 1;
      end;
    end;
    ...Bla, bla, show score...
  end;

GetLoopTicks is defined like this:

function GetLoopTicks(StripChar: TStripChars; InValue: string; SkipChars: TSkipChars; list: TListArray): Int64;
var
  I: Integer;
begin
  ClearList(List);
  Sleep(0);
  SetPriorityClass(GetCurrentProcess, REALTIME_PRIORITY_CLASS);
  SetThreadPriority(GetCurrentThread, THREAD_PRIORITY_TIME_CRITICAL);
  Result := RDTSC;
  for I := Low(List) to High(List) do begin
    List[I] := StripChar(InValue, SkipChars);
  end;
  Result := RDTSC - Result;
  SetThreadPriority(GetCurrentThread, THREAD_PRIORITY_NORMAL);
  SetPriorityClass(GetCurrentProcess, NORMAL_PRIORITY_CLASS);
  Sleep(0);
  ClearList(List);
end;

And the result is stunning. The winner is: ME!!! :-)
Final score:
 # Name                             Average  Difference       % Tries
 1 Workshop Alex (Improved)         3312.40           0  128.27   100
 2 Russell (Improved by WA)         3875.25    56285376  109.64   100
 3 Russell                          3965.84    65344522  107.14   100
 4 Workshop Alex                    4248.95    93655386  100.00   100
 5 PierreC                          5283.82   197142693   80.41   100
 6 DragonSlayer                     5392.33   207993652   78.80   100
 7 DragonSlayer (Improved by WA)    5456.61   214421020   77.87   100
 8 PierreC (Improved by WA)         5494.30   218189957   77.33   100
 9 Madshi                           5537.84   222544357   76.73   100
10 Bart Thomas                      6078.79   276639063   69.90   100
11 Slick812                         9198.76   588636478   46.19   100

My own improved version is 28% faster than the original... I'm going to become sick of all these weird string optimization thingies... I thought that Russells version, although tricky, would be the fastest but no, it isn't.
The latest benchmark source can be found at http://www.workshop-alex.org/Sources/Strip5.dpr and any bugfixes are welcome. The report is still at http://www.workshop-alex.org/Sources/Report.txt and shows the latest score. Upon analyzing this, I noticed that my original version scores quite well when NO or almost no character is stripped from the string. For a change, I also added http://www.workshop-alex.org/Sources/Strip5.zip to my webserver that holds the Delphi 7 version of the benchmark tool. And yes, it is quite big but that's because I provided every solution it's own list of strings to work with, and it's all defined as modifiable constants. This ZIP file also has the latest report and the original sourcecode.

So yes, it is unpredictable with string routines to easily check which routine is the fastest. The fact that the improved version of my own solution end up number one after multiple tests shows it's just impossible to tell. I think all solutions are very close together. Maybe just divide the points evenly then?... Five experts who provided a solution that are fast enough to compete, thus 500/5 is 100 points each. Since Russell's solution seems to be fastest, he'll have the honor of providing the answer, while others just helped. :-)

Okay?
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12316697
@Hypoviax,
> Any prize for last place?
LOL. Maybe I should reserve 20 points for both you and Slick just for your effords at attempting to make a faster version but failing. :-) Leaves 460 points divided over 5 experts. But it would not be fait since you were supposed to make it faster, not slower! :-P

> Oh well at least i found out a way of crashing your benchmark tool ... maybe you'll have to change it so that it can accomodate greedy versions like mine ;-)
Actually, your trick might crash any application if it's called too often. It shows that optimizing Delphi's string routines could not only increase speed a lot, but also save a lot of memory. At this moment, with all solutions above, the benchmark tool only needs 3 MB of memory. If I add your solution, it actually keeps claiming more and more and more and more and more and more and more and more and more and more and more and more (repeat 'and more' until forever)
Problem is, fixing these kinds of greedy solutions should be done from the inside of those greedy solutions. It just has too much string handling active, thus Delphi keeps caching and caching and caching and caching and caching and caching and caching and caching and caching (repeat 'and caching' until forever)

This challenge has one main purpose and that's discovering how to use Delphi strings in the fastest way possible. And I would almost dare to say that the use of PChar's does help a bit sometimes but never adds a huge increase. However, it does show that it's best to avoid as many string routines as possible.
 
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12317179
Even 5 points - for sportsmanship maybe ? Personally i didn't think my code looked that bad but i guess it was ;-)

0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12317203
It will be interesting then with sorting, how much Delphi can be optimised. (I have a bit of knowledge in that ground at least)

Hypoviax
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12317397
Oh, well... It's interesting to see that the Delphi 7 version runs at comparable speeds ar work as at home:

Final score:
 # Name                             Average  DifferencePerformance Tries
 1 Workshop Alex (Improved)         4403.79       0.00%     127.06%   100
 2 Russell                          4954.04       9.83%     112.94%   100
 3 Russell (Improved by WA)         4992.93      10.53%     112.06%   100
 4 Workshop Alex                    5595.29      21.29%     100.00%   100
 5 PierreC (Improved by WA)         5638.83      22.07%      99.23%   100
 6 PierreC                          5685.93      22.91%      98.41%   100
 7 DragonSlayer (Improved by WA)    5822.13      25.35%      96.10%   100
 8 DragonSlayer                     5927.32      27.23%      94.40%   100
 9 Madshi                           6686.58      40.80%      83.68%   100
10 Bart Thomas                      6726.67      41.51%      83.18%   100
11 Slick812                        12241.09     140.07%      45.71%   100

My conclusion is: But Delphi 7 if you need fast string handling because Borland clearly improved it's string-handling routines. But even after being compiled with Delphi 5, the results are interesting:
Final score:
 # Name                             Average  DifferencePerformance Tries
 1 Russell                          3864.06       0.00%     135.15%   100
 2 Russell (Improved by WA)         3866.22       0.04%     135.07%   100
 3 Workshop Alex (Improved)         4036.27       3.30%     129.38%   100
 4 PierreC (Improved by WA)         4827.00      18.44%     108.19%   100
 5 PierreC                          5023.55      22.20%     103.96%   100
 6 Workshop Alex                    5222.27      26.01%     100.00%   100
 7 DragonSlayer (Improved by WA)    5239.67      26.34%      99.67%   100
 8 Bart Thomas                      5305.68      27.61%      98.43%   100
 9 DragonSlayer                     5312.02      27.73%      98.31%   100
10 Madshi                           6319.52      47.02%      82.64%   100
11 Slick812                        11653.89     149.17%      44.81%   100

I am amazed too to see that most solutions still seem to perform slower instead of faster. Only PierreC and Russell perform faster. This is getting too weird... If someone sees the flaw in my code, please let me know since this is really starting to get me worried about my own sanity... :-)
But okay, adding a few more adjustions to the code, like a cleanup method for the list that actually works correctly! (@#$%, I forgot to pass it as a var parameter!) And added some code that actually does something with the data in the list. (Writing it to textfiles.)

Another discovery I made is also funny. If the string passed to the StripChar() function is a string constant, my improved version and all other versions just become a lot slower! The use of string constants in this case to call the benchmark is therefore slowing it down. Under normal circumstances users won't use this function for simple string constant manipulations. It's more likely that you read data from some file and use that data instead. Thus it's better that I use a variable instead of a string constant for my benchmark.

After a bit more tweaking, I got at this Final score:
 # Name                           Average           Difference   Performance  Tries
 1 Workshop Alex (Improved)            4.085.117         0,00%       112,40%    100
 2 Russell                             5.441.655        15,63%        59,45%    100
 3 Russell (Improved by WA)            5.465.397        15,91%        58,76%    100
 4 DragonSlayer (Improved by WA)       5.531.524        16,67%        56,86%    100
 5 Bart Thomas                         5.643.126        17,96%        53,76%    100
 6 DragonSlayer                        6.001.526        22,09%        44,58%    100
 7 PierreC (Improved by WA)            6.439.634        27,14%        34,74%    100
 8 PierreC                             6.520.784        28,07%        33,07%    100
 9 Madshi                              7.816.092        43,00%        11,01%    100
10 Workshop Alex                       8.676.903        52,92%         0,00%    100
11 Slick812                           16.554.810       143,71%       -47,59%    100

I managed to double my own routine speed... :-) And even suprising, PierreCs solution seems a bit slow compared to the others. But Russell still seems to end up on top almost always.

But why is my own version this much faster???
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12317420
@Hypoviax, the minimum I must give when splitting points is 20 points. Thus I can't give less. I can give none, though. :-P Besides, if I reward you, I also have to reward Slick for providing a slower version...

Now, a simple request. Can someone please download the source for the latest version at http://www.workshop-alex.org/Sources/Strip5.dpr and compile it, then run it? It will create a simple textfile in the same folder as the executable which contains the scores. I'm interested if someone else is getting different results than mine... It's annoying that I see my own solution as the fastest. (Compile with optimizations on! And writeable constants on.)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12317821
Okay, http://www.workshop-alex.org/Sources/Strip6.dpr (Yes, an update!) brings the results a bit more to normal. Now I'm filling the list with data and this data is used to calculate the new value to be added to the list. It then writes the list to file so there's some further processing for the list within Delphi. (Just to make the benchmark look more like a normal application.) Even better, every list get's its own, unique value, based on it's index number and the string constant. Thus I will be using 2500 unique strings. Even nicer, the strings will be unique for every test, with an average length between 62 and 66 characters.

This should provide the most reliable benchmark result in my opinion. Final score:
 # Name                           Average          Performance       Compare  Tries
 1 Russell (Improved by WA)            4.782.801        97,71%         0,00%    100
 2 Russell                             4.811.272        96,54%         1,17%    100
 3 PierreC (Improved by WA)            6.176.546        53,10%        44,61%    100
 4 PierreC                             6.366.978        48,52%        49,19%    100
 5 Workshop Alex (Improved)            7.670.432        23,28%        74,43%    100
 6 DragonSlayer (Improved by WA)       7.942.866        19,05%        78,66%    100
 7 Bart Thomas                         7.969.658        18,65%        79,06%    100
 8 DragonSlayer                        8.015.603        17,97%        79,74%    100
 9 Madshi                              8.905.760         6,18%        91,53%    100
10 Workshop Alex                       9.456.243         0,00%        97,71%    100
11 Slick812                           18.798.460       -49,70%       147,41%    100


Russell is a clear winner here, with his improvement on the set. PierreC is a good second. Bart Thomas and DragonSlayer share the 3rd/4th place. Madshi makes it to the 5th place. Slick812 on the sixth place. Hypoviax is seventh. :-)

However, if I use Madshi's original version for this benchmark then his KillChars version will end up even above Russells! Not much, though.
 # Name                           Average          Performance       Compare  Tries
 1 Madshi                              4.579.685       106,21%         0,00%    100
 2 Russell                             4.763.913        98,23%         7,97%    100
...
(For those who are interested, Strip6 will test Madshi's KillChars version if you use the commandline parameter /Madshi when you run the application.)

Everyone in the top-5 have done a good bob here, though. Time to award points:

Suggestion:
Russell - 120 points. (Winner!)
PierreC - 110 points.
Bart Thomas - 90 points
DragonSlayer - 90 points.
Madshi - 90 points.

I'll wait until tonight (9 hours from now) so if no one disagrees and no new solutions are added, this will be final.

Russell showed that part of the speed improvement could be made by not using a set but by using a very simple trick. And it did improve the speed quite drastically. You might actually want to use his improvement in your code, Madshi! ;-)
Russell is also the top performer with all 10 test sets. He even performs faster than the original version if the set [ #0..#255 ] is used, in which the original code actually beats all others.

Most solutions seem to have the most trouble with the [ 'a', 'e', 'i', 'o', 'u', 'y' ] testset. But no one has much problems stripping just spaces.
Slick has the most problems if many characters have to be skipped. He performs okay well if only one or two characters are stripped and beats Madshi when no characters must be stripped! (Actually, when nothing is stripped, only DragonSlayer is slower than Madshi.)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12321839
Okay, case closed, scores awarded. :-) Well done, experts, and I think I can safely assume we all learned from this. Especially Russells trick was very interesting... :-)
0
 
LVL 20

Expert Comment

by:Madshi
ID: 12322033
Will check Russell's trick out, thanks for the idea...    :-)
0
 
LVL 26

Expert Comment

by:Russell Libby
ID: 12322220
First, thanks for the points, very much appreciated...

Regarding the set handling ...

All I did was manually code what the BT instruction does. The problem with the BT instruction (or so I have read) is that it is faster to unroll the check by hand, and thus cut down on the number of cycles by using simple (1 cycle count) instructions; eg - xor, mov, shr, and add. It would appear to be true I guess ;-)

Kind regards to all,
Russell

0
 
LVL 14

Expert Comment

by:DragonSlayer
ID: 12323475
Hmm... I learnt something new about set manipulation ;-)
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12323764
Well, Russell, you've earned them! In some tests, your version was indeed twice as fast as the original version. But so was the improved version that I created, for some weird reason. Your version was almost as fast as Madshi's Killchars version so I guess Madshi should be able to improve his KillChars version quite a lot. I actually wonder if this Killchars version would become a lot faster if he implements your set-handling routines.

Doing the benchmarking for this "simple" quest has shown me a lot more insight in the string handling stuff. It showed, for example, that Delphi can be quite fast at times when handling strings. Or extremely slow and memory-consuming as one post has shown... ;-) And apparantly speed doesn't improve much if you convert a string to PChar if all you're going to do is read characters. (As shown again by my improved version.)

Still, if someone sees a flaw in my benchmark code, please let me know. :-)

I'll post a new challenge soon, (I hope) concerning string handling and this time also file-handling. All I have to do is set up a fair benchmark set and a set of rules. And of course set up exact specifications.
0
 
LVL 5

Expert Comment

by:Hypoviax
ID: 12324549
I'll see you all in my sort challenge early novemeber i hope. Thanks for the great challenge it has been a good learning experience for myself

Best Regards,

Hypoviax
0
 
LVL 14

Expert Comment

by:Pierre Cornelius
ID: 12326452
Thanks Alex and all others. Had some fun. Very educational too.

Just some closing comments and results.

I downloaded the Strip6.dpr and compiled it as per your request. Here are the results from my Intel P4 1.8GHz:
Start list order (sorted by simple speed check).
 # Name                           Average          Performance       Compare  Tries
 1 Russell (Improved by WA)            5,077,079        95.18%         0.00%     10
 2 Russell                             5,087,530        94.78%         0.40%     10
 3 PierreC (Improved by WA)            6,475,680        53.03%        42.15%     10
 4 PierreC                             6,755,954        46.68%        48.50%     10
 5 Workshop Alex (Improved)            7,858,883        26.09%        69.09%     10
 6 Bart Thomas                         8,171,415        21.27%        73.91%     10
 7 DragonSlayer                        8,263,905        19.91%        75.27%     10
 8 DragonSlayer (Improved by WA)       8,274,404        19.76%        75.42%     10
 9 Madshi                              9,030,588         9.73%        85.45%     10
10 Workshop Alex                       9,909,462         0.00%        95.18%     10
11 Slick812                           23,113,448       -57.13%       152.31%     10

--------------------------------------------------------------------------------

Final score:
 # Name                           Average          Performance       Compare  Tries
 1 Russell                             4,958,392        96.79%         0.00%    100
 2 Russell (Improved by WA)            4,969,538        96.35%         0.44%    100
 3 PierreC (Improved by WA)            6,268,743        55.66%        41.14%    100
 4 PierreC                             6,625,243        47.28%        49.51%    100
 5 Workshop Alex (Improved)            8,014,472        21.75%        75.04%    100
 6 Bart Thomas                         8,277,888        17.88%        78.92%    100
 7 DragonSlayer (Improved by WA)       8,305,027        17.49%        79.30%    100
 8 DragonSlayer                        8,407,969        16.05%        80.74%    100
 9 Madshi                              9,056,308         7.75%        89.05%    100
10 Workshop Alex                       9,757,821         0.00%        96.79%    100
11 Slick812                           22,574,350       -56.77%       153.57%    100

--------------------------------------------------------------------------------


A slight suggestion to your benchmark. Your tickcount tested not only the function speed, but also assigning it to "Value" in your GetTicks function and "List[i]" in your GetLoopTicks function. I changed the code as follows:

function GetLoopTicks( StripChar: TStripChars; const SkipChars: TSkipChars; var list: TListArray ): Int64;
var
  I: Integer;
begin
...
    for I := Low( List ) to High( List ) do begin
      //List[ I ] := StripChar( List[ I ], SkipChars ); //*******commented out by PC
      StripChar( List[ I ], SkipChars );  //*******Added by PC
    end;
    Result := RDTSC - Result;
    for I := Low( List ) to High( List ) do begin    //*******Added by PC
      List[ I ] := StripChar( List[ I ], SkipChars ); //*******Added by PC
    end;            //*******Added by PC
...
end;

function GetTicks( StripChar: TStripChars; InValue: string; SkipChars: TSkipChars; var Value: string ): Int64;
begin
...
  Result := RDTSC;
  //Value := StripChar( InValue, SkipChars );   //*******Commented out by PC
  StripChar( InValue, SkipChars ); //*******Added by PC
  Result := RDTSC - Result;
  Value := StripChar( InValue, SkipChars ); //*******Added by PC
...
end;


Wow! The effect is quite noticeable. Look at Russel's performance >300% as opposed to 96% before the change.
After the above change to your code I got the following results:
Start list order (sorted by simple speed check).
 # Name                           Average          Performance       Compare  Tries
 1 Russell (Improved by WA)            2,594,031       242.85%         0.00%     10
 2 Russell                             2,649,251       235.70%         7.15%     10
 3 PierreC (Improved by WA)            4,019,378       121.27%       121.58%     10
 4 PierreC                             4,377,357       103.17%       139.68%     10
 5 DragonSlayer                        5,453,863        63.07%       179.78%     10
 6 Bart Thomas                         5,460,831        62.86%       179.99%     10
 7 DragonSlayer (Improved by WA)       5,565,202        59.81%       183.04%     10
 8 Workshop Alex (Improved)            6,285,944        41.48%       201.36%     10
 9 Madshi                              8,522,940         4.35%       238.50%     10
10 Workshop Alex                       8,893,608         0.00%       242.85%     10
11 Slick812                           22,424,956       -60.34%       303.19%     10

--------------------------------------------------------------------------------

Final score:
 # Name                           Average          Performance       Compare  Tries
 1 Russell (Improved by WA)            2,611,947       331.43%         0.00%    100
 2 Russell                             2,720,032       314.29%        17.14%    100
 3 PierreC (Improved by WA)            4,048,922       178.31%       153.12%    100
 4 PierreC                             4,357,385       158.61%       172.82%    100
 5 Bart Thomas                         5,287,887       113.10%       218.33%    100
 6 DragonSlayer (Improved by WA)       5,352,665       110.53%       220.90%    100
 7 DragonSlayer                        5,391,294       109.02%       222.41%    100
 8 Workshop Alex (Improved)            6,259,183        80.04%       251.40%    100
 9 Madshi                             10,121,742        11.33%       320.10%    100
10 Workshop Alex                      11,268,744         0.00%       331.43%    100
11 Slick812                           22,648,275       -50.24%       381.68%    100

--------------------------------------------------------------------------------

Thanks again everyone but especially Alex. I'm sure we all learnt a lot here.

Looking forward to future challenges.

Regards
Pierre Cornelius
0
 
LVL 17

Author Comment

by:Wim ten Brink
ID: 12328699
Yes, I know that if you don't assign the function result to some variable, it will speed up considerably. But part of the benchmark was to simulate a natural environment as much as possible, which is why I created a huge array of strings so every function call would fill a different variable.
What is funny though, in what you're showing is this: If you assign the function result to a variable, the difference between Russells solution and the original one is about 7 million processor ticks. Nearly twice as fast. If you don't assign the function result then Russells solution becomes a lot faster and the original one a bit slower. About 9 million ticks, over three times faster than the original. Interesting that discarding the result will speed up some functions while actually slowing down others! (Although, only when you repeat the test quite often. The first quick-test shows only a minor difference...
0
 

Expert Comment

by:pinkky4real
ID: 23366491
It is given a chess board with N*N squares. On the board there is a dice with the dimensions
equal with one square on the board and occupies perfectly the surface of a square. On each side of
the dice there is an integer value between 1 and 100.
The dice can move by rotating itself with 90º around one of it`s edge on the board. With this
move it can go in the upper, lower, left and right square. With more moves, the dice can go to each
square on the board. The cost of a path is equal to the sum of the values on the side on the board,
including the first and the last position.
Giving you the dimension of the board N, the six values on the sides of the cube, the starting
position and the final position, find a minimum path from the starting position to the finish one. You
must save in a file the length of the minimum path and the path itself.
Input data: file cube.in
N // board dimension
face back left right up down // the 6 values on the sides of the dice
x1 y1 x2 y2 // the positions of the start and finish squares, with 1 to N numbering
Output data: file cube.out
C // the cost of the minimum path
L // the length of the path, as number of moves of the dice
x1 y1
x2 y2
.....
xL yL // the positions of the squares in the path
Observations: At the start, the cube is positioned with the face side in the positive direction of
Oy axis, the right side on the positive direction of Ox and the top on the positive direction of
Oz.
All the coordinates start from 1.
Limits:
1<=N<=100
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Objective: - This article will help user in how to convert their numeric value become words. How to use 1. You can copy this code in your Unit as function 2. than you can perform your function by type this code The Code   (CODE) The Im…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
This video gives you a great overview about bandwidth monitoring with SNMP and WMI with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're looking for how to monitor bandwidth using netflow or packet s…

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now