{"id":2383,"date":"2021-04-26T19:32:57","date_gmt":"2021-04-26T14:02:57","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=2383"},"modified":"2021-04-26T19:32:57","modified_gmt":"2021-04-26T14:02:57","slug":"lparallel-a-parallel-programming-library","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/26\/lparallel-a-parallel-programming-library\/","title":{"rendered":"lparallel: A Parallel Programming Library"},"content":{"rendered":"

You may recall that in the last article I had reviewed the book “Algorithms in Lisp”<\/strong><\/em><\/a>\u00a0by Vsevolod Domkin<\/strong><\/em>. There was a reference to the lparallel<\/strong><\/em><\/a>\u00a0library in Chapter 15<\/strong><\/em> of the book. That immediately reminded me of the nice discussion of lparallel<\/strong><\/em> by Edi Weitz<\/strong><\/em> in Chapter 11<\/strong><\/em> of his excellent book “Common Lisp Recipes”<\/strong><\/em><\/a>.\u00a0<\/span><\/p>\n

Since I have not used lparallel<\/strong><\/em> so far, I wanted to check it out. Instead of trying something very original, I decided to start with the “pmap”<\/strong><\/em> example in Edi’s book.<\/p>\n

Here is the code for the “pmap”<\/strong><\/em> example:<\/p>\n

\"pmap:<\/a>
pmap: Parallel Map<\/strong><\/figcaption><\/figure>\n

I made a minor change to “test”<\/strong><\/em> and “ptest”<\/strong><\/em> to return “t”<\/strong><\/em> instead of the mapped result. This is to avoid the large data dump when I execute the function on the console. Of course, if I wanted to compare the results of the two maps, I would have retained the original code, but that was not my intention. My focus was on the speed up due to parallel execution.<\/p>\n

Here is my environment:\u00a0<\/span><\/p>\n

1) Intel Core i7-7700 CPU @ 3.60 GHz, 32 GB RAM, Windows 10, 64-bit.\u00a0<\/span><\/span><\/p>\n

2) LispWorks 7.1.2 Enterprise Edition (64-bit).<\/span><\/p><\/blockquote>\n

In fact, before running the “pmap”<\/strong><\/em> test, I wanted to find out the number of CPU cores<\/strong><\/em> on my Windows<\/strong><\/em> machine. Interestingly, in Section 11-6<\/strong><\/em>, Edi Weitz<\/strong><\/em> gives a\u00a0“CFFI”<\/strong><\/em>-based implementation that does the job. I decided to use that:<\/p>\n

\"Finding<\/a>
Finding the Number of CPU Cores<\/strong><\/figcaption><\/figure>\n

Here is what I get when I execute “(get-number-of-processors)”:<\/strong><\/em><\/p>\n

\"Available<\/a>
Available CPU Cores<\/strong><\/figcaption><\/figure>\n

When using lparallel<\/strong><\/em>, we have to specify the number of worker threads to use as part of its “kernel”<\/strong><\/em>.\u00a0<\/span><\/p>\n

First, I ran “(test)”<\/strong><\/em> and “(ptest)”<\/strong><\/em> with 4 kernel threads:<\/p>\n

\"Testing<\/a>
Testing with 4 Kernel Threads<\/strong><\/figcaption><\/figure>\n

Looking at the “Elapsed Time”<\/strong><\/em> field, we see that “ptest”<\/strong>\u00a0is 3 times faster than <\/em>“test”<\/strong>.\u00a0<\/em>To see the CPU utilization<\/strong><\/em>, I ran Window’s Task Manager<\/strong><\/em>.\u00a0This is what I see when the “<\/strong>(test)”<\/strong><\/em> function is executing:<\/p>\n

\"Task<\/a>
Task Manager: CPU Utilization (test)<\/strong><\/figcaption><\/figure>\n

You will notice that the CPU utilization is not that great. When I run the paralel version, “(ptest)”<\/strong><\/em>, the situation changes:<\/p>\n

\"Task<\/a>
Task Manager: CPU Utilization (ptest)<\/strong><\/figcaption><\/figure>\n

You can see the significant jump in the CPU utilization and the reduction in time taken. Good, that shows lparallel<\/strong><\/em> is working!<\/p>\n

By the way, “Cores”<\/strong><\/em> in the utilization chart refers to the “physical”<\/strong><\/em> (or actual) hardware cores in the CPU. “Logical processors”<\/strong><\/em> is the total number of threads that can run in parallel. If the hardware supports “Hyperthreading”<\/strong><\/em>, as is true in my case, then multiple threads can run on the same core in parallel. That is why on my 4-core machine, I am able to run 8 threads in parallel.<\/p>\n

Let us now try the two functions with 8 worker threads.<\/p>\n

\"With<\/a>
With 8 Worker Threads in Kernel<\/strong><\/figcaption><\/figure>\n

What about CPU utilization with increased threads?<\/p>\n

We do not expect “(test)”<\/strong><\/em> to have any impact:<\/p>\n

\"CPU<\/a>
CPU Utilization with 8 Cores: (test)<\/strong><\/figcaption><\/figure>\n

Now see how it changes dramatically when running “(ptest)”<\/em><\/strong>:<\/p>\n

\"CPU<\/a>
CPU Utilization with 8 Cores: (test)<\/strong><\/figcaption><\/figure>\n

We have 100% CPU utilization<\/strong><\/em> when the function executes!<\/p>\n

Next, I wanted to try the classical “Fibonacci”<\/strong><\/em> computation using lparallel<\/strong><\/em>. Here are 3 versions of the implementation:<\/p>\n

\"Calculating<\/a>
Calculating the Fibonacci Series<\/strong><\/figcaption><\/figure>\n

Explanation:<\/p>\n

1) “fib”<\/strong><\/em> is the standard recursive implementation.<\/span><\/p>\n

2) “pfib”<\/strong><\/em> uses the lparallel<\/strong><\/em> construct “plet”<\/strong><\/em>. This results in two parallel threads computing (fib n-1)<\/strong><\/em> and (fib n-2)<\/strong><\/em>. When they are done, the result is summed and returned. Note that the two threads run the first defintion “fib”<\/strong><\/em>.<\/span><\/p>\n

3) “pfib2”<\/strong><\/em> is an extreme case of parallelism. It uses “defpun”<\/strong><\/em> construct of lparallel<\/strong><\/em> to define a function that can automatically execute in a parallel thread. Additionally, it uses “plet”<\/strong><\/em> and makes recursive calls to itself! This results in creating a very large number of threads, unmindful of the hardware support available. This can slow down the computation significantly.<\/span><\/p><\/blockquote>\n

This is what happens when these functions are run:<\/p>\n

\"Performance<\/a>
Performance of Fibonacci Implementations<\/strong><\/figcaption><\/figure>\n

A look at the “Elapsed time”<\/strong> <\/em>shows that “pfib”<\/strong> <\/em>is faster than “fib”<\/strong><\/em> (by about 1.6 times), but “pfib2”<\/strong><\/em> is pathetically slow as expected!<\/p>\n

That concludes today’s discussion on lparallel<\/strong><\/em><\/a>. It is a feature rich library and well documented. I intend to spend more time understanding its capabilities, and hope to apply it in one or more of my Lisp projects.<\/p>\n

You can download<\/strong><\/em><\/a> the source code for today’s experiment.<\/p>\n

Have a nice week ahead!<\/p>\n","protected":false},"excerpt":{"rendered":"

You may recall that in the last article I had reviewed the book “Algorithms in Lisp”\u00a0by Vsevolod Domkin. There was a reference to the lparallel\u00a0library in Chapter 15 of the book. That immediately reminded me of the nice discussion of lparallel by Edi Weitz in Chapter 11 of his excellent book “Common Lisp Recipes”.\u00a0 Since […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[18,17],"tags":[278,277,99,276,279,280],"class_list":["post-2383","post","type-post","status-publish","format-standard","hentry","category-lisp","category-programming","tag-fibonacci","tag-lisp-programming","tag-lispworks","tag-lparallel-lisp-library","tag-map","tag-parallel-map"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-Cr","jetpack-related-posts":[{"id":2377,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/12\/book-review-programming-algorithms-in-lisp\/","url_meta":{"origin":2383,"position":0},"title":"Book Review: Programming Algorithms in Lisp","author":"admin","date":"April 12, 2021","format":false,"excerpt":"Title: Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp Author: Vsevolod Domkin Publisher: Apress Year: 2021 It is only about 5 months since I read and reviewed\u00a0a good book on Lisp written by Micha\u0142 \u201cphoe\u201d Herda. The present book is by Vsevolod Domkin\u00a0and I purchased\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/Book-Cover-209x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":190,"url":"https:\/\/www.rangakrish.com\/index.php\/2016\/03\/15\/book-review-common-lisp-recipes-by-edi-weitz\/","url_meta":{"origin":2383,"position":1},"title":"Book Review: Common Lisp Recipes – A Problem-Solution Approach","author":"admin","date":"March 15, 2016","format":false,"excerpt":"Last Saturday (March 12, 2016), I got my most eagerly awaited book from Amazon.com. Yes, I am talking about Common Lisp Recipes: A Problem-Solution Approach\u00a0authored by Dr.Edmund Weitz. Of course, if you have been programming in Lisp for a couple of years, you would have definitely heard of Dr.Edi Weitz,\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2200,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/11\/08\/book-review-the-common-lisp-condition-system-beyond-exception-handling-with-control-flow-mechanisms\/","url_meta":{"origin":2383,"position":2},"title":"Book Review – The Common Lisp Condition System: Beyond Exception Handling with Control Flow Mechanisms.","author":"admin","date":"November 8, 2020","format":false,"excerpt":"Title: The Common Lisp Condition System: Beyond Exception Handling with Control Flow Mechanisms Author: Micha\u0142 \"phoe\" Herda Publisher: Apress Year: 2020 Unlike with other languages, it is rare to find new books being published on Lisp. The last book on Lisp, which I purchased was \u201cCommon Lisp Recipes\u201d\u00a0\u00a0by Edmund Weitz\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/11\/Cover-page-209x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2406,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/05\/09\/eager-future2-common-lisp-library\/","url_meta":{"origin":2383,"position":3},"title":"Eager Future2 Common Lisp Library","author":"admin","date":"May 9, 2021","format":false,"excerpt":"Eager Future2 is a Common Lisp library that facilitates parallel computation. It is based on the idea of a \u201cfuture\u201d that acts as a \u201cproxy\u201d for a concurrently computed expression. Unlike the \u201clparallel\u201d library that I had discussed in the last article, this library does not give us control over\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Fibonacci Calculation - 3 Ways","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/05\/Code-232x300.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2736,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/03\/19\/book-review-introducing-blockchain-with-lisp\/","url_meta":{"origin":2383,"position":4},"title":"Book Review: Introducing Blockchain with Lisp","author":"admin","date":"March 19, 2022","format":false,"excerpt":"Title: Introducing Blockchain with Lisp: Implement and Extend Blockchains with the Racket Language Author: Boro Sitnikovski Publisher: Apress Year: 2021 Blockchains are a hot topic these days and interestingly, I am getting involved in a project that uses Blockchain. Languages such as C++, Java, Go and Node.js are commonly used\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/03\/Blockchain-Book-300x251.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":3312,"url":"https:\/\/www.rangakrish.com\/index.php\/2024\/01\/28\/the-hy-programming-language\/","url_meta":{"origin":2383,"position":5},"title":"The Hy Programming Language","author":"admin","date":"January 28, 2024","format":false,"excerpt":"In an earlier article\u00a0I had explained how to execute Python code from within Common Lisp using \u201cCLPython\u201d package. In contrast to that approach, \u201cHy\u201d\u00a0is a Lisp-style language (not compatible with Common Lisp) that is embedded in Python and hence provides seamless interoperability with Python code. Installation is straightforward (it is\u2026","rel":"","context":"In "Hy Language"","block_context":{"text":"Hy Language","link":"https:\/\/www.rangakrish.com\/index.php\/category\/hy-language\/"},"img":{"alt_text":"Hy REPL","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2024\/01\/console-300x148.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=2383"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2383\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=2383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=2383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=2383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}