5 ms·
If the author is reading, I believe the problem noted at the end is actually that the code isn’t going through the thunk API and thus no memoization occurs. (Co
by amscanne 4y ago
If the author is reading, I believe the problem noted at the end is actually that the code isn’t going through the thunk API and thus no memoization occurs. (Consider that there is no call to Set in the evaluation tree!)
fib = func(n int) int {
if cache[n].o.IsSome() {
return *cache[n].o.val
}
return fib(n-1) + fib(n-2)
}
Should be:
fib = func(n int) int {
return cache[n-1].Force() + cache[n-2].Force()
}
- deleted 4y ago[deleted]
- tsimionescu 4y agoIndeed, that works, and finishes in 0.00 time - here is a Go Playground to prove it (using *T instead of Optional[T]). https://go.dev/play/p/RxMjU34pjJQ https://go.dev/play/p/RxMjU34pjJQ
- hddqsb 4y agoUnfortunately Go's playground messes with the time, so it's always going to say 0.00s even for the slow version. Here is a hacky workaround to measure the actual time using a syscall: https://go.dev/play/p/kF6Bh048siE https://go.dev/play/p/kF6Bh048siE It shows 979ms for the original version and 0.212ms for the fast version.
- Groxx 4y agoIt does play with time, but essentially only wall-clock time which isn't relevant here. You can easily make tests show non-zero durations.
- hddqsb 4y agoNope. If you call `time.Sleep()` the reported duration will reflect that call, but it's only simulating the delay. The duration of a CPU-heavy task is always reported as 0.00s. Demo: https://go.dev/play/p/UZToqFseAwO https://go.dev/play/p/UZToqFseAwO Output: === RUN TestSleep // calls time.Sleep(2 * time.Second) Real duration: 554µs --- PASS: TestSleep (2.00s) === RUN TestBusyLoop // for i := 0; i < 1000000000; i++ { ... } Real duration: 390.826ms --- PASS: TestBusyLoop (0.00s) PASS The simulation is quite good: if you have multiple threads that use `time.Sleep()`, their output will be interleaved correctly. The output panel will even display the lines one at a time as if it's streaming them from the server, but in reality the entire output is received at once and the "streaming" effect is simulated on the client. Concurrency is one of Go's core features, so it figures the playground would allow some form of concurrency even when the clock is fake.
- Groxx 4y agoInteresting. I suppose that makes sense, to let them speed up execution... I am a bit curious how it'd affect concurrent behavior based on time changes (e.g. if it's cpu-bound for longer than the sleep, does the wake still occur in the middle? Or does it wait to advance time until everything's blocked? What if you runtime.Yield? etc?), but that's certainly an efficient option for a public execution environment like this.
- xena 4y agoOh dear. I pushed an addendum to the article: https://github.com/Xe/site/commit/05135edcbe5e474131c15c24766e0266285fa514 https://github.com/Xe/site/commit/05135edcbe5e474131c15c2476... Thanks for pointing that out!