Re: Q: access to subprogram

[rogoff@sccm.Stanford.EDU (Brian Rogoff)]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
   Concerning performance models:
       I spent this afternoon (when not talking to students) taking the
       integration example and beefing it up to the point where it would
       plausibly take a reasonable amount of time.  I produced three
       versions:

	   Ada (using generic instantiation)
		   compiled with gnatmake -gnatp -cargs -O4
		   Size: 94 lines.

	   Pascal (using nested procedures passed as parameters)
		   compiled with SPARCompiler 4.0 pc -s -native -O4
		   Size: 57 lines.

	   Scheme
		   compiled with stalin -copt "-O4" -d -On -dc
		   (this compiles Scheme to C, then uses gcc as a back end)
		   Size: 40 lines.

       Guess what:  the Pascal and Ada versions both took 18 seconds on
       a "sunu4, Ultra-Enterprise", whatever that is, while the Scheme
       version took 6 seconds.

   I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive"
   for many programmers.

Note that the Pascal compiler was not any better than GNAT on this. The data 
does suggest that the nested procedure approach may have performance 
advantages in addition to its general advantages as a simple programming 
construct. What is stalin doing? Is it dependent on any simplifying 
assumptions about the code?

   To be really honest, I *thought* I knew what the cost model for generics
   was, but have heard repeatedly in this newsgroup that I shouldn't think
   of generic instantiation as macro instantiation.

I like Ada generics, but this is one of those cases where using generics as 
a workaround seems ugly to me, so I'd write integrators differently. I agree 
with your point that generics are one of the parts of the language model where 
the performance model is less clear.

   >>  Most of all, consider the effect on program style and clarity.

   In this particular case (big is bad).
	   Scheme : Pascal	: Ada
   Size	4      : 6      : 9
   Time	1      : 3      : 3

   DO NOT EXTRAPOLATE THE SIZE OR TIME NUMBERS TO OTHER KINDS OF PROBLEMS.

This is a nice little example of the conciseness of this style, and I think 
anyone would be hard pressed to say that the Ada version would be more 
readable.

   >I am not the right person to argue against this, since I think it should have 
   >been part of the language, but there are arguments about the effect of this 
   >feature on implementations using shared generics, and about the impact on 
   >existing implementations.

   I must have missed the discussion of how this would affect shared generics.
   I am all in favour of shared generics, but surely generics cannot _always_
   be shared, so there's always a fallback strategy, or have I misunderstood?

It was one of the refs in Norman Cohen's precis of the discussion, from 
Randy Brukardt at RR Software. Here is the relevant excerpt:

--------------------------------------------------------------------------- 
To put the problem in a nutshell:
 
If 'Access is allowed in generic bodies, generic code sharing requires
distributed overhead.  (Or compilers have to do body analysis of generics
in order to prevent sharing on them).
 
To explain this in detail, I'd have to give a crash course on the construction
of shared generics.  However, here is a simplified version of the problem:
A shared generic passes in some way a pointer to a data area identifying the
generic, and containing its local objects.  [Note that this exists in any but
the most simplified versions of sharing - any sharing algorithm which allows
data in the generic specification or body would have the problem].
However, an access-to-subprogram does not know that the routine comes from
a generic, or even which generic.  The solution to this problem in the
specification is to construct a 'wrapper' routine at instantiation time,
which knows about the appropriate generic instantiation.
 
However, a wrapper cannot be built for 'Accesses in the generic body
inside the generic body.  To do so at instantiation time requires that the
body be compiled before the instantiation, something that has generally been
considered bad in Ada 83.  Doing so eliminates virtually all of the advantages
of sharing.  The main alternative would be to carry and add generic data to
every use of a access to subprogram object - a significant distributed
overhead.
 
(Note that GNU's solution of generating the wrapper at runtime will not work
on some operating systems, because these systems prohibit self-modifying code
for security reasons.  We have even had problems doing this on some UNIX
systems, for this reason.  Therefore, it is not a generally applicable
solution).
 
The result that that eliminating the restrictions on 'Access would make some
code easy to write, but would force the junking of existing code sharing
algorithms, or make the cost of access-to-subprogram substantially higher than
in competing languages.  Those both are very bad ideas.
 
 
                                Randy.
--------------------------------------------------------------------------- 
 

   >Almost all of the books on functional programming use full "upward" closures, 
   >which are not quite what Ada would get if these get added to GNAT say.

   This is misleading.  They use *languages* in which there are few or no
   restrictions on closures.  This does not mean that every *program* using
   closures in these books or in day-to-day functional programming uses
   upward closures all over the place.

How much are upward funargs used in day to day functional programming? I 
think Bob Duff is still looking for a compelling example of why they are 
so much better than the explicitly simulated closure via an instance of a 
tagged type.

   >Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing 
   >it were different. But for me the choice is not between Ada 95 and Clean or 
   >ML, but Ada 95 and C++. Ada 95 still looks very good ;-).

   Well, if you want object orientation, there's O'Caml, which is supposed to
   be pretty good.  

I've played with it. The Win NT versions' GUI doesn't work. The language is 
nice, but I often do work where I can't tolerate boxing of certain types, 
like numerical or pixel types in arrays, and CAML is a bit weak here. 
Ada bindings to the Win 32 API also help. 

-- Brian