Swift memoizing/caching lazy variable in a struct

Question

I drank the struct/value koolaid in Swift. And now I have an interesting problem I don't know how to solve. I have a struct which is a container, e.g.

struct Foo {
    var bars:[Bar]
}

As I make edits to this, I create copies so that I can keep an undo stack. So far so good. Just like the good tutorials showed. There are some derived attributes that I use with this guy though:

struct Foo {
    var bars:[Bar]

    var derivedValue:Int {
        ...
    }
}

In recent profiling, I noticed a) that the computation to compute derivedValue is kind of expensive/redundant b) not always necessary to compute in a variety of use cases.

In my classic OOP way, I would make this a memoizing/lazy variable. Basically, have it be nil until called upon, compute it once and store it, and return said result on future calls. Since I'm following a "make copies to edit" pattern, the invariant wouldn't be broken.

But I can't figure out how to apply this pattern if it is struct. I can do this:

struct Foo {
    var bars:[Bar]
    lazy var derivedValue:Int = self.computeDerivation()
}

which works, until the struct references that value itself, e.g.

struct Foo {
    var bars:[Bar]
    lazy var derivedValue:Int = self.computeDerivation()

    fun anotherDerivedComputation() {
        return self.derivedValue / 2
    }
}

At this point, the compiler complains because anotherDerivedComputation is causing a change to the receiver and therefore needs to be marked mutating. That just feels wrong to make an accessor be marked mutating. But for grins, I try it, but that creates a new raft of problems. Now anywhere where I have an expression like

XCTAssertEqaul(foo.anotherDerivedComputation(), 20)

the compiler complains because a parameter is implicitly a non mutating let value, not a var.

Is there a pattern I'm missing for having a struct with a deferred/lazy/cached member?

matt · Answer 1 · 2018-08-07T16:24:22.257

3

Memoization doesn't happen inside the struct. The way to memoize is to store a dictionary off in some separate space. The key is whatever goes into deriving the value and the value is the value, calculated once. You could make it a static of the struct type, just as a way of namespacing it.

struct S {
    static var memo = [Int:Int]()
    var i : Int
    var square : Int {
        if let result = S.memo[i] {return result}
        print("calculating")
        let newresult = i*i // pretend that's expensive
        S.memo[i] = newresult
        return newresult
    }
}

var s = S(i:2)
s.square // calculating
s = S(i:2)
s.square // [nothing]
s = S(i:3)
s.square // calculating

edited Aug 07 '18 at 16:24

answered Aug 07 '18 at 15:52

matt

515,959
87
875
1,141

1

While a dictionary style cache is often a common implementation of "memoization", I don't think the term is explicitely restricted to said implementations. Wikipedia states "A memoized function "remembers" the results corresponding to some set of specific inputs." But perhaps, the term is misleading, would "caching" be better in the title? – Travis Griggs Aug 07 '18 at 15:57
Well, let me put it another way. Would memoizing in the style I'm suggesting solve the problem? – matt Aug 07 '18 at 16:08
Added an example of what I'm suggesting. – matt Aug 07 '18 at 16:24
Yes that would work. Bottom line seems to be that you have to "box" the changeable value somewhere (whether in a "caching property" box, or a look aside table). – Travis Griggs Aug 07 '18 at 16:26
So who gets the answer here? Your and @OleBegemann answers together steered me in the right direction. And you both have an insane amount of points. :) – Travis Griggs Aug 07 '18 at 21:38
You are allowed to accept your own answer! Wait 48 hours, then accept. It closes the question, and it closes it correctly: your answer is the right answer for you, and it wasn't what either of us said. – matt Aug 07 '18 at 23:28

Ole Begemann · Answer 2 · 2018-08-07T16:48:25.103

The only way I know to make this work is to wrap the lazy member in a class. That way, the struct containing the reference to the object can remain immutable while the object itself can be mutated.

I wrote a blog post about this topic a few years ago: Lazy Properties in Structs. It goes into a lot more detail on the specifics and suggest two different approaches for the design of the wrapper class, depending on whether the lazy member needs instance information from the struct to compute the cached value or not.

score 2 · Accepted Answer · answered Aug 07 '18 at 19:47

I generalized the problem to a simpler one: An x,y Point struct, that wants to lazily compute/cache the value for r(adius). I went with the ref wrapper around a block closure and came up with the following. I call it a "Once" block.

import Foundation

class Once<Input,Output> {
    let block:(Input)->Output
    private var cache:Output? = nil

    init(_ block:@escaping (Input)->Output) {
        self.block = block
    }

    func once(_ input:Input) -> Output {
        if self.cache == nil {
            self.cache = self.block(input)
        }
        return self.cache!
    }
}

struct Point {
    let x:Float
    let y:Float
    private let rOnce:Once<Point,Float> = Once {myself in myself.computeRadius()}

    init(x:Float, y:Float) {
        self.x = x
        self.y = y
    }

    var r:Float {
        return self.rOnce.once(self)
    }

    func computeRadius() -> Float {
        return sqrtf((self.x * self.x) + (self.y * self.y))
    }
}

let p = Point(x: 30, y: 40)

print("p.r \(p.r)")

I made the choice to have the OnceBlock take an input, because otherwise initializing it as a function that has a reference to self is a pain because self doesn't exist yet at initialization, so it was easier to just defer that linkage to the cache/call site (the var r:Float)

Fun and useful at the same time! – matt Aug 07 '18 at 19:54 — matt, Aug 07 '18 at 19:54

Swift memoizing/caching lazy variable in a struct

3 Answers3