amb and return without call/cc?

[naruto...@gmail.com]

hi

I'm seeing strange performance variance about different
implementations (mzscheme,petite,gambit-c), most likely to do with
their implementation of call/cc. Since I only use call/cc for "amb"
and "early abort (return)", is there a way to do amb and early abort
(return) without call/cc?

(heavy number crunching)
petite
time: 602 seconds
=======================================================
gambit-c
time: 208 seconds
=======================================================
mzscheme
time: 107 seconds
=======================================================

(heavy call/cc amb)
petite
time: 101 seconds
=======================================================
gambit-c
time: 384 seconds
=======================================================
mzscheme
.....too long to wait.....

[Jens Axel Søgaard]

naruto...@gmail.com skrev:

> hi
>
> I'm seeing strange performance variance about different
> implementations (mzscheme,petite,gambit-c), most likely to do with
> their implementation of call/cc. Since I only use call/cc for "amb"
> and "early abort (return)", is there a way to do amb and early abort
> (return) without call/cc?

Hard to say without the code.

--
Jens Axel Søgaard

[naruto...@gmail.com]

You will need these two scripts:
http://narutolinux.blogspot.com/2007/06/test-script-for-petite-gambit-c.html
http://narutolinux.blogspot.com/2007/06/script-for-compiling-gambit-c.html
And these three small files:
http://narutolinux.blogspot.com/2007/06/define-macrosc.html
http://narutolinux.blogspot.com/2007/06/define-macross.html
http://narutolinux.blogspot.com/2007/06/topsc.html
And this file:
http://narutolinux.blogspot.com/2007/06/collection-of-scheme-codes_17.html

(you can use your own scripts for producing exact same result with
these three scheme implementations (you can diff and see they produce
the same results). It took awhile to write those small scripts. It
uses the same top.sc file for all three implementations.)

#########################################################
Change this line:
"(define m (make-mask (* N 1)))"
"(define m (make-mask (* N 2)))"
"(define m (make-mask (* N 3)))"
"(define m (make-mask (* N 4)))"
"(define m (make-mask (* N 5)))"
"(define m (make-mask (* N 6)))"
And you get:
petite
time: 272 seconds
=======================================================
gambit-c
time: 102 seconds
=======================================================
mzscheme
time: 52 seconds
=======================================================

petite
time: 544 seconds
=======================================================
gambit-c
time: 173 seconds
=======================================================
mzscheme
time: 114 seconds
=======================================================

petite
time: 1051 seconds
=======================================================
gambit-c
time: 342 seconds
=======================================================
mzscheme
time: 148 seconds
=======================================================

petite
time: 1188 seconds
=======================================================
gambit-c
time: 415 seconds
=======================================================
mzscheme
time: 176 seconds
=======================================================

petite
time: 1411 seconds
=======================================================
gambit-c
time: 463 seconds
=======================================================
mzscheme
time: 199 seconds
=======================================================

petite
time: 2062 seconds
=======================================================
gambit-c
time: 581 seconds
=======================================================
mzscheme
time: 236 seconds
=======================================================

#######################################################
Now for heavy call/cc amb case:
Change this line to:
(define m (make-mask 1)) ;; basically disable previous test
And change this line to:
(define tt (expt 4 4))
(define tt (expt 4 5))
(define tt (expt 4 6))

And you get:
petite
time: 23 seconds
=======================================================
gambit-c
time: 39 seconds
=======================================================
mzscheme
time: 27 seconds
=======================================================

petite
time: 95 seconds
=======================================================
gambit-c
time: 341 seconds
=======================================================
mzscheme
time: 412 seconds
=======================================================

petite
time: 1759 seconds
=======================================================
gambit-c
... too long to wait ...
=======================================================
mzscheme
... too long to wait ...
=======================================================

This strange skew of performance when call/cc (amb) is used.
If I can avoid call/cc but still have "amb" and "return", it would be
nice.

>
> --
> Jens Axel Søgaard

[Jens Axel Søgaard]

naruto...@gmail.com skrev:

> Jens Axel Søgaard wrote:
>> naruto...@gmail.com skrev:
>>> hi
>>>
>>> I'm seeing strange performance variance about different
>>> implementations (mzscheme,petite,gambit-c), most likely to do with
>>> their implementation of call/cc. Since I only use call/cc for "amb"
>>> and "early abort (return)", is there a way to do amb and early abort
>>> (return) without call/cc?
>> Hard to say without the code.
>

In the MzScheme version, try replacing

(define-macro amb
(lambda alts...
`(let ((+prev-amb-fail amb-fail))
(call/cc
(lambda (+sk)
,@(map (lambda (alt)
`(call/cc
(lambda (+fk)
(set! amb-fail
(lambda ()
(set! amb-fail +prev-amb-fail)
(+fk 'fail)))
(+sk ,alt))))
alts...)
(+prev-amb-fail))))))

with

(define-macro amb
(lambda alts...
`(let ((+prev-amb-fail amb-fail))
(call/ec
(lambda (+sk)
,@(map (lambda (alt)
`(call/cc
(lambda (+fk)
(set! amb-fail
(lambda ()
(set! amb-fail +prev-amb-fail)
(+fk 'fail)))
(+sk ,alt))))
alts...)
(+prev-amb-fail))))))

and see if it affects anything.

In general, if your continutations are escape continuation
(used as return) then use call/ec instead of call/cc.

For example in

(define (gaussian-elimination coefficients right-hand-sides)
(call/cc (lambda (return)
...

my guess is that you can use call/ec.

--
Jens Axel Søgaard

[naruto...@gmail.com]

Holy cow, once I change call/cc to call/ec, the runtime was incredibly
reduced for mzscheme.
I re-run the previous tests:

(define tt (expt 4 4))
(define tt (expt 4 5))

petite
time: 29 seconds
=======================================================
gambit-c
time: 44 seconds
=======================================================
mzscheme
time: 12 seconds
=======================================================

petite
time: 105 seconds
=======================================================
gambit-c
time: 393 seconds
=======================================================
mzscheme
time: 68 seconds
=======================================================

I've changed "all" call/cc to call/ec (except the (inner) one in amb
as per your suggestion).
And split the code base with:
(if (equal? "mzscheme" interpreter)
(eval '(define call/ec call/ec))
(eval '(define call/ec call/cc))
)

I've simply had to define "interpreter" for each interpreter's init
code like this:
(define interpreter "mzscheme")
(define interpreter "petite")
(define interpreter "gambit-c")

Fortunately, all my code seems to run fine with call/ec.

Thanks a lot.

>
> --
> Jens Axel Søgaard

[Jens Axel Søgaard]

naruto...@gmail.com wrote:

> I've changed "all" call/cc to call/ec (except the (inner) one in amb
> as per your suggestion).
> And split the code base with:
> (if (equal? "mzscheme" interpreter)
> (eval '(define call/ec call/ec))
> (eval '(define call/ec call/cc))
> )

I believe call/ec is called call/1cc in Chez Scheme.

It would surprise me, if there weren't a similar
trick in Gambit - but try asking on their mailing
list.

--
Jens Axel Søgaard

[naruto...@gmail.com]

Jens Axel Søgaard wrote:
> naruto...@gmail.com wrote:
>
> > I've changed "all" call/cc to call/ec (except the (inner) one in amb
> > as per your suggestion).
> > And split the code base with:
> > (if (equal? "mzscheme" interpreter)
> > (eval '(define call/ec call/ec))
> > (eval '(define call/ec call/cc))
> > )
>
> I believe call/ec is called call/1cc in Chez Scheme.

I've just tried it. It didn't improve much for petite.

petite
time: 94 seconds
=======================================================

petite
time: 93 seconds

[naruto...@gmail.com]

I've e-mailed gambit-c list they haven't got back to me.
I tried to grep through the source code but find nothing.

> >
> > --
> > Jens Axel Søgaard

[Brad Lucier]

On Jun 25, 5:58 pm, narutocan...@gmail.com wrote:
> I've e-mailed gambit-c list they haven't got back to me.
> I tried to grep through the source code but find nothing.

Just for the record, it was pointed out on the Gambit mail list that
the benchmark is written on Gambit so that the code is running
interpreted, so the issue of call/ec vs call/cc is irrelevant on
Gambit at this point.

Brad