continuations to optimize code

[Ulf Wiger]

I've done some work optimizing the syntax highlighter in
CCviewer. It's basically a parser, but written by hand in plain
Erlang (a questionable decision, but it does have some nice
properties.)

I realised that a major rewrite was in order when I found that it
took 4.5 hours to process megaco_text_parser.erl -- 22,000 lines
of code, essentially only two functions.

The first rewrite made the parser reentrant, reading and scanning
the file in chunks, instead of all at once. This brought the time
down from 4.5 hours to ca 15 minutes -- joy!

Then I stumbled across another module, that happened to call
mnesia:transaction(Fun) with an inlined fun that consisted of 230
lines of code (!). This caused BEAM to bail out when it couldn't
allocate space for a 1 GB process heap -- no joy.

I came to the conclusion that the problem was that I was using a
construct like:

parse([{atom,Pos1,Name},{symbol,Pos2,'('}|Ts], ...) ->
   %% function call
   {Arity, Output, RestTs, ...} = function_arguments(Ts, ...),
   output([html_anchor(Name, Arity), "(", Output], ...),
   parse(RestTs, ...).

I.e. not tail-recursive.

I rewrote it in the following style:

parse([{atom,Pos1,Name},{symbol,Pos2,'('}|Ts], ...) ->
   %% function call
   Fun =
      fun(Arity, Output, RestTs, ...) ->
         output([html_anchor(Name, Arity), "(", Output], ...),
         parse(RestTs, ...)
      end,
   function_arguments(Ts, ..., Fun).

(The function function_arguments() then calls Fun(Arity, Output,
RestTs, ...) instead of returning a tuple.)

This brought the processing time of megaco_text_parser.erl down
again from 15 minutes to 100 ms -- ...!!!


Of course, it isn't exactly news that non-tail-recursive
functions are slower than tail-recursive ones, but the
difference in this case was rather extreme. I take it this is
because the data volume was large. The new code isn't quite as
readable, but it's still possible to follow.


After flogging myself for writing such slow code to begin with,
I then started thinking that the rewrite above could possibly be
automated, esp. using a profiling-based optimization tool like
described in http://www.erlang.se/euc/01/Lindgren2001.ps.

I remember that Thomas's tool did "higher-order function
removal". This would be rather the opposite: "higher-order
function exploitation", or something like that.
Basically, if a function is called non-recursively, and the cost
of the function call is high enough that applying a
continuation-passing style is insignificant by comparison, a
non-tail-recursive function could be made tail-recursive quite
easily.

Comments, anyone?

/Uffe
-- 
Ulf Wiger, Senior Specialist,
   / / /   Architecture & Design of Carrier-Class Software
  / / /    Strategic Product & System Management
 / / /     Ericsson Telecom AB, ATM Multiservice Networks