[RESOLVED] Switch case or something better!
I am taking the first char from a string so mystring[0] and using it as an int on a switch case. The switch case has all ascii values starting at 32 (space) up to 255 grouped into a total of 19 switches. My question is basically if this is okay, or should I do this in a different way? See code:
column is a class of vectors of type struct!
Code:
inline column* ptr2col(unsignedint intin)// Returns a pointer to a column class
{
column* ret; //
switch (intin)
{
//c_01 a q
case 1:
case 65: case 97: case 192: case 193: case 194: case 195: case 196: case 197: case 198:
case 224: case 225: case 226: case 227: case 228: case 229: case 230: case 81: case 113:
ret=&c_01;
break;
//c_02 e w
case 2:
case 69: case 101: case 200: case 201: case 202: case 203: case 232:
case 233: case 234: case 235: case 240: case 87: case 119:
ret=&c_02;
break;
and so on etc. ............................
till
//c_19 Rest
case 19:
default:
ret=&c_19;
for every char over 255!
some of the case blocks are very big (20 or 30 "case number:" statements. So I am wondering if I couldn't do this more efficiently!
Regards,
Rigsby :wave:
Re: Switch case or something better!
What is c_01, c_02, c_03 ? This needs to be an array instead of single variables.
Re: Switch case or something better!
You may be able to use a lookup table of 256 entries indexed by intin instead of the switch. That may make the function laid out in your snippet look much neater, but of course you'd need to initialize the table somewhere. (It probably wouldn't make any difference in terms of runtime performance, since the compiler will likely render your switch statement internally using a lookup table of jump target addresses anyway.)
Another option is doing what usually is not recommended and replace the switch with an if ... else if ... else if ... else chain. As you seem to have many adjacent cases that are to be treated identically (like the cases 192 to 198 for instance) you can enhance your code in terms of "code line efficiency" and comprehensibility by using input value range checks instead of checking for equality to individual values. This may be slightly less efficient in terms of runtime performance, though.
Re: Switch case or something better!
Quote:
Originally Posted by
Skizmo
What is c_01, c_02, c_03 ? This needs to be an array instead of single variables.
The c_01, c_02, c_03, etc. are (as explained in my post) class objects (the class is “column”) which contains a vector of type struct!
My question relates 100% to the proficiency of “switch case” as I am not a guru and might be missing a serious performance improvement!
Eri525 – thanks for your comments, which show you have fully understood my question! I really am just asking can I get this to be faster…?
Re: Switch case or something better!
Quote:
Eri525 – thanks for your comments, which show you have fully understood my question! I really am just asking can I get this to be faster…?
His idea is making it much faster. Each case in the switch costs time. If you put it in an array, only one lookup has to be done instead of testing a lot of cases inside the switch.
Turn the c_01, c_02 stuff also in an array and your function can look like this.
'lSomeArray' contains the numbers you usually switch to (witch actually is the index of the 'c_xx' columnarray). For instance, in case 1 you have 65 and 97, so in 'lSomeArray' on position 65 and 97 is a 1.
Code:
inline column* ptr2col(unsignedint intin)// Returns a pointer to a column class
{
column* ret; //
long lSomeArray[256] = {1, 1, 2, 2.... etc}.
long lIndex = lSomeArray[intin];
ret = &ColumnArray[lIndex];
}
Now your function is only 3 lines.
Re: Switch case or something better!
Quote:
Originally Posted by
Rigsby
Eri525 – thanks for your comments, which show you have fully understood my question! I really am just asking can I get this to be faster…?
Probably not. Compilers are usually quite good in translating C++ code like that into machine code. As already stated, I'd expect my proposal #1 to just be about as fast as what the compiler makes out of your current code, and #2 may even be slightly slower. What both IMO would do is make the code look a bit nicer and/or make it easier to understand, but, admittedly, this eventually even is a matter of personal taste to some extent.
Re: Switch case or something better!
Quote:
Originally Posted by
Skizmo
His idea is making it much faster. Each case in the switch costs time. If you put it in an array, only one lookup has to be done instead of testing a lot of cases inside the switch.
Thanks, but now this statement raised my curiosity... :D
So I turned the OP's code into something compilable like that:
Code:
// Test6.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//
#include "stdafx.h"
class column {};
column c_01, c_02, c_19;
inline column* ptr2col(unsigned int intin)// Returns a pointer to a column class
{
column* ret;
switch (intin)
{
//c_01 a q
case 1:
case 65: case 97: case 192: case 193: case 194: case 195: case 196: case 197: case 198:
case 224: case 225: case 226: case 227: case 228: case 229: case 230: case 81: case 113:
ret=&c_01;
break;
//c_02 e w
case 2:
case 69: case 101: case 200: case 201: case 202: case 203: case 232:
case 233: case 234: case 235: case 240: case 87: case 119:
ret=&c_02;
break;
// and so on etc. ............................
// till
//c_19 Rest
case 19:
default:
ret=&c_19;
}
return ret;
}
int _tmain(int argc, _TCHAR* argv[])
{
column *p = ptr2col(0);
return 0;
}
And here's what the compiler made out of it (VC++ 2010, release build, default settings except for turning on the assembly listing output):
Code:
; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.30319.01
TITLE c:\dokumente und einstellungen\administrator\eigene dateien\visual studio 2010\Projects\Test6\Test6\Test6.cpp
.686P
.XMM
include listing.inc
.model flat
INCLUDELIB OLDNAMES
PUBLIC ?ptr2col@@YAPAVcolumn@@I@Z ; ptr2col
PUBLIC ?c_01@@3Vcolumn@@A ; c_01
PUBLIC ?c_02@@3Vcolumn@@A ; c_02
PUBLIC ?c_19@@3Vcolumn@@A ; c_19
EXTRN @__security_check_cookie@4:PROC
?c_01@@3Vcolumn@@A DB 01H DUP (?) ; c_01
ALIGN 4
?c_02@@3Vcolumn@@A DB 01H DUP (?) ; c_02
ALIGN 4
?c_19@@3Vcolumn@@A DB 01H DUP (?) ; c_19
; Function compile flags: /Ogtp
; File c:\dokumente und einstellungen\administrator\eigene dateien\visual studio 2010\projects\test6\test6\test6.cpp
; COMDAT ?ptr2col@@YAPAVcolumn@@I@Z
_TEXT SEGMENT
?ptr2col@@YAPAVcolumn@@I@Z PROC ; ptr2col, COMDAT
; $T5300 = eax
; 12 : column* ret;
; 13 : switch (intin)
00000 0f b6 88 00 00
00 00 movzx ecx, BYTE PTR $LN13@ptr2col[eax]
00007 ff 24 8d 00 00
00 00 jmp DWORD PTR $LN14@ptr2col[ecx*4]
$LN3@ptr2col:
; 14 : {
; 15 : //c_01 a q
; 16 : case 1:
; 17 : case 65: case 97: case 192: case 193: case 194: case 195: case 196: case 197: case 198:
; 18 : case 224: case 225: case 226: case 227: case 228: case 229: case 230: case 81: case 113:
; 19 : ret=&c_01;
0000e b8 00 00 00 00 mov eax, OFFSET ?c_01@@3Vcolumn@@A ; c_01
; 34 : }
; 35 : return ret;
; 36 : }
00013 c3 ret 0
$LN2@ptr2col:
; 20 : break;
; 21 : //c_02 e w
; 22 : case 2:
; 23 : case 69: case 101: case 200: case 201: case 202: case 203: case 232:
; 24 : case 233: case 234: case 235: case 240: case 87: case 119:
; 25 : ret=&c_02;
00014 b8 00 00 00 00 mov eax, OFFSET ?c_02@@3Vcolumn@@A ; c_02
; 34 : }
; 35 : return ret;
; 36 : }
00019 c3 ret 0
$LN8@ptr2col:
; 26 : break;
; 27 :
; 28 : // and so on etc. ............................
; 29 : // till
; 30 : //c_19 Rest
; 31 : case 19:
; 32 : default:
; 33 : ret=&c_19;
0001a b8 00 00 00 00 mov eax, OFFSET ?c_19@@3Vcolumn@@A ; c_19
; 34 : }
; 35 : return ret;
; 36 : }
0001f c3 ret 0
$LN14@ptr2col:
00020 00 00 00 00 DD $LN3@ptr2col
00024 00 00 00 00 DD $LN2@ptr2col
00028 00 00 00 00 DD $LN8@ptr2col
$LN13@ptr2col:
0002c 00 DB 0
0002d 01 DB 1
0002e 02 DB 2
0002f 02 DB 2
00030 02 DB 2
00031 02 DB 2
00032 02 DB 2
00033 02 DB 2
00034 02 DB 2
00035 02 DB 2
00036 02 DB 2
00037 02 DB 2
00038 02 DB 2
00039 02 DB 2
0003a 02 DB 2
0003b 02 DB 2
0003c 02 DB 2
0003d 02 DB 2
0003e 02 DB 2
0003f 02 DB 2
00040 02 DB 2
00041 02 DB 2
00042 02 DB 2
00043 02 DB 2
00044 02 DB 2
00045 02 DB 2
00046 02 DB 2
00047 02 DB 2
00048 02 DB 2
00049 02 DB 2
0004a 02 DB 2
0004b 02 DB 2
0004c 02 DB 2
0004d 02 DB 2
0004e 02 DB 2
0004f 02 DB 2
00050 02 DB 2
00051 02 DB 2
00052 02 DB 2
00053 02 DB 2
00054 02 DB 2
00055 02 DB 2
00056 02 DB 2
00057 02 DB 2
00058 02 DB 2
00059 02 DB 2
0005a 02 DB 2
0005b 02 DB 2
0005c 02 DB 2
0005d 02 DB 2
0005e 02 DB 2
0005f 02 DB 2
00060 02 DB 2
00061 02 DB 2
00062 02 DB 2
00063 02 DB 2
00064 02 DB 2
00065 02 DB 2
00066 02 DB 2
00067 02 DB 2
00068 02 DB 2
00069 02 DB 2
0006a 02 DB 2
0006b 02 DB 2
0006c 00 DB 0
0006d 02 DB 2
0006e 02 DB 2
0006f 02 DB 2
00070 01 DB 1
00071 02 DB 2
00072 02 DB 2
00073 02 DB 2
00074 02 DB 2
00075 02 DB 2
00076 02 DB 2
00077 02 DB 2
00078 02 DB 2
00079 02 DB 2
0007a 02 DB 2
0007b 02 DB 2
0007c 00 DB 0
0007d 02 DB 2
0007e 02 DB 2
0007f 02 DB 2
00080 02 DB 2
00081 02 DB 2
00082 01 DB 1
00083 02 DB 2
00084 02 DB 2
00085 02 DB 2
00086 02 DB 2
00087 02 DB 2
00088 02 DB 2
00089 02 DB 2
0008a 02 DB 2
0008b 02 DB 2
0008c 00 DB 0
0008d 02 DB 2
0008e 02 DB 2
0008f 02 DB 2
00090 01 DB 1
00091 02 DB 2
00092 02 DB 2
00093 02 DB 2
00094 02 DB 2
00095 02 DB 2
00096 02 DB 2
00097 02 DB 2
00098 02 DB 2
00099 02 DB 2
0009a 02 DB 2
0009b 02 DB 2
0009c 00 DB 0
0009d 02 DB 2
0009e 02 DB 2
0009f 02 DB 2
000a0 02 DB 2
000a1 02 DB 2
000a2 01 DB 1
000a3 02 DB 2
000a4 02 DB 2
000a5 02 DB 2
000a6 02 DB 2
000a7 02 DB 2
000a8 02 DB 2
000a9 02 DB 2
000aa 02 DB 2
000ab 02 DB 2
000ac 02 DB 2
000ad 02 DB 2
000ae 02 DB 2
000af 02 DB 2
000b0 02 DB 2
000b1 02 DB 2
000b2 02 DB 2
000b3 02 DB 2
000b4 02 DB 2
000b5 02 DB 2
000b6 02 DB 2
000b7 02 DB 2
000b8 02 DB 2
000b9 02 DB 2
000ba 02 DB 2
000bb 02 DB 2
000bc 02 DB 2
000bd 02 DB 2
000be 02 DB 2
000bf 02 DB 2
000c0 02 DB 2
000c1 02 DB 2
000c2 02 DB 2
000c3 02 DB 2
000c4 02 DB 2
000c5 02 DB 2
000c6 02 DB 2
000c7 02 DB 2
000c8 02 DB 2
000c9 02 DB 2
000ca 02 DB 2
000cb 02 DB 2
000cc 02 DB 2
000cd 02 DB 2
000ce 02 DB 2
000cf 02 DB 2
000d0 02 DB 2
000d1 02 DB 2
000d2 02 DB 2
000d3 02 DB 2
000d4 02 DB 2
000d5 02 DB 2
000d6 02 DB 2
000d7 02 DB 2
000d8 02 DB 2
000d9 02 DB 2
000da 02 DB 2
000db 02 DB 2
000dc 02 DB 2
000dd 02 DB 2
000de 02 DB 2
000df 02 DB 2
000e0 02 DB 2
000e1 02 DB 2
000e2 02 DB 2
000e3 02 DB 2
000e4 02 DB 2
000e5 02 DB 2
000e6 02 DB 2
000e7 02 DB 2
000e8 02 DB 2
000e9 02 DB 2
000ea 02 DB 2
000eb 00 DB 0
000ec 00 DB 0
000ed 00 DB 0
000ee 00 DB 0
000ef 00 DB 0
000f0 00 DB 0
000f1 00 DB 0
000f2 02 DB 2
000f3 01 DB 1
000f4 01 DB 1
000f5 01 DB 1
000f6 01 DB 1
000f7 02 DB 2
000f8 02 DB 2
000f9 02 DB 2
000fa 02 DB 2
000fb 02 DB 2
000fc 02 DB 2
000fd 02 DB 2
000fe 02 DB 2
000ff 02 DB 2
00100 02 DB 2
00101 02 DB 2
00102 02 DB 2
00103 02 DB 2
00104 02 DB 2
00105 02 DB 2
00106 02 DB 2
00107 02 DB 2
00108 02 DB 2
00109 02 DB 2
0010a 02 DB 2
0010b 00 DB 0
0010c 00 DB 0
0010d 00 DB 0
0010e 00 DB 0
0010f 00 DB 0
00110 00 DB 0
00111 00 DB 0
00112 02 DB 2
00113 01 DB 1
00114 01 DB 1
00115 01 DB 1
00116 01 DB 1
00117 02 DB 2
00118 02 DB 2
00119 02 DB 2
0011a 02 DB 2
0011b 01 DB 1
?ptr2col@@YAPAVcolumn@@I@Z ENDP ; ptr2col
_TEXT ENDS
PUBLIC _wmain
; Function compile flags: /Ogtp
; COMDAT _wmain
_TEXT SEGMENT
_argc$ = 8 ; size = 4
_argv$ = 12 ; size = 4
_wmain PROC ; COMDAT
; 40 : column *p = ptr2col(0);
; 41 : return 0;
00000 33 c0 xor eax, eax
; 42 : }
00002 c3 ret 0
_wmain ENDP
_TEXT ENDS
END
You see that the compiler actually uses a two-stage lookup (while I would have expected an ordinary direct lookup), the first lookup fetching an index (from $LN13@ptr2col) into a short table of jump target addresses ($LN14@ptr2col) from where it then gets the actual address to do an indirect jump to. That way it sacrifices a tiny bit of runtime performance for an almost four-fold reduction in lookup table size. It's most likely easy to tweak the optimization settings so that the compiler favors performance over table size reduction, but already the above confirms my point from the last post, so i did no further testing.
Re: Switch case or something better!
Quote:
Originally Posted by
Eri523
...now this statement raised my curiosity... :D
Great analysis.
I think the conclusion should be: don’t presume that you can outrun modern compiler. At least, not before serious profiling.
Offtop: Sorry Eri, but I am not allowed to rate your posts :(
Re: Switch case or something better!
FWIW, you can use chars in a switch statement too.
case 'a'
for example.
Re: Switch case or something better!
Quote:
Originally Posted by
VladimirF
Great analysis.
Thanks! :)
Quote:
I think the conclusion should be: don’t presume that you can outrun modern compiler. At least, not before serious profiling.
Right. It may sometimes pay to try to give the compiler something that's easier to optimize, but it's almost never worth the effort trying to to coerce it into doing something it wouldn't have done naturally anyway.
IMO this "clustered cases" optimization is rather specific, yet practice shows that this is a quite common scenario in everyday programming, so it's worth the effort to program that into the compiler.
Quote:
Offtop: Sorry Eri, but I am not allowed to rate your posts :(
I was able to rate yours, so this does not seem to be due to the current problems with the forum software. (This specifc post of yours may not actually have deserved a rating, but I think overall you deserve one from me from time to time... :)) The last rating I got from you (thanks again :)) was from Feb 29th, almost four weeks ago, but AFAICT the point in time when you can come back and rate a user's post again also depends on how many ratigngs you gave to other users in the meantime. So it's not so easy to calculate...
Re: Switch case or something better!
Thanks guys, :thumb:
Your comments have been great. Fantastic analysis Eri523!
Other systems may look nicer or read better, but the case system was really easy to build in Excel and then copy and paste LOL. Also, remember that an array would then have to be of type column* so would hold pointers to column objects! So I would physically be creating almost 300 pointers, whereby in the switch case a single pointer to an object is returned. Or I would have to return an int and translate this into a pointer with an if() or ironically a switch case LOL
GCDEF: Thanks for the comment! Yes, I know I could switch on char, and I might be wrong but I believe there is some additional overhead in doing this; I seem to remember reading about some kind of conversion that takes place specifically on switch case statements, which makes sense if they simply wrapped the original c header for this. I came to C++ from c and old habits die hard! LOL! And in fact I am entering a char directly into the ptr2col(unsignedint intin)function. So my call is similar to:
Code:
ptr2col(mystring[0])->addnode(n);
An int takes a char without any problem and is an excellent way to access char variables by their ASCII value.
Thanks again,
Rigsby
Re: Switch case or something better!
Quote:
Originally Posted by
Rigsby
[...] the case system was really easy to build in Excel and then copy and paste LOL.
Using VBA you may even have Excel write C++ code for you... :D (Of course that would only really pay if you need that multiple times.)
Quote:
Also, remember that an array would then have to be of type column* so would hold pointers to column objects! So I would physically be creating almost 300 pointers, whereby in the switch case a single pointer to an object is returned.
And what's so scary about something like:
Code:
column c_01, c_02, c_19;
column *pointer_array[] = { &c_01, &c_02, &c_19, &c_01, &c_02, &c_19 };
? As you already said yourself: You'd be instantiating about 300 cheap pointers, not 300 column objects of whatever complexity.
Quote:
[...] Yes, I know I could switch on char, and I might be wrong but I believe there is some additional overhead in doing this; I seem to remember reading about some kind of conversion that takes place specifically on switch case statements [...].
Yes, there would be a conversion overhead involved, but probably that would merely be that of a MOVZX (or MOVSX, see below) instruction versus an ordinary MOV, or three clock cycles versus one. (The figures are taken from a 17 years old Pentium 4 manual that is the only reference about that I have at hand here right now, but that probably hasn't changed much since then, and at least the principle will hold true.) This difference actually is quite small and it may even get hidden entirely by the CPU-internal runtime optimization mechanisms. The numerical difference in clock ticks is three-fold which looks much, but probably is rather irrelevant comapred to the clock ticks consumed by the rest of your code.
Also, that conversion is by no means specific to switch statements in any way. It's an ordinary type conversion between types of different bitness.
Quote:
[...] And in fact I am entering a char directly into the ptr2col(unsignedint intin)[/FONT][FONT=Calibri]function. So my call is similar to:
Code:
ptr2col(mystring[0])->addnode(n);
An int takes a char without any problem and is an excellent way to access char variables by their ASCII value.
In that case you need to be aware that the standard C++ char type is signed, which, in such a scenario, may get you into trouble with characters above the standard ASCII range from 0x00 to 0x7F and code like what you've posted. (At least for VC++ this can be changed using the command line option /J, but of course that way your code would not be standard-conformant, i.e. not portable.)
