Question: Why are Go container Iterators returning container elements via channels ?

95 views
Skip to first unread message

Serge Hulne

unread,
Jun 6, 2010, 5:56:15 AM6/6/10
to golang-nuts
Why are Go container Iterators returning container elements via
channels ?
(as opposed to just returning the values of the container's elements)

Is it to make the iteration process non-blocking ?
(or is it for a more subtile reason ?)

Serge.


Example (from container/vector):
-------------------------------------------

// Iterate over all elements; driver for range
func (p *Vector) iterate(c chan<- interface{}) {
for _, v := range *p {
c <- v
}
close(c)
}


// Channel iterator for range.
func (p *Vector) Iter() <-chan interface{} {
c := make(chan interface{})
go p.iterate(c)
return c
}

Jessta

unread,
Jun 6, 2010, 6:51:44 AM6/6/10
to Serge Hulne, golang-nuts
On Sun, Jun 6, 2010 at 7:56 PM, Serge Hulne <serge...@gmail.com> wrote:
> Why are Go container Iterators returning container elements via
> channels ?
> (as opposed to just returning the values of the container's elements)
>
> Is it to make the iteration process non-blocking ?
> (or is it for a more subtile reason ?)

It's actually a fairly obvious reason. Because the container doesn't
know what value type is in the interface{}.
You'll notice that IntVector.Iter() and StringVector .Iter() actually
do return a chan int and chan string respectfully.

- jessta

--
=====================
http://jessta.id.au

Serge Hulne

unread,
Jun 6, 2010, 7:07:11 AM6/6/10
to golang-nuts
I am sorry, I did not formulate my question precisely enough:

What I meant is:
"Why does the iterating mechanism make use of channels at all ?"

(Why is the use of channels to iterate over a container considered
advantageous ?)

Serge.

On Jun 6, 12:51 pm, Jessta <jes...@gmail.com> wrote:

chris dollin

unread,
Jun 6, 2010, 8:36:24 AM6/6/10
to Serge Hulne, golang-nuts
On 6 June 2010 12:07, Serge Hulne <serge...@gmail.com> wrote:
I am sorry, I did not formulate my question precisely enough:

What I meant is:
"Why does the iterating mechanism make use of channels at all ?"

(Why is the use of channels to iterate over a container considered
advantageous ?)

As opposed to what?

If the container returned a slice, it would have to allocated
space for it. (It would be unwise to return a slice referring to
the containers elements.)

If the container applied a passed function to each element
in turn, there would have to be a protocol for stopping early,
and for arranging to keep state (which is admittedly easy
with closures) etc.

Pumping the results down a channel is simple and leaves it
to the far end to decide what to do with the values.

Chris

--
Chris "allusive" Dollin

Jessta

unread,
Jun 6, 2010, 8:40:49 AM6/6/10
to Serge Hulne, golang-nuts
On Sun, Jun 6, 2010 at 9:07 PM, Serge Hulne <serge...@gmail.com> wrote:
> I am sorry, I did not formulate my question precisely enough:
>
> What I meant is:
> "Why does the iterating mechanism make use of channels at all ?"
>
> (Why is the use of channels to iterate over a container considered
> advantageous ?)
>

Channels are concurrency-safe. You could call vector.Iter() get the
channel and pass it to a bunch of worker goroutines
that can each range over it and each get different items to process,
which is kind of cool.

It also means you don't really need to exposure the underlying data
structure too much. You can range over an slice but it might get a bit
messy if another goroutine wanted to modify that slice while you were
ranging over it. The channel means these kind of issues can be wrapped
up in someway.

Russ Cox

unread,
Jun 7, 2010, 4:21:07 PM6/7/10
to Serge Hulne, golang-nuts
On Sun, Jun 6, 2010 at 02:56, Serge Hulne <serge...@gmail.com> wrote:
> Why are Go container Iterators returning container elements via
> channels ?
> (as opposed to just returning the values of the container's elements)

Because it is trying to implement exp/iterable's Iterable interface.
You don't have to use Iter to range over a vector.

for i, val := range vec
for i, val := range vec.Data()

both avoid the goroutine and channel.

Russ

Serge Hulne

unread,
Jun 7, 2010, 5:24:34 PM6/7/10
to golang-nuts
Hi Russ,

Thanks for your answer !

If I understand correctly, any type which implements the exp/iterable
interface can be iterated :

- Either as a slice, as in your example using vec.Data()
- Or through goroutines/channels.

What is the expected advantage of the second solution ?

Iterators are known from C++, Java and Python. Yet, in these
languages, the iteration takes place in the current thead.
In Go however, there is the possiblity to pull each consecutive
element of the container from a separate channel.

What is the main advantage expected from that novel, Go-specific,
approach (which, to my knowledge, does not exist in C++ or Java or
Python).

At first glance, to a non expert, it looks like a mechanism aimed at
iterating trough a container in a multi-threaded way. Is that the
intended purpose ?

On the other hand, is there not a penalty associated with using that
approach (in terms of memory usage, threads or execution time,
compared to, say, the C++ approach, e.g. the iterators associated with
the STL containers), in particular if the application uses maps or
arrays with a very large number of elements ?

Serge.


On Jun 7, 10:21 pm, Russ Cox <r...@golang.org> wrote:

Russ Cox

unread,
Jun 9, 2010, 2:01:05 AM6/9/10
to Serge Hulne, golang-nuts
> If I understand correctly, any type which implements the exp/iterable
> interface can be iterated ...

>
> What is the main advantage expected from that novel, Go-specific,
> approach (which, to my knowledge, does not exist in C++ or Java or
> Python).

The package exp/iterable, like everything in exp, is experimental.

There are beautiful and elegant programs one can write using explicit
data streams. Doug McIlroy's power series work, both the
Newsqueak and Haskell implementations, is one common example.
Here's another common example: given two binary trees, check
whether the sets defined by the two binary trees match.
Recursion is a great way to traverse one binary tree, by letting
the stack, stack pointer, and program counter do the lifting,
but it fails if you have two to traverse simultaneously... unless
you have two stacks, stack pointers, and program counters,
in which case you can do two recursions at once, in different goroutines.
[http://c2.com/cgi/wiki?SameFringeProblem]

Try to code the binary tree example without goroutines + channels,
or compare the recursive traversal with the implementation of the
C++ STL map::iterator, and you'll see the advantage. But they
do have a cost and they don't make sense for everything.
Walking a slice is one of those things.

Ultimately I think the exp/iterable package is a failed experiment,
or at least an unfortunate distraction, because it has led people to
use goroutines for walking through a slice, which is a bit like
hunting sparrows with a cannon. When a goroutine is really needed,
it's just as easy, and typically more convenient, to return a
chan int directly and not worry about the iterable package.

Russ

Reply all
Reply to author
Forward
0 new messages