Optimizie code - Githubissues

User4martin commented 1 year ago

Various very very small speed improvements.

Running 5 repeats for each benchmark. Use -c <n> to change

                                                          Match count  # Orig       # RegNext inlined # FindInCharClass
========================================================================================================================
                                                  /Twain/ :      2388  #     37 ms  #     40 ms       #     37 ms 
                                              /(?i)Twain/ :      2657  #     56 ms  #     56 ms       #     56 ms 
                                             /[a-z]shing/ :      1877  #    250 ms  #    240 ms       #    243 ms 
                             /Huck[a-zA-Z]+|Saw[a-zA-Z]+/ :       396  #     37 ms  #     34 ms       #     37 ms 
                                                      /./ :  18905427  #    425 ms  #    425 ms       #    425 ms 
                                                    /(.)/ :  18905427  #    693 ms  #    693 ms       #    693 ms 
                                                      /e/ :   1781425  #     81 ms  #     81 ms       #     81 ms 
                                                    /(e)/ :   1781425  #    106 ms  #    103 ms       #    106 ms 
                                           /(?s).{1,45} / :    475715  #     37 ms  #     37 ms       #     37 ms 
                                         /(?s)\G.{1,45} / :     10616  #    165 ms  #    168 ms       #    168 ms 
                                         /\G(?s).{1,45} / :     10616  #     18 ms  #     15 ms       #     15 ms 
                                          /(?s).{1,45}? / :   3241534  #    156 ms  #    165 ms       #    165 ms 
                                        /(?s)\G.{1,45}? / :     69431  #    165 ms  #    168 ms       #    168 ms 
                                        /\G(?s).{1,45}? / :     69431  #     15 ms  #     21 ms       #     18 ms 
                                              /\b\w+nn\b/ :       359  #    243 ms  #    250 ms       #    253 ms 
                                       /[a-q][^u-z]{13}x/ :      4929  #    684 ms  #    697 ms       #    690 ms 
                            /Tom|Sawyer|Huckleberry|Finn/ :      3015  #     37 ms  #     37 ms       #     37 ms 
                        /(?i)Tom|Sawyer|Huckleberry|Finn/ :      4820  #    196 ms  #    190 ms       #    184 ms 
                    /.{0,2}(Tom|Sawyer|Huckleberry|Finn)/ :      3015  #   2665 ms  #   2578 ms       #   2575 ms 
                    /.{2,4}(Tom|Sawyer|Huckleberry|Finn)/ :      2220  #   2890 ms  #   2806 ms       #   2784 ms 
                      /Tom.{10,25}river|river.{10,25}Tom/ :         2  #     56 ms  #     56 ms       #     56 ms 
                                           /[a-zA-Z]+ing/ :     95863  #    609 ms  #    628 ms       #    625 ms 
                                  /\s[a-zA-Z]{0,12}ing\s/ :     67810  #    268 ms  #    271 ms       #    272 ms 
                          /([A-Za-z]awyer|[A-Za-z]inn)\s/ :       313  #    640 ms  #    615 ms       #    631 ms 
                              /["'][^"']{0,30}[?!\.]["']/ :      9857  #     78 ms  #     78 ms       #     78 ms 
                                /Tom(.{3,3}|.{5,5})*Finn/ :        11  #   3190 ms  #   3193 ms       #   3162 ms 
                                    /Tom(...|.....)*Finn/ :        11  #   1700 ms  #   1634 ms       #   1618 ms 
                                   /Tom(...|.....)*?Finn/ :        11  #   1640 ms  #   1584 ms       #   1587 ms 
                      /Tom((...|.....){2,9}\s){1,5}?Finn/ :        11  #   4559 ms  #   4237 ms       #   4231 ms 
                      /Tom((...|.....){2,9}?\s){1,5}Finn/ :        11  #   4353 ms  #   4290 ms       #   4300 ms 
                                        /\G(?is).(?=.*$)/ :  20045118  #    931 ms  #    971 ms       #    968 ms 
                                /\G(?is).(?=(.){1,5}?$)?/ :  20045118  #   3603 ms  #   3603 ms       #   3597 ms 
                                       /\G(?is).(?=.*+$)/ :  20045118  #    956 ms  #    921 ms       #    921 ms 
                /\G(?is).{10,10}(?=(e|y|on|fin|.){0,20})/ :   2004511  #   2378 ms  #   2090 ms       #   2100 ms 
              /\G(?is).{10,10}(?=(?>e|y|on|fin|.){0,20})/ :   2004511  #   2378 ms  #   2090 ms       #   2096 ms 
                                          /Tom(?!.*Finn)/ :      2441  #     34 ms  #     34 ms       #     37 ms 
     /(?i)(?>[aeoui][bcdfghjklmnpqrstvwxyz \r\n]*){1,40}/ :    579843  #    622 ms  #    615 ms       #    609 ms 
Total:                                                                 #  36965 ms  #  35731 ms       #  35675 ms

Off topic to the pull request.

I started an experimental change https://github.com/User4martin/TRegExpr/commit/a09083f90301449bda27ad7195a835440cc3a06e

If you have /[02468]/, it may sometimes be faster to first check the lowest and highest, before iterating the entire list.

But

if the list has to few elements, then the extra compares for the bounds add more cost than savings.
if the list isn't very dense /[\n0aAzZ]/ then the bounds include almost everything, and don't add benefit.

I can't yet tell if the changes provide real benefit. The benchmark doesn't have much ranges. One of my real apps, which runs for about 1 minute appears to save 0.2 or maybe 0.3 seconds => however that may be wishful thinking, as the jitter in the timing is bigger that that (and given the time it takes, I have only very limited sample runs...)

There may be potential, if...

[AB\dCDEF] would join the 2 OpKind_Char into one
if meta classes had known ranges ['\d] where ' may have an ordinal very close to 0-9. Therefore the entire [] could start with a OpKind_MinMaxGuard, that would give the min/max for entering the group at all. (Again depends on the resulting density)

But for now, it's just experimental.

Alexey-T commented 1 year ago

Next := scan + PRENextOff(AlignToPtr(scan + 1))^; // inlined regNext;

that is reading badly. can you add functiion with inline, which can replace regNext?

Alexey-T commented 1 year ago

FindInCharClass, small optimizations is OK.

User4martin commented 1 year ago

Next := scan + PRENextOff(AlignToPtr(scan + 1))^; // inlined regNext;

that is reading badly. can you add functiion with inline, which can replace regNext?

I can... But I am doubtful about it.

Inlining is conditional on a define.
Even if the define is set, at least for FPC inlining is at the compilers good will (the compiler may not, either by user settings, or by its own decision)
Similar code pre-exists as not-inlined => that is not just regNext, but any access to any value in the stream

e.g.

      OP_EXACTLY_CI:
        begin
          opnd := scan + REOpSz + RENextOffSz; // OPERAND
          Len := PLongInt(opnd)^;

PLongInt doesn't even read PReDataLength as for example PReOpLookBehindOptions.

All access to the program is done directly. RegNext is special during compile. Because in the first pass it needs to act as dummy.

And last, not least (though this one I am not sure about): I think that (if I find the time in the long run) it will be removed for half the Opcodes.
Many opcodes don't have data (OP_ANYSPACE, OP_ANY, ....)
Those that do have data, can then increase the value of next as they need (if they are of fixed len, they still don't need a next field).
If at the end of a branch/loop a different next is needed, then an OP_GOTO can do that.
For the big question: Is it worth it? Don't know, only experiment will show. It reduces the size, so more data fits into a cache line of the CPU. It removes some calculation from the loop. It could gain some speed. It could..., or not.
--- Though this last item, is "in the long run, someday maybe". Hence on its own it isn't a reason against any change now.

IMHO the important bit is the 3rd one: None of the other code is outsourced to functions.

Alexey-T commented 1 year ago

why we cannot make new func

function regNextInlined(scan: ...): ...; {$ifdef InlineFuncs} inline; {$endif}
begin
  Result := scan + PRENextOff(AlignToPtr(scan + 1))^;
end;

and use it in proposed places? it is the same as your code but readable.

Alexey-T commented 1 year ago

also, your change (with new func or not) changes the pointer, even in pass-1. before, pointer wasn't changed in pass-1. is it OK?

User4martin commented 1 year ago

why we cannot make new func

As I said, we can. I simply stated my reasons for not doing it in first. If you still think it's better to have it => no problem

also, your change (with new func or not) changes the pointer,

Where?

Alexey-T commented 1 year ago

Where?

sorry, my mistake.

User4martin commented 1 year ago

However I did miss something

  if offset = 0 then
    Result := nil

which is used in MatchPrim while scan <> nil do Error(reeMatchPrimCorruptedPointers);

But, IMHO pointless: If the mem is corrupted, it has a 1 in 256 chance of being a zero byte.

We can add a new define {$DEFINE WITH_ASSERTS} And then check for 0, and for the new value being in the Program (regCodeSize).

But IMHO there is no point to run this by default. So I would remove the still existing remains of that check, and put them in ifdef.

User4martin commented 1 year ago

sorry about the indentation.

I keep synchronizing 2 copies of the file, and I can't compare space-changes, because there are thinks like trailing spaces that don't exist in both copies.

User4martin commented 1 year ago

Merged? I am confused now, I though I was still changing the code to an inlined function?

Alexey-T commented 1 year ago

i merged because I thought it's ready fix. please fix more if needed.

Alexey-T commented 1 year ago

with regNext(), result can be Nil
with inlined, result is always <>Nil

change is needed here?

Alexey-T commented 1 year ago

so

            repeat
              FillFirstCharSet(scan + REOpSz + RENextOffSz);
              scan := scan + PRENextOff(AlignToPtr(scan + 1))^; // inlined regNext(scan);
            until (scan = nil) or (PREOp(scan)^ <> OP_BRANCH);

will run longer than before, in pass-1, right? scan = nil will not be true.

it means the inlined-func, as i suggested, is better?

Alexey-T commented 1 year ago

Martin, I made regNextInlined. but feel free to propose fix again over current code. but patch should not slowdown the pass-1 as before.

User4martin commented 1 year ago

Well, its fine as it is. I was looking at the inlined function, as you preferred it.

About the = nil check.

It cannot happen in a real run. Only if memory is corrupted, and then it is likely to be <> nil anyway.

But I could/would place assert code in (with more checks that just =nil).

Do you prefer

actual assert() (toggled by -Sa)
{$IFDEF WITH_REGEX_ASSERT}

What is the existing {$DEFINE USE_ASSERTS} for? It does not seem to be used at all?

repeat FillFirstCharSet

will run longer than before, in pass-1, right? scan = nil will not be true.

The repeat you quoted is actually inside FillFirstCharSet.

The call to FillFirstCharSet is from CompileRegExpr but only after both passes have finished. (line 3165)

All other invocations of FillFirstCharSet are recursive.

So yes, that is safe.

User4martin commented 1 year ago

Martin, I made regNextInlined

Ok, things moving to fast. I would have done it myself. But I can barely finish one reply before the next :)

User4martin commented 1 year ago

I made regNextInlined

Ok, but the entire point was to remove

if p = @regDummy then

The inlined version is never called in the first pass.

It could have an

  assert(fSecondPass); // fSecondPass will also be true in MatchPrim.

User4martin commented 1 year ago

I'll do a new pull request.

Just let me know

Do you prefer

actual assert() (toggled by -Sa) {$IFDEF WITH_REGEX_ASSERT}

What is the existing {$DEFINE USE_ASSERTS} for? It does not seem to be used at all?

Alexey-T commented 1 year ago

changed regNextInlined. OK now?

What is the existing {$DEFINE USE_ASSERTS} for? It does not seem to be used at all?

IDK, seems the leftover from old authors.

User4martin commented 1 year ago

changed regNextInlined. OK now?

Yes.

Though, as I said, I strongly propose to move the if offset = 0 then into an IFDEF.

For fpc this works

{$IFDEF FPC}{$IFOPT C+} {$DEFINE UseAsserts} {$ENDIF}{$ENDIF} // Only if compile with -Sa

Not sure how to change that for Delphi?

Also, maybe better rename to WITH_REGEX_ASSERT. Which users are less likely to accidentally set?

Alexey-T commented 1 year ago

okay, so what is proposed change now? I'm puzzled.

User4martin commented 1 year ago

Moved to #342

Those errors should never happen. IMHO they should be assert.

And it has a noticeable effect on speed.

Alexey-T commented 1 year ago

Ah, okay..

andgineer / TRegExpr

Optimizie code #341