early termination for `map'

early termination for `map'

[Andy Wingo]

Hello,

If you call `map' or `for-each' with more than one list, our versions of
these operators will detect if the lists are of unequal length, and
throw an error in that case.

However, SRFI-1 has long provided an extension to this, to allow for
early termination when any of the lists runs out.  R6RS adopted this,
and it looks like R7RS will ratify that.

So perhaps it's time for us to change as well.

This would also allow us to get rid of the hack in srfi-1.c in which,
when and if GOOPS gets loaded, srfi-1 extends the `map' and `for-each'
primitive generics with its own early-termination code, which in effect
gives early termination to every `map' user, regardless of whether that
module has imported srfi-1 or goops.  Sometimes I think that Mikael put
the Oops in Goops for a reason ;-)

Andy
-- 
http://wingolog.org/

Re: early termination for `map'

[Noah Lavine]

That makes sense.

On Thu, May 5, 2011 at 11:24 AM, Andy Wingo <wingo@pobox.com> wrote:
> Hello,
>
> If you call `map' or `for-each' with more than one list, our versions of
> these operators will detect if the lists are of unequal length, and
> throw an error in that case.
>
> However, SRFI-1 has long provided an extension to this, to allow for
> early termination when any of the lists runs out.  R6RS adopted this,
> and it looks like R7RS will ratify that.
>
> So perhaps it's time for us to change as well.
>
> This would also allow us to get rid of the hack in srfi-1.c in which,
> when and if GOOPS gets loaded, srfi-1 extends the `map' and `for-each'
> primitive generics with its own early-termination code, which in effect
> gives early termination to every `map' user, regardless of whether that
> module has imported srfi-1 or goops.  Sometimes I think that Mikael put
> the Oops in Goops for a reason ;-)
>
> Andy
> --
> http://wingolog.org/
>
>

Re: early termination for `map'

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> writes:

> If you call `map' or `for-each' with more than one list, our versions of
> these operators will detect if the lists are of unequal length, and
> throw an error in that case.
>
> However, SRFI-1 has long provided an extension to this, to allow for
> early termination when any of the lists runs out.  R6RS adopted this,
> and it looks like R7RS will ratify that.
>
> So perhaps it's time for us to change as well.

To change the default ‘map’ & ‘for-each’ to do like SRFI-1’s, right?

> This would also allow us to get rid of the hack in srfi-1.c in which,
> when and if GOOPS gets loaded, srfi-1 extends the `map' and `for-each'
> primitive generics with its own early-termination code, which in effect
> gives early termination to every `map' user, regardless of whether that
> module has imported srfi-1 or goops.  Sometimes I think that Mikael put
> the Oops in Goops for a reason ;-)

Heh.  :-)

Code not using GOOPS can tell the difference between the default and
SRFI-1 versions, and it can arrange to explicitly use one or the other.
So changing the default versions would be an incompatibility—arguably
not an important one, but still maybe enough to wait until 2.2?

Thanks,
Ludo’.

Re: early termination for `map'

[Andy Wingo]

On Thu 05 May 2011 18:26, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> If you call `map' or `for-each' with more than one list, our versions of
>> these operators will detect if the lists are of unequal length, and
>> throw an error in that case.
>>
>> However, SRFI-1 has long provided an extension to this, to allow for
>> early termination when any of the lists runs out.  R6RS adopted this,
>> and it looks like R7RS will ratify that.
>>
>> So perhaps it's time for us to change as well.
>
> To change the default ‘map’ & ‘for-each’ to do like SRFI-1’s, right?

Yeah, that was the proposal; but the argument is a bit weaker, now that
I found that the R6RS did not go with this change.  So I don't really
know.

The reason I was thinking of doing this is because it turns out to help
performance to have map in scheme, at this point; or at least not hurt
it, and things will get better when we grow an optimizer.

So I implemented map in Scheme, with circularity detection and all, only
to find strange errors in the ecmascript compiler (!).  Turns out those
errors happened when loading goops, because it tried to extend a
primitive generic, but map wasn't a primitive any more, and instead of
failing nicely it corrupted memory.

>> This would also allow us to get rid of the hack in srfi-1.c in which,
>> when and if GOOPS gets loaded, srfi-1 extends the `map' and `for-each'
>> primitive generics with its own early-termination code, which in effect
>> gives early termination to every `map' user, regardless of whether that
>> module has imported srfi-1 or goops.  Sometimes I think that Mikael put
>> the Oops in Goops for a reason ;-)
>
> Heh.  :-)
>
> Code not using GOOPS can tell the difference between the default and
> SRFI-1 versions, and it can arrange to explicitly use one or the other.
> So changing the default versions would be an incompatibility—arguably
> not an important one, but still maybe enough to wait until 2.2?

Yeah, perhaps you are right, and the srfi-1 / goops interaction should
probably get some other resolution -- like merge-generics on import, or
something.

Thanks for your thoughts,

Andy
-- 
http://wingolog.org/

Re: early termination for `map'

[Ludovic Courtès]

Andy Wingo <wingo@pobox.com> writes:

> On Thu 05 May 2011 18:26, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> writes:
>>
>>> If you call `map' or `for-each' with more than one list, our versions of
>>> these operators will detect if the lists are of unequal length, and
>>> throw an error in that case.
>>>
>>> However, SRFI-1 has long provided an extension to this, to allow for
>>> early termination when any of the lists runs out.  R6RS adopted this,
>>> and it looks like R7RS will ratify that.
>>>
>>> So perhaps it's time for us to change as well.
>>
>> To change the default ‘map’ & ‘for-each’ to do like SRFI-1’s, right?
>
> Yeah, that was the proposal; but the argument is a bit weaker, now that
> I found that the R6RS did not go with this change.  So I don't really
> know.

Oh, OK.

> The reason I was thinking of doing this is because it turns out to help
> performance to have map in scheme, at this point; or at least not hurt
> it, and things will get better when we grow an optimizer.

Yes, and I think we can keep rewriting SRFI-1 in Scheme, even in 2.0.

> So I implemented map in Scheme, with circularity detection and all, only
> to find strange errors in the ecmascript compiler (!).  Turns out those
> errors happened when loading goops, because it tried to extend a
> primitive generic, but map wasn't a primitive any more, and instead of
> failing nicely it corrupted memory.

Ooh, interesting.  :-)

Thanks,
Ludo’.

Re: early termination for `map'

[Andy Wingo]

Hi,

On Thu 05 May 2011 22:21, ludo@gnu.org (Ludovic Courtès) writes:

> Yes, and I think we can keep rewriting SRFI-1 in Scheme, even in 2.0.
>
>> So I implemented map in Scheme
>
> Ooh, interesting.  :-)

I pushed to stable-2.0.  Let me know if you want me to back it out.

Cheers,

Andy
-- 
http://wingolog.org/

Re: early termination for `map'

[Ludovic Courtès]

Hi Andy,

Andy Wingo <wingo@pobox.com> writes:

> Hi,
>
> On Thu 05 May 2011 22:21, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Yes, and I think we can keep rewriting SRFI-1 in Scheme, even in 2.0.
>>
>>> So I implemented map in Scheme
>>
>> Ooh, interesting.  :-)
>
> I pushed to stable-2.0.  Let me know if you want me to back it out.

It seems to break fresh builds (from <http://hydra.nixos.org/build/1077886>):

--8<---------------cut here---------------start------------->8---
  GUILEC texinfo/plain-text.go
Backtrace:
In system/base/compile.scm:
 192: 19 [read-and-compile #<input: texinfo/plain-text.scm 37> #:from ...]
 204: 18 [lp (# # # # ...) #<directory # 1903a20> #<directory # 1903a20>]
 170: 17 [lp (#<procedure compile-tree-il (x e opts)>) (define # #) ...]
In ice-9/boot-9.scm:
2103: 16 [save-module-excursion #<procedure 1bce360 at language/scheme/compile-tree-il.scm:29:3 ()>]
In language/scheme/compile-tree-il.scm:
  31: 15 [#<procedure 1bce360 at language/scheme/compile-tree-il.scm:29:3 ()>]
In ice-9/psyntax.scm:
1034: 14 [chi-top-sequence ((define # #)) () ((top)) ...]
1003: 13 [#<procedure 1bbf780 at ice-9/psyntax.scm:1002:36 ()>]
1530: 12 [chi-simple-lambda (# . #) () (()) ...]
1420: 11 [parse (((# # #) . #(syntax-object # # #))) () () () () () ()]
In ice-9/boot-9.scm:
 541: 10 [map #<procedure 1bce030 at ice-9/psyntax.scm:1420:50 (x)> ((# . #))]
In ice-9/psyntax.scm:
1253: 9 [#<procedure 1bc9910 (e0 e1)> string-concatenate (#)]
In ice-9/boot-9.scm:
 541: 8 [map #<procedure 1bd0280 at ice-9/psyntax.scm:1253:35 (e)> (#)]
In ice-9/psyntax.scm:
1186: 7 [chi (map-in-order stexi->plain-text body) (# # #) (# # #) ...]
1121: 6 [syntax-type (map-in-order stexi->plain-text body) (# # #) (# # #) ...]
1106: 5 [syntax-type map-in-order (# # #) (# # #) ...]
 583: 4 [lookup map-in-order (# # #) (hygiene texinfo plain-text)]
 289: 3 [get-global-definition-hook map-in-order (hygiene texinfo plain-text)]
In unknown file:
   ?: 2 [module-variable #<directory (texinfo plain-text) 1903a20> map-in-order]
In ice-9/boot-9.scm:
3364: 1 [replace #<directory (texinfo plain-text) 1903a20> map-in-order ...]
 119: 0 [#<procedure 15aa8c0 at ice-9/boot-9.scm:110:6 (thrown-k . args)> wrong-number-of-args ...]

ice-9/boot-9.scm:118:20: In procedure #<procedure 15aa8c0 at ice-9/boot-9.scm:110:6 (thrown-k . args)>:
ice-9/boot-9.scm:118:20: Wrong number of arguments to #<procedure replace (module name int1 val1 int2 val2 var val)>
make[2]: *** [texinfo/plain-text.go] Error 1
--8<---------------cut here---------------end--------------->8---

Thanks,
Ludo’.

‘map’ and ‘for-each’ written in Scheme

[Ludovic Courtès]

Hello!

Could you add benchmarks so we can see how the Scheme and C
implementations compare?

For the record, the results for ‘fold’:
<http://thread.gmane.org/gmane.lisp.guile.devel/10652>.

Thanks,
Ludo’.

Re: ‘map’ and ‘for-each’ written in Scheme

[Andy Wingo]

On Sun 08 May 2011 17:05, ludo@gnu.org (Ludovic Courtès) writes:

> Could you add benchmarks so we can see how the Scheme and C
> implementations compare?

Done.

Current Guile:
  $ ./benchmark-guile srfi-1.bm
  Benchmarking /home/wingo/src/guile/meta/guile ... srfi-1.bm
  with GUILE_LOAD_PATH=/home/wingo/src/guile/benchmark-suite
  ;; running guile version 2.0.1.22-4cbd6
  ;; calibrating the benchmarking framework...
  ;; framework time per iteration: 5.72204532623291e-8
  ;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
  ;;;       or pass the --no-auto-compile argument to disable.
  ;;; compiling /home/wingo/src/guile/benchmark-suite/benchmarks/srfi-1.bm
  ;;; compiled /home/wingo/src/guile/cache/guile/ccache/2.0-LE-8-2.0/home/wingo/src/guile/benchmark-suite/benchmarks/srfi-1.bm.go
  ("srfi-1.bm: fold: big" 30 user 2.03 benchmark 2.0299982833864 bench/interp 2.0299982833864 gc 0.0)
  ("srfi-1.bm: fold: small" 2000000 user 1.54 benchmark 1.42555909347534 bench/interp 1.42555909347534 gc 0.0)
  ("srfi-1.bm: drop-while: big" 30 user 1.78 benchmark 1.7799982833864 bench/interp 1.7799982833864 gc 0.0)
  ("srfi-1.bm: drop-while: small" 2000000 user 1.38 benchmark 1.26555909347534 bench/interp 1.26555909347534 gc 0.0)
  ("srfi-1.bm: map: big" 30 user 4.55 benchmark 4.5499982833864 bench/interp 4.0847600543864 gc 0.465238229)
  ("srfi-1.bm: map: small" 2000000 user 3.2 benchmark 3.08555909347534 bench/interp 2.97014448647534 gc 0.115414607)
  ("srfi-1.bm: for-each: big" 30 user 2.96 benchmark 2.9599982833864 bench/interp 2.9599982833864 gc 0.0)
  ("srfi-1.bm: for-each: small" 2000000 user 2.34 benchmark 2.22555909347534 bench/interp 2.22555909347534 gc 0.0)


Guile 1.8:
  $ /opt/guile-1.8/env ./benchmark-guile -i /opt/guile-1.8/bin/guile srfi-1.bm
  Benchmarking /opt/guile-1.8/bin/guile ... srfi-1.bm
  with GUILE_LOAD_PATH=/home/wingo/src/guile/benchmark-suite
  ERROR: no code for module (benchmark-suite lib)
  wingo@unquote:~/src/guile$ GUILE_LOAD_PATH=. /opt/guile-1.8/env ./benchmark-guile -i /opt/guile-1.8/bin/guile srfi-1.bm
  Benchmarking /opt/guile-1.8/bin/guile ... srfi-1.bm
  with GUILE_LOAD_PATH=/home/wingo/src/guile/benchmark-suite:.
  ;; running guile version 1.8.7
  ;; calibrating the benchmarking framework...
  ;; framework time per iteration: 9.5367431640625e-8
  ("srfi-1.bm: fold: big" 30 user 7.14 benchmark 7.13999713897705 bench/interp 3.72999713897705 gc 3.41)
  ("srfi-1.bm: fold: small" 2000000 user 6.07 benchmark 5.87926513671875 bench/interp 2.91926513671875 gc 2.96)
  ("srfi-1.bm: drop-while: big" 30 user 5.51 benchmark 5.50999713897705 bench/interp 2.92999713897705 gc 2.58)
  ("srfi-1.bm: drop-while: small" 2000000 user 3.18 benchmark 2.98926513671875 bench/interp 1.90926513671875 gc 1.08)
  ("srfi-1.bm: map: big" 30 user 7.93 benchmark 7.92999713897705 bench/interp 4.90999713897705 gc 3.02)
  ("srfi-1.bm: map: small" 2000000 user 4.04 benchmark 3.84926513671875 bench/interp 2.42926513671875 gc 1.42)
  ("srfi-1.bm: for-each: big" 30 user 5.35 benchmark 5.34999713897705 bench/interp 4.02999713897705 gc 1.32)
  ("srfi-1.bm: for-each: small" 2000000 user 3.22 benchmark 3.02926513671875 bench/interp 1.91926513671875 gc 1.11)

Map and for-each are slower than fold right now because they check for
circular lists.  Dunno how useful that is, but it's what they always
have done.

Andy
-- 
http://wingolog.org/

Re: early termination for `map'

[Andy Wingo]

On Thu 05 May 2011 17:24, Andy Wingo <wingo@pobox.com> writes:

> If you call `map' or `for-each' with more than one list, our versions of
> these operators will detect if the lists are of unequal length, and
> throw an error in that case.
>
> However, SRFI-1 has long provided an extension to this, to allow for
> early termination when any of the lists runs out.  R6RS adopted this,
> and it looks like R7RS will ratify that.

FWIW I think I misremembered here: R6RS map requires the lists to be of
the same length.

Andy
-- 
http://wingolog.org/