|
ms
newsgroups
|
|||||||||||||||||||||||
|
|||||||||||||||||||||||
switch case and efficiencyI have well over a thousend cases after a switch.
1. Is there a practical limit to the number of cases? 2. Can I optimize (and uglify) my code so that switch-case runs faster? 3. How is switch implemented (binary search, linear search...)? Thank you " Martijn Mulder" <i@m> wrote in message According to MSDN, there is no limit to the number of cases. This is news:494ea8ac$0$24255$dbd49001@news.wanadoo.nl... >I have well over a thousend cases after a switch. > > 1. Is there a practical limit to the number of cases? > 2. Can I optimize (and uglify) my code so that switch-case runs faster? > 3. How is switch implemented (binary search, linear search...)? > > Thank you > stated on this page: http://msdn.microsoft.com/en-us/library/06tc147t.aspx. Since the first case statement is matched, I think it is just a linear search as the logic matches the first found case. Not knowing what you are doing with each of the thousands of cases, it would be hard to recommend what you should do to optimize things. If you are using a switch statement to find the house address of a list of phone numbers, then obviously a better way can be recommended. -- Mike
Show quote
Hide quote
>>I have well over a thousend cases after a switch. In fact, the number is only a few hundreds, but rising. The great number >> >> 1. Is there a practical limit to the number of cases? >> 2. Can I optimize (and uglify) my code so that switch-case runs faster? >> 3. How is switch implemented (binary search, linear search...)? >> >> Thank you > According to MSDN, there is no limit to the number of cases. This is > stated on this page: > http://msdn.microsoft.com/en-us/library/06tc147t.aspx. Since the first > case statement is matched, I think it is just a linear search as the logic > matches the first found case. > > Not knowing what you are doing with each of the thousands of cases, it > would be hard to recommend what you should do to optimize things. If you > are using a switch statement to find the house address of a list of phone > numbers, then obviously a better way can be recommended. > > -- > Mike stems from a recent attempt to simplify key handling code with this technique: override protected void OnKeyDown(System.Windows.Forms.KeyEventArgs a) { base.OnKeyDown(a); switch(ModifierKeys.ToString()+' '+a.KeyCode) { case"Shift, Control F": System.Console.WriteLine("You pressed the Shift, Control and F key similtaniously" ); break; } } It's neat, but it adds up Martijn Mulder wrote:
Show quoteHide quote >>> I have well over a thousend cases after a switch. Well, you might have mentioned that you were switching on strings, as it's >>> >>> 1. Is there a practical limit to the number of cases? >>> 2. Can I optimize (and uglify) my code so that switch-case runs faster? >>> 3. How is switch implemented (binary search, linear search...)? >>> > >> According to MSDN, there is no limit to the number of cases. This is >> stated on this page: >> http://msdn.microsoft.com/en-us/library/06tc147t.aspx. Since the first >> case statement is matched, I think it is just a linear search as the logic >> matches the first found case. >> >> Not knowing what you are doing with each of the thousands of cases, it >> would be hard to recommend what you should do to optimize things. If you >> are using a switch statement to find the house address of a list of phone >> numbers, then obviously a better way can be recommended. >> > > In fact, the number is only a few hundreds, but rising. The great number > stems from a recent attempt to simplify key handling code with this > technique: > > override protected void OnKeyDown(System.Windows.Forms.KeyEventArgs a) > { > base.OnKeyDown(a); > switch(ModifierKeys.ToString()+' '+a.KeyCode) > { > case"Shift, Control F": > System.Console.WriteLine("You pressed the Shift, Control and F key > similtaniously" ); > break; > } > } > quite different from switching on integers. The compiler will emit a lazily initialized hashtable containing all the strings you're switching on, mapping them to integers. These, in turn, will be used in a regular switch opcode. Pretend you're building a hashtable yourself containing all the strings you're switching on and you'll have a better idea of the limits. For starters, if you have a great many cases, you'll be eating up a great deal of memory. Switching is also none too efficient, as computing a hash over a string is far less efficient than looking up a single number. In any case, you probably don't need a switch statement at all, and I fail to see how this "simplifies" key handling code, other than by saving you conscious thought about what the cases have in common. The statement you give as an example could be easily rewritten to a single series of print statements. Even if your actual code is more complex, it's still very likely that you could reduce it to a limited number of numerical switch statements (for starters, every key plus modifiers easily fits in an int). -- J.
Show quote
Hide quote
"Jeroen Mostert" <jmost***@xs4all.nl> schreef in bericht IIUC the compiler will generate an efficient int-based switch that I cannot news:494ec364$0$188$e4fe514c@news.xs4all.nl... > Martijn Mulder wrote: >>>> I have well over a thousend cases after a switch. >>>> >>>> 1. Is there a practical limit to the number of cases? >>>> 2. Can I optimize (and uglify) my code so that switch-case runs faster? >>>> 3. How is switch implemented (binary search, linear search...)? >>>> >> >>> According to MSDN, there is no limit to the number of cases. This is >>> stated on this page: >>> http://msdn.microsoft.com/en-us/library/06tc147t.aspx. Since the first >>> case statement is matched, I think it is just a linear search as the >>> logic matches the first found case. >>> >>> Not knowing what you are doing with each of the thousands of cases, it >>> would be hard to recommend what you should do to optimize things. If >>> you are using a switch statement to find the house address of a list of >>> phone numbers, then obviously a better way can be recommended. >>> >> >> In fact, the number is only a few hundreds, but rising. The great number >> stems from a recent attempt to simplify key handling code with this >> technique: >> >> override protected void OnKeyDown(System.Windows.Forms.KeyEventArgs a) >> { >> base.OnKeyDown(a); >> switch(ModifierKeys.ToString()+' '+a.KeyCode) >> { >> case"Shift, Control F": >> System.Console.WriteLine("You pressed the Shift, Control and F key >> similtaniously" ); >> break; >> } >> } > Well, you might have mentioned that you were switching on strings, as it's > quite different from switching on integers. > > The compiler will emit a lazily initialized hashtable containing all the > strings you're switching on, mapping them to integers. These, in turn, > will be used in a regular switch opcode. > > Pretend you're building a hashtable yourself containing all the strings > you're switching on and you'll have a better idea of the limits. For > starters, if you have a great many cases, you'll be eating up a great deal > of memory. Switching is also none too efficient, as computing a hash over > a string is far less efficient than looking up a single number. > > In any case, you probably don't need a switch statement at all, and I fail > to see how this "simplifies" key handling code, other than by saving you > conscious thought about what the cases have in common. The statement you > give as an example could be easily rewritten to a single series of print > statements. Even if your actual code is more complex, it's still very > likely that you could reduce it to a limited number of numerical switch > statements (for starters, every key plus modifiers easily fits in an int). beat, while I keep the readability, the flexibility and the extensibility on my side? I am more than satisfied with that :) Thank you Martijn Mulder wrote:
Show quoteHide quote > "Jeroen Mostert" <jmost***@xs4all.nl> schreef in bericht I have no idea how you derive this conclusion from my statements. Are you > news:494ec364$0$188$e4fe514c@news.xs4all.nl... >> Martijn Mulder wrote: >>>>> I have well over a thousend cases after a switch. >>>>> >>>>> 1. Is there a practical limit to the number of cases? >>>>> 2. Can I optimize (and uglify) my code so that switch-case runs faster? >>>>> 3. How is switch implemented (binary search, linear search...)? >>>>> >>>> According to MSDN, there is no limit to the number of cases. This is >>>> stated on this page: >>>> http://msdn.microsoft.com/en-us/library/06tc147t.aspx. Since the first >>>> case statement is matched, I think it is just a linear search as the >>>> logic matches the first found case. >>>> >>>> Not knowing what you are doing with each of the thousands of cases, it >>>> would be hard to recommend what you should do to optimize things. If >>>> you are using a switch statement to find the house address of a list of >>>> phone numbers, then obviously a better way can be recommended. >>>> >>> In fact, the number is only a few hundreds, but rising. The great number >>> stems from a recent attempt to simplify key handling code with this >>> technique: >>> >>> override protected void OnKeyDown(System.Windows.Forms.KeyEventArgs a) >>> { >>> base.OnKeyDown(a); >>> switch(ModifierKeys.ToString()+' '+a.KeyCode) >>> { >>> case"Shift, Control F": >>> System.Console.WriteLine("You pressed the Shift, Control and F key >>> similtaniously" ); >>> break; >>> } >>> } > > >> Well, you might have mentioned that you were switching on strings, as it's >> quite different from switching on integers. >> >> The compiler will emit a lazily initialized hashtable containing all the >> strings you're switching on, mapping them to integers. These, in turn, >> will be used in a regular switch opcode. >> >> Pretend you're building a hashtable yourself containing all the strings >> you're switching on and you'll have a better idea of the limits. For >> starters, if you have a great many cases, you'll be eating up a great deal >> of memory. Switching is also none too efficient, as computing a hash over >> a string is far less efficient than looking up a single number. >> >> In any case, you probably don't need a switch statement at all, and I fail >> to see how this "simplifies" key handling code, other than by saving you >> conscious thought about what the cases have in common. The statement you >> give as an example could be easily rewritten to a single series of print >> statements. Even if your actual code is more complex, it's still very >> likely that you could reduce it to a limited number of numerical switch >> statements (for starters, every key plus modifiers easily fits in an int). > > > IIUC the compiler will generate an efficient int-based switch that I cannot > beat, while I keep the readability, the flexibility and the extensibility on > my side? I am more than satisfied with that :) > saying you're *not* using strings? If you're not actually interested in a full answer to the question, just in hearing that what you're doing works and will probably not be too inefficient: what you're doing works and will probably not be too inefficient. Most optimizations aren't necessary. -- J.
Show quote
Hide quote
"Jeroen Mostert" <jmost***@xs4all.nl> wrote in message You can make this easier to maintain by doing a two layer switch. The first news:494ec364$0$188$e4fe514c@news.xs4all.nl... > Martijn Mulder wrote: >>>> I have well over a thousend cases after a switch. >>>> >>>> 1. Is there a practical limit to the number of cases? >>>> 2. Can I optimize (and uglify) my code so that switch-case runs faster? >>>> 3. How is switch implemented (binary search, linear search...)? >>>> >> >>> According to MSDN, there is no limit to the number of cases. This is >>> stated on this page: >>> http://msdn.microsoft.com/en-us/library/06tc147t.aspx. Since the first >>> case statement is matched, I think it is just a linear search as the >>> logic matches the first found case. >>> >>> Not knowing what you are doing with each of the thousands of cases, it >>> would be hard to recommend what you should do to optimize things. If >>> you are using a switch statement to find the house address of a list of >>> phone numbers, then obviously a better way can be recommended. >>> >> >> In fact, the number is only a few hundreds, but rising. The great number >> stems from a recent attempt to simplify key handling code with this >> technique: >> >> override protected void OnKeyDown(System.Windows.Forms.KeyEventArgs a) >> { >> base.OnKeyDown(a); >> switch(ModifierKeys.ToString()+' '+a.KeyCode) >> { >> case"Shift, Control F": >> System.Console.WriteLine("You pressed the Shift, Control and F key >> similtaniously" ); >> break; >> } >> } >> > Well, you might have mentioned that you were switching on strings, as it's > quite different from switching on integers. > > The compiler will emit a lazily initialized hashtable containing all the > strings you're switching on, mapping them to integers. These, in turn, > will be used in a regular switch opcode. > > Pretend you're building a hashtable yourself containing all the strings > you're switching on and you'll have a better idea of the limits. For > starters, if you have a great many cases, you'll be eating up a great deal > of memory. Switching is also none too efficient, as computing a hash over > a string is far less efficient than looking up a single number. > > In any case, you probably don't need a switch statement at all, and I fail > to see how this "simplifies" key handling code, other than by saving you > conscious thought about what the cases have in common. The statement you > give as an example could be easily rewritten to a single series of print > statements. Even if your actual code is more complex, it's still very > likely that you could reduce it to a limited number of numerical switch > statements (for starters, every key plus modifiers easily fits in an int). > > -- > J. > layer will be on the function keys and is only 8 switches long similar to the following. Switch ModiferKeys case Shift : ProcessShift(a) case Ctrl : ProcessCtrl(a) case Alt : ProcessAlt(a) case Shift+Ctrl : ProcessShiftCtrl(a) case Shift+Alt : ProcessShiftAlt(a) case Shift+Ctrl+Alt : ProcessShiftCtrlAlt(a) case Ctrl+Alt : ProcessCtrlAlt(a) case else : ProcessRaw(a) end Switch Each of the Process<Shiftkeys>(a) would then be used to process the actual keys for that combination of Ctrl, Shift, and Alt. This will simplify your code maintenance. The reality is that the computer is far faster than your users, so the small extra time required to call the second function will never be noticed. Mike Ober. Martijn Mulder wrote:
> I have well over a thousend cases after a switch. Then you may have a design issue, and a possible maintenance issue. I do > hope that file is machine generated. Even so, see if there's a more compact way. Are all the case statements unique, with no opportunity for generalization? > 1. Is there a practical limit to the number of cases? I honestly don't know. When your compiler times out, eats up too much memory or crashes with an internal error, you've probably hit it. This is the most likely case. It would also be possible for the CLR to hit the limit as it's loading or JIT-compiling your code, but this seems less likely. There are no relevant theoretical upper limits. If we assume that the switch is always implemented with a jump table (i.e. there is no opportunity for optimizing it further by rewriting the case blocks) then it can't have more than 4 294 967 295 cases, but this will hardly be the limiting factor in any case (for starters, the table alone would take up 16 GiB). And even then there's no rule that it has to be implemented like this. This is one of those "if you have to ask, it's probably time to rethink your solution" kind of limits. > 2. Can I optimize (and uglify) my code so that switch-case runs faster? There is no *general* way to optimize a switch, it's already the purest expression of "if this, then that". Depending on the specifics (what you're doing in every case block, what values you're using for both switch and cases and what the compiler/runtime are doing) it may be possible to optimize it. For example, you could replace it with something else altogether, like a hashtable and a general function. > 3. How is switch implemented (binary search, linear search...)? It depends on the compiler, the CLR and the specific statement.> The compiler may choose to emit a series of compares and jumps (likely if the switches are wildly disparate), or it may emit a switch opcode (if the switches are consecutive) or a combination of these. That's just what Microsoft's current C# compiler does, mind you -- certainly nothing prohibits the compiler from, say, generating a minimal perfect hash function and using that to index a jump table. (Which, incidentally, is another possible way of optimizing your switch by replacing it with something else.) These opcodes may in turn be compiled by the CLR in whatever way it chooses. I'm not aware of any guarantee on the efficiency of the switch statement, and the CIL specification certainly doesn't mandate one. The switch opcode (which requires consecutive, zero-based values) is almost certainly implemented as an indexed jump, as there's no general way to do it better. The CLR may or may not recognize a series of compares-and-jumps as a high-level switch statement and optimize accordingly. In short: if you're that interested in efficiency, profile. -- J. Jeroen Mostert wrote:
> Martijn Mulder wrote: Just as some define procedural programming as goto free>> I have well over a thousend cases after a switch. >> > Then you may have a design issue, and a possible maintenance issue. I do > hope that file is machine generated. Even so, see if there's a more > compact way. Are all the case statements unique, with no opportunity for > generalization? programming, then other define object oriented programming as switch free programming. There are also plenty of coding conventions that limit method length to 50 or 100 lines. I don't agree with those rules being the ultimate truth. But non the less a method violating several common coding rules is a good indication that something is wrong. Conclusion: I had to use 9 lines to say that I agree with Jeroen. Arne  |
|||||||||||||||||||||||
Other interesting topics