C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  HOWTO: Need performance improvement for SWITCH-CASE inside F Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message BV Guest Posted: Sat Aug 14, 2004 4:36 am    Post subject: HOWTO: Need performance improvement for SWITCH-CASE inside F Suppose that performance (obviously an issue!) in the example below needs to be improved, how can this be done? This is a program snippet that performs some operations on 1-dimensional array that's inside a for-loop, then switch-case. Can some performance be gained using STL, and how? for(int i=0; i<50; i++) { switch (char_string[i]) { case 1: //some strcat() operation break; case 2: //some strcat() operation break; Back to top Andrea Griffini Guest Posted: Sat Aug 14, 2004 10:38 am    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi On 14 Aug 2004 00:36:26 -0400, BV <dont (AT) bug (DOT) me> wrote: Quote: Suppose that performance (obviously an issue!) in the example below needs to be improved, how can this be done? This is a program snippet that performs some operations on 1-dimensional array that's inside a for-loop, then switch-case. Can some performance be gained using STL, and how? for(int i=0; i<50; i++) { switch (char_string[i]) { case 1: //some strcat() operation break; case 2: //some strcat() operation break; Compilers are normally quite good at implementing switch statements, so my suspect is that the performance problem is not the "switch" but the part you omitted (strcat). If the string you are building is big you should remember that every time you use strcat the library has to read from the start of the buffer to see where is the first ''. This will make your "translation" operation O(n^2) in the length of the string. A faster alternative I can think to is something like the following: void writestr(char *& dest,const char *src) { while ( (*dest=*src++)!='' ) ++dest; } used as: ... char *wp = destination_buffer; for (int i=0; i<50; i++) { switch(char_string[i]) { case 1: ... writestr(wp,repl1a); ... writestr(wp,repl1b); ... writestr(wp,repl1c); break; case 2: ... writestr(wp,repl2); ... } } These are the result I got with a little test... do_nothing does nothing inside cases do_strcat uses strcat(buffer,str) do_sprintf1 uses wp += sprintf(buffer,str) do_sprintf2 uses wp += sprintf(buffer,"%s",str) do_writestr uses writestr(wp,str) Borland BCC55 do_nothing = 0.079s do_strcat = 2.031s do_sprintf1 = 1.297s do_sprintf2 = 0.953s do_writestr = 0.312s Visual C++ Toolkit 2003 do_nothing = 0.000s do_strcat = 0.843s do_sprintf1 = 1.000s do_sprintf2 = 0.750s do_writestr = 0.141s Visual C++ 6 do_nothing = 0.015s do_strcat = 1.438s do_sprintf1 = 1.109s do_sprintf2 = 0.766s do_writestr = 0.203s g++ 3.2 (cygwin) do_nothing = 0.016s do_strcat = 0.640s do_sprintf1 = 3.094s do_sprintf2 = 4.078s do_writestr = 0.157s Of course these tests are nowhere nearly as useful as tests done on your real data and real code. Nowdays things are so complex both at the hardware level and at the software level that optimization is no more an exact science even on a single specific installation. Just experiment, measure, and decide. HTH Andrea [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Vaclav Haisman Guest Posted: Sat Aug 14, 2004 1:30 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi You can make a table with pointers to functions that do the work and instead of the switch use table lookup. Or if you do always some strcat operation you can store the parameters inside the table and omit the functions. V.H. "BV" <dont (AT) bug (DOT) me> wrote Quote: Suppose that performance (obviously an issue!) in the example below needs to be improved, how can this be done? This is a program snippet that performs some operations on 1-dimensional array that's inside a for-loop, then switch-case. Can some performance be gained using STL, and how? for(int i=0; i<50; i++) { switch (char_string[i]) { case 1: //some strcat() operation break; case 2: //some strcat() operation break; . . . . case 50: //etc. break; .... } } [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Sat Aug 14, 2004 1:32 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi In article <cfj5ve$cid$1 (AT) ls219 (DOT) htnet.hr>, BV <dont (AT) bug (DOT) me> writes Quote: Suppose that performance (obviously an issue!) in the example below needs to be improved, how can this be done? What makes you think that it can be improved? Compilers optimises switch statements pretty well. One way they do it is by creating a 'jump-table' that is indexed by the control integer. Quote: This is a program snippet that performs some operations on 1-dimensional array that's inside a for-loop, then switch-case. Can some performance be gained using STL, and how? for(int i=0; i<50; i++) { switch (char_string[i]) { case 1: //some strcat() operation break; case 2: //some strcat() operation break; . . . . case 50: //etc. break; .... } } -- Francis Glassborow ACCU Author of 'You Can Do It!' see http://www.spellen.org/youcandoit For project ideas and contributions: http://www.spellen.org/youcandoit/projects [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alex Vinokur Guest Posted: Sat Aug 14, 2004 1:33 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi "BV" <dont (AT) bug (DOT) me> wrote Quote: Suppose that performance (obviously an issue!) in the example below needs to be improved, how can this be done? This is a program snippet that performs some operations on 1-dimensional array that's inside a for-loop, then switch-case. Can some performance be gained using STL, and how? for(int i=0; i<50; i++) { switch (char_string[i]) { case 1: //some strcat() operation break; case 2: //some strcat() operation break; . . . . case 50: //etc. break; .... } } [snip] It seems that using switch is the fastest way to do that. See also the thread titled "How to redesign big switch case?" at http://groups.google.com/groups?threadm=Ggu7c.14785%24PY1.328948%40bgtnsc05-news.ops.worldnet.att.net -- Alex Vinokur http://mathforum.org/library/view/10978.html http://sourceforge.net/users/alexvn [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Sat Aug 14, 2004 6:27 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi [email]agriff (AT) tin (DOT) it[/email] (Andrea Griffini) wrote (abridged): Quote: A faster alternative I can think to is something like the following: void writestr(char *& dest,const char *src) { while ( (*dest=*src++)!='' ) ++dest; } Good idea. It might be faster to avoid the dereferences in the inner loop, and the side-effect on the argument, by returning the end pointer: char *writestr( char *dest, const char *src ) { while ((*dest = *src) != '') ++dest, ++src; return dest; } used like: wp = writestr( wp, repl1a ); I find this clearer anyway. I hate side effects. Compilers often optimise better when everything is local. In your version, dest might be an alias of src. -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top BV Guest Posted: Sat Aug 14, 2004 6:31 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi Quote: Suppose that performance (obviously an issue!) in the example below needs to be improved, how can this be done? This is a program snippet that performs some operations on 1-dimensional array that's inside a for-loop, then switch-case. Can some performance be gained using STL, and how? for(int i=0; i<50; i++) { switch (char_string[i]) { case 1: //some strcat() operation break; case 2: //some strcat() operation break; . . . . case 50: //etc. break; .... } } Thanks for your replies. Actually I did tests today when I converted the switch-case to use a jump-table. No gains whatsoever. I did some tests by converting strcat() to use append() from STL but things only got worse because results were much slower. [I don't know what I'm saying here I'm a STL newbie] The strings I'm doing with strcat() are not longer than 25 characters, but they are all assembled in the switch-case structure. I did tests as you Andrea instructed and I'm thrilled that I got faster results! Your function is great ))) Anyone got anything faster? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bronek Kozicki Guest Posted: Sat Aug 14, 2004 6:33 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi Andrea Griffini wrote: Quote: If the string you are building is big you should remember that every time you use strcat the library has to read from the start of the buffer to see where is the first ''. This is good point.If using C++ is an option here, I'd suggest trying std::string, from two or more different implementation of standard C++ library if possible. B. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David B. Held Guest Posted: Sun Aug 15, 2004 10:52 am    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi Dave Harris wrote: Quote: [...] char *writestr( char *dest, const char *src ) { while ((*dest = *src) != '') ++dest, ++src; return dest; } [...] This is spelled "stpcpy()" in some non-standard implementations (such as GCC). And when a platform doesn't have it, I always write it anyway, because it's so useful. Dave [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrea Griffini Guest Posted: Sun Aug 15, 2004 10:53 am    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi On 14 Aug 2004 14:27:58 -0400, [email]brangdon (AT) cix (DOT) co.uk[/email] (Dave Harris) wrote: Quote: Good idea. It might be faster to avoid the dereferences in the inner loop, and the side-effect on the argument, by returning the end pointer: char *writestr( char *dest, const char *src ) { while ((*dest = *src) != '') ++dest, ++src; return dest; } used like: wp = writestr( wp, repl1a ); This is what I was used to, but for no real reason I found myself using "char *&" parameters every now and then. In this case it was a bad idea indeed. Quote: I find this clearer anyway. I hate side effects. Compilers often optimise better when everything is local. In your version, dest might be an alias of src. Yeah. Compiler must be paranoid, and this is good. Long time ago I was working in the realtime 3D field, and it was depressing not being able to tell the compiler that some bad aliasing was not going to happen. And that is IMO the reason for which a human can still write better assembler code than a compiler; the two are not solving the same problem: the human is solving the "real" problem while the compiler is translating a piece of C++ code to assembler... a completely different thing. This kind of added "semantic noise" is probably unavoidable. And indeed with BCC55, VC++ 6 and g++ for example writestr2 is quite faster than writestr. With Visual C++ 2003 the speed is the same... I suppose that given that the compiler in my test program sees the whole thing the optimizer is able to prove there is no alias. Impressive. BCC55 do_writestr = 0.312s do_writestr2 = 0.188s VC++ 2003 do_writestr = 0.141s do_writestr2 = 0.141s VC++ 6 do_writestr = 0.203s do_writestr2 = 0.157s g++ do_writestr = 0.157s do_writestr2 = 0.109s Andrea [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top AndyCanfield Guest Posted: Sun Aug 15, 2004 10:57 am    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi What about setting up your const char* into an array and then use Duff's device to unroll the 0 to 50 loop. Then modify Andrea's function to also increment i? int count = 50; int n=(count+7)/8; int i = 0; char *wp = destination_buffer; const char *src; switch(count%{ case 0: do{ src=arrayOfStrings[i];writestr(i,wp,src); case 7: src=arrayOfStrings[i];writestr(i,wp,src); case 6: src=arrayOfStrings[i];writestr(i,wp,src); case 5: src=arrayOfStrings[i];writestr(i,wp,src); case 4: src=arrayOfStrings[i];writestr(i,wp,src); case 3: src=arrayOfStrings[i];writestr(i,wp,src); case 2: src=arrayOfStrings[i];writestr(i,wp,src); case 1: src=arrayOfStrings[i];writestr(i,wp,src); }while(--n > 0); } where Andrea's function has been modified like so? void writestr(int &i,char *& dest,const char *src){ while ( (*dest=*src++)!='' ) ++dest; i++; } Because Andrea's function is very fast the only other way I see to speed it up would be to unroll your outer loop. I have used Duff's device in the past to unroll loops which copy one file buffer to another and it does seem to add speed to that quit well. Perhapse it would work in this case also. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alex Vinokur Guest Posted: Sun Aug 15, 2004 11:01 am    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi "Andrea Griffini" <agriff (AT) tin (DOT) it> wrote Quote: On 14 Aug 2004 00:36:26 -0400, BV <dont (AT) bug (DOT) me> wrote: [snip] If the string you are building is big you should remember that every time you use strcat the library has to read from the start of the buffer to see where is the first ''. This will make your "translation" operation O(n^2) in the length of the string. A faster alternative I can think to is something like the following: void writestr(char *& dest,const char *src) { while ( (*dest=*src++)!='' ) ++dest; } [snip] Why do we need strcat()? In other words, can we always use writestr() instead strcat()? -- Alex Vinokur http://mathforum.org/library/view/10978.html http://sourceforge.net/users/alexvn [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Sun Aug 15, 2004 2:21 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi In article <cflfo6$otd$1 (AT) ls219 (DOT) htnet.hr>, BV <dont (AT) bug (DOT) me> writes Quote: I did some tests by converting strcat() to use append() from STL but things only got worse because results were much slower. [I don't know what I'm saying here I'm a STL newbie] Did you pre-allocate enough memory? If not std::string will have very poor performance as it will repeatedly copy the data to a new location. -- Francis Glassborow ACCU Author of 'You Can Do It!' see http://www.spellen.org/youcandoit For project ideas and contributions: http://www.spellen.org/youcandoit/projects [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Radoslaw Grzanka Guest Posted: Sun Aug 15, 2004 2:22 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi Dnia Sat, 14 Aug 2004 14:31:59 -0400, BV napisa=B3(a): Hi, Quote: I did some tests by converting strcat() to use append() from STL but things only got worse because results were much slower. [I don't know what I'm saying here I'm a STL newbie] What compiler are you using and are options for optimilizing on? I don't mean STL should be faster but much slower? I have dubts. At least not from my experience. Best Regards, Radoslaw -- "Oceniaj=B1 mnie, cho=E6 nic o mnie nie wiedz=B1. To dlatego jestem sam" - = Shrek ========================== ========================== ========================== = e-mail: sad[na]rpg[kropka]pl JID: radekg[na]chrome[kropka]p= l L:C++ E+++ T-- !R P+++ D G++ F:ADoM RL--- !RLA W:CP Q++ AI++ RN+ Hp- Re++ S= + [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David B. Held Guest Posted: Sun Aug 15, 2004 10:46 pm    Post subject: Re: HOWTO: Need performance improvement for SWITCH-CASE insi Alex Vinokur wrote: Quote: [...] Why do we need strcat()? In other words, can we always use writestr() instead strcat()? Technically, yes. But you will often want to save the returned pointer, which strcat() avoids having to do. It's the difference between: char buf[1024]; strcpy(buf, "Hello "); strcat(buf, "world"); strcat(buf, "."); and: char buf[1024]; char* s = buf; s = stpcpy(s, "Hello "); s = stpcpy(s, "world"); stpcpy(s, "."); If all you have is a reference to the start of a string, then strcat() is handy, since you will need to do a strlen() or something to get the end of the string anyway. It is only in the multiple sequential use cases where it is inefficient. Dave [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.