Running out of memory in a simple monad

[Alastair Reid]

David Bergman <davidb@home.se> writes:
> One problem, though, is that I would like not to get rid of the CAF,
> since I (presumably wrongly) assume that CAFs are implemented more
> efficiently in Hugs than "normal" definitions. Am I right in this
> assumption?

There isn't much to choose between them in raw efficiency.  A rough
initial analysis is:
  
  CAFs are looked up in an array of all definitions - access is small
  constant time.
  
  non-CAFs are looked up in an environment which is potentially linear
  in size of environment but environments are very small and, perhaps
  more significantly, has been optimized so that it is usually small
  constant time.
  
  Adding a CAF to an environment would add one 'cell' (8 bytes) to heap
  consumption but, again, optimizations of environment building should
  mean that environments get built rarely and are shared effectively.

  [note that these are per-CAF costs]
  
Much more significant than these raw costs are the issues of how many
times an expression is evaluated and how much space it takes to store
these results between evaluations.  I'd expect typical costs to these
to be 10-1000 times larger than the raw costs given above.  I think
that many of these questions can't readily be answered by existing
techniques and that some are outside the scope of what we normally ask
optimizers to do because they boil down to space-time tradeoffs and
solving these requires a lot of contextual information about the
application, the input data, desired response times, capability of
target machine(s), acceptable impact on other applications running on
same machine, etc.  Anyone out there wanting a topic for their PhD?

--
Alastair Reid                 alastair@reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/