home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2034 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  4.2 KB
  1. Path: sparky!uunet!olivea!spool.mu.edu!uwm.edu!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: pcg@aber.ac.uk (Piercarlo Grandi)
  3. Newsgroups: comp.compilers
  4. Subject: Re: static estimation of conditional branches?
  5. Keywords: optimize, analysis, algol68
  6. Message-ID: <92-12-066@comp.compilers>
  7. Date: 15 Dec 92 15:36:14 GMT
  8. References: <92-12-029@comp.compilers> <92-12-047@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: pcg@aber.ac.uk (Piercarlo Grandi)
  11. Organization: Prifysgol Cymru, Aberystwyth
  12. Lines: 75
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. (Herman Rubin) writes:
  16. > ... the programmer should have some way of communicating this,
  17. > and other, frequency considerations to the compiler.  As far as
  18. > I know, this has not been done since the "FREQUENCY" statement
  19. > in fairly early Fortran.  [As I recall, Fortran II dropped
  20. > FREQUENCY because it was infrequently used and made little
  21. > difference.  I've heard that it may even have been implemented
  22. > backwards and nobody noticed. -John]
  23.  
  24. Actually there was an Algol 68 compiler with a kind of 'rarely' gragma, to
  25. be used usually after then or else, as in
  26.  
  27.     IF a < b THEN ... ELSE PR rarely PR ... FI
  28.  
  29. Such a pragma has important performance effects; not only it helps with
  30. instruction scheduling, and avoiding wasting optimizer effort and table
  31. space on infrequently executed basic blocks, it also allows the rarely
  32. executed code to be offlined to some other section of the executable.
  33.  
  34. This often substantially reduces the working set of the code, as in most
  35. production programs a lot of code is involved only in initial setup, and
  36. in error handling, and it is only executed once or never at all; and it's
  37. bad if it gets interspepsed within the code that really does the work.
  38.  
  39. Henry Spencer responded:
  40. > The other problem that occurs with such facilities is that
  41. > programmer intuition is notoriously unreliable about such things.
  42.  
  43. But this is not a compiler problem -- it is a programmer education
  44. problem. If the programmer does not know the macroscopic performance
  45. profile of the algorithms used, then too bad. And intuition has nothing to
  46. do with knowing such things; programmers that deserve the title either
  47. know the properties of the algorithms they use, or they analyze them with
  48. the right tools; not many do either.
  49.  
  50. I reckon that one of the two cases where even a programmer often gets
  51. surprised is not the level of algorithmic complexity, but at the level of
  52. the actual implementation and its interactions with the performance
  53. profile of the environment, which is often poorly documented.
  54.  
  55. The other major cause of programmer surprise is that quite often the input
  56. data fed to the program is quite different in consequences from that
  57. expected by the programmer; and because such a case is frequent, this is
  58. often not terribly useful:
  59.  
  60. > Now, if you amend Herman's statement to "the *profiler* should
  61. > have some way of communicating this...", I'd agree... and observe
  62. > that there are already compilers that will accept profiler data
  63. > and exploit it for optimization.
  64.  
  65. because the profiler data can be misleading unless the data used to
  66. generate the profile fed to the optimizer can be guaranteed to be typical.
  67. But then a programmer that knows which input data are typical as to the
  68. performance of his program already knows its performance profile, or at
  69. least is competent enough to also be able to understand the algorithms he
  70. uses and interpret and weight profiler data.
  71.  
  72. Unfortunately most programmers don't have a clue as to the performance
  73. profile of the algorithms they use, and cannot interpret profile data, and
  74. equivalently could not choose a set of appropriate input data for the runs
  75. that would drive the optimizer.
  76.  
  77. > I don't know whether they do this particular optimization, but I
  78. > wouldn't be surprised.
  79.  
  80. There are some compilers that use profiler output, e.g. notably the MIPS
  81. compilers. But Hank Dietz (if I remember well) has done some studies on
  82. (looping) branch prediction and apparently static prediction works well
  83. there too.
  84.  
  85. --
  86. Piercarlo Grandi, Dept of CS, PC/UW@Aberystwyth <pcg@aber.ac.uk>
  87. -- 
  88. Send compilers articles to compilers@iecc.cambridge.ma.us or
  89. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  90.