Checking Speed of SynEdit Highlighters

[Martin_fr]

But always, you'll need to do one more step (calculate the hush function). It's algorithm.

There is another difference:

* Hash functions:
  Make comparisons with n characters.

* First-char-prefix:
  Make comparisons with n-1 characters.

Yes, but depending on the hash algorithm used, you may have less false positives. (less string compares, for none keywords).

[Martin_fr]

The current hash returns 0..191 (that are 192 values) of which 89 have a function assigned

So over half of the calculated hashes are immediately resulting in "not a token". Originally that ratio was better, because less keywords existed (fpc was extended)


In your case there are 26 letters in the alphabet (case does not matter, all identifiers in pascal start with a..z).
I do not know how many of them have a keyword? If I counted correct about 20.

That means 76% of the letters, will require a compare of the string. That is way more than when using the hash.

And on top, the hash could be modified to use a bigger result range, improving its efficiency.

--
Note: I do not say that the hash is indeed better. But it may possible be. (That is comparing the average case / and assuming a better implementation)

[Edson]

You are right Martin.

That is the only point, where I see, the hash function could be faster, because of the false positives.

I can see now, that we know very well the advantages and disadvantages of both methods. (I will document this on my article about SynEdit.)

But don't forget we have at least one test. I will put on this way:

* PHP highlighter (with hash-functions and 46 functions):    11seg, 11 seg, 11 seg.
* PHP highlighter (with first-char-prefix and 26 functions):    10 seg, 10 seg, 10 seg.

(Probably they have not the best implementation)

PD: Which highlighter hash returns 192 values and have 89 function assigned?

[Martin_fr]

PD: Which highlighter hash returns 192 values and have 89 function assigned?

Pascal

[Morton]

* implementation.
The current hash base does a lot of subroutine calls. that slows stuff down.
Maybe the new prefix based implementation has less function calls / more code in a single procedure?
- inline some (e.g. KeyHash, IdentKind)
- skip creation of  exception frames ({$IMPLICITEXCEPTIONS off})
  (do have a fair compare, add this to BOTH)

The call tables are part of the algorithm, which performs extremely well with highly optimizing compilers.
Ported to NET with a few changes to prevent to much safety guarding it will still outperform FPC.
The cross platform nature of FPC makes highly optimizing a lot
harder than for single platform ones.
Maybe the newer FPC compiler could optimize better if the right directives are used.

[Edson]

So probably, our FPC is not so fast as we believe.

Any way, if the "call tables" is slow, it will affect both algorithm, especially to the hash-functions, because it use two "call tables" (the First-char-prefix just one).

[marcov]

So probably, our FPC is not so fast as we believe.

I don't know, I couldn't find Morton's report nor could I reproduce his findings.
 

[Martin_fr]

It is not the call tables that are slow ( I guess that was somehow derived from an earlier statement of mine, but that is not what I said.)

If code that is called very very very often, is spread over more subroutines, and has to make calls to those, then that code may be slower then the same code all inlined.

Note: it "may". It is not in all cases. I never said, it was always.

The entire point I made was, that the tiny speed difference that was reported *can* same as good be due to implementation, as it can be due to algorithm.

[Morton]

So probably, our FPC is not so fast as we believe.

Just NET is not as slow as many believe, ideed it can be very fast.
Net may be slowed by safety guarding.
There is much less safety guarding within the current scope.
Last time I have checked simply assign something within the current method eg. a string and then accessing the new assignment improved speed significantly if accessed more than one or two times eg. by scanning a string.

[Morton]

For the Pascal highlighter.
With standard optimization:
{$inline on}
{$IMPLICITEXCEPTIONS off}
and inlining KeyHash, KeyComp, Next and GetEol gives about 18% more speed.
Reassign the aKey as PChar in KeyComp gives another percent.
Inlining the table calls seems not to be possible.
With the highest optimization the difference is about 40%.
Thats about 70MB sec. instead of about 40MB sec. on my PC.

BTW I have noticed some needles string copying,
which should not occur in a high performance tool.

[Martin_fr]

BTW I have noticed some needles string copying,
which should not occur in a high performance tool.

Can you point them out please?

[Morton]

BTW I have noticed some needles string copying,
which should not occur in a high performance tool.

Can you point them out please?

Func89
    Txt := copy(fLine, Run + 7, length(fLine));

Not the fastest possible too.
                            (AnsiStrComp(PChar(copy(Txt, i+1, 6)), PChar('rivate')) = 0) )
                       or ( (i+8 <= l) and
                            ((i+8 = l) or (Txt[i+9] in [#1..#32])) and
                            (AnsiStrComp(PChar(copy(Txt, i+1, ), PChar('rotected')) = 0) )

BraceOpenProc;
    Txt := copy(fLine, Run, length(fLine));

                        (AnsiStrComp(PChar(copy(Txt, i+1, 4)), PChar('fold')) = 0)

[Martin_fr]

Fixed...

Well: the first block ("strict private") of code can probably be replaced by something far simpler. I need to review that...

[Morton]

From playing a bit with the highlighters I would reccoment just placing {$OPTIMIZATION ON} in highlighter units. Will enhance speed greatly. The effect of {$IMPLICIT EXCEPTIONS off} is then neglible and inlining may have even a negative effect if the project does not use at least level 2 optimization.

[Martin_fr]

{$IMPLICIT EXCEPTIONS off}  are mainly in combinations with strings (except const param). So using more pchar can help here.

Applications can add callbacks via HookAttrChangeEvent.

When this callback is triggered, and user code throws an exception, the any HL method that is in the callstack at that time will need the implicit exceptions (or leak memory).

This will be only a very few methods, but they need to be identified. Also this should not include any of the methods involved in the actual scan.
But the directive should only cover parts of the unit.


IMHO optimization should follow the project/package settings.