{"id":5298,"date":"2018-11-27T12:49:34","date_gmt":"2018-11-27T12:49:34","guid":{"rendered":"https:\/\/www.dyalog.com\/blog\/?p=5298"},"modified":"2024-08-15T09:45:09","modified_gmt":"2024-08-15T09:45:09","slug":"dianes-lasagne-problem","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2018\/11\/dianes-lasagne-problem\/","title":{"rendered":"Diane&#8217;s Lasagne Problem"},"content":{"rendered":"<h2>Making Lasagne<\/h2>\n<p>Participants in the SA2 Performance Tuning workshop at the Dyalog \u201918 User Meeting were encouraged to bring their own problems for the group to work on. Diane Hymas of ExxonMobil brought a good one. The one-liner computation is as follows:<\/p>\n<pre><code class=\"language-apl\">lasagne0 \u2190 {groups {+\u233f\u2375}\u2338 amts \u00d7[\u2395io] spices[inds;]}<\/code><\/pre>\n<p>where<\/p>\n<pre><code class=\"language-apl\">   n \u2190 8e5\r\n   spices \u2190 ?6000 44\u23740\r\n   groups \u2190 +\\(16\u21911 2)[?n\u237416]\r\n   inds   \u2190 ?n\u2374\u2262spices\r\n   amts   \u2190 ?n\u23740\r\n<\/code><\/pre>\n<p>Applying <code class=\"language-apl\">lasagne0<\/code> to this dataset:<\/p>\n<pre><code class=\"language-apl\">   \u2374 lasagne0 \u236c\r\n100015 44\r\n   \u2262 \u222a groups\r\n100015\r\n\r\n   )copy dfns wsreq cmpx\r\n\r\n   wsreq 'lasagne0 \u236c'\r\n844799820\r\n   cmpx  'lasagne0 \u236c'\r\n2.12E\u00af1\r\n<\/code><\/pre>\n<p>The problem with <code class=\"language-apl\">lasagne0<\/code> is space rather than time. The 845 MB required for this dataset may be acceptable, but we can be called upon to cook up large batches of lasagne in a smallish workspace, on a machine with limited RAM. (Large <code class=\"language-apl\">n<\/code> and large <code class=\"language-apl\">\u2262\u222agroups<\/code>.)<\/p>\n<p>All benchmarks in this document were run in Dyalog APL version 17.0, in a 2 GB workspace, on a machine with generous RAM.<\/p>\n<h2>Solutions<\/h2>\n<p>Marshall Lochbaum solved the problem. The alternative solutions are as follows:<\/p>\n<pre><code class=\"language-apl\">lasagne0 \u2190 {groups {+\u233f\u2375}\u2338 amts \u00d7[\u2395io] spices[inds;]}\r\nlasagne1 \u2190 {\u2191 (groups{\u2282\u2375}\u2338amts) {+\u233f\u237a\u00d7[\u2395io]spices[\u2375;]}\u00a8 groups{\u2282\u2375}\u2338inds}\r\nlasagne2 \u2190 {\u2191 (groups{\u2282\u2375}\u2338amts)      {\u237a+.\u00d7spices[\u2375;]}\u00a8 groups{\u2282\u2375}\u2338inds}\r\nlasagne3 \u2190 {\u2191 {amts[\u2375]+.\u00d7spices[inds[\u2375];]}\u00a8 {\u2282\u2375}\u2338groups}\r\n<\/code><\/pre>\n<p><code class=\"language-apl\">lasagne0<\/code> is the original expression; <code class=\"language-apl\">lasagne1<\/code> and <code class=\"language-apl\">lasagne2<\/code> were derived by Marshall during the workshop; <code class=\"language-apl\">lasagne3<\/code> was suggested by a participant in the workshop. The four functions produce matching results. Comparing the space and time:<\/p>\n<table border=\"0\">\n<tr>\n<td><\/td>\n<td style=\"text-align:center\">space (MB)<\/td>\n<td style=\"width:auto\"><\/td>\n<td style=\"text-align:left\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;time<\/td>\n<\/tr>\n<tr>\n<td align=\"left\"><code class=\"language-apl\">lasagne0<\/code><\/td>\n<td style=\"text-align:center;\"><code class=\"language-apl\">845<\/code><\/td>\n<td style=\"width:auto\"><\/td>\n<td style=\"text-align:left;\"><code class=\"language-apl\">2.29e\u00af1 \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395<\/code><\/td>\n<\/tr>\n<tr>\n<td align=\"left\"><code class=\"language-apl\">lasagne1<\/code><\/td>\n<td style=\"text-align:center;\"><code class=\"language-apl\">74<\/code><\/td>\n<td style=\"width:auto;\"><\/td>\n<td style=\"text-align:left;\"><code class=\"language-apl\">3.60e\u00af1 \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395<\/code><\/td>\n<\/tr>\n<tr>\n<td><code class=\"language-apl\">lasagne2<\/code><\/td>\n<td style=\"text-align:center;\"><code class=\"language-apl\">74<\/code><\/td>\n<td style=\"width:auto;\"><\/td>\n<td style=\"text-align:left;\"><code class=\"language-apl\">2.39e\u00af1 \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395<\/code><\/td>\n<\/tr>\n<tr>\n<td><code class=\"language-apl\">lasagne3<\/code><\/td>\n<td style=\"text-align:center;\"><code class=\"language-apl\">74<\/code><\/td>\n<td style=\"width:auto;\"><\/td>\n<td style=\"text-align:left;\"><code class=\"language-apl\">2.93e\u00af1 \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395<\/code><\/td>\n<\/tr>\n<\/table>\n<h2>lasagne0 <em>v<\/em>&nbsp;&nbsp;lasagne1<\/h2>\n<p>Nearly all of the space required to evaluate <code class=\"language-apl\">lasagne0<\/code> is accounted for by the space for computing the right argument to <em>key<\/em>:<\/p>\n<pre><code class=\"language-apl\">   wsreq 'lasagne0 \u236c'\r\n844799820\r\n\r\n   wsreq 'amts \u00d7[\u2395io] spices[inds;]'\r\n844799548\r\n<\/code><\/pre>\n<p>In fact, the array <code class=\"language-apl\">spices[inds;]<\/code>, all by itself, is already very large. It has shape <code class=\"language-apl\">(\u2374inds),1\u2193\u2374spices<\/code> <code class=\"language-apl\">(\u2261 8e5 44)<\/code>, each item requiring 8 bytes.<\/p>\n<pre><code class=\"language-apl\">   wsreq 'spices[inds;]'\r\n281599556\r\n\r\n   \u2374 spices[inds;]\r\n800000 44\r\n\r\n   8 \u00d7 \u00d7\/ \u2374 spices[inds;]\r\n281600000\r\n\r\n   qsize\u2190{\u2395size '\u2375'}    \u235d # bytes for array \u2375\r\n   qsize spices[inds;]\r\n281600040\r\n<\/code><\/pre>\n<p><code class=\"language-apl\">lasagne1<\/code> avoids creating these large intermediate results, by first partitioning the arguments (<code class=\"language-apl\">groups{\u2282\u2375}\u2338amts<\/code> and <code class=\"language-apl\">groups{\u2282\u2375}\u2338inds<\/code>) and then applying a computation to each partition. In that computation, the operand function <code class=\"language-apl\">{+\u233f\u237a\u00d7[\u2395io]spices[\u2375;]}<\/code>, <code class=\"language-apl\">\u237a<\/code> is a partition of <code class=\"language-apl\">amts<\/code> and <code class=\"language-apl\">\u2375<\/code> is the corresponding partition of <code class=\"language-apl\">inds<\/code>.<\/p>\n<p><code class=\"language-apl\">lasagne1<\/code>, <code class=\"language-apl\">lasagne2<\/code> and <code class=\"language-apl\">lasagne3<\/code> require the same amount of space to run, so the comparison among them is on time.<\/p>\n<h2>lasagne1 <em>v<\/em>&nbsp;&nbsp;lasagne2<\/h2>\n<p>The only change is from <code class=\"language-apl\">+\u233f\u237a\u00d7[\u2395io]spices[\u2375;]<\/code> to <code class=\"language-apl\">\u237a+.\u00d7spices[\u2375;]<\/code>, which are equivalent when <code class=\"language-apl\">\u237a<\/code> is a vector. The interpreter can compute <code class=\"language-apl\">+.\u00d7<\/code> in one go rather than doing <code class=\"language-apl\">+\u233f<\/code> separately after doing <code class=\"language-apl\">\u00d7[\u2395io]<\/code>; in such computation the interpreter can and does exploit the additional information afforded by <code class=\"language-apl\">+.\u00d7<\/code> and is faster by a factor of <code class=\"language-apl\">1.5<\/code> <code class=\"language-apl\">(= 2.39 \u00f7\u2368 3.60)<\/code>.<\/p>\n<h2>lasagne2 <em>v<\/em>&nbsp;&nbsp;lasagne3<\/h2>\n<p>The idea in <code class=\"language-apl\">lasagne3<\/code> is doing one <em>key<\/em> operation rather than the two in <code class=\"language-apl\">lasagne2<\/code>. Therefore, the changes between <code class=\"language-apl\">lasagne2<\/code> <em>v<\/em> <code class=\"language-apl\">lasagne3<\/code> are:<\/p>\n<table border=\"0\">\n<tr>\n<td><code class=\"language-apl\">lasagne2<\/code><\/td>\n<td style=\"white-space:pre;\"><code class=\"language-apl\">groups{\u2282\u2375}\u2338amts<br \/>\ngroups{\u2282\u2375}\u2338inds<\/code><\/td>\n<td><code class=\"language-apl\">\u237a<\/code><\/td>\n<td><code class=\"language-apl\">spices[\u2375;]<\/code><\/td>\n<\/tr>\n<tr>\n<td><code class=\"language-apl\">lasagne3<\/code><\/td>\n<td><code class=\"language-apl\">{\u2282\u2375}\u2338groups<\/code><\/td>\n<td><code class=\"language-apl\">amts[\u2375]<\/code><\/td>\n<td><code class=\"language-apl\">spices[inds[\u2375];]<\/code><\/td>\n<\/tr>\n<\/table>\n<p>All three <em>key<\/em> operations involve <code class=\"language-apl\">{\u2282\u2375}\u2338<\/code> with <code class=\"language-apl\">groups<\/code> as the key, and are roughly equally fast, each taking up no more than 7% of the total time.<\/p>\n<pre><code class=\"language-apl\">   cmpx 'groups{\u2282\u2375}\u2338amts' 'groups{\u2282\u2375}\u2338inds' '{\u2282\u2375}\u2338groups'\r\n  groups{\u2282\u2375}\u2338amts \u2192 1.69E\u00af2 |   0% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n* groups{\u2282\u2375}\u2338inds \u2192 1.39E\u00af2 | -18% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n* {\u2282\u2375}\u2338groups     \u2192 1.36E\u00af2 | -20% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n<\/code><\/pre>\n<p><code class=\"language-apl\">lasagne3<\/code> is doing one less <em>key<\/em> operation than <code class=\"language-apl\">lasagne2<\/code> in exchange for doing, for each of the <code class=\"language-apl\">\u2262\u222agroups<\/code> <code class=\"language-apl\">(= 100015)<\/code> executions of the operand function, <code class=\"language-apl\">amt[\u2375]<\/code> <em>v<\/em> <code class=\"language-apl\">\u237a<\/code> and <code class=\"language-apl\">spices[ind[\u2375];]<\/code> <em>v<\/em> <code class=\"language-apl\">spices[\u2375;]<\/code>. Indexing is by no means slow, but it&#8217;s not as fast as references to <code class=\"language-apl\">\u237a<\/code> and <code class=\"language-apl\">\u2375<\/code>. Therefore, <code class=\"language-apl\">lasagne2<\/code> is faster.<\/p>\n<p>The trade-off may differ for different values of <code class=\"language-apl\">groups<\/code>. In this case <code class=\"language-apl\">groups<\/code> are small-range integers so operations using it as the key value are fast.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Making Lasagne Participants in the SA2 Performance Tuning workshop at the Dyalog \u201918 User Meeting were encouraged to bring their own problems for the group to work on. Diane Hymas of ExxonMobil brought a good one. The one-liner computation is &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2018\/11\/dianes-lasagne-problem\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[34,4,23],"tags":[],"class_list":["post-5298","post","type-post","status-publish","format-standard","hentry","category-dyalog-18","category-events","category-musings"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/5298","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=5298"}],"version-history":[{"count":16,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/5298\/revisions"}],"predecessor-version":[{"id":5411,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/5298\/revisions\/5411"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=5298"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=5298"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=5298"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}