GNU bug report logs - #13188
par-map causes VM stack overflow

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 13188 in the body.
You can then email your comments to 13188 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Nala Ginrut <nalaginrut <at> gmail.com>
To: bug-guile <at> gnu.org
Subject: par-map causes VM stack overflow
Date: Sat, 15 Dec 2012 16:12:32 +0800

Here is the error message.
Anyway, par-map shouldn't cause stack overflow.

-----------------------err msg------------------------------
scheme@(guile-user)> (par-map 1+ (iota 10000))
While executing meta-command:
ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack
overflow" ())'.
-------------------------end--------------------------------

Message #10 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Nala Ginrut <nalaginrut <at> gmail.com>
Cc: 13188-done <at> debbugs.gnu.org
Subject: Re: bug#13188: par-map causes VM stack overflow
Date: Wed, 27 Mar 2013 18:12:16 +0100

Hi,

Nala Ginrut <nalaginrut <at> gmail.com> skribis:

> scheme@(guile-user)> (par-map 1+ (iota 10000))
> While executing meta-command:
> ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack
> overflow" ())'.

Commit 8a177d3 fixes this.  I added a paragraph in the documentation
that explains what happens: delimited continuations to the rescue once
again!  ;-)

Comments welcome.

Ludo’.

Message #13 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: Nala Ginrut <nalaginrut <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>, guile-devel <at> gnu.org
Cc: 13188-done <at> debbugs.gnu.org
Subject: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map
	causes VM stack overflow)
Date: Thu, 28 Mar 2013 10:55:34 +0800

On Wed, 2013-03-27 at 18:12 +0100, Ludovic Courtès wrote:
> Hi,
> 
> Nala Ginrut <nalaginrut <at> gmail.com> skribis:
> 
> > scheme@(guile-user)> (par-map 1+ (iota 10000))
> > While executing meta-command:
> > ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack
> > overflow" ())'.
> 
> Commit 8a177d3 fixes this.  I added a paragraph in the documentation
> that explains what happens: delimited continuations to the rescue once
> again!  ;-)
> 
> Comments welcome.
> 

oh~I love delimited continuations!

But I'm still puzzled with the performance of par-map:
--------------------cut-------------------
scheme@(guile-user)> ,time (define a (map (lambda (x) (expt x 5)) (iota
10000)))
;; 0.008019s real time, 0.007979s run time.  0.000000s spent in GC.
scheme@(guile-user)> ,time (define a (par-map (lambda (x) (expt x 5))
(iota 10000)))
;; 6.596471s real time, 6.579375s run time.  1.513880s spent in GC.
--------------------end-------------------

So my question is, what's the proper scenario to use par-map?



> Ludo’.

Message #16 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Nala Ginrut <nalaginrut <at> gmail.com>
Cc: Ludovic Courtès <ludo <at> gnu.org>, 13188-done <at> debbugs.gnu.org,
	guile-devel <at> gnu.org
Subject: Re: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map
	causes VM stack overflow)
Date: Thu, 28 Mar 2013 01:05:32 -0400

Nala Ginrut <nalaginrut <at> gmail.com> writes:

> But I'm still puzzled with the performance of par-map:
> --------------------cut-------------------
> scheme@(guile-user)> ,time (define a (map (lambda (x) (expt x 5)) (iota
> 10000)))
> ;; 0.008019s real time, 0.007979s run time.  0.000000s spent in GC.
> scheme@(guile-user)> ,time (define a (par-map (lambda (x) (expt x 5))
> (iota 10000)))
> ;; 6.596471s real time, 6.579375s run time.  1.513880s spent in GC.
> --------------------end-------------------
>
> So my question is, what's the proper scenario to use par-map?

It only makes sense to use 'par-map' when the procedure is fairly
expensive to compute.  There is inevitably a lot of overhead in creating
and joining the threads.  Granted, we should be able to do much better
than we're doing now, but it would *never* make sense to use 'par-map'
when each computation is as simple as (expt x 5).

      Regards,
        Mark

Message #19 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Mark H Weaver <mhw <at> netris.org>
Cc: 13188-done <at> debbugs.gnu.org, guile-devel <at> gnu.org,
	Nala Ginrut <nalaginrut <at> gmail.com>
Subject: Re: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map
	causes VM stack overflow)
Date: Thu, 28 Mar 2013 14:44:03 +0100

Mark H Weaver <mhw <at> netris.org> skribis:

> Nala Ginrut <nalaginrut <at> gmail.com> writes:
>
>> But I'm still puzzled with the performance of par-map:
>> --------------------cut-------------------
>> scheme@(guile-user)> ,time (define a (map (lambda (x) (expt x 5)) (iota
>> 10000)))
>> ;; 0.008019s real time, 0.007979s run time.  0.000000s spent in GC.
>> scheme@(guile-user)> ,time (define a (par-map (lambda (x) (expt x 5))
>> (iota 10000)))
>> ;; 6.596471s real time, 6.579375s run time.  1.513880s spent in GC.
>> --------------------end-------------------
>>
>> So my question is, what's the proper scenario to use par-map?
>
> It only makes sense to use 'par-map' when the procedure is fairly
> expensive to compute.

Indeed.

> There is inevitably a lot of overhead in creating and joining the
> threads.

We use a thread pool, so there’s no such cost.

But there are other costs.  When delimited continuations are used, we’re
on the slow path.  Also, Guile’s fat mutexes & co. are terribly
inefficient.  And finally, there may be contention on the futexes mutex
(esp. when the computations is too small.)

So yes, there’s room for improvement.  Yet, it should be fruitful,
provided you use it for reasonably long computations, as Mark outlines.

Ludo’.

Message #22 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: ludo <at> gnu.org (Ludovic Courtès)
Cc: 13188-done <at> debbugs.gnu.org, guile-devel <at> gnu.org,
	Nala Ginrut <nalaginrut <at> gmail.com>
Subject: Re: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map
	causes VM stack overflow)
Date: Thu, 28 Mar 2013 14:00:52 -0400

Hi Ludovic,

ludo <at> gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw <at> netris.org> skribis:
>
>> It only makes sense to use 'par-map' when the procedure is fairly
>> expensive to compute.
>
> Indeed.
>
>> There is inevitably a lot of overhead in creating and joining the
>> threads.
>
> We use a thread pool, so there’s no such cost.

Sorry, I was using the term 'threads' not in the sense of OS-level
threads, but in a more general sense.  I should have been more clear.

What I meant is that from the user's perspective, threads are being
created and joined, and even if you build those using a pool of OS-level
threads, this inevitably involves thread synchronization, which is very
expensive on modern architectures.  So I maintain that there _is_ such a
cost, and it can't be avoided.

The point I was really trying to make here, in the simplest possible
terms, is that it will *never* make sense to replace all uses of 'map'
with 'par-map' wherever it is safe to do so.

> But there are other costs.  When delimited continuations are used, we’re
> on the slow path.  Also, Guile’s fat mutexes & co. are terribly
> inefficient.  And finally, there may be contention on the futexes mutex
> (esp. when the computations is too small.)

Indeed, I wouldn't be surprised if we could improve this by an order of
magnitude.  More items for my TODO list :)

> So yes, there’s room for improvement.  Yet, it should be fruitful,
> provided you use it for reasonably long computations, as Mark outlines.

     Regards,
       Mark

Message #25 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Mark H Weaver <mhw <at> netris.org>
Cc: 13188-done <at> debbugs.gnu.org, guile-devel <at> gnu.org,
	Nala Ginrut <nalaginrut <at> gmail.com>
Subject: Re: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map
	causes VM stack overflow)
Date: Thu, 28 Mar 2013 21:07:12 +0100

Mark H Weaver <mhw <at> netris.org> skribis:

> ludo <at> gnu.org (Ludovic Courtès) writes:
>
>> Mark H Weaver <mhw <at> netris.org> skribis:
>>
>>> It only makes sense to use 'par-map' when the procedure is fairly
>>> expensive to compute.
>>
>> Indeed.
>>
>>> There is inevitably a lot of overhead in creating and joining the
>>> threads.
>>
>> We use a thread pool, so there’s no such cost.
>
> Sorry, I was using the term 'threads' not in the sense of OS-level
> threads, but in a more general sense.  I should have been more clear.
>
> What I meant is that from the user's perspective, threads are being
> created and joined, and even if you build those using a pool of OS-level
> threads, this inevitably involves thread synchronization, which is very
> expensive on modern architectures.  So I maintain that there _is_ such a
> cost, and it can't be avoided.

Ah yes, OK.

> The point I was really trying to make here, in the simplest possible
> terms, is that it will *never* make sense to replace all uses of 'map'
> with 'par-map' wherever it is safe to do so.

Indeed!

Ludo’.

Message #28 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: Nala Ginrut <nalaginrut <at> gmail.com>
To: Mark H Weaver <mhw <at> netris.org>
Cc: Ludovic Courtès <ludo <at> gnu.org>,
	13188-done <at> debbugs.gnu.org, guile-devel <at> gnu.org
Subject: Re: Whats' the proper senario of par-map? (Was Re: bug#13188:
	par-map causes VM stack overflow)
Date: Fri, 29 Mar 2013 10:36:50 +0800

On Thu, 2013-03-28 at 01:05 -0400, Mark H Weaver wrote:
> Nala Ginrut <nalaginrut <at> gmail.com> writes:
> 
> > But I'm still puzzled with the performance of par-map:
> > --------------------cut-------------------
> > scheme@(guile-user)> ,time (define a (map (lambda (x) (expt x 5)) (iota
> > 10000)))
> > ;; 0.008019s real time, 0.007979s run time.  0.000000s spent in GC.
> > scheme@(guile-user)> ,time (define a (par-map (lambda (x) (expt x 5))
> > (iota 10000)))
> > ;; 6.596471s real time, 6.579375s run time.  1.513880s spent in GC.
> > --------------------end-------------------
> >
> > So my question is, what's the proper scenario to use par-map?
> 
> It only makes sense to use 'par-map' when the procedure is fairly
> expensive to compute.  There is inevitably a lot of overhead in creating
> and joining the threads.  Granted, we should be able to do much better
> than we're doing now, but it would *never* make sense to use 'par-map'
> when each computation is as simple as (expt x 5).
> 

Well, is there any example?
And there're two possible applications:
1. handle the requests in a server
2. read files from disk (but how big file is proper for par-map)
Are these ways heavy enough for par-map?

Potentially, I inclined to use the lovely delimited-continuation to
handle the requests, but seems ludo think this way is slower? Or there's
improvement room?

>       Regards,
>         Mark

Message #31 received at 13188-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Nala Ginrut <nalaginrut <at> gmail.com>
Cc: Mark H Weaver <mhw <at> netris.org>, 13188-done <at> debbugs.gnu.org,
	guile-devel <at> gnu.org
Subject: Re: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map
	causes VM stack overflow)
Date: Fri, 29 Mar 2013 10:52:51 +0100

Nala Ginrut <nalaginrut <at> gmail.com> skribis:

> And there're two possible applications:
> 1. handle the requests in a server
> 2. read files from disk (but how big file is proper for par-map)

Quoting the fine manual:

  Note that futures are intended for the evaluation of purely
  functional expressions.  Expressions that have side-effects or rely on
  I/O may require additional care, such as explicit synchronization (*note
  Mutexes and Condition Variables::).

IOW, think twice before you use it for something not purely computational.
:-)

Ludo’.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.