Author Archives: Brian Becker

Hashing It Out: Lookup Performance in Dyalog APL

Posted on by
Reply

Sometimes it seems that I have the attention span of a cocker spaniel puppy. I start to look at one thing, and then something pops up to distract me and I follow that until another distraction or tangent comes along and then…. well, you get the point. What started out as one blog post has morphed a few times into what you’re about to read!

Background and Original Goal

In a former life, I wrote an APL-based full-text search engine for searching legislative and regulatory texts. At the time, its speed rivalled any of the online search engines. In that governmental context, words like “the” and “of” have significance, for example, the “the” in “the white house” is significant, as are the “of” and “the” in “speaker of the house”. Most search engines would ignore those high-frequency “noise” words – mine couldn’t. My goal was to be able to search for such phrases without having to examine the data for the high-frequency words. I found this to be an interesting problem at the time (in the 1990s) and subsequently included it 25 years later as the 2015 APL Problem Solving Competition Phase 2 Applications Problem 2. My original idea for this blog post was to examine approaches to that problem.

The core of the problem was straightforward – you have a list of words (vector of character vectors) and a corresponding vector of frequencies for each word. We’ll call these two vectors Words and Freqs. For those interested, the source data I used for my recent effort came from a repository that tracks Wikipedia word frequencies. The task is to, for a given phrase, break the phrase up into individual words (we’ll call this words), look up words in Words, and use the indices to extract their frequencies from Freqs. This is basic APL, the sort of thing we do all the time: Freqs[Words ⍳ words]. If we want to consider the case where a word in words isn’t found in Words, we can append 0 to Freqs.

The source for Words and Freqs has 2,765,377 words. To emulate my original work done in the 1990s when we were using only ASCII characters, I decided to remove words containing non-ASCII characters. As a result, we’re left with 1,905,526 words.

Tangent #1 – ⎕CSV

If you’re interested in obtaining Words and Freqs yourself, you can download the raw data file and use ⎕CSV and a bit of code:

      (Words Freqs)←⎕CSV⍠('Separator' ' ')('Invert' 2)⊢'{your-path-here}/enwiki-2023-04-13.txt' ''(1 2)
      (Words Freqs)/⍨←⊂Words(∧/∊)¨⊂⎕C⎕A ⍝ limit words to ASCII alphabetics

⎕CSV can do some amazing things. Adám Brudzewsky made a very interesting video on Parsing content from text files using ⎕CSV.

From that list, the five most and least frequent words are:

      ⍉↑5(↑,-⍛↑)¨Words Freqs ⍝ look mom! I used ⍛ (behind)!
 the          186631452
 of            88349543
 in            76718795
 and           76039670
 a             54631147
 byodoinji            3
 houryuuji            3
 groendorpen          3
 witotoanas           3
 kimely               3

Interestingly, it seems a word must occur at least 3 times in Wikipedia to make it into this list. Okay, enough background information…

Distraction #1

In my testing, I found that, when words exceeded 3 elements, things slowed down a lot. For example:

      ]RunTime -c "Words⍳'the' 'big' 'dog'" "Words⍳'the' 'big' 'fuzzy' 'dog'"
  Words⍳'the' 'big' 'dog'         → 1.3E¯4 |       0%                                          
* Words⍳'the' 'big' 'fuzzy' 'dog' → 2.5E¯1 | +202400% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

One would expect the performance to degrade linearly with the number of words. This appears to be true until you reach 4 elements in the right argument. Let’s create some test cases using lists of 1 to 6 words; since ‘the’ is the first word in the list, these searches should be as fast as possible.

      (p1 p2 p3 p4 p5 p6)←1 2 3 4 5 6⍴¨⊂'the'

Now let’s see what happens when we search for lists of 1 to 4 words:

      ]RunTime -c Words⍳p1 Words⍳p2 Words⍳p3 Words⍳p4
  Words⍳p1 → 2.1E¯2 |     0% ⎕⎕⎕                                      
* Words⍳p2 → 4.2E¯2 |  +102% ⎕⎕⎕⎕⎕⎕                                   
* Words⍳p3 → 6.2E¯2 |  +204% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕                               
* Words⍳p4 → 2.6E¯1 | +1147% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

It looks linear for lengths 1 to 3, but jumps at length 4. If we look at lengths 4 to 6, we see a linear pattern, albeit considerably slower.

      ]RunTime -c Words⍳p4 Words⍳p5 Words⍳p6
  Words⍳p4 → 2.5E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕   
* Words⍳p5 → 2.5E¯1 | +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  
* Words⍳p6 → 2.6E¯1 | +4% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

What’s going on?! After a bit of research (I asked Morten!), I found that Dyalog is hashing Words extemporaneously when words exceeds 3 elements. Because the hash table is not retained, Words is hashed for each iteration in ]RunTime, causing the slowdown.

Since creating the hash table is a relatively expensive operation, it only makes sense to do if there is a mechanism to retain the table from which subsequent searches can benefit or the right argument is long enough to justify the upfront cost.

Tangent #2 – A Brief History of Hashing in Dyalog APL

First, a bit of terminology – search functions have a “principal” argument (the array being searched) and a “subject” argument (the items being searched for). In the example above, Words is the principal argument and words is the subject argument.

Hashing, in one form or another, has existed in Dyalog APL from its earliest days; it’s an industry standard technique. The interpreter decides, based on a number of factors, whether to hash an array extemporaneously or not. This hashing is an internal process and beyond the user’s control.

Dyalog v10.0, released in 2003, gave users the ability to bind a search function like ⍳ (index of), ∊ (membership), ∩ (intersection), ∪ (union), or ~ (without) to its principal argument, resulting in a derived function that will, on its first invocation, create and retain a hash table. The disadvantage of this is that the hash table is used exclusively for the bound search function. If you needed to use more than one search function you would bind them individually and each would have its own hash table.

Dyalog v15.0, released in 2016, introduced 1500⌶ (hash array). This allows the user to mark an array for hashing and, after the first search operation creates the hash table, the hash table is available for all applicable search functions. array←1500⌶array returns a copy of array that is marked for hashing. The hash is created on the first invocation of a search function on array. 1(1500⌶)array returns 0 if array has not been marked for hashing, 1 if array has been marked for hashing but the hash has not been created yet, and 2 if array has a hash table. For example:

      1 (1500⌶) Words ⍝ not marked yet
0
      Words←1500⌶ Words ⍝ mark for hashing
      1 (1500⌶) Words
1
      Words⍳⊂'the' ⍝ perform a search (this is a bit slow)
      1 (1500⌶) Words ⍝ Words now has a hash table
2
      Words,←⊂'thermoflocker' ⍝ add a new word to the tail end
      1 (1500⌶) Words ⍝ still hashed
2
      Words← 1 ↓ Words ⍝ drop something from the front end
      1 (1500⌶) Words ⍝ no longer hashed nor marked for hashing
0

The size of the hash table can impact performance. In general, larger hash tables result in faster lookups. Dyalog v19.0, released in 2024, introduced 8468⌶ (hash table size), which allowed the user to adjust the size factor of created hash tables. Its purpose was to allow users to evaluate the potential side effects of a proposed larger hash table size.

Hash tables in Dyalog APL work best with (mostly) static principal arrays. In general, modifying the array invalidates the hash and the array will need to be rehashed. However, there are three forms of modified assignment that will preserve and efficiently update the hash – notice that they all involve the tail end of the principal array.

      R,←Y    ⍝ only for scalar or vector R
      R⍪←Y
      R↓⍨←Y   ⍝ only for negative singleton Y

Dyalog v20.0, released in 2025, implemented hash tables that are 8 times (2*3) larger than previously and also removed 8468⌶. More on this later…

Why Hash?

The simplistic approach to search functions like ⍳ and ∊ is to perform a linear search, starting at the first element of the principal argument and iterating through its elements until you find a match. Obviously, elements that occur near the front will be found faster. In a worst case, searching for an element that’s not in the principal argument will have to search its entirety. Doing a linear search on the first word in Words and for a word not found in Words demonstrates this:

      ]RunTime -c "Words⍳⊂'the'" "Words⍳⊂'thermoflocker'"
  Words⍳⊂'the'           → 0.0E0  |    -100%                                          
* Words⍳⊂'thermoflocker' → 2.0E¯2 | +250200% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Hashing smooths out this variability and makes all lookups relatively similar in performance, not to mention considerably faster. Doing the same search on aWords, a hashed version of Words, shows this.

      ]RunTime -c "aWords⍳⊂'the'" "aWords⍳⊂'thermoflocker'"
  aWords⍳⊂'the'           → 2.1E¯7 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕     
* aWords⍳⊂'thermoflocker' → 2.4E¯7 | +11% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

“I Feel the Need for Speed” (Top Gun, 1986)

Let’s revisit the issue that led us down the hashing path. We’ll create a hashed copy of Words, but leave Words alone so that we can compare performance. We’ll also create a function bound with ⍳.

      hWords←1500⌶Words ⍝ hWords is marked for hashing
      hWords⍳⊂'the'      ⍝ first search creates the hash table
1
      fWords←Words∘⍳      ⍝ also create the derived function  
      fWords ⊂'the'      ⍝ first search creates the hash table
1
      p←'the' 'big' 'fuzzy' 'dog'
      ]RunTime -c "hWords ⍳ p" "fWords p" "Words ⍳ p"
                                                                        
  hWords ⍳ p → 0.0E0  |    -100%                                          
  fWords p → 0.0E0    |    -100%                                          
  Words ⍳ p  → 3.5E¯1 | +556800% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Once we have a retained hash table, all lookups, no matter the length of words, will be faster.

Tangent #3 – When Does a Principal Argument Get Hashed?

The short answer is: it depends on a number of factors, such as:

  • whether a search function like ⍳ or ∊ is used
  • the sizes of the principal and subject arrays
  • the datatypes of the arrays – character, integer, floating point, complex
  • are the arrays simple (depth 0 or 1) or not?
  • the amount of workspace available – can it fit the hash table?

In short, Dyalog APL hashes an array when it “thinks” doing so will help. However, you know your application and its data better than the interpreter does. In my example above, the interpreter can’t know if my search is a one-time thing or something that will be executed many times.

How can you determine where hashing kicks in? What I did was to start with a single element subject argument and increase its length until I saw a “bump” in runtime:

      iv←1e7?2*24  ⍝ build 10-million element integer vector with no duplicates

      ⍝ now time lookups for subject arrays of length 1 to 15
      ⎕SE.UCMD 'runtime -c',∊' iv⍳iv['∘,¨(⍕¨⍳15),¨⊂'⍴5000000]'
  iv⍳iv[1⍴5000000]  → 1.0E¯3 |     0%                                          
* iv⍳iv[2⍴5000000]  → 2.1E¯3 |  +100% ⎕                                        
* iv⍳iv[3⍴5000000]  → 3.2E¯3 |  +206% ⎕                                        
* iv⍳iv[4⍴5000000]  → 4.3E¯3 |  +315% ⎕⎕                                       
* iv⍳iv[5⍴5000000]  → 5.3E¯3 |  +412% ⎕⎕                                       
* iv⍳iv[6⍴5000000]  → 6.2E¯3 |  +503% ⎕⎕⎕                                      
* iv⍳iv[7⍴5000000]  → 7.3E¯3 |  +609% ⎕⎕⎕                                      
* iv⍳iv[8⍴5000000]  → 8.4E¯3 |  +718% ⎕⎕⎕⎕                                     
* iv⍳iv[9⍴5000000]  → 9.3E¯3 |  +800% ⎕⎕⎕⎕                                     
* iv⍳iv[10⍴5000000] → 1.0E¯2 |  +909% ⎕⎕⎕⎕⎕                                    
* iv⍳iv[11⍴5000000] → 9.2E¯2 | +8784% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
* iv⍳iv[12⍴5000000] → 9.1E¯2 | +8757% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
* iv⍳iv[13⍴5000000] → 9.2E¯2 | +8818% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
* iv⍳iv[14⍴5000000] → 9.2E¯2 | +8821% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
* iv⍳iv[15⍴5000000] → 9.2E¯2 | +8806% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Can you spot where hashing kicks in? That’s right – when the subject array exceeds 10 elements. But what if my subject array is only ever a single element? Then you need to determine whether the one-time cost of building the hash table is less than the accumulated time of subsequent lookups. Once hashed, all lookups are faster.

One caveat about using the ]RunTime user command – the cost of creating the hash table on the first lookup of a hashed array is lost because ]RunTime executes each expression once before collecting timing information. ⎕PROFILE provides a more accurate picture:

     ∇ r←test_iv;iv;hiv;_;d;l;t;i
[1]    iv←10000000?2*24 ⍝ 10,000,000 integers in the range 1-2*24
[2]    hiv←1500⌶iv      ⍝ hiv is marked for hashing
[3]    i←5000000⊃iv     ⍝ search for the middle element
[4]   l1:⎕PROFILE¨'stop' 'clear' 'start'
[5]    _←iv⍳i  ⍝ unhashed lookup
[6]    _←hiv⍳i ⍝ first hashed lookup (creates hash table)
[7]    _←hiv⍳i ⍝ subsequent hashed lookup     
[8]   l2:⎕PROFILE'stop'
[9]    d←⎕PROFILE'data'
[10]   l←l1+⍳l2-l1+1 
[11]   r←(↓'%',⍨⍕⍪⌊0.5+100ׯ1+t÷⌊/t),(⎕NR⊃⎕SI)[1+l],⍨3⍕⍪t←d[;4]⌿⍨d[;2]∊l
[12]   ⎕PROFILE'clear'
     ∇

      test_iv
   1044%   1.047  _←iv⍳i  ⍝ unhashed lookup
 236125% 216.147  _←hiv⍳i ⍝ first hashed lookup (creates hash table) 
      0%   0.092  _←hiv⍳i ⍝ subsequent hashed lookup

In this case, the cost of creating the hash table is about 200× the cost of doing a single lookup. Subsequent hashed lookups are about 10× faster. It’s up to you, and your understanding of your application, to determine whether retaining the hash table is worth it.

TANSTAAFL (There Ain’t No Such Thing As A Free Lunch)

The other cost of using hash tables for faster searching is that hash tables take up space. Remember when I mentioned that the default hash table size in Dyalog v20.0 is 8x larger than previously? The working theory is that larger hash tables ought to result in faster searches, but how much faster and at what cost in space? Unfortunately there isn’t a direct way to measure the hash table size. You have to look at the differential in ⎕WA before and after creating the hash table:

      ]Config MAXWS
 MAXWS  1GB
       
      cf ⎕SIZE'Words' ⍝ cf is a utility to comma-format numbers
97,547,968

      cf ⎕WA-⍨(hWords⍳⊂'the')⊢(hWords←1500⌶Words)⊢⎕WA
268,435,664

In my 1GB workspace, the hash table for Words is 268MB and 2.75× the size of the Words itself. In Dyalog v20.0, we removed 8468⌶ which would allow you to set a scaling factor for the hash table size; there is an experimental I-Beam currently being developed, 8470⌶1 which does much the same thing. 8470⌶1 factor, where factor is an integer in the range ¯3 to 3, will increase or decrease the hash table size by 2*factor times. When Dyalog v20.0 was initially released, the default value for factor was 0 but based on feedback it’s now ¯3 Let’s use this to examine its effect on hash table size. I wrote an ugly little operator, set, to build hash tables with specified scaling factors and look at the ⎕WA differential after each:

      ]Config MAXWS
 MAXWS  10GB
      'abcdefg' ('Words'set) ¯4+⍳7
 aWords  ¯3       33,555,104 
 bWords  ¯2       67,109,536 
 cWords  ¯1      134,218,400 
 dWords   0      268,436,128 
 eWords   1      536,871,584 
 fWords   2    1,073,742,496 
 gWords   3    2,147,484,320

As expected, each hash table grows by a factor of 2.

Tangent #4 – Mapped Files

The ⎕MAP system function associates a mapped file with an array in the workspace. One of the client projects I’ve worked on involves loading CSV data with 47 million records of 85 fields, totalling about 7.5GB. Each field is stored in a separate ⎕MAP-compatible file. In a 4GB workspace, I’m able to map all 85 files and have it seemingly consume only a bit over 2MB of workspace:

      ]Config MAXWS
 MAXWS  4GB 

      ⍝ MapFiles maps 85 files into variables in a namespace named Data
      cf wa←⎕WA ⋄ MapFiles ⋄ cf wa-⎕WA 
4,284,076,808
2,009,600

      cf +/Data.(⎕SIZE ⎕NL ¯2)
7,577,998,192

Pretty neat huh? This makes 7.5GB of data available in a 4GB workspace!

One of the fields, Data.Record_ID, is a 16-column character matrix and has a size of about 760MB:

      ⍴Data.Record_ID
47647772 16
      cf ⎕SIZE 'Data.Record_ID'
762,364,392

Let’s bind ⍳ with Data.Record_ID:

      lFind←Data.Record_ID∘⍳     ⍝ create the bound function
      lFind 1↑Data.Record_ID     ⍝ create the hash table
WS FULL
      fRec 1↑Data.Record_ID
      ∧

Uh oh… It seems we don’t have enough room in a 4GB workspace for the hash table. Let’s start a new session with 10GB:

      ]Config MAXWS
 MAXWS  10GB 
      lFind←Data.Record_ID∘⍳
      cf ⎕WA-⍨(lFind 1↑Data.Record_ID)⊢⎕WA
8,589,934,752

With the Dyalog v20.0 default scaling factor, the hash table takes 8.5GB of my 10GB workspace. That’s a hefty chunk. What if we try the smallest scaling factor, ¯3?

      8470⌶1 ¯3
0
      sFind←Data.Record_ID∘⍳
      cf ⎕WA-⍨(sFind 1↑Data.Record_ID)⊢⎕WA
 1,073,741,984

That’s more manageable and would fit in my 4GB workspace. Why did I use a bound function rather than 1500⌶ on Data.Record_ID? Currently, 1500⌶ doesn’t work with mapped files, but this may be taken under consideration in the future.

      z←1500⌶Data.Record_ID
DOMAIN ERROR
      z←1500⌶Data.Record_ID
            ∧

Tangent #5 – What Timer Is It?

The ]runTime user command is a wonderfully easy tool to use to get a rough idea of performance and it remains a staple in my toolbox. runtime is based on cmpx which is found in the dfns workspace. I’ve found that runtime‘s results can sometimes vary significantly from one invocation to the next. Dyalog APL provides several system functions to help collect performance data:

  • ⎕AI, one of whose elements is cumulative CPU time of your session. You can use the before and after differential of ⎕AI to get an approximate idea of the speed of an expression. This is what runtime and cmpx use.
  • ⎕MONITOR, which can be used to turn monitoring on for specific lines of a function.
  • ⎕PROFILE, the “heavy hitter” of performance measurement. Even though its primary use case is profiling the performance of entire applications, I still find it useful to get impressive-looking, high-precision, performance data.

I have a template that I use when I want to use ⎕PROFILE to compare performance of expressions:

     ∇ r←timer n;i;d;l;t
[1]   ⍝ n is the number of iterations to run
[2]   ⍝ r is [;1] the relative percents based on the fastest expression
[3]   ⍝      [;2] the accumulated time in ms for the expression
[4]   ⍝      [;3] the expression
[5]    ⎕PROFILE¨'stop' 'clear' 'start'
[6]   l1: :For i :In ⍳n
[7]   ⍝ insert expressions to time between l1 and l2
[8]   l2: :EndFor
[9]    ⎕PROFILE'stop'
[10]   d←⎕PROFILE'data'
[11]   l←l1+⍳l2-l1+1
[12]   r←(↓'%',⍨⍕⍪⌊0.5+100ׯ1+t÷⌊/t),({⍵↓⍨+/∧\' '=⍵}¨(⎕NR⊃⎕SI)[1+l]),[1.1]⍨↓3⍕⍪t←d[;4]⌿⍨d[;2]∊l
[13]   ⎕PROFILE'clear'
     ∇

The Speed/Space Tradeoff

We saw earlier that different scaling factors result in different size hash tables, but what’s the impact on the speed of searching? Using our 7 hashed versions of Words and running 1,000,000 iterations:

 9%   547.303  _←aWords⍳phrase 
 6%   534.984  _←bWords⍳phrase 
 0%   504.180  _←cWords⍳phrase 
 0%   504.822  _←dWords⍳phrase 
 0%   505.082  _←eWords⍳phrase 
 0%   505.404  _←fWords⍳phrase 
 0%   504.561  _←gWords⍳phrase

In this example, the smallest hash table, aWords runs 9% slower than the 8-times-larger default, dWords. There’s no significant speedup using a hash table larger than cWords, at half the default size.

Let’s take a look at my 47-million record table. Since 1500⌶ doesn’t work (yet) with mapped files, we’ll have to use function binding. First, we’ll use the default setting of 8470⌶1 0 to create an 8.5GB hash table and then use 8470⌶1 ¯3 to create a hash table 1/8 (2*¯3) the default size or about 1GB.

      {}8470⌶1 0 ⋄ b←⎕WA ⋄ lfind←Data.Record_ID∘⍳ ⋄ {}lfind 2↑Data.Record_ID ⋄ cf b-⎕WA
  8,589,934,808
      {}8470⌶1 ¯3 ⋄ b←⎕WA ⋄ sfind←Data.Record_ID∘⍳ ⋄ {}sfind 2↑Data.Record_ID ⋄ cf b-⎕WA
  1,073,742,040
      recs←Data.Record_ID[10?≢Data.Record_ID;]
      timer 1e6
  0%    920.916  _←lfind recs 
 11%   1025.790  _←sfind recs

Is an 11% speedup worth an extra 7.5GB of workspace? That’s really up to you and your priorities for your application.

The Long and Winding Blog (with apologies to The Beatles)

Let’s try to summarize…

If your application needs to search data that’s “mostly” static, you can benefit from using retained hash tables. By “mostly”, I mean that the only changes to the array are adding or deleting elements from the end. A typical scenario might be, during application initialization, load the data into the workspace, or map a file, and do a search, thereby creating the hash table. Then all subsequent uses of search functions on that array will be considerably faster.

I’ve got some ideas on things that we at Dyalog Ltd might want to consider doing. Most of these involve empowering the user to have more control over how and when hashing is done. For example, we could:

  • make 8470⌶1 ready for release and publish it so that users can understand how to tune hash table size for their best space/speed tradeoff.
  • make 1500⌶ work with mapped files.
  • make it easier to query the size of a hash table rather than relying on ⎕WA differentials.
  • make it possible to mark an array as “unhashable”. Consider the scenario where hash-table-triggering searches are done on an array that’s not static. Whenever the array changes, the hash table is discarded, only for a new hash table to be generated on a subsequent search. In this case, it’s probably better that the interpreter fall back to a non-hashing approach.
  • Make it possible to monitor where, when, and how often extemporaneous hashing is done.

Disclaimers – YMMV (Your Mileage May Vary)

The examples shown in this post are a very small sampling of possible hashing scenarios. They were run on my 32GB Lenovo laptop using Windows 11 and Dyalog v20.0. Your environment and hashing opportunities are likely to be different. In writing this post, I hope to have accomplished spurring you on to do your own investigations as there are potentially significant benefits to be explored.

I was caught off guard by the apparent slowdown due to the interpreter repeatedly hashing Words extemporaneously. This led me to try to understand how and when hashing is done and what tools are available to the user. I feel I’ve been marginally successful at this, but it feels like there is still much to learn.

Addendum

I wrote the above in January 2026. Sharing my findings with the Dyalog development team set in motion an initiative to review some aspects of doing lookups. One result of this initiative was to change the default scaling factor for hash table size (8470⌶1 x) from 0 to ¯3. This means that, by default, hash tables in the latest releases of Dyalog v20.0 are 1/8 the size that they were before. Changing to a smaller hash table scaling factor results in slightly slower lookups, but at a significant savings in workspace consumed.

Other work looking at the performance of lookup functions is being undertaken.

Lookups are Complicated

When you use a lookup function like ⍳ or ∊, the interpreter attempts to pick the best technique, in order from simplest to most complex, between doing a linear search, using a lookup table, or using a hash table. The decision is based on datatype, size, and depth of the arguments, workspace available, and whether the cost of doing the setup of a more complex technique is likely to result in faster overall execution. In general, the interpreter does a good job of deciding. That doesn’t mean there aren’t exceptions. Again, this is where you come in – you know your data and how it’s used.

Email, RSS Follow

Mind Boggling Performance

Posted on by

Or is it Minding Boggle Performance?

Better late than never? This was a blog post I started to write during COVID-19 and now I’ve finally gotten around to finishing it.

In the 2019 APL Problem Solving Competition, we presented a problem to solve the Boggle game . In Boggle, 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.

Rich Park’s webinar from 17 October 2019 presents, among other things, a very good discussion and comparison of two interesting solutions submitted by Rasmus Précenth and Torsten Grust. As part of that discussion, Rich explores the performance of their solutions. After seeing that webinar, I was curious about how my solution might perform.

Disclaimer

Please take note that performance was not mentioned as one of the criteria for this problem other than the implicit expectation that code completes in a reasonable amount of time. As such, this post is in no way intended to criticize anyone’s solutions – in fact, in many cases I’m impressed by the elegance of the solutions and their application of array-oriented thinking. I have no doubt that had we made performance a primary judging criterion, people would have taken it into consideration and possibly produced somewhat different code.

Goals

I started writing APL in 1975 at the age of 14 and “grew up” in the days of mainframe APL when CPU cycles and memory were precious commodities. This made me develop an eye towards writing efficient code. In developing my solution and writing this post, I had a few goals in mind:

  • 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.
  • Illustrate some approaches to optimization that may be generally applicable.
  • 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:

      found←words FindWords board

where:

  • words is a vector of words. We used Collins Scrabble Words, a ≈280,000-word word list used by tournament Scrabble™ players. We store this in a variable called AllWords. Note that single letter words like “a” and “I” are not legitimate Scrabble words.
  • board is a matrix where each cell contains one or more letters. A standard Boggle board is 4×4.
  • the result, found is a vector that is a subset of words containing the words that can be made from board without revisiting any cells.

Although the actual Boggle game uses only words of 3 letters or more, for this problem we permit words of 2 or more letters.

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

     AllWords FindWords ⎕← b2← 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:

      b4← 4 4⍴ 't' 'p' 'qu' 'a' 's' 'l' 'g' 'i' 'r' 'u' 't' 'e' 'i' 'i' 'n' 'a' ⍝ 4×4 board
      b6← 6 6⍴'jbcdcmvueglxriybgeiganuylvonxkfeoqld' ⍝ 6×6 board

If you’re using Dyalog v20.0 or later, you can represent this using array notation:

⍝ using array notation with single-line input:
      b4←['t' 'p' 'qu' 'a' ⋄ 's' 'l' 'g' 'i' ⋄ 'r' 'u' 't' 'e' ⋄ 'i' 'i' 'n' 'a']
      b6←['jbcdcm' ⋄ 'vueglx' ⋄ 'riybge' ⋄ 'iganuy' ⋄ 'lvonxk' ⋄ 'feoqld']

⍝ or, using array notation with multi-line input:
      b4←['t' 'p' 'qu' 'a'
          'slgi'
          'rute'
          'iina']

      b6←['jbcdcm'
          'vueglx'
          'riybge'
          'iganuy'
          'lvonxk'
          'feoqld']

The representation does not affect the performance or the result:

      b4 b6
┌──────────┬──────┐
│┌─┬─┬──┬─┐│jbcdcm│
││t│p│qu│a││vueglx│
│├─┼─┼──┼─┤│riybge│
││s│l│g │i││iganuy│
│├─┼─┼──┼─┤│lvonxk│
││r│u│t │e││feoqld│
│├─┼─┼──┼─┤│      │
││i│i│n │a││      │
│└─┴─┴──┴─┘│      │
└──────────┴──────┘

There were 9 correct solutions submitted for this problem. We’ll call them f1 through f9 – my solution is f0. Now let’s run some comparative timings using cmpx from the dfns workspace. cmpx will note whether the result of any of the latter expressions returns a different result from the first expression. We take the tally (≢) of the resulting word lists to make sure the expressions all return the same result. We assume that the sets of words are the same if the counts are the same. These timings were done using Dyalog v20.0 with a maximum workspace (MAXWS) of 1GB running under Windows 11 Pro. To keep the expressions brief I bound AllWords as the left argument to each of the solution functions:

      f0←≢AllWords∘#.Brian.Problems.FindWords

To make it easier to run timings, I wrote a simple function to call cmpx with the solutions of my choosing (the default is all solutions).

      )copy dfns cmpx
      time←{⍺←¯1+⍳10 ⋄ cmpx('f',⍕,' ',⍵⍨)¨⍺}

This allows me to compare any 2 or more solutions, or by default, all solutions on a given board variable name.

      time 'b4' ⍝ try a "standard" 4×4 Boggle board
  f0 b4 → 1.2E¯2 |      0%
  f1 b4 → 2.3E¯1 |  +1791% ⎕⎕
  f2 b4 → 4.3E¯1 |  +3491% ⎕⎕⎕
  f3 b4 → 7.3E¯1 |  +5941% ⎕⎕⎕⎕⎕                                    
  f4 b4 → 5.6E0  | +46600% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
  f5 b4 → 1.1E0  |  +8758% ⎕⎕⎕⎕⎕⎕⎕⎕                                 
  f6 b4 → 8.9E¯1 |  +7325% ⎕⎕⎕⎕⎕⎕                                   
  f7 b4 → 1.1E0  |  +9275% ⎕⎕⎕⎕⎕⎕⎕⎕                                 
  f8 b4 → 4.2E0  | +34750% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕           
  f9 b4 → 2.0E0  | +16291% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

If we try to run on the 6×6 sample

      0 1 2 3 4 5 6 7 9 time'b6'
  f0 b6 → 2.2E¯2 |       0%                                          
  f1 b6 → 3.7E¯1 |   +1577%                                          
  f2 b6 → 1.0E0  |   +4581%                                          
  f3 b6 → 1.5E0  |   +6872%                                          
  f4 b6 → 1.6E2  | +705950% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
  f5 b6 → 2.3E0  |  +10409% ⎕                                        
  f6 b6 → 1.9E0  |   +8463%                                          
  f7 b6 → 2.0E0  |   +9131% ⎕
  f9 b6 → 2.4E0  |  +10822% ⎕

f8 is excluded as it would cause a WS FULL in my 1GB workspace.

Why is f0 about 16-18 times faster than the next fastest solution, f1? I didn’t set out to make FindWords fast, it just turned out that way. Let’s take a look at the code…

     ∇ r←words FindWords 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
     ∇

Attacking the Problem

Intuitively, this felt like an iterative problem. A mostly-array-oriented solution might be to generate character vectors made up from the contents of all paths in board and then do a set intersection with words. But that would be horrifically inefficient – there are over 12-million paths in a 4×4 matrix and, in the case of b4, there are only 188 valid words. What about a recursive solution (many of the submissions used recursion)? I tend to avoid recursion unless there are clear advantages to using it, and in this case I didn’t see any advantages, clear or otherwise. So, iteration it was…

I decided to use two parallel structures to keep track of progress:

  • paths – the paths traversed through the board
  • stubs – the word “stubs” built from the contents of the cells in paths

paths is initialized to the indices of the board, and stubs is initialized to the contents of each cell. Then iterate:

  1. Keep any stubs that are in words
  2. Append the contents of each candidate’s unvisited neighboring cells to the candidates, resulting in a new candidates list
  3. Repeat until there’s nothing left to look at

Setup

First, I need to find the adjacent cells for each cell in board.

[1]    inds←⍳⍴board                                      ⍝ board indices
[2]    neighbors←(,inds)∘∩¨↓inds∘.+(,¯2+⍳3 3)~⊂0 0       ⍝ matrix of neighbors for each cell

You might recognize line [2] as a stencil-like (⌺) operation. Why, then, didn’t I use stencil? To be honest, it didn’t occur to me at the time – I knew how to code what I needed without using stencil. As it turns out, for this application, stencil is slower. The stencil expression is shorter, more “elegant”, and possibly more readable (assuming you know how stencil works), but it takes more than twice the time. Granted, this line only runs once per invocation so the performance improvement from not using it is minimal.

      inds←⍳4 4
      ]RunTime -c '(,inds)∘∩¨↓inds∘.+(,¯2+⍳3 3)~⊂0 0' '{⊂(,⍺↓⍵)~(⍵[2;2])}⌺3 3⊢inds'
                                                                                              
  (,inds)∘∩¨↓inds∘.+(,¯2+⍳3 3)~⊂0 0 → 2.2E¯5 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕                       
  {⊂(,⍺↓⍵)~(⍵[2;2])}⌺3 3⊢inds       → 5.0E¯5 | +127% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

I wrote a helper function nextcells which, given a path, returns the unvisited cells adjacent to the last cell in the path. For example, if we have a path that starts at board[1;1] and continues to board[2;2], then the next unvisited cells for this path are given by:

      nextcells (1 1)(2 2)
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│
││1 2│││1 3│││2 1│││2 3│││3 1│││3 2│││3 3││
│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┘

A contributor to improved performance is set up next. I created a parallel transposed matrix copy of words.

[6]    mwords←⍉↑words ⍝ matrix of candidate words, use a columnar matrix for faster ∧.=

Why create another version of words and why is it transposed?

  • In general, it’s faster to operate on simple arrays.
  • Simple arrays – arrays containing only flat, primitive, data without any nested elements – are stored in a single, contiguous, block of memory. Elements are laid out contiguously in row-major order, meaning the last dimension changes fastest. For a 2D matrix, it stores the first row left-to-right, then the second row, and so on. Transposing the word matrix makes prefix searching as we look for candidates that could become valid words much more efficient. Consider a matrix consisting of the words “THE” “BIG” “DOG”. If stored one word per row, the interpreter has to “skip” to find the first letter in each word. However, in a column-oriented matrix the first letters are next to one another and likely to be in cache, making them much quicker to access.

Things Run Faster If You Do Less Work

Smaller searches are generally faster than larger ones. If we pare down words and stubs as we progress, we will perform smaller searches. The first pass at minimizing the data to be searched is done during setup – we remove any words that don’t begin with a first letter of any of board‘s cells as well as words that contain letters not found in board:

[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

For board b4, this reduces the number of words to be searched from 267,752 to 16,247 – a ~94% reduction. Then we iterate, appending each path’s next unvisited cells and creating new stubs from the updated paths:

[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

Append any stubs that are in words to the result:

[16]       r,←words∩stubs                                ⍝ add any matching words

Because a cell can have more than one letter, we might have stubs of different lengths, so we need to iterate over each unique length:

[19]       lens←≢¨stubs           ⍝ length of each stub
[20]       :For n :In ∪lens       ⍝ for each unique stub length

Because we’re doing prefix searching, the inner product ∧.= can tell us which stubs match prefixes of which words. Now we can see the reason for creating mwords. Since the data in mwords is stored in “raveled” format, n↑mwords quickly returns a matrix of all n-length prefixes of words:

[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

We then use our two Boolean arrays, found and mask, to pare down paths/stubs and words/mwords respectively. If we look at the number of words and stubs at each step, we can see that the biggest performance gain is realized by doing less work:

┌──────────────────┬───────┬──────┐
│Phase             │≢words │≢stubs│
├──────────────────┼───────┼──────┤
│Initial List      │267,752│     0│
├──────────────────┼───────┼──────┤
│After Initial Cull│ 16,247│    16│
├──────────────────┼───────┼──────┤
│After 2-cell Cull │  7,997│    56│
├──────────────────┼───────┼──────┤
│After 3-cell Cull │  2,736│   152│
├──────────────────┼───────┼──────┤
│After 4-cell Cull │  1,159│   178│
├──────────────────┼───────┼──────┤
│After 5-cell Cull │    371│   119│
├──────────────────┼───────┼──────┤
│After 6-cell Cull │     87│    42│
├──────────────────┼───────┼──────┤
│After 7-cell Cull │     16│    10│
├──────────────────┼───────┼──────┤
│After 8-cell Cull │      2│     1│
├──────────────────┼───────┼──────┤
│All Done          │      0│     0│
└──────────────────┴───────┴──────┘

Does mwords Make Much of a Difference?

As an experiment, I decided to write a version, f10, that does not used transposed word matrix mwords (it still does the words and stubs culling). I compared it to my original version,f0, and the fastest submitted version, f1:

      0 1 10 time 'b4'
  f0  b4 → 1.4E¯2 |     0% ⎕⎕                                       
  f1  b4 → 2.2E¯1 | +1551% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  f10 b4 → 2.1E¯1 | +1422% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Interestingly, f10 performed remarkably close to f1. When I looked at the code for f1, I saw that the author had implemented a similar culling approach and had commented in several places that the construct was to improve performance. Good job! But this does demonstrate that maintaining a parallel, simple, copy of words makes the solution run about 15× faster.

Takeaways

There are a couple of other optimizations I could have implemented:

  • In the setup, I could have filtered out all words that were longer than ≢∊board.
  • If this FindWords was used a lot, and I could be fairly certain that words was static (unchanging), then I could create mwords outside of FindWords. The line that creates mwords consumes about half of total time of the function.

When thinking about performance and optimization:

  • Unless there’s an overwhelming reason to do so – don’t sacrifice code clarity for performance. If you implement non-obvious performance improvements, note them in comments or documentation.
  • Optimize effectively – infinitely speeding up a piece of code that contributes 1% to an application’s CPU consumption makes no real impact.
  • Consider how your data is structured and how that might affect performance. In this case, representing words as a vector of words is convenient, readable, and there aren’t those extra spaces that might occur in a matrix format. But as we saw, it performs poorly compared to a simple matrix format. Don’t be afraid to make the data conform to a more performant organization.
  • Along similar lines, consider how simple arrays are stored in contiguous memory and whether you can take advantage of that.

In case you were wondering, the two solutions Rich Park looked at in his webinar were f4 and f7 in the timings above. The fastest submission, f1, was submitted by Julian Witte. Please remember that we did not specify performance as a criterion for the problem, so this is in no way a criticism of any of the submissions.

If you’re curious to look at the code for the submissions, this .zip file includes namespaces f0–f9, each of which contains a FindWords function and any needed subordinate functions (in addition to the solution namespaces, the .zip file also includes AllWords, the time function and 4 sample boards – b2,b3,b4, and b6). You can extract and use the code as follows:

  1. Unzip Submissions.zip to a directory of your choosing.
  2. In your APL session, enter:
    ]Link.Import # {the directory you chose}/Submissions
    This step might take several seconds when Link.Import brings in AllWords

You can then examine the code, run your own timings, and so on. One interesting thing to explore is which submissions properly handle 1×1 and 0×0 boards.

Postscript

When I started to write the explanation of my code, it occurred to me: “This is 2026 and we have LLMs that might be able to explain the code. Let’s give them a try…”

So, I asked each of Anthropic’s Claude Opus 4.6 Extended, Google’s Gemini Pro, and Microsoft’s Copilot Think Deeper the following:

Explain the attached code. Note that a cell in board can have multiple letters like “qu” or “ough”. Also note that the words list is the official scrabble words list and has no single letter words.

The results were interesting and, in several places, a more concise and coherent explanation than I might produce. But how accurate and useful were their explanations? Stay tuned for a blog post about how well different LLMs explain APL code!

Email, RSS Follow

Hacking with APL

Posted on by
Vassar Hackathon Poster

Vassar Hackathon Poster

Thanks to our dear friend Dr. Ray Polivka, Dan Baronet and I had the opportunity to travel to Vassar College to participate in their Community Hackathon held on 5-6 February 2016.

“What’s a hackathon?” you ask?
Well, we did too, as we’d never participated in one before.  🙂
According to the Hackathon’s announcement:

“CommunityHack is a way to bridge the gap between Vassar CS Majors and Vassar students in other departments as well as local high school and community college students in order to provide them with the opportunity to explore innovative applications of Computer Science. Dance, music, art, video games? CS can be incorporated into all of that and more!”

StuCommunityHack_Sponsorsdents from Vassar as well as nearby colleges and high schools were invited to attend. In other words, it was a great opportunity to introduce APL to a new generation.  As this was our first Hackathon, we had no idea what to expect.  Laura, the Hackathon’s organizer, did a wonderful job organizing the event and making us feel welcome. We were invited to give an hour long presentation and Dyalog was listed as an event sponsor.

The Hackathon was a 24 hour event where students were encouraged to split up into groups and pick a problem to solve.  During the course of the event, presentations were made on a variety of subjects including “Autonomous Robots Test Ideas About the Evolution of Brains”, “How to make games quick!”, “Virtual Reality”, and of course “Hacking with APL”. Friday evening started with introductions and ice-breakers. During our introduction, I was able to talk a bit about APL and the presentation we would be making on Saturday. Apparently this generated some interest as a number of students came up to Dan, Ray, Jon McGrew and me to ask about APL. We spent several hours showing them APL, to which they seemed eagerly receptive.

I had the pleasure of working with Grace, a CS sophomore, to implement APL (A Puppy Language) in APL. Her project idea was to write an application for potential puppy owners to use so they could get an idea of the responsibility of owning and caring for a puppy. We worked into the wee hours of the night and wound up implementing a multi-threaded domain-specific-language (DSL) where the “puppy”, running in a separate thread, would react to commands typed into the APL session. Negative actions and ignoring the puppy would cause the the puppy’s happiness points (PHPs) to decrease whereas positive actions would increase PHPs.   Grace seemed to really enjoy working with APL and returned to the hackathon twice on Saturday as her schedule permitted to continue work on her project.

Saturday, I was slightly concerned that following a talk on virtual reality, APL might not seem all that “cool”, but my fears were allayed for, as I was waiting before my presentation, several students asked the person at the registration desk specifically about the APL presentation.

HackingWithAPL

The presentation went rather well.  Watching the jaw-dropping “Wow!” expressions on the faces of many of the students as we showed the power of APL notation made me reminisce back to the time when I first learned APL and was amazed at what I could do with a computer.  It also reminded me how blessed I’ve been to have used APL throughout my career.

Our participation in the Hackathon was a great experience. We were able to show Dyalog to close to 100 students, promote the upcoming APL Problem Solving Competition, and encourage people to download and try Dyalog – we had 18 student downloads over the Hackathon weekend. This may have been our first Hackathon, but I’m certain it won’t be our last.

On a personal note, after Dan and I drove up to Montreal to spend the upcoming week working with the APL Tools Team, I received a very nice email from Grace where she wrote “I just wanted to thank you so much for taking the time to work with me on puppy.dws — it is currently my favorite thing that I have ever made.” and “It was really fun working in APL, and I will definitely check out the Dyalog competition.”

HackingWithAPL3

 

Email, RSS Follow

Solving the 2014 APL Problem Solving Competition – How Tweet It Is

Posted on by

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition.

The problems presented in Phase 1 of the competition were selected because they could be solved succinctly, generally in a single line of APL code. This makes them well suited for experimentation on TryAPL.org.

Problem 2 of Phase 1, entitled “How tweet it is” reads

“Twitter messages have a 140 character limit – what if the limit was even shorter? One way to shorten the message yet retain most readability is to remove interior vowels from its words. Write a dfn which takes a character vector and removes the interior vowels from each word.”

Test cases:
      {your_solution} 'if you can read this, it worked!'
if yu cn rd ths, it wrkd!
      {your_solution} 'APL is REALLY cool'
APL is RLLY cl
      {your_solution} '' ⍝ an empty vector argument should return an empty vector

      {your_solution} 'a' ⍝ your solution should work with a single character message
a

We’ll examine a couple of approaches to this problem – one that’s more “traditional APL” code, and another that makes use of a really helpful Dyalog feature.

This problem could be restated as “find and remove the vowels that aren’t at the beginning or end of a word”. To start with, we need to determine where the words are and where the vowels are. A word is a contiguous set of letters; multiple words are separated by spaces or punctuation. For simplicity’s sake, we’ll ignore contractions and possessives.

The “Traditional APL” Approach

This approach employs a technique that is not commonly found outside of APL and its brethren – using a Boolean vector to determine which elements to remove or keep. First, let’s find where all the vowels are:

      string←'If you can read this, it worked!'
      vowels←{⍵∊'aeiouAEIOU'}
      vowels string
1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0

To help illustrate what’s happening, I’ll write a little operator called “show” to compactly display the string, the Boolean vector, and the elements that would be selected by applying the Boolean to the string.

      show←{⍵⍪⍵{↑(1 0⍕ ⍵)(⍵\⍵/⍺)}⍺⍺ ⍵}
      vowels show string
If you can read this, it worked!
10001100100011000010001000100100
I   ou  a   ea    i   i   o  e

Next we want to remove vowels that aren’t at either end of a word. First, find where the words are by finding where the letters are.  There are several ways to do this; the most obvious may be to use a character vector constant:

      letters←{⍵∊'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'}

Long character constants seem a bit awkward to me.  So, another technique uses the Unicode Conversion system function to return the 26 characters starting at the code points for each of ‘a’ and ‘A’:

      letters←{⍵∊⎕UCS (⍳26)∘.+¯1+⎕UCS'aA'}

Yet another way might be to use the code point values directly and do numerical operations:

      letters←{{((⍵≥65)∧⍵≤90)∨(⍵≥97)∧⍵≤122}⎕UCS ⍵}

Which technique you choose is largely a matter of taste and style. All three return the same result and have comparable performance. My personal preference is the second one – it has fewer characters for me to mistype 🙂

      letters show string
If you can read this, it worked!
11011101110111101111001101111110
If you can read this  it worked

So now let’s mark the interior letters of the words. This employs a technique known as shift and compare that I learned in the early 1980s when I was privileged to work with Bob Smith. Among Bob’s many contributions to the APL world was a book on Boolean Functions and Techniques. To mark the interior letters, we’ll do both a right and left shift:

      interior←{⍵∧(¯1↓0,⍵)∧1↓⍵,0}
      {interior letters ⍵} show string
If you can read this, it worked!
00001000100011000110000000111100
    o   a   ea   hi       orke

The last step is to find interior vowels and negate:

      {(vowels ⍵)∧interior letters ⍵} show string
If you can read this, it worked!
00001000100011000010000000100100
    o   a   ea    i       o  e  

      {(vowels ⍵)⍲interior letters ⍵} show string
If you can read this, it worked!
11110111011100111101111111011011
If y u c n r  d th s, it w rk d!

Putting it all together…

      tweet←{⍵/⍨~(⍵∊'aeiouAEIOU')∧{(1↓⍵,0)∧¯1↓0,⍵}⍵∊⎕UCS(⍳26)∘.+¯1+⎕UCS'aA'}
      tweet string
If yu cn rd ths, it wrkd!

The Other Technique – Using Regular Expressions

In version 13.0, Dyalog introduced the system functions ⎕S and ⎕R as interfaces to the PCRE (Perl Compatible Regular Expression) library. Like APL, regular expressions may seem a bit alien at first, but in the years since their incorporation into Dyalog, I’ve grown to appreciate their power and flexibility – they can frequently accomplish complex string manipulations more succinctly than their APL equivalents thus furthering Dyalog’s power as a tool of thought, notation and execution.

      tweet←{('\B[AEIOU]\B' ⎕R '' ⍠ 1) ⍵}
      tweet string
If yu cn rd ths, it wrkd!

The expression above replaces any vowel (⍠ 1means case-insensitive) that is not at the beginning or end of a word with the empty vector, effectively removing the interior vowels. A blog post is not enough space to give an adequate overview of regular expressions. But I hope the expression above piques your interest and encourages you to experiment with ⎕S and ⎕R on TryAPL.org or with a Dyalog system of your own.

Email, RSS Follow

Simply A-maze-ing

Posted on by

maze

One of many things I like about APL is that it’s fun to use for recreational computing. I will frequently happen upon an interesting problem, puzzle, or piece of code and consider how I might implement it in APL.

I was thinking about how to generate mazes for an idea I have about a game to help kids learn APL (that may be a topic for a future blog entry). Anyhow, I found an interesting web page about maze generating algorithms where the author found one, the “Growing Tree Algorithm“, to be of particular interest. His page included roughly 100 lines Ruby code to implement the algorithm. The algorithm can be boiled down to:

  • Seed a list of visited cells with a cell selected at random
  • While there are unvisited cells
    • If the current cell has any unvisited neighboring cells
      • Select one at random
      • Remove the wall between the cells
      • Add the new cell to the list of visited cells
    • Otherwise backtrack (drop from the visited cell list) until you find a cell with an unvisited neighbor

Here’s a clip of the algorithm implemented in APL building a 10×10 maze.
Notice how whenever it hits a “dead end” it backtracks to the last cell that hasn’t been visited.

What might an APL approach to this algorithm look like? How to represent the maze? My first thought was to separate the maze generation from the drawing. After an hour (or so 😉 ) of tinkering, I’d come up with something that seemed to work pretty well and took about a dozen lines of code.

When I originally thought about writing this blog entry, I was going to launch into a discussion of the code and I realized that it might get lengthy and (egad!) boring. So instead, I’ll highlight a couple of the clever bits, show you the core maze generation code, and point you at the complete namespace for your own amusement and experimentation.

First the clever bits (at least I hope they’re clever)…

  • Represent the cells of the maze as an integer matrix where each element is an encoding of the walls surrounding each cell.  Use powers of 2 for the encoding.
  • Precalculate the indices of the neighboring cells around each cell so the core loop only has to use indexing and no on-the-fly computation.
  • Write a function to remove the common wall between two cells. I originally named the function “Reagan” (after President Reagan’s 1987 exhortation “Mr. Gorbachev, tear down this wall”), but in the spirit of political mindfulness, I renamed it “dewall”.

The core code for the maze generation looks like this:

∇ cells←maze size;valid;neighbors;dewall;visited;current;n;choices;next
 ⍝ Maze - modeled from http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
 ⍝ BPB  - Dec2014
 ⍝ size  - size of the maze in rows/cols
 ⍝ cells   - (2⍴size) integer matrix describing the walls around each cell using powers of 2
 ⍝       1
 ⍝     ┌───┐         ┌───┐
 ⍝   8 │   │ 2       │   │ = 11 = 1 + 2 + 8
 ⍝     └───┘
 ⍝       4
  size←2⍴size  ⍝ set size to square if singleton supplied as argument     

  valid←{{⍵/⍨⍵≢¨⊂⍬}size∘{(0∊⍵)⍱⍵∨.>⍺:⍵ ⋄ ⍬}¨⍵} ⍝ determine if a maze coordinate is valid
  neighbors←valid¨↓(⍳size)∘.+,1 ¯1∘.×1 0⌽¨⊂1 0 ⍝ calculate neighbors for each cell
     
  dewall←{{⍵[2]=0:{(1=⍵)⌽4 1}⍵[1] ⋄ {(1=⍵)⌽2 8}⍵[2]}⍺-⍵}  ⍝ remove wall between cells
     
  cells←size⍴15 ⍝ all cells start with 4 walls
     
  visited←,⊂?size ⍝ random starting cell
     
  :While 15∊cells       ⍝ while we still have cells to examine
      current←1↑visited   ⍝ pop the most recent cell
      :If 0=n←⍴choices←cells{⍵/⍨15=⍺[⍵]}current⊃neighbors ⍝ does it have any unvisited neighbors?
          visited↓⍨←1       ⍝ if none, backtrack
      :Else
          visited,⍨←next←choices[?n] ⍝ otherwise, add the new cell to the front of the list
          cells[next current]-←⊃next⊃.dewall current ⍝ update cell values for which wall was removed
      :EndIf
  :EndWhile
∇

You can get all the code in my maze generating namespace from GitHub. Save a local copy and use the SALT Load command to load it into your workspace, or just cut and paste it into your own namespace script with the editor. The maze namespace contains the following functions of interest:

 

      intmat←{animate} maze size
  • animate is an optional Boolean to indicate whether to animate the maze generation
  • size is the size (rows,cols) of the maze to generate; a single number generates a square maze
  • intmat is the integer matrix representation of the maze

For example: mat←1 maze 10 animates and generates a 10×10 maze

 

      z←{line} draw intmat
  • line is an optional Boolean that indicates:
    • 1 = use line-drawing characters
    • 0 = use ASCII characters
  • intmat is an integer matrix representation of a maze
  • z is the drawing of the maze in ASCII or line-drawing characters

For example: pic←1 draw mat produces a line-drawing of the maze generated in the example above

 

      z←html intmat
  • intmat is an integer matrix representation of a maze
  • z is the HTML necessary to render the maze in a web browser. Save it to a native file and open the file in your browser.

For example: h←html mat produces an HTML representation of the maze generated in the example above

 

Email, RSS Follow

Solving the 2014 APL Problem Solving Competition – It’s All Right

Posted on by

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition.

The problems presented in Phase 1 of the competition were selected because they could be solved succinctly, generally in a single line of APL code. This makes them well suited for experimentation on TryAPL.org.

pythProblem 1 of Phase 1, entitled “It’s all right” reads,

“Write a dfn that takes the length of the legs of a triangle as its left argument, and the length of the hypotenuse as its right argument and returns 1 if the triangle is a right triangle, 0 otherwise.”

Test cases:
      3 4 {your_solution} 5
1
      2 3 {your_solution} 4
0

This uses the Pythagorean theorem – A² + B² = C². It’s trivial to implement an almost direct translation of this in APL – in a dfn, using ⍺[1] for A, ⍺[2] for B and ⍵ for C yields:

right←{((⍺[1]*2)+(⍺[2]*2))=⍵*2}

This seems rather clunky though… what if we consider the problem as “Are the sums of the squares of each argument equal?” To get the sum of the squares, first we can use the composition *∘2 (composing the power function * with the constant 2) to mean “square” and +/ to mean “sum”, and combine them in a 2-item function train (also known as an “atop”): ((+/)*∘2)

then apply this to each argument:   ((+/)*∘2)¨⍺ ⍵

and compare the results for equality, resulting in the dfn:

right1←{=/((+/)*∘2)¨⍺ ⍵}

Still this seems clunky to me. Let’s see…squaring a number is just multiplying the number by itself, so, if we use the monadic commute operator with multiplication,   ×⍨
we get the equivalent of squaring. Then we can use that function in an inner product with addition to also get “sum of the squares”:   +.×⍨

The rest is essentially the same as in right1 above:

right2←{=/+.×⍨¨⍺ ⍵}

All three of these solutions solve the contest problem. The first one, right, is not commutative though – the legs of the triangle must be supplied as the left argument. However, right1 and right2 are commutative and the order of arguments is not significant.

Email, RSS Follow