[cs] funky String.lastIndexOf performance

[Simn]

HL

Our benchmarks suggest that lastIndexOf does something weird when there should be a match on the first attempt:

Case: StringScan
  Suite: length 20003
           indexOf hit: 3,116,116 (100.00%)
          indexOf find:    33,330 (  1.06%)
       lastIndexOf hit:    16,091 (  0.51%)
      lastIndexOf find:    16,075 (  0.51%)
        indexOf nofind:    11,043 (  0.35%)
    lastIndexOf nofind:    11,030 (  0.35%)
            split find:     8,278 (  0.26%)
          split nofind:     7,323 (  0.23%)

The "lastIndexOf hit" should have the same result as "indexOf hit" because the provided offset points directly at the substring we're looking for.

Neko has the same characteristics but I suppose we're not gonna fix that.

C#

This is also weird:

Case: StringScan
  Suite: length 20003
       lastIndexOf hit: 12,904,904 (100.00%)
           indexOf hit:  6,123,123 ( 47.45%)
      lastIndexOf find:     91,203 (  0.70%)
          indexOf find:     91,160 (  0.70%)
        indexOf nofind:     45,690 (  0.35%)
    lastIndexOf nofind:     43,590 (  0.33%)
          split nofind:      9,047 (  0.07%)
            split find:      8,327 (  0.06%)

indexOf must be doing something worse than lastIndexOf here.

[ncannasse]

What does "hit" means there? I'm not sure what's the problem. Performances?

[Simn]

Yes it's about performance. "hit" means that it uses a startIndex which is close (in this case directly on) the sub-string we're looking for. The test is here: https://github.com/HaxeFoundation/haxe/blob/development/tests/benchs/src/cases/StringScan.hx#L16

The performance characteristics suggests that it walks a large portion of the string instead of starting at startIndex.

[ncannasse]

I'm not surprised that several platforms exhibit the same behavior, as I mostly copy/pasted the implementation when adding a new platform.

[ncannasse]

I made a small fix in lastIndexOf in ac8b78a
But the problem remain that we don't have a native way to search bytes backward, which would be necessary to reach the required performances.

[ncannasse]

I've opened HaxeFoundation/hashlink#239 not to forget about it