From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Damien Mattei Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: Re: map-par slower than map Date: Thu, 13 Oct 2022 12:44:42 +0200 Message-ID: References: <87bkqg7lmp.fsf@laura> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="00000000000016985805eae833c6" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="6406"; mail-complaints-to="usenet@ciao.gmane.io" To: Olivier Dion , guile-user , guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Thu Oct 13 12:47:04 2022 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oivjz-0001Pj-Fr for guile-devel@m.gmane-mx.org; Thu, 13 Oct 2022 12:47:03 +0200 Original-Received: from localhost ([::1]:40768 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oivjv-0008GH-2T for guile-devel@m.gmane-mx.org; Thu, 13 Oct 2022 06:46:59 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:45224) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oivhz-0008C3-0x; Thu, 13 Oct 2022 06:45:02 -0400 Original-Received: from mail-ed1-x536.google.com ([2a00:1450:4864:20::536]:33622) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oivhw-0001O0-Vz; Thu, 13 Oct 2022 06:44:58 -0400 Original-Received: by mail-ed1-x536.google.com with SMTP id a13so2078003edj.0; Thu, 13 Oct 2022 03:44:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=5EgrknzbFT+TqQSYUlJuEfsX8rkSQ7pYvXNW0g19oqk=; b=XAIikd2NxQsV/lDa6pxlwGHpUiJ+bh/OKfi2N8zjtU5zC247kjnfi+FFXLMaprCOiM CeltP8OO4m4X9njGI6vwJOUx/7HHktNBX5JAfYLUrudm0HO3sMPdNuRAMW3s9CgVewCt 3QdOiLwErvZBFtWjjpq3r0VpkwL5O/aFHK8mprCYCM3KCdkGe+CjQVRhCY/btVS6QDVX 78bdH5CevNJvssKn45+GVLhAVA9RQLxdvS1gFsxSrgZAHl1ElNLDoa5ZiOmDjqWA0Vqd aj9+G+oEmI6n1OgRRdHS74RHduQle2y//R2rUrzUtfc/A+hZvWZolxqEsuO6MWvcR5j7 0/lQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=5EgrknzbFT+TqQSYUlJuEfsX8rkSQ7pYvXNW0g19oqk=; b=TRbAqNwmJb8+9KOIP4/dVt32qhJoU/NfB9PhlMsBEeKHGD5TvAaDSfS91bRMrS60Ac Gz8HtRzsMGvrZXPBTeDy0h81ZTr1S/u7R5leSTmd/8dtyihmd7nCMxjChRMdm8N+HA+m Ce12eOTI0McSIKssb9MtbVOK+8/PUSdBhvm+9RUXYHecroblUf1RBT3Qxh50T/1FFZFY M8G7aIhcnT9KRKEVC+hKdexFnHJfilWYKrmF7P06C30rTwVNH28tdBN/vivz0uqNgooD R+v/3DMJVophgYpArEZUel6Y9p+yU0I34tErvbMz48OjgWIrCPasPZ/GLUmKtVFUxfMD b5AA== X-Gm-Message-State: ACrzQf3ojX1RB/kw5K1Ij8TSd0S9zLzUdKFgUJkp5sr2o9cZVJSuoJZ+ L3v1UTsW5yvuv8v5cPJ9NuQsyG/WPslI4O1BmQw= X-Google-Smtp-Source: AMsMyM7rQUJRQNgGfhh8zlOHO7FCjpqUo/XWvMsYskddiP2RIviXqeu0FPx6Db81WGAW2ubWRI+QpJV1KeBNb6p8r+U= X-Received: by 2002:a05:6402:354a:b0:459:7a7f:6778 with SMTP id f10-20020a056402354a00b004597a7f6778mr30882292edd.281.1665657893983; Thu, 13 Oct 2022 03:44:53 -0700 (PDT) In-Reply-To: <87bkqg7lmp.fsf@laura> Received-SPF: pass client-ip=2a00:1450:4864:20::536; envelope-from=damien.mattei@gmail.com; helo=mail-ed1-x536.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:21424 gmane.lisp.guile.user:18636 Archived-At: --00000000000016985805eae833c6 Content-Type: text/plain; charset="UTF-8" i trying to use your code but it seems there is a ) mismatch somewhere? On Wed, Oct 12, 2022 at 11:55 PM Olivier Dion wrote: > On Wed, 12 Oct 2022, Damien Mattei wrote: > > Hello, > > all is in the title, i test on a approximately 30000 element list , i got > > 9s with map and 3min 30s with par-map on exactly the same piece of > > code!? > > I can only speculate here. But trying with a very simple example here: > --8<---------------cut here---------------start------------->8--- > (use-modules (statprof)) > (statprof (lambda () (par-map 1+ (iota 300000)))) > --8<---------------cut here---------------end--------------->8--- > > Performance are terrible. I don't know how par-map is implemented, but > if it does 1 element static scheduling -- which it probably does because > you pass a linked list and not a vector -- then yeah you can assure that > thing will be very slow. > > You're probably better off with dynamic scheduling with vectors. Here's > a quick snippet I made for static scheduling but with vectors. Feel > free to roll your own. > > --8<---------------cut here---------------start------------->8--- > (use-modules > (srfi srfi-1) > (ice-9 threads)) > > (define* (par-map-vector proc input > #:optional > (max-thread (current-processor-count))) > > (let* ((block-size (quotient (vector-length input) max-thread)) > (rest (remainder (vector-length input) max-thread)) > (output (make-vector (vector-length input) #f))) > (when (not (zero? block-size)) > (let ((mtx (make-mutex)) > (cnd (make-condition-variable)) > (n 0)) > (fold > (lambda (scale output) > (begin-thread > (let lp ((i 0)) > (when (< i block-size) > (let ((i (+ i (* scale block-size)))) > (vector-set! output i (proc (vector-ref input i)))) > (lp (1+ i)))) > (with-mutex mtx > (set! n (1+ n)) > (signal-condition-variable cnd))) > output) > output > (iota max-thread)) > (with-mutex mtx > (while (not (< n max-thread)) > (wait-condition-variable cnd mtx)))) > (let ((base (- (vector-length input) rest))) > (let lp ((i 0)) > (when (< i rest) > (let ((i (+ i base))) > (vector-set! output i (proc (vector-ref input i)))) > (lp (1+ i))))) > output)) > --8<---------------cut here---------------end--------------->8--- > > -- > Olivier Dion > oldiob.dev > --00000000000016985805eae833c6 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
i t= rying to use your code but it seems there is a ) mismatch somewhere?

On Wed, Oct 12, 2022 at 11:55 PM Olivier Dion <olivier.dion@polymtl.ca> wrote:
On Wed, 12 Oct 2022, Damien Mat= tei <damien= .mattei@gmail.com> wrote:
> Hello,
> all is in the title, i test on a approximately 30000 element list , i = got
> 9s with map and 3min 30s with par-map on exactly the same piece of
> code!?

I can only speculate here.=C2=A0 But trying with a very simple example here= :
--8<---------------cut here---------------start------------->8---
(use-modules (statprof))
(statprof (lambda () (par-map 1+ (iota 300000))))
--8<---------------cut here---------------end--------------->8---

Performance are terrible.=C2=A0 I don't know how par-map is implemented= , but
if it does 1 element static scheduling -- which it probably does because you pass a linked list and not a vector -- then yeah you can assure that thing will be very slow.

You're probably better off with dynamic scheduling with vectors.=C2=A0 = Here's
a quick snippet I made for static scheduling but with vectors.=C2=A0 Feel free to roll your own.

--8<---------------cut here---------------start------------->8---
(use-modules
=C2=A0(srfi srfi-1)
=C2=A0(ice-9 threads))

(define* (par-map-vector proc input
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0#:optional
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0(max-thread (current-processor-count)))

=C2=A0 (let* ((block-size (quotient (vector-length input) max-thread))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(rest (remainder (vector-length input) ma= x-thread))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(output (make-vector (vector-length input= ) #f)))
=C2=A0 =C2=A0 (when (not (zero? block-size))
=C2=A0 =C2=A0 =C2=A0 (let ((mtx (make-mutex))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (cnd (make-condition-variable)) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (n 0))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (fold
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lambda (scale output)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(begin-thread
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (let lp ((i 0))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (when (< i block-size)<= br> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (let ((i (+ i (* sc= ale block-size))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (vector-set!= output i (proc (vector-ref input i))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (lp (1+ i))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (with-mutex mtx
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (set! n (1+ n))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (signal-condition-variable= cnd)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0output)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0output
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(iota max-thread))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (with-mutex mtx
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (while (not (< n max-thread))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (wait-condition-variable cnd mtx)= )))
=C2=A0 =C2=A0 (let ((base (- (vector-length input) rest)))
=C2=A0 =C2=A0 =C2=A0 (let lp ((i 0))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (when (< i rest)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (let ((i (+ i base)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (vector-set! output i (proc (vect= or-ref input i))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (lp (1+ i)))))
=C2=A0 =C2=A0 output))
--8<---------------cut here---------------end--------------->8---

--
Olivier Dion
oldiob.d= ev
--00000000000016985805eae833c6--