bug#13188: par-map causes VM stack overflow

bug#13188: par-map causes VM stack overflow

[Nala Ginrut]

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--------------------------------

bug#13188: par-map causes VM stack overflow

[Ludovic Courtès]

Hi,

Nala Ginrut <nalaginrut@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’.

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Nala Ginrut]

On Wed, 2013-03-27 at 18:12 +0100, Ludovic Courtès wrote:
> Hi,
> 
> Nala Ginrut <nalaginrut@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’.

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Mark H Weaver]

Nala Ginrut <nalaginrut@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

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Ludovic Courtès]

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

> Nala Ginrut <nalaginrut@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’.

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Mark H Weaver]

Hi Ludovic,

ludo@gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw@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

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Ludovic Courtès]

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

> ludo@gnu.org (Ludovic Courtès) writes:
>
>> Mark H Weaver <mhw@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’.

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Nala Ginrut]

On Thu, 2013-03-28 at 01:05 -0400, Mark H Weaver wrote:
> Nala Ginrut <nalaginrut@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

bug#13188: Whats' the proper senario of par-map? (Was Re: bug#13188: par-map causes VM stack overflow)

[Ludovic Courtès]

Nala Ginrut <nalaginrut@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’.