home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compiler / 1944 < prev    next >
Encoding:
Text File  |  1992-11-24  |  2.0 KB  |  49 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: chased@rbbb.Eng.Sun.COM (David Chase)
  4. Subject: Re: optimizing case-statement execution
  5. Reply-To: chased@rbbb.Eng.Sun.COM (David Chase)
  6. Organization: Sun Microsystems, Mt. View, Ca.
  7. Date: Mon, 23 Nov 1992 20:44:07 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-11-136@comp.compilers>
  10. Keywords: C, code, optimize
  11. References: <92-11-126@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 34
  14.  
  15. raymond@harp.ecn.purdue.edu (Ray Kamin) writes:
  16. >How do compilers (in my case gcc v2.2.2) handle large switch statements?
  17. >I have a 120 way switch in my code.  I looked at the sparc assembly code
  18. >produced by gcc and it apparently doesn't use any sort of jump table, but
  19. >merely does sequential comparisons and branches.
  20.  
  21. >With this in mind, I rewrote the code [with an array of function pointers].
  22.  
  23. >The code is working correctly, however, it is not any faster at all.  Does
  24. >anyone have any insight into this, or how this should be written for speed?
  25.  
  26. Sure -- log N grows pretty slowly.  I'm pretty sure that 120 compact
  27. cases go faster if you use a table lookup, but not by much.  Last time
  28. I looked hard at this, break-even was somewhere around 32 (for
  29. "binary" (*) search versus table lookup), but handling 128 cases is
  30. only two compares and two branches more per switch execution.  You're
  31. lucky your code didn't run slower, seeing as how you added parameter
  32. movement, a return, and (possibly) a SAVE and RESTORE pair per switch
  33. execution.
  34.  
  35. >[There are three general ways to generate code for a switch: a jump table,
  36. >...a binary-compare and branch tree, ... a sequential compare and branch.
  37.  
  38. Don't forget hash tables, though they may not always be appropriate.
  39.  
  40. (*) "Binary" means that the appropriately weighted tree should be in
  41. cost-balance.  This includes accounting both for case-frequency and
  42. taken/not-taken branch costs.
  43.  
  44. David Chase
  45. Sun
  46. -- 
  47. Send compilers articles to compilers@iecc.cambridge.ma.us or
  48. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  49.