John Scholes' Conway's Game of Life: Difference between revisions

Jump to navigation Jump to search
(Performance notes and timings)
Line 279: Line 279:
== Performance ==
== 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.
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 ([[Roger Hui]] states that the Game of Life motivated some improvements to Boolean functions in [[Dyalog APL 13.2|Dyalog 13.2]] and [[Dyalog APL 14.0|14.0]]<ref>[[Morten Kromberg]] and [[Roger Hui]]. D11: [https://dyalog.tv/Dyalog13/?v=84t87EO5ZEE Primitive Performance] at [[Dyalog '13]]  ([https://www.dyalog.com/uploads/conference/dyalog13/presentations/D11_Primitive_Performance/perfscript1.htm#2 script]). 2013-10.</ref>). 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.
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.

Navigation menu