Fast string inversion

[Jacques Oberto]

I need to invert a bunch of very long strings 'abcdef' -> 'fedcba'
I tried this but it's way too sloooow:

for i := Length(S1) downto 1 do S2 := S2 + S1[i]

Does anyone have a fast way maybe asm?
Thanks,

Jacques

[Ignacio Vazquez]

"Jacques Oberto" <j...@N.O.S.P.A.M> wrote in message
3f86e02a$1...@newsgroups.borland.com...

> for i := Length(S1) downto 1 do S2 := S2 + S1[i]
>
> Does anyone have a fast way maybe asm?

var
i, Len: Integer;
S1, S2: String;
begin
...
Len:=Length(S1);
SetLength(S2, Len);
for i:=1 to Len do
S2[i]:=S1[Len-i+1];
...
end;

Cheers,
Ignacio

--
No, don't send me e-mail directly. No, just don't.

[Harry Barclay]

Jacques Oberto wrote:
> I need to invert a bunch of very long strings 'abcdef' -> 'fedcba'
> I tried this but it's way too sloooow:

> Does anyone have a fast way maybe asm?
> Thanks,
>
> Jacques
>
>

In the StrUtils Unit is a ReverseString function which seems reasonably
fast to me. I think this was new in Version 6 although I am not sure. If
you don't have that function then you might try the faststrings library
at http://www.droopyeyes.com/

Harry

[Craig Stuntz [TeamB]]

Jacques Oberto wrote:

> Does anyone have a fast way maybe asm?

Call ReverseString from StrUtils.

-Craig

--
Craig Stuntz [TeamB] . Vertex Systems Corp. . Columbus, OH
Delphi/InterBase Weblog : http://delphi.weblogs.com
Useful articles about InterBase and Delphi development:
http://delphi.weblogs.com/articles

[Luis Dib]

Hope this will help. Both use the same algorithm.

Luis

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

procedure InvertStr(var S: String);
var
I: Integer;
C: Char;
Len: Integer;
begin
Len := Length(S); // More efficient in a variable
for I := 1 to Len div 2 do
begin
C := S[Len - I + 1];
S[Len - I + 1] := S[I];
S[I] := C;
end;
end;

procedure InvertStrAsm(var S: String);
var
Len: Integer;
P: Pointer;
begin
Len := Length(S);
P := @S[1];
asm
push edi
push esi // save edi and esi
mov ecx, Len
shr ecx, 1 // ecx = Len div 2
mov esi, P // esi = @S[1]
mov edi, P
add edi, Len
dec edi // edi = @S[Len]
@1:
mov al, byte ptr [esi] // al <- byte at [esi]
mov dl, [edi] // dl <- byte at [edi]
mov byte ptr [esi], dl // byte at [esi] <- bl
mov byte ptr [edi], al // byte at [edi] <- al
inc esi // esi <- esi + 1
dec edi // edi <- edi + 1
loopnz @1 // dec ecx; if ecx <> 0, jump to @1
pop esi
pop edi // restore edi and esi
end;
end;

"Jacques Oberto" <j...@N.O.S.P.A.M> wrote in message

news:3f86e02a$1...@newsgroups.borland.com...

[Craig Stuntz [TeamB]]

Luis Dib wrote:

> Len := Length(S); // More efficient in a variable

You save a little something by avoiding the function call, but note
that Length with an AnsiString is *much* more efficient than a length
function is with a null-terminated string (since Delphi stores the
length at the start of an AnsiString). Hence, avoiding calls to length
is not nearly as important in Delphi as it is in many languages.

[Luis Dib]

By assigning Length(S) to a variable, a single assembly instruction is used
on its references. Using Length(S) directly uses about 5 instructions. I
agree with you
that probably overall the improvement is minimal. But there is some
improvement.
Besides, AFAIK, when there is a call to a function the CPU lookahead buffer
is
discarded, further reducing the efficiency of a call.

Anyway, here is a pure Pascal version that is as far as I can tell nearly as
efficient as
a pure assembly one:

procedure InvertStr2(var S: String);

var
I: Integer;
C: Char;

P1: PChar;
P2: PChar;
begin
P1 := @S[1];
P2 := @S[Length(S)];
for I := 1 to Length(S) div 2 do
begin
C := P2^;
P2^ := P1^;
P1^ := C;
Inc(P1);
Dec(P2);
end;
end;

"Craig Stuntz [TeamB]" <cst...@nospam.please [a.k.a. vertexsoftware.com]>
wrote in message news:3f86f543$1...@newsgroups.borland.com...

[Craig Stuntz [TeamB]]

Luis Dib wrote:

> By assigning Length(S) to a variable, a single assembly instruction
> is used on its references. Using Length(S) directly uses about 5
> instructions.

Er, that's exactly what I said in my post. You save a little on the
function call, but not much. Compare this with the code for getting
the length of a null-terminated string, OTOH.

-Craig

--
Craig Stuntz [TeamB] . Vertex Systems Corp. . Columbus, OH
Delphi/InterBase Weblog : http://delphi.weblogs.com

InterBase in Multi-tier World -- Use multiple RDMs, IB features in
your appserver: http://delphi.weblogs.com/stories/storyReader$195

[bob]

Don't know how you are using the reversed string, but if you only need
portions of it at a time:

function getReverseSubStr (S : string; first, last : integer) : string;
// first, last refer to the reversed string
var i, theEnd : integer;
subStr : string;
begin
theEnd := length(s);
setLength (subStr, last-first+1);
for i := 1 to last-first+1 do subStr[i] := S[theEnd - first + 1 - i];
result := substr;
end;

--
bob mackey
myName = 'bobsnews';
myISP = 'comcast.net';
myaddress := myName + '@' + myISP;

[Jacques Oberto]

I did some benchmarking with all the presented routines and the
ASM InvertStrAsm is the fastest so far; about 2.5x faster than
Delphi's ReverseString.
Many thanks to all for the responses.

Jacques