On Sat, Dec 06, 2008 at 08:23:48AM +0100, Lemmih wrote:
I've been looking at some grin output and it seems that tags have been dropped in favour of indirect calls. That is, 'eval' now does an indirect call instead of inspecting the node tag. Is there a reason for this?
There were a couple reasons that functionality was added, Mainly it came down to flexibility of implementation. It provides a straightforward path for separate compilation. It is not intended that indirect calls be used always for evaluation, it just provides a universal fall-back case when direct execution is not appropriate for various reasons. Although jhc is a whole program optimizer, some support for separate compilation would be very convinient, if nothing else it will be needed for dynamic code loading at run-time. Another reason had to do with the points-to analysis, I found myself "chasing my tail" a lot of the time, in the face of features such as arbitrary impredicativity and GADTs, it became harder and harder to ensure the points-to analysis would produce an accurate and useful result in all possible cases, being able to fall back on an indirect evaluation in those cases simplified things dramatically. improving the front end, and improving the accuracy of the point-to analysis could be decoupled and no longer had to be done in lock-step. The dynamic nature of haskell programs also played a part, when looking at a histogram of the number of targets a given heap location could evaluate to it was very tail-heavy, I found that by far, exactly 1 was the most common possibility. Furthermore, after a point, the size of the jump table in the cache killed the advantage of the direct call over an indirect one. So all in all, it made sense to concentrate on a couple cases, the direct case, when you can reduce the number of possibilities to just a couple choices, and the fallback case where an indirect call is used. Note that where the "sweet spot" lies for optimal performance in terms of direct vs indirect execution is rather CPU architecture dependent. http://www.complang.tuwien.ac.at/forth/threading/ contains some test code for testing various threading methods in a forth implementation, which is somewhat relevant at least in demonstrating how different CPUs behave. John -- John Meacham - ⑆repetae.net⑆john⑈