[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements

[bugzilla_noreply at novell.com]

https://bugzilla.novell.com/show_bug.cgi?id=655380

https://bugzilla.novell.com/show_bug.cgi?id=655380#c19


Kornél Pál <kornelpal at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kornelpal at gmail.com

--- Comment #19 from Kornél Pál <kornelpal at gmail.com> 2010-11-27 18:33:38 UTC ---
MS csc does the following three things:
- ldstr and IsInterned (1.x only, basically native hashtable lookup)
- op_Equality comparisons (small number of strings)
- Dictionary (more than 6 strings)

Since all string cases has to be constant generating prefect hash functions
could be a solution that however adds considerable extra complexity so may not
be reasonable to implement.

On the other hand something like that could be implemented:
- create a switch on the string length
- if there are multiple cases of the same length create a sub-switch based on
the first character index that is different in each string
- finally compare the whole string

This should work in most cases but the compiler could fall back to the current
Hashtable/comparison implementation when this optimization is not possible.

An example:
switch (s)
{
case "a":
    break;
case "ab":
    break;
case "aaa":
    break;
case "abc":
    break;
case "acc":
    break;
case "adf":
    break;
default:
    throw new NotImplementedException();
}

Could be transformed to this:
if (s == null)
    goto defaultCase;
switch (s.Length)
{
case 1:
    if (s != "a")
        goto defaultCase;
    goto endSwitch;
case 2:
    if (s != "ab")
        goto defaultCase;
    goto endSwitch;
case 3:
    switch (s[1])
    {
    case 'a':
        if (s != "aaa")
            goto defaultCase;
        goto endSwitch;
    case 'b':
        if (s != "abc")
            goto defaultCase;
        goto endSwitch;
    case 'c':
        if (s != "acc")
            goto defaultCase;
        goto endSwitch;
    case 'd':
        if (s != "adf")
            goto defaultCase;
        goto endSwitch;
    }
    break;
}
defaultCase:
throw new NotImplementedException();
endSwitch:;

Note that I haven't done any performance testing I just expect it to be more
efficient for relatively large strings since the full string is being walked
only once.

When lengths/characters are too far from each other and switch is transformed
to ifs there may be no gain from the above transformation.

-- 
Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.