Fun with Go Iterators
xnacly.me
xnacly.me
My guess is that Go is probably wrapping the body of the range loop into a closure, and passing that closure into the iterator function as the yield function. A break in the body of the loop becomes a "return false" in the closure.
The allocation is probably the closure environment struct (giving access to variables prior to the range loop).
This closure might escape through the iterator function so Go can't just put the environment struct onto the stack, it has to escape to the heap.
The cost is small but it's not free. Usually, not having to think about the allocation is an advantage. In the rare case can't afford the iterator, do it differently.
Go is great.
This is a place where I feel like the type of simplicity that Go touts doesn't actually feel like it's optimizing for the right thing. Having a single type for all pointers certainly has a sort of abstract simplicity to it, but I feel like it doesn't actually make things simpler when using it in the long run. My perspective is that "conceptual" simplicity is a balancing act between not having too many concepts but also not having concepts being too confusing individually, and I'm surprised that Go is used for domains like needing to completely avoid allocations in a hot path when the language doesn't really feel like it's designed to make easy.
That is clear sign that Go was not the right tool for the job
There are community libraries that implement similar API surface with structs that can be completely allocation-free and frequently dispatched statically.
Moreover, with the advent of `T where T : allows ref struct` you can finally write proper LINQ-like abstraction for Span<T>s, even if it's a bit less pretty. I have been playing with a small toy prototype[0] recently and it looks like this:
// Efectively C's array constant
var numbers = (ReadOnlySpan<int>)[1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var iter = numbers
.Where((int n) => n % 2 == 0)
.Select((int n) => n * 2);
// Inspired by Zig :)
using var vec = NVec<int, Global>.Collect(iter);
At the end of the day, .NET's GC implementations can sustain 4-10x allocation throughput when compared to Go one (it's not strictly better - just different tradeoffs), with further tuning options available, so one allocation here and there is not the end of the world, and not all LINQ methods allocate in the first place, and many of them allocate very little thanks to optimizations made in that area in all recent releases.
[0]: https://github.com/neon-sunset/project-anvil/blob/master/Sou...
https://medium.com/@sanjanasw99/an-in-depth-guide-to-linq-in...
Go is supposed to be an improvement over C for most programming tasks.
This is not true. s/Go/Zig is true. That is why I'm switching to Zig now.
This sort of “chaining” syntax is pretty standard in many languages (Java, JS, Elixir, etc). Especially for streams/iterators/lists. You can have pretty well named and flat logic too. I think it’s just poorly written demo code. To me, this “functional” style of chaining is great. It highlights intent when reading the chain (you read “filter” as a step instead of a for loop with a conditional inside). It’s also really easy to recompose or reorder, and the code-review diffs are super easy to reason about when that happens.
I don’t think it really generates anything conventionally called “horrors” either - you can still use named functions and everything you love, this just makes it easier to use. It may encourage more well-written code too.
Imagine a simple example - get all files in some directory, filter out non-json files, perform some name-manipulation (map) function, and then return a new list. The “old” way would require a series of for loops that make and fill slices passed to each. You then wrap that whole thing in a new method called “GetRenamedJsonFiles(path string) []File”.
With the iterator chaining, you can still wrap it in a named method, but now you can replace the repeated for loops and intermediary slices with: “return GetFiles(path).Filter(isJsonFunc).Map(updateFileNameFunc).Collect()”. It’s probably easier to read, easier to change up later if requirements change, and easier to validate intent when reviewing, etc. It even encourages smaller, dedicated, easy to update or share methods - it encourages named methods for the intermediary steps (getFiles, isJson, updateName).
func GetRenamedJsonFiles(path string) []File {
files := GetFiles(path)
jsonFiles := KeepJson(files) // or `Filter(files, IsJson)`
renamedFiles := RenameFiles(jsonFiles) // or `Map(jsonFiles, RenameFile)`
return renamedFiles
}
It is not even like that "map" and "filter" don't have their places in this style. In fact function chaining is just a concise way to rephrase that! You can write in a functional style without having any function chaining, because the style is all about immutability and resulting composability. Mutability tends to not mix together---any such combination results in something more complex. As long as that can be eliminated, anything would work.
One-time use variables that are consumed on the next line aren’t valuable. Chaining exists as a widely used pattern because it’s useful to not generate a ton of intermediary variables.
In fact, the typing point you bring up is actually less clear. In the iterator chain, the type is “iterator”, which is a standard type that can be produced from many sources as business requirements change. In your example, the types need be compared to the function parameters and methods need to be written explicitly use the same types.
Consider a slightly more complicated example that filters on multiple conditions, say file type, size, and last modified date. These filters could be applied sequentially, leading to names like jsonFiles, then bigJsonFiles, then recentlyModifiedBigJsonFiles. Or alternatively, names which drop that cumulative context.
Of course that can be extracted out into a standalone function that filters on all criteria at once or we can use a combinator to combine them or apply any number of other changes, but generally naming intermediate states can be challenging.
Yeah, but that does not necessarily make something easier to understand. Which function do you think is easier to understand?
func quadraticFormula(a int, b int, c int) {
return (-b+sqrt(b*b-4*a*c))/2*a;
Or naming intermediate steps (since we only get to apply one function at a time, and math operators are just functions, why should they be special)?
func quadraticFormula(a int, b int, c int) {
minus_b := -b
squared_b := b*b
four_times_a := 4*a
four_times_a_times_c := four_times_a*c
inside_of_sqrt := squared_b - four_times_a_times_c
sqrt_result := sqrt(inside_of_sqrt)
numerator := minus_b + sqrt_result
denominator := 2*a
return numerator/denominator;
Sometimes naming intermediate steps makes code easier to read. Sometimes it doens't. It depends a lot if the intermediate step has a semantic meaning or not, if you want the reader to pause and do a mental checkpoint or if it makes more sense to keep going. Kind of like when you are writing English, and you decide to stop a sentence, or keep going, you don't want your sentences to be too long, but also not too large. That's why good code should follow guidelines, but not hard rules. The programmer should write it in a way that is easier for the reader to understand, and that depends on the context of what is being done.
There’s an asterisk here because you cherrypicked a function that is already widely known and understood. All we really need to understand that function is its name. If you chose complex niche business logic, or The Wave Function, it would have made for a more fair and instructive example.
That said, I noticed something odd here. In order for a module like this to really shine, I think all these operations need to be functionally pure. Right now, some of these mutate the iterator's `iter` method mid-stream, which is about as side-effect-ful as you can get.
```
func (i Iterator[V]) Map(f func(V) V) Iterator[V] {
cpy := i.iter
i.iter = func(yield func(V) bool) {
for v := range cpy {
v = f(v)
if !yield(v) {
return
}
}
}
return i
Unless I'm misreading that, `i.iter` has new behavior after this call. A better way would be to return a new _iterator_ with the custom iter behavior instead.
``` func (i Iterator[V]) Map(f func(V) V) Iterator[V] {
// create a fresh iterator around a custom closure (NewIterator() is hypothetical in this case)
return NewIterator(func(yield func(V) bool) {
for v := range i.iter {
v = f(v)
if !yield(v) {
return
}
}
})
Personally, the article’s implementation seems fine to me. The iter is a private field of a throwaway struct created on the fly in order to support chaining. If anyone is then relying on the (private) contents of that struct, I think that’s user error. I can’t see personally why you’d do that.
a := []int{1,2,3,4}
it := slices.All(a)
it = slices.Reverse(it)
it = slices.Map(it)
it = slices.Filter(it, func(i int) bool { return i % 2 == 0 })
slices.ForEach(it, func(i int) { fmt.Println(i) })
Type-inferred arrow lambda for function arguments would go such a long way in making this code nicer... And not make compilation slower at all.
it = slices.Filter(it, i => i % 2 == 0)
slices.ForEach(it, i => fmt.Println(i)) a := []int{1, 2, 3, 4}
out := []int{}
for idx := range a {
val := a[len(a)-idx-1]
if mappedVal := Map(val); mappedVal % 2 == 0 {
out = append(out, mappedVal)
fmt.Println(mappedVal)
}
}
Plus, in a for loop approach, it is not true that the caller may need another loop with a copy. They may just loop over the result and skip over the things they don't need. They only need a copy if they are going to pass that on to something else.
A drum I can not stop banging on is that you can not just take a neat technique out of one language and slam it into another without examining the end result to make sure that you haven't murdered the cost/benefits tradeoff. You can slam together all the maps and filters and reduces you want in Haskell, and applicatives and monads and all the fun, due to a combination of the laziness and various safe optimizations like loop fusion. In an eager context that lacks loop fusion, going .Map().Map().Map().Map() has radically different performance implications. For instance, "take 10 $ map f list" in Haskell will only call "f" 10 times. .Map().Take(10) in most implementations will create the full array, however large it is, and slice ten off the end after that.
In imperative languages, contrary to frequent claims from the functional programming crowd, for loops are actually often better in practice. The solution to their pathologies is to be aware of them and not do them. But it is far, far easier to get good performance out of a for loop in an imperative language than to contort one's code into a pale parody of functional programming.
Which imperative language? In Java and rust, two languages I know, all these operations are lazy until the final collect. So no copy is made
One case where the for-loop would be much more efficient is a simple transformation like incrementing each element of an array, or adding two arrays element-wise. A serious C compiler could unroll such a loop into several vector instructions which work on several elements at once. Maybe even LLVM can recognize something like that in Go code.
If you have a .Collect() call, you're in the deforestation branch. This has its own issues with stressing the inliner (turning simple, direct for loops over large collections into traversals that include several indirect method calls per item in addition to the payload is pretty easy), but that's still generally better than stressing the RAM.
Rust's map doesn't operate on arrays at all from what I can see but operates on iterators directly. This is good and generally more correct. However there's a lot of languages that don't support that. Rust is generally also going to be more reliable about compiling it all away than a lot of other languages where it will be really easy to spill over what the inliner can handle. Those long compile times in Rust do have their benefits.
There's also languages that sort of split the difference, e.g., it is not that difficult in Python to use itertools and generators to correctly write something that will not generate a lot of intermediate arrays, but it is also easy to write a series of calls and list comprehensions to write otherwise equivalent code that will create a lot of intermediate arrays.
I expect as we continue to build new languages over time they're going to all look like Rust here. It's pretty obvious that conceiving of loops as iteration over some sequence is the way to go. However, that is a result that we got to precisely because of our experiences with a lot of languages that don't support it as well, or support it inconsistently, or as is actually quite common, the language nominally supports it but the ecosystem tends to assume concrete values a lot more often than it should, and all these languages are still around.
Writing in this style correctly in imperative code is more difficult than a lot of people jumping up and down about how we should rewrite all our loops as maps and filters tend to account for. It can be done, but it's often harder than it looks, in at least one of the writing and the performance if not both, and the harder it is, the more the costs stack up on the costs side, and the harder the costs/benefits analysis becomes. And I still don't like how it refactors in most cases.
This is incorrect. In fact, the only such mainstream language that I can think of is JavaScript. Python, Java, C#, even C++ all have proper abstractions for lazy sequences, which would get used in such circumstances - and their whole point is that they are composable.
> Plus, in a for loop approach, it is not true that the caller may need another loop with a copy. They may just loop over the result and skip over the things they don't need. They only need a copy if they are going to pass that on to something else.
The point is that your function doesn't know what the caller needs. Yet by making it an eager loop with a copy, you are making that decision for the caller.
The updated version has just one such function.
A function gets less readable as you have to go context switch to more and more different functions to understand what it's doing.
Yes, the `slices` functions are named such that you can make a decent educated guess as to what they're doing, but if there's a problem you're trying to debug that doesn't save you from having to dive into each one.
This is true.
A function also gets less readable every time you have to mentally translate from low-level implementation code, to a high-/human-level description of "what is this actually doing?" (e.g. `val := a[len(a)-idx-1]` - "ohhh, ok, that's iterating in reverse"). Extracting out common patterns to methods with well-known names like `Filter` or `Map` or `ForEach` short-circuits that repeated parsing.
> that doesn't save you from having to dive into each one.
99% of the time, it really does. If you can't trust something as basic and well-defined as `Map` to do what you expect it to do, you've chosen a poor library on which to take a dependency.
The original comment said:
it = slices.Map(it)
Then I went to look it up, and turns out that slices.Map does not in fact exist. https://pkg.go.dev/slices
Personally I feel like this exchange is a vivid illustration of exactly my original point.
In fact, the very fact that you originally thought of the correct interpretation despite the fact that it had been misrepresented is a great example of why common shorthands are useful.
Some people consider `Map` to be a fundamental tool. Like the original commenter mentioned, some people also prefer Typescript to Go.
If I was interviewing someone for my (primarily golang) company and they mentioned that not having `Map` to be a downside of Go that hindered its readability, that would be a strong mark against them. I would not want to try to dig through the N levels of abstraction they would create in the codebase to hide what was happening with all its bugs.
Other companies don't mind this, and use other languages, like Javascript or the latest versions of Python.
Python in particular is great for what you mention, as nearly every slightly common programming idiom has its own keyword with its own special usage, so you can always use that instead of writing the fundamentals yourself.
Personally I hate Python because I prefer not to have to learn a dozen new obscure tools and keywords with each minor language release. I dislike trying to read packages written in Python, because they use whatever 20% subset of the language the author was aware of. I like Go because I can look at the source code for nearly any function in nearly any library and understand it immediately. Nobody would import "leftpad" in Go.
Different languages for different people.
As you say, different languages for different people. Best of luck to you, and thank you for an insightful and civil discussion :)
I write a lot of typescript and golang and I often notice in typescript my chains end up iterating the same array N times when it couldbe been done in one smarter iteration.
I don't think I care though -- both styles are way more than performant enough. You can be more careful about it in cases it is not.
for i := range arr {
foo1(arr[i])
...
foo10(arr[i])
}
for i := range arr {
foo1(arr[i])
}
...
for i := range arr {
foo10(arr[i])
}I tried it, code: https://pastebin.com/cA8YkE8R
Result:
process1: 2s 251.327833ms
process2: 1s 537.721625ms function process3(input) {
return input
.flatMap((n) => (n % 2 === 0 ? n * 2 : []))
.reduce((a, b) => a + b, 0)
} function processfor(input){
let sum = 0
for (let i = 0; i < input.length; i++){
if (input[i] % 2 !== 0){ continue }
sum += input[i] * 2
}
return sum
}
Of course, if you want the most performant solution an imperative for loop is faster (which is what I said in my last comment).
or if you want it really silly.
input.reduce((a, b) => a + (b % 2 && b * 2), 0)
dont ask me why but for(a of b) is slower than for(i=0;i<b.length;i++)
> dont ask me why but for(a of b) is slower than for(i=0;i<b.length;i++)
Probably because for of loops use the iterator protocol. So I'm assuming under the hood the JS engine is actually invoking the Symbol.iterator method (which is slower).
#! /usr/bin/env node --experimental-strip-types
function processIterator(input: number[]) {
let sum = 0
for (let i = input[Symbol.iterator](), r; (r = i.next()); ) {
if (r.done) return sum
if (r.value % 2 === 0) sum += r.value * 2
}
}
function processfor(input: number[]) {
let sum = 0
for (let i = 0; i < input.length; i++) {
const value = input[i]
if (value % 2 === 0) sum += value * 2
}
return sum
}
const input = Array.from({ length: 1_000_000 }, (_, i) => i)
console.time('normal for loop')
console.log(processfor(input))
console.timeEnd('normal for loop')
console.time('iterator for loop')
console.log(processIterator(input))
console.timeEnd('iterator for loop')A proper comparison could be:
# Case 1.
for n in range(len(data)):
data[n] = transform1(data[n])
data[n] = transform2(data[n])
# Case 2.
for n in range(len(data)):
data[n] = transform1(data[n])
for n in range(len(data)):
data[n] = transform2(data[n])https://play.rust-lang.org/?version=stable&mode=release&edit...
(I'd recommend running it on your own machine as the rust playground limits memory and will likely kill this program)
Output from my machine:
$ cargo run --release
Finished `release` profile [optimized] target(s) in 0.05s
Running `target/release/iterator`
Process 1 returned 18270843109002848788 and took 64.58175ms
Process 2 returned 18270843109002848788 and took 308.969083msIt's only for small arrays actually that the cost of the loop infra and the extra cache miss per loop matters.
There is no such function as "slices.Map()".
The functional style is fine for simple filter/map algorithms, but once you get into zipping multiple iterators together, classic for-loops are often easier.
My company's hiring coding task had this "trap", at one point you needed to write an algorithm to merge consecutive "empty" cells in a data structure that is used to represent a simple table. This is dead easy with a regular for-loop, but writing it in a "functional" style could easily become extremely hairy and/or have O(N^2) complexity.
(But - yes, bravo, correct, you're right and you should say it)
a := []int{1,2,3,4}
it := slices.All(a)
itRev := slices.Reverse(it)
itMap := slices.Map(it)
itFilter := slices.Filter(it, func(i int) bool { return i % 2 == 0 })
slices.ForEach(it, func(i int) { fmt.Println(i) })
Can someone explain the reason for this?
strs := []string{"abc", "defgh", "klmnopqrst"}
ints := From[string, int](strs).
Map(func(a string) int { return len(a) }).
Filter(func(a int) bool { return a >= 4 })
Iterator[int, float32](ints).
Map(func(a int) float32 { return float32(a) }).
Each(func(a float32) { fmt.Printf("%v\n", a) })
//prints 5, then 10
Note that the original implementation in the article modifies the collections in place, in which case this issue doesn't come up at all: you can't put strings in an array of ints. My implementation creates copies of these collections so that the concept of mapping to a new type actually makes sense.
import (
. "github.com/samber/lo"
)
You are not supposed to chain them. This addiction to try and chain everything everywhere all the time is so freaking weird and has been for a very long time.
Not only you are completely losing grasp on what is going on and write code prone to errors, but you are making it unreadable for other people that will be maintaining or just reading your code who will come long after you are gone from the company or abandon your library.
This is where Go's simplicity approach and splitting each action into its own for loop or block of code is a godsend for maintainability.
(† Are iterators even expected/required to be reusable? If they are reusable, are they expected to be stable?)
Still, you need the option, and while reverse is one of the more common iterators, it's still usually avoidable if you need to. But if at all possible I'd suggest a "reverse" type-specialized to slices, and as necessary and possible, type-specialized to whatever other types you are using to actually crawl a value "backwards" rather than collecting a full iterator into a slice.
(Then again, I'm not a fan of this approach in imperative languages in general, due to the generalized difficulty in refactoring code written in this style and the fact that observationally, people just don't refactor it once written and it affords a style rife with repetition. One of the most important considerations about code is how easily it can be refactored. In Haskell, this approach is excellent, precisely because it refactors very, very well in Haskell. In imperative languages, it tends not to, thus, serving as another example of why you can't just blindly bring over nice things from one language into another without verifying they haven't become sour in the process.)
func (i *Iterator[V]) Reverse() *Iterator[V] {
collect := i.Collect()
counter := len(collect) - 1
for e := range i.iter {
collect[counter] = e
counter--
}
return From(collect)
}
(Your broader point about wanting to avoid creating an intermediate array at all for iterators and using type information to intelligently reverse "at the source" definitely still stands, in a broader context, though.)
Edit: I should add that a "Reverse" that takes an iterator has no choice but to manifest the list and then reverse on the list. (Goodness help you if you try to reverse an infinite list.) But you can do type-dependent reverse iterators that don't have to if the data structure doesn't force it, and if you can do that you should, in general. This paragraph isn't about Go; this is the iterator protocol itself.
(FWIW, in C#, the IEnumerable extension method Reverse() just captures the whole sequence to an array and then iterates it in reverse. And yeah, woe unto you if you try to reverse an infinite sequence.)
[0] https://developer.apple.com/documentation/swift/lazysequence...
Not in some languages. Clojure and Google Guava are lazy, nothing is created, only transformed and only as needed. Swift has lazy but it doesn't default to lazy.
What this sort of thing lacks is any ability to optimize. For example, let's say the operation is Reverse().Take(20). There's no reason for the reverser to keep more than 20 elements in its buffer. But to express that, you have to make sure the iterator can be introspected and then rewritten to merge the operators and maybe unroll some of the loops to get better cache locality. This is what Haskell can achieve via Stream Fusion, which is pretty neat. But not so viable in Go.
So the Reverse implementation in this article wouldn't work with single-use iterators. The iter package isn't clear whether a function that requires a multi-use iterator needs to be documented as such.
Because it’s not JavaScript, and that is a good thing.
The stages of learning a language are something along the lines of:
1. Force language patterns from previous language
2. Frustration
3. Write library to make it easier
4. Anger
5. Acceptance
It was updated to 1.23, so it is as idiomatic as I can get. And yes it has a map method between two types. Just a single simple trick used.
https://github.com/picosh/pubsub/blob/main/pubsub.go#L18
We have seen in other languages like JS and python the power of iterators and we are happy to see it in Go
def chain( Accumulant, *Functions_list ):
for f in Functions_list: Accumulant = f( Accumulant )
return Accumulant
Also, local names can sometimes be useful documentation when the function names don’t really get the point across (perhaps because they’re at a different level of abstraction). Or alternatively, in Go it’s idiomatic to keep them short.
Because you want to make code more readable, and getting rid of extraneous intermediate results is one way of achieving that.
2. Implicitly chain everything all the time!
In Factor, you might do it as:
reverse [ sq ] [ even? ] map-filter [ . ] each
reverse [ sq ] map [ even? ] filter [ . ] each
a = [1, 2, 3, 4]
print([v*v for v in reversed(a) if v*v % 2 == 0]) FOURTH-> print([THIRD-> v*v for v in FIRST-> reversed(a) if SECOND-> v*v % 2 == 0])
a = [1, 2, 3, 4]
a = reversed(a)
a = [v*v for v in a]
a = [w for w in a if a % 2 == 0]
print(a)I often use generator expressions for the intermediate values (so I don't allocate a new list for each step), but I find this to be much more readable.