Automatic memory reuse of immutable data in Kotlin

Abstract

Immutable data brings many advantages to programming, including safer concur- rency and easier debugging, but it comes with a drawback: immutability means the data cannot be altered. Operations on it require allocating additional memory, but when it is known that the original data will no longer be used, it becomes possible to perform in place updates instead, thus saving memory. This thesis presents a method to identify such cases by analysing the control flow graph of a program to determine if a variable has a only single usage. The only use of a variable is also guaranteed to be its last usage, which provides a safe approximation for when in place updates can be applied. This approach results in a lookup table that maps each variable to its usage, which provides important information to any program transformation that reduces allocations. To facilitate these in place updates, this thesis introduces an API-like pattern that allows functions to either allocate new data or update arguments in place, depend- ing on the usage of the relevant argument. This approach is highly extensible, as it can be readily implemented by any library developer, making it a versatile solution for managing immutable data efficiently.