Recent

Author Topic: optimization will generate wrong result  (Read 1126 times)

powerpcer

  • Full Member
  • ***
  • Posts: 100
optimization will generate wrong result
« on: May 11, 2021, 06:26:08 pm »
for function below, if i change the optimization to -O2, the result will be wrong 11, the correct one is 18.
i test this code on win10 x64
Code: Pascal  [Select][+][-]
  1.   function edit_distance_bit(str1,str2:string):integer;
  2.         var
  3.           Peq:array[0..255] of Uint64;
  4.                 Pv, Eq, Xv, Xh, Ph, Mh, Mv, ONE:Uint64;
  5.                 i,j,m,n,Score:integer;
  6.                 p1,p2:pbyte;
  7.                 s:string;
  8.   begin
  9.     if (length(str1) < length(str2)) then
  10.     begin
  11.       p1:=@str2[1];
  12.                 p2:=@str1[1];
  13.       m := length(str2);
  14.       n := length(str1);
  15.     end
  16.                 else
  17.                 begin
  18.       p1:=@str1[1];
  19.                 p2:=@str2[1];
  20.       m := length(str1);
  21.       n := length(str2);
  22.                 end;
  23.  
  24.     ONE := 1;
  25.                 fillbyte(Peq,0,sizeof(Peq));
  26.     Mv  := 0;
  27.     Score := m;
  28.  
  29.     for i := 0 to m do
  30.                 begin
  31.         Peq[p1[i]] :=Peq[p1[i]] or ONE shl i;
  32.         Pv :=Pv or (ONE shl i);
  33.     end;
  34.     for j := 0 to n do
  35.                 begin
  36.         Eq := Peq[p2[j]];
  37.         Xv := Eq or Mv;
  38.         Xh := (((Eq and Pv) + Pv) xor Pv) or Eq;
  39.         Ph := Mv or (not (Xh or Pv));
  40.         Mh := Pv and Xh;
  41.         if (Ph and (ONE shl (m - 1)))<>0 then
  42.                                         inc(Score)
  43.         else
  44.                                 if (Mh and (ONE shl (m - 1)))<>0 then
  45.                                         dec(Score);
  46.         Ph :=Ph shl ONE;
  47.         Pv := (Mh shl ONE) or (not (Xv or Ph));
  48.         Mv := Ph and Xv;
  49.     end;
  50.     result := Score;
  51.   end;
with testing code
Code: Pascal  [Select][+][-]
  1. j:=edit_distance_bit('agtcaaaagtcagtcagtcagtcagtcacagtcagaaggcatccaaccga','ccgttagtcagaaacagtcagtcagtcagtcagtccagtcttaggcccgga');

AlexTP

  • Hero Member
  • *****
  • Posts: 2365
    • UVviewsoft
Re: optimization will generate wrong result
« Reply #1 on: May 11, 2021, 06:31:05 pm »
FPC 3.2 fixes; Linux x64.

-O0: 14
-O1: 14
-O2: 16

bytebites

  • Hero Member
  • *****
  • Posts: 625
Re: optimization will generate wrong result
« Reply #2 on: May 11, 2021, 06:42:33 pm »
Code: Pascal  [Select][+][-]
  1. fillbyte(Peq,0,sizeof(Peq));

Your code is wrong. The second argument of fillchar is count, the last is value.

Code: Pascal  [Select][+][-]
  1. Pv :=Pv or (ONE shl i);

Pv is not initialised.

powerpcer

  • Full Member
  • ***
  • Posts: 100
Re: optimization will generate wrong result
« Reply #3 on: May 12, 2021, 03:13:23 am »
thanks,
after fixed, -O3 optimize faster little, from 40ms to 30ms
« Last Edit: May 12, 2021, 03:18:01 am by powerpcer »

 

TinyPortal © 2005-2018