guile-user
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: map-par slower than map


From: Zelphir Kaltstahl
Subject: Re: map-par slower than map
Date: Wed, 12 Oct 2022 21:29:34 +0000

Hi!

On 10/12/22 22:27, Damien Mattei wrote:
https://github.com/damien-mattei/library-FunctProg/blob/master/guile/logiki%2B.scm#L1674

i commited the current version of code here with all files but it is
huge.... :-/

On Wed, Oct 12, 2022 at 10:20 PM Damien Mattei <damien.mattei@gmail.com>
wrote:

Mutex? i do not think code has situation where dead lock could happen, it
is a code about minimalising logic expressions, it uses minterms , minterms
set is a set of minterms :like this:

example:
((1 1 0) (1 1 1)) will be unified : (1 1 x)
because 0 and 1 are replaced by x
the minterms-set could have thousands of pair (mathematic not lisp)
minterms to unify
if there is more than one x as result there is no need to continue so i
escape with a continuation:

minterms-set =
{
((1 0 1 0) (1 1 1 0))
((1 0 1 0) (1 1 0 1))
((1 0 1 0) (1 0 1 1))
((1 0 1 0) (0 1 1 1))
((0 1 1 0) (1 1 1 0))
((0 1 1 0) (1 1 0 1))
((0 1 1 0) (1 0 1 1))
((0 1 1 0) (0 1 1 1))
((0 1 0 1) (1 1 1 0))
((0 1 0 1) (1 1 0 1))
((0 1 0 1) (1 0 1 1))
((0 1 0 1) (0 1 1 1))
((0 0 1 1) (1 1 1 0))
((0 0 1 1) (1 1 0 1))
((0 0 1 1) (1 0 1 1))
((0 0 1 1) (0 1 1 1))
}

replace { } by () to have the list, other example at another level :

minterms-set =
{
((0 x 1 1) (x 1 1 1))
((0 x 1 1) (1 x 1 1))
((0 x 1 1) (1 1 x 1))
((0 x 1 1) (1 1 1 x))
((x 0 1 1) (x 1 1 1))
((x 0 1 1) (1 x 1 1))
((x 0 1 1) (1 1 x 1))
((x 0 1 1) (1 1 1 x))
((0 1 x 1) (x 1 1 1))
((0 1 x 1) (1 x 1 1))
((0 1 x 1) (1 1 x 1))
((0 1 x 1) (1 1 1 x))
((x 1 0 1) (x 1 1 1))
((x 1 0 1) (1 x 1 1))
((x 1 0 1) (1 1 x 1))
((x 1 0 1) (1 1 1 x))
((0 1 1 x) (x 1 1 1))
((0 1 1 x) (1 x 1 1))
((0 1 1 x) (1 1 x 1))
((0 1 1 x) (1 1 1 x))
((x 1 1 0) (x 1 1 1))
((x 1 1 0) (1 x 1 1))
((x 1 1 0) (1 1 x 1))
((x 1 1 0) (1 1 1 x))
((1 0 1 x) (x 1 1 1))
((1 0 1 x) (1 x 1 1))
((1 0 1 x) (1 1 x 1))
((1 0 1 x) (1 1 1 x))
((1 x 1 0) (x 1 1 1))
((1 x 1 0) (1 x 1 1))
((1 x 1 0) (1 1 x 1))
((1 x 1 0) (1 1 1 x))
}

here we see some minterms are already unified

  it is not easy to read even by me because i wrote the code many years ago
and is split in many files, but here it is:

(par-map function-unify-minterms-list minterms-set)

{function-unify-minterms-list <+ (λ (L) (apply
function-unify-two-minterms-and-tag L))}

(define (unify-two-minterms mt1 mt2)
   (function-map-with-escaping-by-kontinuation2
  (macro-function-compare-2-bits-with-continuation) mt1 mt2))

;; (function-map-with-escaping-by-kontinuation2
(macro-function-compare-2-bits-with-continuation)   '(1 1 0 1 0 1 1 0) '(1
1 0 1 1 1 1 1))

;; list1 = (1 1 0 1 0 1 1 0)
;; more-lists = ((1 1 0 1 1 1 1 1))
;; lists = ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 1))
;; clozure = #<procedure:...gos-DrRacket.scm:195:11>

;; #f
;;
;;  (function-map-with-escaping-by-kontinuation2
(macro-function-compare-2-bits-with-continuation)    '(1 1 0 1 0 1 1 0) '(1
1 0 1 1 1 1 0))

;; list1 = (1 1 0 1 0 1 1 0)
;; more-lists = ((1 1 0 1 1 1 1 0))
;; lists = ((1 1 0 1 0 1 1 0) (1 1 0 1 1 1 1 0))
;; clozure = #<procedure:...gos-DrRacket.scm:195:11>

;; '(1 1 0 1 x 1 1 0)
(define (function-map-with-escaping-by-kontinuation2 clozure list1 .
more-lists)
   (call/cc (lambda (kontinuation)
     (let ((lists (cons list1 more-lists))
   (funct-continu ;; this function have the kontinuation in his environment
    (lambda (arg1 . more-args)
      (let ((args (cons arg1 more-args)))
(apply clozure kontinuation args))))) ;; a tester: (apply clozure (cons
conti args))

          ;; (newline)
          ;; (dv list1)
          ;; (dv more-lists)
          ;; (dv lists)
  ;; (dv clozure)
          ;; (newline)

       (apply map funct-continu lists)))))

(define-syntax macro-function-compare-2-bits-with-continuation ;;
continuation version of macro-compare-2-bits
   ;; i need a macro because of external function to the clozure
   (syntax-rules ()
     ((_) (let ((cnt 0)) ;; counter
   (lambda (continuation b1 b2) (if (equal? b1 b2)
  b1
  (begin
    (set! cnt (add1 cnt)) ;; we leave with continuation in case cpt > 1, we
can have used a flag too instead of a counter
    (when (> cnt 1) (continuation #f)) ;; escaping with the continuation
    'x))))))) ;; return x in case of (b1,b2) = (O,1) or (1,0)

what could have caused mutex if in the latter definition above (let ((cnt
0)) ;; counter was defined at top level and shared by all threads!!! yes
there could have be some mutex  but this is not the case, i think even all
function are pure so why is it more slow with // than without?
Damien

On Wed, Oct 12, 2022 at 8:45 PM Maxime Devos <maximedevos@telenet.be>
wrote:

On 12-10-2022 19:19, 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!?
  > [...]
  >
translated from Scheme+ to Scheme:
(define unified-minterms-set-1 (map function-unify-minterms-list
minterms-set)) ;;(par-map function-unify-minterms-list minterms-set))
The definition of 'function-unify-minterms-list' and 'minterms-set' is
missing.  Without a test case, we can only speculate what's going on.
(E.g., maybe it grabs a mutex).

Greetings,
Maxime.
I don't want to scare anyone, just maybe warn about parallel map. I once tried to use Guile's parallel map function for a decision tree implementation (https://notabug.org/ZelphirKaltstahl/guile-ml/src/cf666801fea91c9fa8fa290764ff6c60b7f3949d/decision-tree.scm), where each branch while learning the tree would call parallel map again for sub branches and so on. Somehow it made Guile crash (I don't have the error message any longer, but I did post about it on the mailing list back then.). I never figured out, what went wrong. All I had was pure function calls and math inside the thing that parallel map was supposed to run.

Ultimately I simply tried other parallelism constructs and when I switched to using futures instead, everything worked fine, no crashes, no errors.

Since that time, I did not use parallel map and instead used futures. Recently I made a parallelization thing for solving exercises of Project Euler using multiple cores, so that some solutions are calculated faster. Maybe this can help or can be adapted to another use case:

https://notabug.org/ZelphirKaltstahl/guile-project-euler-solutions/src/ebb19b11b465903105924adb6252f1e2ecf63859/lib/parallelism.scm#L11-L30

It expects ranges of things, which are called `segments` in the code. Usually ranges of numbers for Project Euler things. Here is the code to split a range into segments:

https://notabug.org/ZelphirKaltstahl/guile-project-euler-solutions/src/ebb19b11b465903105924adb6252f1e2ecf63859/lib/segment.scm

(Check any solution using it for an example.)

So this might be a bit too specific for general parallel things, but I guess one could change the way futures are used in `run-in-parallel`, to fit any other purpose.

Best regards,
Zelphir

--
repositories: https://notabug.org/ZelphirKaltstahl




reply via email to

[Prev in Thread] Current Thread [Next in Thread]