Thank you Basile. The article you pointed is exactly what I wanted to find. The paper summarized switch optimization very well, and it enlightened me. I am also glad that it mentioned imperfect and perfect hash for switch statement.
Unfortunately, the super-optimization that the paper suggests doesn't adopt any of hash table ways. In addition, the paper skimmed the advantage of perfect hash table and it didn't even mention minimal perfect hash table at all. I think that for the "speed" optimization, perfect hash way is the best candidate after jump table if it is applicable. I am currently working on PlayStation3 game development, and we don't want to use branch operation. Since 3d games value relatively more on speed than space, I am still interested on perfect hash for switch statement, because it is more generic than others the paper mentioned. It will also require (possibly) zero branching. It would be not only my personal preference but also the favorite of most game developers. As usual for 3d game programming process, we have pre-calculation steps for graphics data. During the process I am thinking to add one more process that generates perfect hash table. The manual implementation of perfect hash table as an alternative mean for switch statement does not seem hard. So I may do it by myself without too much pain, but It can make my job easier if gcc can play the role. I wish to see gcc can adopt any of better switch optimization ways in near future. I haven't heard about "MELT" before and still don't know what exactly it is. Is it able to deal with this kind of problem? Thank you anyway. Without the reply mail, I couldn't be satisfied this much. :-) Regards, Jay On Sun, Mar 14, 2010 at 3:59 PM, Basile Starynkevitch <bas...@starynkevitch.net> wrote: > Jae Hyuk Kwak wrote: >> >> Hello, GCC developers. >> >> In addition, I found that switch statement can use "Hash Table" rather >> than just replacing with "else if". >> Besides using "jump table", "Hash Table" can increase speed. >> Hash table idea can alleviate the problem of a huge size of jump table as >> well. >> > > > It is much more complex than that. Read the paper "A Superoptimizer > Analysis of Multiway Branch Code Generation" by Roger A. Sayle in GCC summit > 2008 proceedings. www.gccsummit.org/2008/gcc-2008-proceedings.pdf > > Regards. > -- > Basile STARYNKEVITCH http://starynkevitch.net/Basile/ > email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359 > 8, rue de la Faiencerie, 92340 Bourg La Reine, France > *** opinions {are only mines, sont seulement les miennes} *** >
