| dc.description.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. | |
