2,951
edits
John Scholes' Conway's Game of Life: Difference between revisions
Jump to navigation
Jump to search
John Scholes' Conway's Game of Life (view source)
Revision as of 16:50, 12 April 2020
, 16:50, 12 April 2020Performance notes and timings
(Translations to GNU and dzaima/APL) |
(Performance notes and timings) |
||
| Line 276: | Line 276: | ||
grid ← glider⍢(¯3 ¯3∘↑) 10 10⍴0 ⍝ This works | grid ← glider⍢(¯3 ¯3∘↑) 10 10⍴0 ⍝ This works | ||
</source> | </source> | ||
== Performance == | |||
Although it uses [[nested]] arrays to organize the computation, Scholes' Game of Life implementation can still be a fairly fast algorithm on medium and large matrices, competitive with straightforward C implementations. This is because the [[simple]] arrays stored in the outer nested array all have the same size as the argument. There are only nine of these arrays, so the overhead associated with nesting is constant and small. Until they are summed, these arrays are [[Boolean]], allowing them to be stored in a packed representation and [[rotate]]d quickly. When adding them, recent versions of Dyalog APL use [[vector instructions]], enabling many numbers to be added at once. | |||
The following code times how long it takes to perform 1000 iterations of the Game of Life on a shape <source lang=apl inline>1000 1000</source> array. This computation performs a billion cell updates, so the total time in seconds is equal to the time taken per update in nanoseconds. | |||
<source lang=apl> | |||
)copy dfns cmpx | |||
b←1=?1e3 1e3⍴2 | |||
1 cmpx 'Life⍣1000 ⊢b' | |||
</source> | |||
The timings below were taken with various versions of [[Dyalog APL]] on an Intel Kaby Lake i7. The largest change appears in 17.0, when [[Boolean]]-integer [[addition]] was implemented using vector instructions (on this processor, AVX2). | |||
{|class=wikitable | |||
! Version !! Time (s) | |||
|- | |||
| [[Dyalog APL 15.0|15.0]] || 14.0 | |||
|- | |||
| [[Dyalog APL 16.0|16.0]] || 13.5 | |||
|- | |||
| [[Dyalog APL 17.0|17.0]] || 1.32 | |||
|- | |||
| [[Dyalog APL 17.1|17.1]] || 1.31 | |||
|- | |||
| [[Dyalog APL 18.0|18.0]] (pre-release) || 0.75 | |||
|} | |||
== References == | == References == | ||
<references /> | <references /> | ||