Speed versus Accuracy: the User’s Choice

At Dyalog we have long striven for both correctness and high performance in our implementation. However, our views on this matter have recently undergone an historic shift in paradigm which we are excited to share with our users. We now intend to provide the best experience to the user of Dyalog APL not by providing correctness and speed, but rather correctness or speed, with a user-specified tradeoff between the two.

The upcoming release of version 17.1 includes a powerful new feature: the correctness–performance slider. To find this option, select Options>Configure>General in the IDE, or Edit>Preferences>General in RIDE. The slider is labelled “Execution Properties” and may be set at any time, although users should note that the effective correctness may be reduced if this is done while an in-progress function is on the stack.

With the slider at its default position near the middle, Dyalog will make an effort to balance performance and correctness. Computations will proceed at a reasonably brisk pace, and slightly wrong answers will appear occasionally while very wrong ones come up only rarely. As the slider is moved to the left, correctness is increased at the expense of performance. You’ll have to wait for your results but when you get them they’ll be numbers you can trust. Moving the slider to the right will have the opposite effect, increasing speed at the expense of more frequent misparsings and significant floating point error. Perfect for startups!

Motivation

The seasoned programmer has most likely experienced the same issues as us, and may already be rushing to incorporate our ideas in his or her own code. In the interest of transparency, however, we wish to explain a bit further our experiences with the speed-correctness tradeoff.

Most often we encounter this tradeoff in one direction: when writing to improve the performance of a particular interpreter operation we sometimes find the results returned are different. In the past such cases were seen as bugs to be corrected, but we now understand them to simply be instances of a universal rule. Conversely, fixes for obscure parsing issues which slow down parsing of equally obscure but already correct cases are no longer cause for concern: we simply condition them on the appropriate slider threshold.

In the graph below we plot the accuracy and performance of several algorithms to compute the inner product !.○ on two large array arguments. Performance is measured in throughput (GB/s) while accuracy is defined to be the cosine similarity of the returned solution relative to a very precise result worked out with paper and pencil.

On plotting these results the nature of our plight became clear, and we added the performance-correctness slider to Dyalog version 17.1 as fast as possible. This post was written as accompaniment, with similar haste.

Results

We profiled a large sample program with many different execution settings and obtained the results shown below. As you can see, Dyalog can be quite stable, or quite fast, depending on how the performance-correctness slider is set.

We believe these results demonstrate excellent value for all of our clients. Large and conscientious businesses can set the slider to correctness to encounter very few errors in execution. Rest assured, if errors are reported with these settings, we will do our best to shift them to the right side of the performance-correctness continuum! In contrast, the APL thrill-seeker will find much to like at the speedy end of the spectrum, as more frequent crashes are compounded by an interpreter that gets to them faster.

Future extensions

Although we believe the provided options will satisfy most users, some tasks require an implementation so fast, or so correct, that Dyalog cannot currently offer satisfactory performance along the relevant axis. To rectify this in the future we intend to offer more powerful facilities which extend the extremes of the correctness-performance slider. Potential clients who are exceptionally interested in correctness, such as NASA and Airbus, should contact us about an interpreter which runs multiple algorithms for each operation and chooses the majority result. For users interested in speed above all else we propose to offer an interpreter which only computes a part of its result and leaves the rest uninitialised, thus obtaining for example a 50% correct result in only half the time.

Even more extreme tradeoffs are possible. For the most correct results we are considering an algorithm which adds the desired computation to Wikipedia’s “List of unsolved problems in mathematics”, and then scans mathematical journals until a result with proof is obtained. For extremely fast responses we propose to train a shallow neural network on APL sessions so that it can, without interpreting any APL, print something that basically looks like it could be the right answer. Such an option would be a useful and efficient tool for programmers who cannot use APL, but insist on doing so anyway.

Although our plans for the future may be much grander, we’re quite excited to be the first language to offer user-selectable implementation tradeoffs at all. We’re sure you’ll be happy with either the correctness or the performance of Dyalog 17.1!

Welcome Richard Park

Richard Park is the latest addition to the Dyalog team and is based at Dyalog HQ in the UK. Richard has been living in the same house in Bramley his entire life and recently returned to the village after one successful degree in physics at the University of Manchester, and one unsuccessful degree in education at Manchester Metropolitan University.

How Richard and Dyalog came to meet is a story that deserves to be told, albeit a bit embarrassing for poor Richard!

One day, while walking his dog and father, Richard rang the office doorbell to inquire about any software-related opportunities that might be available. He had developed an interest in computers from using them at young age, building circuits for A-level electronics and learning about the physics of computers (as well as computational physics) at University. If only Richard had been able to convey any of that to Jay Foad, who answered the door, instead of standing like a “gormless idiot” (his words) whilst his father jumped in and asked about internships and job opportunities…

Richard went home that evening and browsed the Dyalog website… the Pandora’s box of APL edged ajar and he began to imbibe the symbols. He also sent an amusing email explaining the earlier awkward encounter and clearly showing that he was not a “gormless idiot”. This resulted in a meeting with the CEO and CXO, Gitte and Morten, in October 2018. After that meeting Richard showed enough aptitude and interest, while pair-programming a simplistic physics simulation with Morten, that they decided to keep him.

Given that Richard’s previous experience includes programming an autonomous robot for the QMC team in the 2012 and 2013 Student Robotics competitions and using MATLAB and CERN’s ROOT library to process experimental data and run simulations, he was very surprised that he had never heard of APL before. He sees a potential in APL to develop domain specific programming languages and software packages to help teachers convey concepts in a way which more closely matches the syntax and jargon in which problems are already described.

In his new role at Dyalog, Richard is developing teaching materials and demos to promote APL.

Pool Stories: Fergus back on Form

It has been almost 2 years since our last post about Jo Fergus (daughter of our Customer Account Manager, Karen Shaw) the pool player who Dyalog have sponsored in the past. When we last updated you, Jo had just had her daughter, Remy, and made the difficult decision to take some time out from pool to concentrate on her new family.

On June 30th 2018 she married Tom Fergus, Remy’s Dad, in a small ceremony at Trowbridge County Hall and became Jo Fergus. The wedding came as a bit of a surprise to friends and family who thought they were attending a birthday lunch but the sun shone and a fantastic day was had by all. Jo started to miss playing pool and in 2018 she went to the Wiltshire county pool trials and was invited back into the Wiltshire Ladies A county team. After a successful season, in which they didn’t lose a match, the team has qualified for National County Finals taking place at the beginning of March. Jo has also joined a team playing in her local pool league.

In 2019 Jo took the decision to test herself and her pool skills and signed up to the 2019 IPA Ladies Tour which will see her play at 5 events across the UK. There are only 32 places on this Ladies tour and it will give Jo a chance to play against high level opposition, which she feels will improve her game. Ranking points will be awarded and the top 8 in the rankings after Tour 5 will automatically qualify for the first ever IPA Ladies Blackball Premier League.

Dyalog are proud to be sponsoring Jo for this tour and it is planned that all Ladies finals will be live streamed on freesports.tv so we have our fingers crossed she makes at least one final!

Ascending and Descending

Lexicographic Ordering

Lexicographic ordering is what the APL primitives and provide:

   ⎕io←0     ⍝ ⎕io delenda est
   ⎕rl←7*5   ⍝ to get reproducible random results

   a←?11 3⍴3

   a          a ⌷⍨⊂ ⍋a
2 1 0      0 1 0
0 2 2      0 2 2
1 1 1      1 0 0
1 0 0      1 0 1
1 1 1      1 0 1
1 2 1      1 1 0
1 0 1      1 1 1
1 0 1      1 1 1
1 1 0      1 2 1
0 1 0      1 2 2
1 2 2      2 1 0

First order by column 0, resulting in groups of rows with the same values in column 0. Then, within each group, order by column 1, getting subgroups with the same values in columns 0 and 1. Then, within each subgroup, order by column 2, getting subsubgroups with the same values in columns 0, 1, and 2. In general, for each subsub…subgroup, order by column k, getting groups with identical values in columns ⍳k.

The preceding discourse is descriptive rather than prescriptive—algorithms for can use more efficient and more straightforward approaches. As well, for ease of understanding, the description is for a matrix and speaks of columns and rows. In general, any non-scalar array can be ordered, whence instead of rows, think major cells, instead of column, think item in a major cell. Symbolically and more succinctly, ⍋⍵ ←→ ⍋⍪⍵.

can be used if the orderings in the process are all ascending, or if all descending. The problem to be solved here is where the orderings are a mix of ascending and descending.

Numeric Arrays

Since ⍒⍵ ←→ ⍋-⍵ if is numeric, for such multiply each descending column by ¯1 and each ascending column by 1, then apply . This induces a “control array” having the same shape as a major cell of the argument, with a ¯1 for descending and a 1 for ascending.

   adn←{⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ⊢⍵}

For the array a in the previous section:

   a              1 ¯1 1 adn a        ¯1 1 1 adn a
2 1 0          0 2 2               2 1 0  
0 2 2          0 1 0               1 0 0  
1 1 1          1 2 1               1 0 1  
1 0 0          1 2 2               1 0 1  
1 1 1          1 1 0               1 1 0  
1 2 1          1 1 1               1 1 1  
1 0 1          1 1 1               1 1 1  
1 0 1          1 0 0               1 2 1  
1 1 0          1 0 1               1 2 2  
0 1 0          1 0 1               0 1 0  
1 2 2          2 1 0               0 2 2  

In 1 ¯1 1 adn a, column 0 is ascending, and within that, column 1 is descending, and within that, column 2 is ascending. In ¯1 1 1 adn a, column 0 is descending, and within that, column 1 is ascending, and within that, column 2 is ascending.

Ordinals

An array to be sorted can be converted to an order-equivalent integer array by assigning to each item an ordinal (an integer) which has the same ordering relationship as the original item relative to other items in the array:

   sort    ← {(⊂⍋⍵)⌷⍵}
   ordinal ← {⎕ct←0 ⋄ ⍵⍳⍨sort,⍵}

That is, the ordinals obtain as the indices of the original array in the sorted list of the ravelled elements, using exact comparisons. (Exact comparisons are used because sorting necessarily uses exact comparisons.)
For example:

   ⊢ d←¯1 'syzygy' (3 ¯5) 1j2 'chthonic' (¯1)
┌──┬──────┬────┬───┬────────┬──┐
│¯1│syzygy│3 ¯5│1J2│chthonic│¯1│
└──┴──────┴────┴───┴────────┴──┘
   ordinal d
0 5 3 2 4 0

In the example, the data items are ¯1, 'syzygy', 'chthonic', 3 ¯5, 1j2, and ¯1 again. With respect to ordering, these data items are perfectly represented by the ordinals (numbers) 0, 5, 3, 2, 4, and 0, respectively. That is, ⍋d ←→ ⍋ordinal d.

   ⍋ d
0 5 3 2 4 1
   ⍋ ordinal d
0 5 3 2 4 1

As the example illustrates, it is imperative that identical ordinals are assigned to identical items, else the ordering relationships would be changed. For example, if b←0,⍪2 1 and the 0s are assigned different ordinals,

   ⊢ b←0,⍪2 1               
0 2
0 1
   ordinal b                 ⊢ bo←0 3,⍪1 2  ⍝ faux ordinals
0 3                       0 3
0 2                       1 2
   ⍋ ordinal b               ⍋ bo
1 0                       0 1
   ⍋ b
1 0

Computation of ordinals is greatly facilitated by the total array ordering introduced in Dyalog APL version 17.0.

Non-Numeric Arrays

A general solution for the ordering problem obtains by first converting the array to an order-equivalent integer array through the use of ordinals.

   ado ← {⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ordinal ⍵}

For example:

   ⎕rl←7*5   ⍝ to get reproducible random results

   x0← ?19⍴4                            
   x1← (⊂?19⍴2) ⌷ 'alpha' 'beta'          
   x2← (⊂?19⍴3) ⌷ 'abc'                   
   x3← (⊂?19⍴3) ⌷ 'able' 'baker' 'charlie'

   x ← x0,x1,x2,⍪x3

   ordinal x
13 49 19 42
10 49 32 68
13 49 63 68
 4 49 63 42
 0 27 19 23
13 49 32 42
 0 49 19 42
10 49 32 68
10 27 32 23
 4 49 32 68
 4 49 32 68
 4 27 32 23
 4 49 32 68
 0 49 63 68
13 49 63 68
 0 49 32 42
13 27 32 23
 4 27 63 42
13 49 19 42

   (⍋x) ≡ ⍋ ordinal x
1

Suppose x is to be sorted ascending in columns 0 and 2 and descending in columns 1 and 3. The control array is 1 ¯1 1 ¯1, and:

   x                       1 ¯1 1 ¯1 ado x
┌─┬─────┬─┬───────┐     ┌─┬─────┬─┬───────┐
│2│beta │b│baker  │     │0│beta │a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │0│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │0│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│b│baker  │     │0│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │b│charlie│     │0│beta │c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │a│baker  │     │0│alpha│c│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│charlie│     │1│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│baker  │     │1│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│able   │     │1│alpha│c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │a│able   │     │2│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │2│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│alpha│c│able   │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│charlie│     │3│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│alpha│c│baker  │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│2│beta │a│baker  │     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │c│charlie│     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │3│alpha│b│baker  │
└─┴─────┴─┴───────┘     └─┴─────┴─┴───────┘

Finally

   (ordinal x) ≡ ordinal ordinal x
1

That is, ordinal is idempotent. Actually, this is kind of obvious, but I never miss an opportunity to use the word “idempotent”.☺

Dyalog ’18 Videos, Final Week

Welcome to the eighth – and final – week of recordings from the Dyalog User Meeting in Belfast! I’d like to take this opportunity to thank all the speakers who helped make Dyalog ’18 another valuable experience! Fittingly, we’re wrapping up with a larger, and even more varied collection than usual: two talks by members of the Dyalog team, two by users of Dyalog APL, and one from the British APL Association – five in total!

1. There are big changes afoot at the British APL Association and Paul Grosvenor, the chairman of the BAA, took to the stage in Belfast to tell us about them. Most importantly, the Vector magazine is going online after 25 years as a printed publication – and the removal of printing costs means that membership is now free! An annual conference in April/May is being planned. There has never been a better time to join the BAA, and you don’t need to live in the UK to do so! In addition to watching Paul’s talk, you can read about many of the changes here and on the new vector website (coming soon!).

2. Arianna Francia from SimCorp Italiana works in one of the largest APL development teams in the world. IFRS 9 is an International Financial Reporting Standard (IFRS) promulgated by the International Accounting Standards Board (IASB). Fortunately, although Arianna’s talk is titled “The IFRS 9 Project”, she completely avoids the subject of IFRS, and instead offers valuable insights into how a rapidly growing team, faced with an extraordinarily complex project, adapted and adopted a combination of agile practices and ideas from Ed Catmull’s book Creativity, Inc, which is about his experience managing Pixar.

3. For many Dyalog users, the least attractive aspect of Dyalog’s MiServer as a tool for cross-platform user interfaces is that it comes with a completely new set of controls or “widgets”, which essentially means you will need to rewrite your ⎕WC-based user interface. If you are facing this problem, Chris and Michael Hughes have very good news for you: in their talk “⎕WC on the Web”, they demonstrate a new tool that emulates ⎕WC, allowing you to create your UI in a web browser or the HTMLRenderer component included with recent versions of Dyalog APL.

4. Nested arrays make it easy – sometimes, too easy – to represent tables as 2-dimensional arrays. However, if each column of a matrix has the same data type, there are very significant savings to be had in both space and time if you “invert” such tables and represent them as a list of vectors, each containing the values for one column. In his talk on “Inverted Tables”, Roger Hui evolves a set of short, elegant and efficient functions for common operations on inverted tables.

5. It appears that the APL community came very close to losing John Scholes after he read the September 1989 edition of British Computer Journal special edition on Lazy Functional Languages and was struck by the beauty of functional programming. Fortunately, John decided to work on functional extensions to APL, and came up with dfns. This new notation was added to APL in 1996, only six years after Haskell 1.0 appeared. In his talk entitled “dfns, past present and future”, John revisits the early days and muses about things that could have been done differently, but quickly moves on to talk about ideas for future extensions to dfns, like guarded guards, where clauses, and optional type specifications.

I hope that you enjoy watching your choice of recordings as I have enjoyed revisiting them in order to write about them. As you may have noticed, we have taken a break from webinars while we have been rolling the Dyalog’18 recordings out. Now that we’re done, remember to set time aside at 16:00 (U.K. time) on the 3rd Thursday of each Month to follow the webinar series. The next webinar will be on Thursday February 21st: a presentation by our CTO Jay Foad, on his adventures as a participant in the Advent of Code programming competition, which was held in December.

Summary of this week’s videos:

New York Dyalog Meetup

I am very pleased to announce the creation of the New York Dyalog APL Meetup group, details of which can be found online at https://www.meetup.com/New-York-Dyalog-APL-Meetup/. The meetup has been created and is organised by Paul Mansour, who is also sponsoring the venue for the inaugural meetup, scheduled for 6-9pm on Thursday February 7th, at Alley, 119 West 24th Street, New York. If you are interested in meeting APL users in the New York area, please join the Meetup group so that you will be notified of future events. Please sign up for events that you intend to attend so we know you are coming!

Meetup is a service used to organize online groups that host in-person events for people with similar interests, including programming languages. In addition to the New York group, there is also an APL Meetup group in Frankfurt which meets regularly. We welcome the creation of more local meetups! If you create one in your area, remember to inform us at Dyalog so that we can add a link from our event calendar, and arrange to stop by and speak when we are in your neighborhood!

The program for the meetup on February 7th is as follows:

6:00-6:30pm: Time for Networking

6:30-8:00: Morten Kromberg: New Ways of Working with APL

When you are busy solving problems, new technology can be an unwelcome distraction – but every now and again technologies appear which have the potential to make development, maintenance or distribution significantly easier. Morten will demonstrate some of the new ways of working with APL that have become available in the last few years, and also discuss likely features in the next couple of releases of Dyalog APL: 17.1 in Q2 of 2019 and 18.0 in 2020.

8:00-8:15 Short Break

8:15-9:00 Paul Mansour: Keeping it Simple – A Git Workflow for APLers.

Abstract: Git is great, but the newcomer can easily drown in a sea of commands and options. Git doesn’t tell you when or why to branch, when or why to merge or rebase, how to version your project or prepare a release. AcreFlow is a radically simplified Git workflow that answers these questions. It is implemented in Dyalog APL so you can branch, commit, and put out new versions directly from the APL session.