home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / sys / transput / 1238 < prev    next >
Encoding:
Text File  |  1992-11-22  |  3.1 KB  |  78 lines
  1. Newsgroups: comp.sys.transputer
  2. Path: sparky!uunet!inmos!titan.inmos.co.uk!news
  3. From: stevec@wren.inmos.co.uk (Stephen Clarke)
  4. Subject: Tail-call optimisation [WAS Re: IS Occam3 recursive?]
  5. Message-ID: <1992Nov23.114322.28686@titan.inmos.co.uk>
  6. Sender: news@titan.inmos.co.uk
  7. Reply-To: stevec@inmos.co.uk (Stephen Clarke)
  8. Organization: INMOS Limited, Bristol, UK.
  9. References: <1992Nov17.093335.11067@inmos.co.uk> <Bxuxz5.F0E@cs.bham.ac.uk> <1992Nov18.130407.12799@titan.inmos.co.uk> <rob.722124411@dutncp8> <BxyLs4.Hn5@sci.kun.nl>
  10. Date: Mon, 23 Nov 1992 11:43:22 GMT
  11. Lines: 65
  12.  
  13. In article <BxyLs4.Hn5@sci.kun.nl> marcok@cs.kun.nl (Marco Kesseler) writes:
  14. >In article <1992Nov18.130407.12799@titan.inmos.co.uk> Stephen Doyle,
  15. >steved@lion.inmos.co.uk writes:
  16. >>INMOS' soon to be shipping new
  17. >optimising C 
  18. >>compiler has a specific optimisation for tail call recursion i.e.
  19. >>
  20. >>void p (int q)
  21. >>{
  22. >>  ...
  23. >>  return(p(...));
  24. >>}
  25. >>
  26. >>in this case the workspace of p is reused as the function recurses,
  27. >also, 
  28. >>nested returns are omitted so that only one return is needed no matter
  29. >how many 
  30. >>levels of recursion take place.
  31. >
  32. >The compatibility issues mentioned above make me wonder if such
  33. >an 'optimisation' is conform ANSI standards. Forgive me my ignorance,
  34. >but would such a procedure work in any implementation of ANSI C?
  35. >It guess this is a new feature of C.
  36.  
  37. Provided that you check that certain enabling conditions are satisfied
  38. (eg. you haven't put the addresses of local variables in global data),
  39. then tail-call optimisation is perfectly legal according to the ANSI
  40. standard for C, and a very large number of C compilers (including gcc)
  41. implement this optimisation.  It is not a new feature of C, just an
  42. optimisation technique.
  43.  
  44. (Incidentally, none of the optimisations performed in INMOS' C compiler
  45. violates the ANSI standard for C.)
  46.  
  47. >Perhaps a rather superfluous
  48. >thing to do as well. C has loops.
  49.  
  50. Although you can express tail-recursion in terms of loops in C, you cannot
  51. express the more general case of tail-calling at source level in C.
  52.  
  53. As an example of the effect of tail-call optimisation, when compiling the
  54. SPEC  benchmark 'li' for the transputer, tail call optimisation reduces
  55. stack usage from 4700 bytes to 4000 bytes, meaning you can fit the entire
  56. stack in on-chip memory, this alone provides a 12% speed-up.
  57.  
  58. 'li' is written in C and it was chosen to be part of the SPEC benchmark
  59. suite because it is typical of a certain type of application: I don't
  60. think that this speed-up on a 'typical' application is superfluous.
  61.  
  62. ('li' is an xlisp interpreter executing a lisp program to solve the
  63. 8-queens problem, so it is about as recursive as they come.
  64. You wouldn't generally expect this kind of speed-up from tail-call
  65. optimisation (though I have seen speed-ups of 20% for a simple coding
  66. of the Ackermann function), but for all those heavily recursive
  67. applications, tail-call optimisation is definitely worthwhile.)
  68.  
  69. >Marco
  70.  
  71. Cheers,
  72. Steve.
  73.  
  74. ---
  75. Stephen Clarke      INMOS Ltd, Bristol | EMail(UK) stevec@inmos.co.uk
  76. The opinions above are my personal     | Internet: stevec@inmos.com
  77. views and do not reflect INMOS policy. |
  78.