Functional programming has been around since the late 1950’s, based on lambda calculus concepts dating back 100 years. It has been embraced by just about every modern language, because of guarantees it offers.
Immutability is one property of functional programming, where functions never change a variable, but instead return a new one. When an function takes an input array, it doesn’t modify that array, but instead create a new array and returns it.
Cache is one of the most powerful concepts of Computer Architecture. Processor cache sits close to the computational core, between the processor core and system memory. Cache speeds up system memory reads and writes, by anticipating program behavior to be spatially and temporally coherent. In other words, cache counts on certain program behaviors. When programs access a memory location, caches expect programs to access nearby locations. Cache also counts on programs to access the same location more than once.
When programs behave is this fashion, cache provides significant performance acceleration. However, when programs don’t behave with spatial and/or temporal coherence, caches slow performance down. For example, for sequential access to an array, caches perform very well. However, when array accesses are random, caches along with DDR system memory can slow down by 100X.
Functional Meets Architecture
The main goal of the immutability property of functional programming is to not reuse the same array, but to always create a new output array and return it from a function. This violates the temporal coherency that cache relies on to achieve higher performance.
Spatial coherency may also be reduced, as the immutability makes operations be not in-place. Spatial coherency of accessing the source array and of the destination array are preserved, even when accesses aren’t in-place.
Updating Computer Architecture
To support functional programming constructs, benchmarks that are used to drive Computer Architecture optimization decisions need to include applications and algorithms implemented using functional techniques. This will move Computer Architecture to support functional programming better.
Hopefully, these creative architectural improvements will lead to some unique designs.