Hi guys,
I propose to merge the "new ByNeed" branch with the main trunk, so that
it will be part of the upcoming Mozart release 1.3.0. This branch
contains the implementation of the new definitions of ByNeed, '!!', and
failed values. Comments (and possible objections) are welcome.
Below is a definition of the new semantics, its implementation, and an
evaluation of it. It gives you an idea of the work I have done with
(notably) Fred, Peter, Kostja, Christian, Kevin, and Denys.
-1- New Semantics
- The definition of by-need synchronization relies on making explicit
the concept of needing a value. Every variable can be needed or not.
Once needed, it remains needed. Determined variables are needed by
convention. A variable becomes needed when a thread synchronizes on
it, or when unified with a needed variable, or when it becomes
determined. Three primitives are provided, together with a new
definition of ByNeed:
{WaitNeeded X} blocks until X is needed.
{IsNeeded X B} tests whether X is needed (nonblocking).
{Value.makeNeeded X} makes X needed.
proc {ByNeed P X}
thread {WaitNeeded X} {P X} end
end
- The statement R=!!X makes R a read-only view of variable X. It works
as before. If R is needed, X is needed too.
- The statement F={Value.failed E} makes F a failed value encapsulating
exception E. The only difference with former 'failed futures' is
that they are no longer considered futures, and have a status of
their own. The call {Value.status F} returns 'failed', and is in
direct relation with {IsFailed F} returning true.
- The new operation ByNeedFuture combines the three concepts together.
The by-need computation is protected by a read-only, and exceptions
are catched and returned as failed values. This was suggested by
Denys. It is equivalent to
fun {ByNeedFuture P}
!!{ByNeed fun {$} try {P} catch E then {Value.failed E} end end}
end
-2- New Implementation
- The former implementation of futures will be removed from Mozart.
Maintaining both implementations introduces unnecessary complexity,
and therefore degrades readability of the code. This decision is
supported by the fact that no performance degradation has been
observed with the new implementation (see below).
- Therefore the implementation will no longer use the term 'future',
but rather 'read-only' and 'failed value'. The concepts are now
clearly separate.
- By-need synchronization is no longer attached to futures. Each
variable has a state telling whether it is needed. LIMITATION:
currently this applies to simple and read-only variables.
Constrained and ext variables are needed by default.
- Read-only variables (the ones you get with !!X) have been
reimplemented, in a way very similar to former futures. As said
before, they can be needed or not.
- Failed values have been reimplemented, too. Their implementation is
no longer mixed with other stuff.
-3- Evaluation
- I have compared time performances between my version and the one it
evolved from. So the difference between the two is the new
implementation of ByNeed, '!!', and failed values.
- The first test was to compile a bunch of functors, namely the ones in
the directory 'share' of Mozart. The difference between both
implementations is around 1% in favor of the former one. If you
don't compile with a chronometer in hand, you won't notice.
- Other tests involve the implementation in Oz of realistic programs.
I adapted a few ones from the Haskell nofib test suite. Time
performances are very similar. The new implementation is even
slightly faster.
- I also tested an optimization of 'fun lazy' with the programs above.
The program ran 25% faster. The optimization is rather simple: tail
recursive calls in lazy functions do not need to create new threads.
The example below shows the proposed expansion of a lazy function
Ints. The expansion avoids the creation of a new thread for each
recursive call, but loops in the same thread instead.
fun lazy {Ints N} N|{Ints N+1} end
local
proc {Loop N ?Res}
{WaitNeeded Res} Res=N|{Loop N+1}
end
in
fun {Ints N}
thread {Loop N} end
end
end
This optimization will be part of the Oz compiler in a later release.
raph
-
Please send submissions to hackers@mozart-oz.org
and administriva mail to hackers-request@mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.