ML23 Immutable Arrays Help Mutating Arrays More Efficiently

[ML’23] Immutable Arrays Help Mutating Arrays More Efficiently Sven-Bodo Scholz When trying to compile declarative programs into efficiently executable code, intuitively, it may seem that an ability to be more explicit about low-level details helps enabling a compiler or a code generator to lead to more runtime-efficient, parallel implementations. In this paper, we argue that quite the opposite is true, at least in the context of computations on large arrays. Keeping arrays immutable enables compiler transformations that, at the final code generation stage, leads to very efficient implementations through mutable arrays. Such tuning on the level of immutable arrays allows for more radical target-architecture-specific optimisations than what would be possible on the level of explicit memory, explicitly destructive updates and explicitly nested loops.