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

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

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

Re: 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’.

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

Re: 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’.

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

Re: 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:
> --------------------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-------------------
[...]
> Well, is there any example?

The timings above suggest that, on your machine, the overhead of
'par-map' is in the neighborhood of 660 microseconds per thread (that's
the total run time divided by 10000 iterations).  So if the procedure
takes significantly longer than that to run, the overhead will not be so
bad.  For example, if the procedure takes 10 milliseconds to run, then
the 'par-map' overhead would be about 6.6% (660/10000).  If the
procedure takes 100 milliseconds to run, then the overhead would be
about 0.6% (660/100000).

That's the way I'd suggest to think about it.

     Mark

Extremely high overhead of 'par-map'

[Mark H Weaver]

I wrote:

> Nala Ginrut <nalaginrut@gmail.com> writes:
>> --------------------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-------------------
> [...]
>> Well, is there any example?
>
> The timings above suggest that, on your machine, the overhead of
> 'par-map' is in the neighborhood of 660 microseconds per thread (that's
> the total run time divided by 10000 iterations).

I must say that 'par-map' has shockingly poor performance.
We really ought to try to improve this.

     Mark

Re: 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’.

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

[Mark H Weaver]

I wrote:

> Nala Ginrut <nalaginrut@gmail.com> writes:
>> --------------------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-------------------
> [...]
>> Well, is there any example?
>
> The timings above suggest that, on your machine, the overhead of
> 'par-map' is in the neighborhood of 660 microseconds per thread (that's
> the total run time divided by 10000 iterations).

BTW, I notice that the overhead of 'par-map' is much less for shorter
lists.  It's about 9 times faster for lists of length 1000, and about 20
times faster for lists of length 100.

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> ,time (define a (par-map (lambda (x) (expt x 5)) (iota 10000)))
;; 8.293139s real time, 8.281802s run time.  1.310634s spent in GC.
scheme@(guile-user)> ,time (define a (for-each (lambda (k) (par-map (lambda (x) (expt x 5)) (iota 1000))) (iota 10)))
;; 0.908630s real time, 0.916819s run time.  0.070018s spent in GC.
scheme@(guile-user)> ,time (define a (for-each (lambda (k) (par-map (lambda (x) (expt x 5)) (iota 100))) (iota 100)))
;; 0.330130s real time, 0.418148s run time.  0.045255s spent in GC.
--8<---------------cut here---------------end--------------->8---

      Mark

Re: Extremely high overhead of 'par-map'

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1098 bytes --]

I agree. Do you have any idea what's causing the overhead?

I tried to benchmark it, but got a segmentation fault. I think we have
plenty of work to do here. :-)

Noah


On Fri, Mar 29, 2013 at 2:00 AM, Mark H Weaver <mhw@netris.org> wrote:

> I wrote:
>
> > Nala Ginrut <nalaginrut@gmail.com> writes:
> >> --------------------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-------------------
> > [...]
> >> Well, is there any example?
> >
> > The timings above suggest that, on your machine, the overhead of
> > 'par-map' is in the neighborhood of 660 microseconds per thread (that's
> > the total run time divided by 10000 iterations).
>
> I must say that 'par-map' has shockingly poor performance.
> We really ought to try to improve this.
>
>      Mark
>
>

[-- Attachment #2: Type: text/html, Size: 1703 bytes --]

Re: Extremely high overhead of 'par-map'

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1748 bytes --]

Oh, sorry to email twice so soon, but I have an idea for making par-map
usable in more cases: add a keyword argument called "block-size". Its value
should be a positive integer, and the meaning is to have each thread do
block-size iterations. That should make it easier to use par-map for cases
like this where the cost of each function is very small.

I realize it's not a great solution because you still have to iterate
through the list to get to the later elements. A hypothetical
"vector-par-map" would solve that.

Noah


On Fri, Mar 29, 2013 at 4:24 PM, Noah Lavine <noah.b.lavine@gmail.com>wrote:

> I agree. Do you have any idea what's causing the overhead?
>
> I tried to benchmark it, but got a segmentation fault. I think we have
> plenty of work to do here. :-)
>
> Noah
>
>
> On Fri, Mar 29, 2013 at 2:00 AM, Mark H Weaver <mhw@netris.org> wrote:
>
>> I wrote:
>>
>> > Nala Ginrut <nalaginrut@gmail.com> writes:
>> >> --------------------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-------------------
>> > [...]
>> >> Well, is there any example?
>> >
>> > The timings above suggest that, on your machine, the overhead of
>> > 'par-map' is in the neighborhood of 660 microseconds per thread (that's
>> > the total run time divided by 10000 iterations).
>>
>> I must say that 'par-map' has shockingly poor performance.
>> We really ought to try to improve this.
>>
>>      Mark
>>
>>
>

[-- Attachment #2: Type: text/html, Size: 2784 bytes --]

Re: Extremely high overhead of 'par-map'

[Mark H Weaver]

Hi Noah,

Noah Lavine <noah.b.lavine@gmail.com> writes:
> Oh, sorry to email twice so soon, but I have an idea for making
> par-map usable in more cases: add a keyword argument called
> "block-size". Its value should be a positive integer, and the meaning
> is to have each thread do block-size iterations.

IMO, we should avoid adding anything like this.  It would be hard for
callers to know what value to pass.  I think it should be possible to
make 'par-map' act sensibly and efficiently without this kind of help.

> I tried to benchmark it, but got a segmentation fault. I think we
> have plenty of work to do here. :-)

Ouch.  Can you please file a bug report with the full details?

    Regards,
      Mark

Re: Extremely high overhead of 'par-map'

[Ludovic Courtès]

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

> I must say that 'par-map' has shockingly poor performance.
> We really ought to try to improve this.

IMO we must improve futures, not necessarily ‘par-map’ itself, because
lists are not a good data structure for parallel processing anyway (“get
rid of cons” said Steele ;-)).

Ludo’.

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

[Andy Wingo]

On Fri 29 Mar 2013 06:49, Mark H Weaver <mhw@netris.org> writes:

>> 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.
>
> The timings above suggest that, on your machine, the overhead of
> 'par-map' is in the neighborhood of 660 microseconds per thread (that's
> the total run time divided by 10000 iterations).

Per item, you mean?  Anyway this seems like a really high overhead, and
we shouldn't make too many excuses for it ;)

Andy
-- 
http://wingolog.org/