Debunking The Expensive Exported-Function Call Myth

[Thomas Lindgren]

--- James Hague <james.hague@REDACTED> wrote:
> An alternate example is that you could determine the
> return type of a
> local function via "type discovery," then propagate
> that information
> to the calling function.  That is, if you knew a
> local function always
> returned a list, then specialized code could be used
> to process that
> value after it is returned.

Indeed. Type analysis has shown itself to be useful in
other dynamic languages, so it might well be so in
Erlang too. Type analysis has been done for donkey's
years too; my introduction to its "serious use" was
Peter Van Roy's thesis in 1990. Reasonably low-risk
thus.

For Erlang, there are two extra hurdles, both due to
code loading. The first hurdle is that a function
exported from a module can in principle be called with
any argument in the future, since we can't say if code
will be loaded in the future that calls an exported
function. This obviously dilutes the available type
information (used when optimizing the function body). 

The second hurdle is the converse, that a remote call
can return anything or might not exist (since your
analyzer again needs to be conservative in the face of
code loading, and you don't know the future code of
the called module). So function calls to other modules
yield no information either.

As an example, consider this:

socket_info(Socket) ->
    case inet:peername(Socket) of
	{ok, {Address, Port}} ->
            case inet:gethostbyaddr(Address) of
                {ok, Hostent} ->
                    ...;
                {error, Reason} ->
                    ...
            end;
        {error, Reason} ->
            {error, Reason}
    end.

Here, you can't say anything about what
inet:peername/1 or inet:gethostbyaddr/1 will return
since module inet may be replaced in the future. If
get_peerhost/1 is exported, Socket could be anything
too.

When I experimented with type analysis for
optimization at the start of the Hipe project
(mid-90s), I came to the conclusion that a
straightforward per-module type analysis was no better
than a per-function type analysis on "real code" (OTP
at the time). Bummer.

There may be ways around that, of course. One approach
is to deprecate export_all and so on, so that more
code is local and analyzers may gain more information.
That seems to be the road taken by Hipe and OTP, as
far as I can tell. 

A second one is to use a more robust analysis
framework, which permits multiple specialized versions
of functions. While this is much harder to get right,
it might be feasible. 

My preferred approach is a third one: module merging
and profile-driven optimization on top of that, with
type analysis as one part. See an Uppsala tech report
from 1996 and my EUC 2001 paper for an overview, not
including type analysis as such.

If this third approach was used with the example
above, I would expect the subsequent compiler to see
something like this:

%% latest(inet) checks that local definitions of
%% inet:peername and inet:gethostbyaddr are still
valid
%%
%% is_socket(Sock) tests that Sock is a socket/port,
%% because profiling has shown that this is usually
%% the case.
%%
%% local_inet_peername/1 and
local_inet_gethostbyaddr/1
%% are made local and are now visible to the analyzer
%% and optimizer.

socket_info(Socket) 
  when is_socket(Socket), latest(inet) ->
    case local_inet_peername(Socket) of
	{ok, {Address, Port}} ->
            case local_inet_gethostbyaddr(Address) of
                {ok, Hostent} ->
                    ...;
                {error, Reason} ->
                    ...
            end;
        {error, Reason} ->
            {error, Reason}
    end;
<fallback clauses>

(Note that this may, e.g., enable inlining or unboxing
of the returned tuples too, as a follow-on
optimization.)

To end on a down-beat, there are certainly drawbacks
to this "third way" too. Profile-based optimization is
always more difficult to put into practical use. More
infrastructure is needed to handle code loading. There
may be more code in total than before due to merging
and duplication (though hopefully the hot/important
code is smaller). No doubt there are other drawbacks
as well. Still, I consider it quite promising.

Best,
Thomas





		
__________________________________ 
Do you Yahoo!? 
Make Yahoo! your home page 
http://www.yahoo.com/r/hs