The second problem in Project Euler is
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Nine years ago, I wrote a blog post that showed how to solve this in Python using iterators and in Go using channels. The Go code started simple, but ended up a bit complicated because it also had stop channels to allow early exit. See euler.py for the Python code, and channel.go for the Go code using channels.
Go issue #61405 proposes to add a new function-based iterator protocol to Go. To test it, I rewrote the Go code using push function iterators. See functional.go. The code is notably simpler and shorter than the channel based code.
Worth noting is that a version of the code that just uses a plain for loop and if statements is significantly faster and shorter than the versions using push functions. The cost is that the code for generating Fibonacci numbers is a little obscure. A middle ground is to use a push function for fibs, but filter and sum inside a normal loop. See nonfunctional.go.
Take these benchmarks with a grain of salt as the numbers will change if the proposal is finalized and optimization begins in earnest.
>>> timeit.timeit('functional()', globals=globals())
5.410251271969173
timeit.timeit('nonfunctional()', globals=globals())
>>> timeit.timeit('nonfunctional()', globals=globals())
2.24513187300181
For context, Python takes about 5 microseconds functionally and 2.5 microseconds imperatively, a 2x overhead for functional looping.
$ gotip test -v -benchmem -bench . .
=== RUN TestEuler
--- PASS: TestEuler (0.00s)
goos: darwin
goarch: amd64
pkg: x/euler
cpu: Intel(R) Core(TM) i7-1060NG7 CPU @ 1.20GHz
BenchmarkFunctional
BenchmarkFunctional-8 3613938 327.7 ns/op 136 B/op 8 allocs/op
BenchmarkNonfunctional
BenchmarkNonfunctional-8 38324710 30.15 ns/op 0 B/op 0 allocs/op
BenchmarkHybrid
BenchmarkHybrid-8 17409680 69.89 ns/op 0 B/op 0 allocs/op
BenchmarkChannels
BenchmarkChannels-8 32686 38886 ns/op 490 B/op 7 allocs/op
PASS
ok x/euler 5.796s
$ GOMAXPROCS=1 gotip test -v -benchmem -bench . .
=== RUN TestEuler
--- PASS: TestEuler (0.00s)
goos: darwin
goarch: amd64
pkg: x/euler
cpu: Intel(R) Core(TM) i7-1060NG7 CPU @ 1.20GHz
BenchmarkFunctional
BenchmarkFunctional 3516156 348.3 ns/op 136 B/op 8 allocs/op
BenchmarkNonfunctional
BenchmarkNonfunctional 36625514 30.08 ns/op 0 B/op 0 allocs/op
BenchmarkHybrid
BenchmarkHybrid 17324220 68.38 ns/op 0 B/op 0 allocs/op
BenchmarkChannels
BenchmarkChannels 55174 21107 ns/op 488 B/op 7 allocs/op
PASS
ok x/euler 5.494s
Go takes around 30 nanoseconds imperatively and 300 nanoseconds functionally, approximately a 10x overhead. A hybrid version of that code that generates the fib sequence using a push function, but filters and sums it using normal Go if statements does much better with only a 2x overhead (70 nanoseconds). A channel version takes an absurd 40 microseconds, which is slower than Python's functional version (5 microseconds). The speed of the channel version increases by setting GOMAXPROCS to 1, making it only 20 microseconds.
- Channel based code is very rare in production because it is too verbose and too slow.
- The signature for push functions is quite long.
func(yield func(int64) bool) bool
is bad enough. Something likefunc TakeUntil(limit int64, it Iter[int64]) Iter[int64]
would be totally unreadable ifIter[int64]
were expanded. - It's not clear what to return for the final bool. Does
true
indicate exhaustion or non-cancellation? - I think I could tolerate a 2x performance hit to use a push function in production, but I'm not sure I could tolerate the performance hit that comes from stacking them.
- Should I be using stop functions somewhere in here? I think you only need them if you convert a push function into a pull function via coro.Pull, but it's not totally clear.
- It's a little odd that you can write
for someBool
but have to writefor range someInt
. I understand why, but it's easy to forget therange
.
one of the best design decisions of the Go language, is that
if
statement only allow booleans. so you cant do this:you have to be explicit:
because of decisions like this, Go is one of the most readable languages currently (to me). please don't advocate for any changes that would hurt that.