[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c Miguel de Icaza changed: What|Removed |Added AssignedTo|mig...@xamarin.com |msa...@xamarin.com AssignedTo|mig...@xamarin.com |msa...@xamarin.com -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c Miguel de Icaza changed: What|Removed |Added AssignedTo|mig...@xamarin.com |msa...@xamarin.com AssignedTo|mig...@xamarin.com |msa...@xamarin.com -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c22 Susanne Oberhauser changed: What|Removed |Added AssignedTo|michael.mil...@suse.com |mig...@xamarin.com --- Comment #22 from Susanne Oberhauser 2011-07-20 12:29:48 UTC --- Reassigning to Miguel to drive further resolution... -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c20 --- Comment #20 from Miguel de Icaza 2010-11-27 18:48:54 UTC --- Kornel, that is a great idea. I was thinking of doing something based on v[N], but I did not think the problem through. Your solution to switch on string length + using determining differences on the string is very good. -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380
https://bugzilla.novell.com/show_bug.cgi?id=655380#c19
Kornél Pál changed:
What|Removed |Added
CC||kornel...@gmail.com
--- Comment #19 from Kornél Pál 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.
___
mono-bugs maillist - mono-bugs@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c18 --- Comment #18 from Zoltan Varga 2010-11-23 19:54:18 UTC --- The last timings were from a loaded machine, here are the correct ones: Switch 1343 If 388 2 -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c17 --- Comment #17 from Zoltan Varga 2010-11-23 18:20:32 UTC --- On my tegra, the timings are: Switch 2910 If 566 The hash table based implementation does lots of work under the hood: - it makes a couple of method calls instead of the approximately 1-2 calls the if based implementation does - it computes the hash code of the input string which is not very fast, even on x86. - it iterates over the hash table - it does a final string comparison on the item found in the hash table So this will be slower on all architectures, it just happens to be much slower on arm. -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c16 --- Comment #16 from Mantas Puida 2010-11-23 15:22:55 UTC --- Did the test with 1 iterations: switch : 450-550 ms if : 30-45 ms Ratio between switch and if remains about the same. -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c15 --- Comment #15 from Paolo Molaro 2010-11-23 14:45:11 UTC --- Mantas you don't have to lecture about the importance of milliseconds in games. The issue is that your numbers are meaningless, because the measurement noise is comparable to the thing you're trying to measure. You should have the loop run for many more iterations, let's say 1 or 10 and show the results of that. -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c14 --- Comment #14 from Mantas Puida 2010-11-23 14:29:06 UTC --- I run the same test on 1st generation "iPod touch" and results are even worse: switch statement : ~4.0-6.0 ms if statement : ~0.33 ms I feel like there is need to additionally explain why few milliseconds are important for us. These tests are extracted from real world example. Imagine 3D game running on this iPod touch, game has ~100 C# based gameobjects (some of them are active and rendering on screen some are not). Users typically use some string property to "tag" object role and discriminate one gameobject from another. Image that you have 25 objects of type "EvilEnemyType1", 25 of type "EvilEnemyType2", etc. Every frame runs the code which iterates through all these 100 gameobjects and make switch by "tag" property. And if the type is "EvilEnemyType1" then code A should be executed and so on. If you want nice looking and responsive game you usually aim 30 FPS, which translates to 33 ms budget per frame, so if your code loosing 4-6 ms for switch statement alone (versus 0.33 ms) then you are in a trouble, because it is ~20% of CPU budget for single frame, which you probably would like to spend on physics or processing more stuff for rendering (like skinning animated meshes). I understand that using ints as "tag" property would solve most of these problems, but there are several thousands .NET developers in the wild, who are making games for iPhone. It is not an easy task to educate all of them how write well performing code, especially when some magic is happening behind the scenes. If compiler (gmcs or JIT) could improve performance out of the box it would be very nice. -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380 https://bugzilla.novell.com/show_bug.cgi?id=655380#c13 --- Comment #13 from Marek Safar 2010-11-23 12:13:41 UTC --- You are still not reading it correctly. I reported observed behaviour on my machine, where am I blaming anyone? I can see I should be more precise when explaining myself about the if/else implementation. So, let me get it right What I meant was that on my mono 182 against 289 is about 0.6x faster which is not ideal but comparing to 78 against 279 is about 3.5x faster which would be significant but we are not that fast hence the low priority. The guy reported 0.70 ms against 0.12 ms on IPhone which seemed to me as to be too much difference to be caused by hashtable only. I was wrong on "insisting" that someone investigates the issue as it must be compiler bug. -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email --- You are receiving this mail because: --- You are the QA contact for the bug. ___ mono-bugs maillist - mono-bugs@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-bugs
[Mono-bugs] [Bug 655380] String switch statement 2x slower if compared to simple list of if statements
https://bugzilla.novell.com/show_bug.cgi?id=655380
https://bugzilla.novell.com/show_bug.cgi?id=655380#c12
Paolo Molaro changed:
What|Removed |Added
Summary|String switch statement |String switch statement 2x
|runs 5x slower on iPhone if |slower if compared to
|compared to simple list of |simple list of if
|if statements |statements
--- Comment #12 from Paolo Molaro 2010-11-23 11:28:29 UTC ---
This is not an iphone issue: this is a bug about gmcs producing slow code for
no good reason on all the architectures and all the existing runtimes. You try
to push the blame when you give credit to sub millisecond benchmark numbers,
measure yourself that the code gmcs produces is always slow and still insist
that this is someone else problem ("I could implement if/else for smaller
counts but it makes sense only when our if comparison becomes as fast as .net
one").
We currently have no indication that on arm/iphone the code is significantly
slower than on other platforms: someone with an iphone needs to run the test
with reasonable repetition counts. If and when that happens, we'll open a
separate bug about dictionary lookups being slower with arm/aot code.
--
Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
You are the QA contact for the bug.
___
mono-bugs maillist - mono-bugs@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-bugs
