2,951
edits
Performance: Difference between revisions
Jump to navigation
Jump to search
Reference counting
No edit summary |
(Reference counting) |
||
| Line 22: | Line 22: | ||
=== Alternate array representations === | === Alternate array representations === | ||
Internally, APL arrays are usually stored as two lists in memory. The first is a list of the shape (although some implementations also include the "stride"<ref>Nick Nickolov ''Compiling APL to JavaScript'' (Vector Volume 26)</ref>). The second is the ravel of elements in the array. Nested arrays consist of pointers to arrays which may be distributed across memory, their use can lead to very inefficient memory read patterns - in contrast to flat arrays which are stored as a contiguous block. | Internally, APL arrays are usually stored as two lists in memory. The first is a list of the shape (although some implementations also include the "stride"<ref>Nick Nickolov ''Compiling APL to JavaScript'' (Vector Volume 26)</ref>). The second is the ravel of elements in the array. Nested arrays consist of pointers to arrays which may be distributed across memory, their use can lead to very inefficient memory read patterns - in contrast to flat arrays which are stored as a contiguous block. | ||
=== Reference counting and data reuse === | |||
Because APL's immutable arrays do not permit [[wikipedia:circular reference|circular reference]]s (although other features like [[objects]] might), APL implementations almost universally use [[wikipedia:reference counting|reference counting]] as a memory management technique. In some implementations, such as [[Dyalog APL]], reference counting is supplemented with [[wikipedia:tracing garbage collection|tracing garbage collection]], which is run infrequently to handle circular references. | |||
Because reference counting keeps track of the exact number of references, and not just whether an array is referenced or not, it can be used not only to find when an array can be released (reference count 0), but also to find when it can be reused when passed as an argument (reference count 1).<ref>Cantrill, Brian. [https://queue.acm.org/detail.cfm?id=1531242 "A Conversation with Arthur Whitney"]. 2009.</ref> When permitted, reusing arguments can reduce memory usage and improve cache locality. In some cases, it also allows for faster primitive implementations: for example, [[Reshape]] can change only an array's [[shape]] while leaving its [[ravel]] data in place, [[Take]] can free trailing [[major cell]]s from an array while leaving the remainder, and [[At]] can modify only part of an array. | |||
=== Operation merging and dynamic compilation === | === Operation merging and dynamic compilation === | ||