[plt-scheme] Native code generation and immutable pairs

From: Jim Blandy (jimb at red-bean.com)
Date: Fri Feb 10 12:07:33 EST 2006

On 2/10/06, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
> With Andrew's soft type Scheme system (based on Chez),
> we could create speedups on benchmarks between 10% and
> 8x. The average, if I recall this correctly, got close
> to 40% (someone can also look up the published number).

The original point I was trying to raise is that preemptive threads
will erase all of these advantages, because in many --- I think most
--- cases you will no longer be able to rely on the type of values
remaining the same, even while control has "remained" in the code
under analysis.  Because, of course, control has not remained there at
all --- it has been proceeding in other threads as well.

In C and C++, it suffices to have a rule, as the POSIX thread model
does, saying that if you don't use mutexes to protect shared data
structures properly, all bets are off.  But Scheme wants to be a safe
language, and the consequence of getting a type wrong may be a crash,
so this loophole isn't available to us.

The other weakness in these analyses appears as sort of a footnote
towards the end of J. Michael Ashley's paper on n-CFA flow analysis
(where he introduces functions that act as "tuning parameters" on the
resolution of the analysis): in the presence of separate compilation,
the win from flow analysis, which was substantial in the context of
Chez, would vanish.

So you need two things to make this analysis pay:
1) You need to restrict mutation of the objects you're traversing by
other threads.  Since pairs are so common, restricting pair mutation
is pretty much required.
2) You need a separate compilation system that somehow summarizes the
results of the analysis of one module in a way that can be used to
retain more information when compiling modules that import it.

If you're interested, I can look up the POSIX rule and find the bit of
Mike's paper that I have in mind.

Posted on the users mailing list.