# Suggested algorithm to control upper bound of space "leaks"

Shelby Moore shelby at coolpage.com
Sat Oct 31 15:07:22 EDT 2009

```One possible runtime optimization to provide an upper bound for cache
control, might be to not cache thunks when the runtime computation time
times number of cache hits, is less than the round-trip paging time
multiplied by recent system paging load.

Is this novel?  Is it useful?

=================
Note, functional programming is new to me so please excuse naive errors or
naive blindness.  I am sharing early-- as I understand to be a principle
of open source.  Noise may be a useful signal with the right filter (aka
from crap ideas sometimes spawn great ones, aka in theory, practice
derives from theory. In practice, it inverts...just my little spin on
famous quote :).

Here follows the context from "Essence to Functional Programming for
Imperative Programmers", an online guide I am researching and writing.

Allocation Size Determinism
---------------------------

Pure functional with lazy evaluation obscures virtual memory space
allocation "leaks", because two functions may compile and perform the same
logical algorithm in outcomes other than space allocation.

repeat x = xs where xs = x : xs

{- List contains references to itself, thus lazy allocated size grows
to maximum size shared by all references to this function. -}
repeat'leak x = x : repeat'leak x

leak'none x = take 1000000 repeat x

leak'million x = take 1000000 repeat'leak x

This enables orthogonality of algorithm and cache space algorithm
reasoning[5], can be selectively disabled[5], and is no worse than
emulating lazy list cache resizing in non-lazy languages-- e.g. the
fibonacci example in Javascript-- with better orthogonality and tools for
the lazy default[6]. Space "leaks" are uncontrolled caching that are
re-usable in future runtime, thus unlike traditional memory leaks, impact
performance relative to virtual memory paging versus re-computation speed.
One possible runtime optimization to provide an upper bound for cache
control, might be to not cache thunks when the runtime computation time
times number of cache hits, is less than the round-trip paging time
multiplied by recent system paging load.