I found that I had a wrong assumption on this issue. In order to use Perfect Hash Table, we need to know every key values at compile time, but the key values are determined at run-time so that it is not feasible idea.
On my project, however, the key values were fixed amount, so that I confused at that point. I'm sorry... Jay On Mon, Mar 15, 2010 at 12:19 AM, Jae Hyuk Kwak <wrice...@gmail.com> wrote: > 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} *** >> >
