[Mono-devel-list] [PATCH] Faster String.Equals

[Ben Maurer]

On Sat, 2004-05-22 at 06:38, Andreas Nahr wrote:
> However I see some problems with that approach:
> 1. Substantial code multiplication. We need Supported_Architectures + 1 code
> implementations for every method instread of just 1. This will be horrible
> to maintain and a lot of additional work.
Agreed.

However, you miss one important point. We are only going to do this for
*VERY* common methods. If you take a step back, there are really three
approaches we can take to optimizing low level methods like this:
     1. Handwritten assembly
     2. Messy c# optimizations like unrolling loops
     3. Writing "standard" code.

For the most frequent methods, we would do 1. For methods that are
frequent but not critical, 2. Others, 3. So, we only have code
multiplication.

And remember, this is opt-in. You dont have to provide an impl if you
dont want to.

> 2. Too platform specific optimizations. Look at your String.Equals that is
> only implemented for x86. If somebody uses a lot of String.Equals in his own
> classes then his implementation will perform seriously slower/ different on
> other platforms. This may lead to problematic optimizations for classes
> which internally use these methods.
In no case does this code result in string.equals being slower than it
is today -- on any platform. So, this is really a moot point

> 3. Defeats the purpose of having a platform - neutralizing platform.
Take a look at glibc.

> 4. Although it does not have the overhead of an icall AFAIU it still poses a
> problem for optimizations. A compiler (like ngen) may be able to completely
> eliminate a case like:
> "Test" != "Test"
> to a false constant (very simple example). Is that still possible with your
> implementation?
> 
> Or
> String a = "dh"
> String b = "dfh"
> a.Equals (b)
> might get inlined and *optimized* by the compiler or JIT or especially AOT
> because it can guarantee that a and b can never be null (which is checked in
> Equals).

Absolutely we can still do this. Actually, there is a much more
important optimization. We can inline something like:

if (a == "abcdef") into code with no calls.

> 
> 5. A compiler tries (should try) to optimize to the maximum global speed,
> you optimize for a maximum local speed which MIGHT lead to slower overall
> performance (surely not nowadays because our compilers are not anywhere near
> that level of optimization)
How exactly would this lead to a slowdown?

> 6. We still need a fast managed implementation for cases when a ASM -
> version is not available
Yes, but it is not as critical.

> 7. Finding bugs will be much harder if we have architecture specific
> implementations for specific methods.
We should run tests with and without the optimization enabled.

> Therefore IMHO we should:
> 1. Add that ASM - injection architecture, but not enable it by default. We
> could have a --AsmInject switch which enables it.

IMHO it should be enabled. It comes at practically 0 cost, and gives
alot of gain.
> 2. I would love to see a asm - coded version of string CreateString (int
> length)  :-)
Probably not possible with the current gc.
> 
> 
> I've attached my version of String.Equals which is also a lot faster than
> the current version (especially for larger compares)
> Microbench:
> chars 7: 4196 -> 3054
> chars 88: 2743 -> 1772
> chars a lot: 1011 -> 591

This is nice. However, note that I did not have to resort to unrolling
to get this result. If I hand code unrolling, it may be even faster.

-- Ben