Mind Boggling Performance

or is it Minding Boggle Performance?

In the 2019 APL Problem Solving Competition, we presented a problem to solve the Boggle game where a player tries to make as many words as possible from contiguous letters in a 4×4 grid with the stipulation that you cannot reuse a position on the board.
Richard Park’s 17 October 2019 webinar presents, among other things, a very good discussion about two excellent solutions submitted by Rasmus Précenth and Torsten Grust. A part of that discussion explores the performance of their solutions.  After seeing that webinar, I was curious about how my solution might perform.  Since COVID-19 has curtailed my social life, I find myself with some extra time to write about it in this blog post.
Disclaimers and Goals:

• Performance was not mentioned as one of the criteria for this problem, other than the implicit expectation that your code complete in a reasonable amount of time.  As such, this post is in no way intended to criticize either Rasmus’ or Torsten’s solutions.  In fact, I’m somewhat in awe of the elegance of their code and their application of array-oriented thinking. I have no doubt that if we made performance a primary judging criteria, they would both excel, albeit possibly with modified code.
• I started writing APL in 1975 at the age of 14 and “grew up” in the days of mainframe APL when CPU cycles were a precious commodity.  This more or less forced me to develop an eye towards optimization.
• I’ve tried to use straightforward algorithm optimizations and not leverage or avoid any specific features in the interpreter. Having a bit of understanding about how APL stores its data helps though.
• One goal here is to illustrate some approaches to optimization that may be generally applicable.
• Another goal is to encourage discussion and your participation.  I don’t present my solution as the paragon of performance. I’m sure there are further optimizations that can be made and hope you’ll (gently) suggest some.

The task was to write a function called FindWords that has the syntax:

      words←dictionary FindWords boggleBoard

where

• dictionary is a vector of words. We used SOWPODS, a ~280,000-word word list used by tournament Scrabble™ players.
• boggleBoard is a matrix where each cell contains one or more letters. A standard Boggle board is 4×4.
• the result is a vector which is a subset of dictionary contained the words that can be made from boggleBoard.

Here’s an example of a 2×2 board.

     SOWPODS FindWords ⎕←2 2⍴'th' 'r' 'ou' 'gh'
┌──┬──┐
│th│r │
├──┼──┤
│ou│gh│
└──┴──┘
┌──┬───┬────┬─────┬─────┬──────┬───────┐
│ou│our│thou│rough│routh│though│through│
└──┴───┴────┴─────┴─────┴──────┴───────┘

First let’s define some variables that we’ll use in our exploration.

      w← SOWPODS ⍝ lowercase list of words
      b1← 4 4⍴ 't' 'p' 'qu' 'a' 's' 'l' 'g' 'i' 'r' 'u' 't' 'e' 'i' 'i' 'n' 'a'
      b2← 3 3⍴'s' 'ou' 'gh'  't' 'i' 't' 'the' 'ist' 's'
      b3← 6 6⍴'jbcdcmvueglxriybgeiganuylvonxkfeoqld'
      b1  b2  b3
┌──────────┬────────────┬──────┐
│┌─┬─┬──┬─┐│┌───┬───┬──┐│jbcdcm│
││t│p│qu│a│││s  │ou │gh││vueglx│
│├─┼─┼──┼─┤│├───┼───┼──┤│riybge│
││s│l│g │i│││t  │i  │t ││iganuy│
│├─┼─┼──┼─┤│├───┼───┼──┤│lvonxk│
││r│u│t │e│││the│ist│s ││feoqld│
│├─┼─┼──┼─┤│└───┴───┴──┘│      │
││i│i│n │a││            │      │
│└─┴─┴──┴─┘│            │      │
└──────────┴────────────┴──────┘

Now let’s run some timings using the user command ]runtime. ]runtime will note if the result of the second (or later) timed expression differs from the result of the first expression. Because the solutions may return their word lists in different orders, we use tally ≢ just to make sure that all the solutions return the same number of words (we assume the sets of words are the same if the counts are the same). These timings were done using Dyalog APL v18.0 with a maximum workspace of 256MB running under Windows 10 Pro.
For a “standard” 4×4 Boggle board, we get the following.

      ]runtime "≢w FindWords1 b1" "≢w FindWords2 b1" "≢w FindWords3 b1" -compare
  ≢w FindWords1 b1 → 3.7E¯2 |      0%
  ≢w FindWords2 b1 → 3.2E0  |  +8559% ⎕⎕⎕⎕⎕⎕⎕
  ≢w FindWords2 b3 → 1.7E1  | +46600% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

We see there are factors of about 85× and 450× between FindWords1 versus FindWords2 and FindWords3 respectively.
Let’s look at the 3×3 example…

      ]runtime "≢w FindWords1 b2" "≢w FindWords2 b2" "≢w FindWords3 b2" -compare
  ≢w FindWords1 b2 → 4.1E¯2 |     0% ⎕
  ≢w FindWords2 b2 → 1.5E0  | +3698% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ≢w FindWords3 b2 → 1.5E0  | +3595% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

So, for a smaller board, FindWords1 is about 35× faster than the other two.  What about the larger 6×6board?

      ]runtime "≢w FindWords1 b3" "≢w FindWords2 b3" "≢w FindWords3 b3" -compare
  ≢w FindWords1 b3 → 5.4E¯2 |       0%
  ≢w FindWords2 b3 → 4.3E2  | +788703% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ≢w FindWords3 b3 → 3.4E2  | +621957% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

     ∇ r←words FindWords1 board;inds;neighbors;paths;stubs;nextcells;mwords;mask;next;found;lens;n;m;map
[1]    inds←⍳⍴board                                  ⍝ board indices
[2]    neighbors←(,inds)∘∩¨↓inds∘.+(,¯2+⍳3 3)~⊂0 0   ⍝ matrix of neighbors for each cell
[3]    paths←⊂¨,inds                                 ⍝ initial paths
[4]    stubs←,¨,board                                ⍝ initial stubs of words
[5]    nextcells←neighbors∘{⊂¨(⊃⍺[¯1↑⍵])~⍵}          ⍝ append unused neighbors to path
[6]    mwords←⍉↑words                                ⍝ matrix of candidate words, use a columnar matrix for faster ∧.=
[7]    mask←mwords[1;]∊⊃¨,board                      ⍝ mark only those beginning with a letter on the board
[8]    mask←mask\∧⌿(mask/mwords)∊' ',∊board          ⍝ further mark only words containing only letters found on the board
[9]    words/⍨←mask                                  ⍝ keep those words
[10]   mwords/⍨←mask                                 ⍝ keep them in the matrix form as well
[11]   r←words∩stubs                                 ⍝ seed result with any words that may already be formed from single cell
[12]   :While (0∊⍴paths)⍱0∊⍴words                    ⍝ while we have both paths to follow and words to look at
[13]       next←nextcells¨paths                      ⍝ get the next cells for each path
[14]       paths←⊃,/(⊂¨paths),¨¨next                 ⍝ append the next cells to each path
[15]       stubs←⊃,/stubs{⍺∘,¨board[⍵]}¨next         ⍝ append the next letters to each stub
[16]       r,←words∩stubs                            ⍝ add any matching words
[17]       mask←(≢words)⍴0                           ⍝ build a mask to remove word beginnings that don't match any stubs
[18]       found←(≢stubs)⍴0                          ⍝ build a mask to remove stubs that no words begin with
[19]       lens←≢¨stubs                              ⍝ length of each stub
[20]       :For n :In ∪lens                          ⍝ for each unique stub length
[21]           m←n=lens                              ⍝ mark stubs of this length
[22]           map←(↑m/stubs)∧.=n↑mwords             ⍝ map which stubs match which word beginnings
[23]           mask∨←∨⌿map                           ⍝ words that match
[24]           found[(∨/map)/⍸m]←1                   ⍝ stubs that match
[25]       :EndFor
[26]       paths/⍨←found                             ⍝ keep paths that match
[27]       stubs/⍨←found                             ⍝ keep stubs that match
[28]       words/⍨←mask                              ⍝ keep words that may yet match
[29]       mwords/⍨←mask                             ⍝ keep matrix words that may yet match
[30]   :EndWhile
[31]   r←∪r
     ∇