Go channel race condition safety

[John Nagle]

- "Effective Go" says "Do not communicate by sharing memory;
instead, share memory by communicating." Then look at the
first example:

go func() {
list.Sort()
c <- 1
}()

"list" is shared between two goroutines, and no useful data is
sent over the channel. The "channel" is just being used for
locking, not data transmission. This is a clear case of "do what I
say, not what I do". Most of the channel examples in "Effective
Go" are like that.

This perpetuates a bad programming style, where data is locked
by a lock not associated with the data being locked. Consider "list"
above. The language doesn't indicate that "c" is the lock for "list".
That lack of association is a classic cause of race conditions.
Compare Ada monitors and Java "synchronized" objects, where lock
and data are tied together at the language level.

When I first saw Go channels, I thought there would be restrictions
on data sharing between goroutines. There aren't. Arguably,
shared objects should be either synchronized (in the Java sense)
or immutable (in the Python sense). That's safe. Go isn't.

How did that happen?

John Nagle

[Donovan Hide]

Do some more reading before making vast generalisations:

http://talks.golang.org/2012/concurrency.slide#1

http://golang.org/doc/articles/concurrency_patterns.html

http://golang.org/pkg/sync/

Also consider how many lines of code and imported libraries it would take to launch a unit of work on a separate CPU in Python or Java. Try writing some code in Go, you might enjoy it!

[Jan Mercl]

On Fri, Jan 18, 2013 at 7:25 PM, John Nagle <na...@animats.com> wrote:
> How did that happen?

The example you are dissecting (shown here:
http://golang.org/doc/effective_go.html#channels) is not an example of
any concurrent access to `list`. Also no concept of locking is
involved in this. I believe your objections are not valid.

Instead, this example, and it is explicitly written in the surrounding
text, exhibits how to do two _mutually unrelated_, _no memory sharing_
tasks concurrently and how to _synchronize one with the completion of
the other_ in an idiomatic way.

-j

PS: And yes, you can shoot yourself into the foot in Go. And you can
call it like 'Go isn't safe', if you will. Then maybe better choose a
"safe" language perhaps?

[andrey mirtchovski]

The example given in the channels section is not an example of "share
by communicating". The paragraph above the one you quoted contains the
gist: "Go encourages a different approach in which shared values are
passed around on channels and, in fact, never actively shared by
separate threads of execution."

To turn your example into a "share by communicating" one we would
write something possibly similar to:

c := make(chan *list)
go func() {
list.Sort()
c <- list
}()

[minux]

On Sat, Jan 19, 2013 at 2:25 AM, John Nagle <na...@animats.com> wrote:
> - "Effective Go" says "Do not communicate by sharing memory;
> instead, share memory by communicating." Then look at the
> first example:
>
> go func() {
> list.Sort()
> c <- 1
> }()
>
> "list" is shared between two goroutines, and no useful data is
> sent over the channel. The "channel" is just being used for
> locking, not data transmission. This is a clear case of "do what I
> say, not what I do". Most of the channel examples in "Effective
> Go" are like that.
>
> This perpetuates a bad programming style, where data is locked
> by a lock not associated with the data being locked. Consider "list"
> above. The language doesn't indicate that "c" is the lock for "list".
> That lack of association is a classic cause of race conditions.
> Compare Ada monitors and Java "synchronized" objects, where lock
> and data are tied together at the language level.

I'd argue that bundle lock with data doesn't prevent data race either,
firstly, if people know to provide locks then a lot data races would disappear.
secondly, some times a lock only protects a part of a larger data structure,
and to prevent concurrent use of that part, the compiler must give errors
for unlocked (un-synchronized) access, and that will require the language
to provide a way to do the lock-data association. However, Go is not that
kind of language.

Also, for your original example, i think the reason is pretty clear
why a channel
is preferable than a lock, because the concurrent access is localized
(in term of
code distance); that is, may be that the sort goroutine is the only
place that list
is concurrently accessed by another goroutine, and it's unwise to provide a
lock just for that.

[John Nagle]

On 1/18/2013 10:37 AM, Jan Mercl wrote:
> On Fri, Jan 18, 2013 at 7:25 PM, John Nagle <na...@animats.com> wrote:
>> How did that happen?
>
> The example you are dissecting (shown here:
> http://golang.org/doc/effective_go.html#channels) is not an example of
> any concurrent access to `list`.

The same variable is visible in two goroutines at the same time.
That's concurrent access.

> Instead, this example, and it is explicitly written in the surrounding
> text, exhibits how to do two _mutually unrelated_, _no memory sharing_
> tasks concurrently and how to _synchronize one with the completion of
> the other_ in an idiomatic way.

Wrong. "list" is shared between two goroutines. It happens
not to be used by both of them at the same time, but it's visible
to both.

To do this with no memory sharing, you'd send the entire
array over a channel, and get a sorted array back over a channel.
That would be doing this with "_no memory sharing_". Like this:

func sorttask(inchan chan []string, outchan chan []string) {
list := <- inchan // data received from sending task
sort.Strings(list) // sort
outchan <- list // results returnd to sending task
}

func dosort(in []string) []string {
inchan := make(chan []string)
outchan := make(chan []string)
go sorttask(inchan, outchan)
inchan <- in // data sent to sort task, sort starts
result := <- outchan // wait for data from sort task
return result
}

That demonstrates "Do not communicate by sharing memory; instead, share
memory by communicating." The example in "Effective Go" does
not.

Incidentally, don't be afraid of the "overhead" of copying data.
It's less than you would expect on modern x86 CPUs, unless the compiled
code is very bad. When you copy but use the data immediately, you don't
get cache misses and don't wait for the writeback to main RAM.
Short copies tend to be done entirely in the L1 cache. People
obsess over copying overhead, especially for message-passing
microkernels, but it just isn't that high in practice. I used
to write real-time code for QNX, where everything is done by
message passing. There's a measurable overhead, but it's
maybe 5-10% of total CPU time in practice. (Mach has
higher overhead for historical reasons.)

John Nagle

[Donovan Hide]

func sorttask(inchan chan []string, outchan chan []string) {
    list := <- inchan    // data received from sending task
    sort.Strings(list)   // sort
    outchan <- list      // results returnd to sending task
}

func dosort(in []string) []string {
    inchan := make(chan []string)
    outchan := make(chan []string)
    go sorttask(inchan, outchan)
    inchan <- in         // data sent to sort task, sort starts
    result := <- outchan // wait for data from sort task
    return result
}

Even in this example the invoker of dosort would have access to in []string while sorttask was executing, eg:

http://play.golang.org/p/FtChIu0JuR

Besides which the sort is in place, so you are just duplicating references to the same array backing the slice in three separate places! 

You are fighting against the language based on your experience of other languages. Try out some of the widely discussed patterns, they are truly useful :-)

[Donovan Hide]

Correction: The line:

inchan <- in 

does ensure in is locked, but then the invoker is blocked, so you lose all advantage of using a goroutine in dosort!

[Donovan Hide]

Maybe this what you are trying to achieve:

http://play.golang.org/p/rvpnS5C0U0

I think the point is that you can adopt whatever locking strategy you want for whatever you need to do. There are sharp knives in the drawer if you need them...

[John Nagle]

On 1/18/2013 4:24 PM, Donovan Hide wrote:
>> func sorttask(inchan chan []string, outchan chan []string) {
>> list := <- inchan // data received from sending task
>> sort.Strings(list) // sort
>> outchan <- list // results returnd to sending task
>> }
>>
>> func dosort(in []string) []string {
>> inchan := make(chan []string)
>> outchan := make(chan []string)
>> go sorttask(inchan, outchan)
>> inchan <- in // data sent to sort task, sort starts
>> result := <- outchan // wait for data from sort task
>> return result
>> }
>>
>
>
> Even in this example the invoker of dosort would have access to in []string
> while sorttask was executing,

Right. A slice is a reference and a send isn't a deep copy. It's
hard to not share memory across concurrency boundaries in this language.
More isolation by default would have been better.

The "do not communicate by sharing memory; instead, share memory by
communicating� line in "Effective Go" is misleading. Erlang has that
property. Go doesn't.

John Nagle

[Jesse McNelis]

On Jan 19, 2013 3:13 PM, "John Nagle" <na...@animats.com> wrote:
>    The "do not communicate by sharing memory; instead, share memory by

> communicating”  line in "Effective Go" is misleading.  Erlang has that
> property.  Go doesn't.

Erlang doesn't share memory. Go allows you to share memory by communicating. Erlang only lets you share values by communicating. Each has trade offs.

[Patrick Mylund Nielsen]

To be fair, sharing values by communicating in most languages with immutability isn't the same as sharing by communicating in languages with mutability. The former can just share the memory since it is guaranteed to not be modified--so it _is_ actually sharing memory because there's no risk. You just have a huge increase in memory allocations and gc pauses to worry about.

I wouldn't recommend passing around big structs with arrays inside on Go channels--just use channels to mediate when something is actually accessed, like you would a mutex. I think I agree that the sharing statement is a little misleading--copying everything is not what most people actually do.

--
 
 

[Ziad Hatahet]

On Fri, Jan 18, 2013 at 8:29 PM, Patrick Mylund Nielsen <pat...@patrickmylund.com> wrote:

You just have a huge increase in memory allocations and gc pauses to worry about.

What about an intermediate approach? Something like being able to prove at compile time that only a single reference owns the data at a time, such as via unique pointers (http://pcwalton.github.com/blog/2012/10/03/unique-pointers-arent-just-about-memory-management).
 

--
Ziad

[John Nagle]

On 1/18/2013 8:29 PM, Patrick Mylund Nielsen wrote:
> To be fair, sharing values by communicating in most languages with
> immutability isn't the same as sharing by communicating in languages with
> mutability. The former can just share the memory since it is guaranteed to
> not be modified--so it _is_ actually sharing memory because there's no
> risk.

I'd looked at that once as a possible direction for Python, in which
a wide range of objects are immutable. If all shared objects must be
either immutable or Java-type synchronized, race conditions are
eliminated. This looked like a way to get Python past the Global
Interpreter Lock bottleneck, which gets more embarrassing as everybody
gets more CPUs per chip.

(This was a few years ago, when Google's Unladen Swallow project
was supposed to make Python at least 5x faster and eliminate the GIL.
That project failed. It may be time to look at this again. Amusingly,
the direction Python has gone is to discourage threading and to use
separate communicating processes instead. That's really heavyweight
threading; each task has a Python interpreter and all the libraries.)

It's better to have deadlocks than race conditions. If you have
a deadlock, you known you have a deadlock. Race conditions manifest
themselves as intermittent, difficult to reproduce defects.

(Early in my career, I used to debug mainframe operating systems from
crash dump information. Finding race conditions in large bodies of code
written by others is a slow, painful experience. Relying on "patterns"
to avoid this is not good enough in practice.)

John Nagle

[John Nagle]

That's a reasonable idea. It shows up regularly in C++ libraries,
"auto_ptr" being the original implementation. Thinking circa 2008
can be seen here:
http://stackoverflow.com/questions/94227/smart-pointers-or-who-owns-you-baby
It never quite works in C++; raw pointers keep leaking out because
they're needed for system calls and such.

The three big questions in C/C++:
How big is it? (the cause of buffer overflows)
Who owns it? (the cause of dangling pointers)
Who locks it? (the cause of race conditions.)
C and C++ require the programmer to obsess on those issues but
provide little help in dealing with them.

Go fixes the first two, but not the third. In a language with
garbage collection, you don't need to be so explicit about ownership
for allocation purposes. Ownership for locking purposes, though,
remains an open question in Go. Monitors, as with the Ada rendezvous,
explicitly address "who has this data locked right now". Go
doesn't have that.

John Nagle

[Patrick Mylund Nielsen]

Definitely. Funny--the article mentions CSP, and Rob Pike's quote, then goes on to enumerate the manifestations:

> There are three simple ways to do this:

>

> 1. Copy all messages sent from actor to actor. Changes that one actor makes to the contents of any message do not affect the other actors’ copies of  the message.

>

> 2. Require that all messages sent from actor to actor be immutable. No actor may make changes to any message after it’s created.

>

> 3. Make messages inaccessible to the sender once sent–senders “give away” their messages. Only one actor may mutate a message at any given time.

#3 is the key take-away when this adage is applied to Go, IMO: if you pass pointers on channels, and don't keep a reference to them, you are giving them away. Granted, the "don't use it after giving it away" part isn't enforced, and it is sharing memory, but if you are reasonably disciplined and use channels, it's harder to run into the problems often faced when using locks! Yes, #1 is also possible, but far less common for anything but simple or reference types (which are sharing memory anyway.)

Unique pointers could have been interesting. However, I have not yet felt that I needed them.

[Ian Lance Taylor]

On Fri, Jan 18, 2013 at 9:02 PM, John Nagle <na...@animats.com> wrote:
>
> The three big questions in C/C++:
> How big is it? (the cause of buffer overflows)
> Who owns it? (the cause of dangling pointers)
> Who locks it? (the cause of race conditions.)
> C and C++ require the programmer to obsess on those issues but
> provide little help in dealing with them.
>
> Go fixes the first two, but not the third. In a language with
> garbage collection, you don't need to be so explicit about ownership
> for allocation purposes. Ownership for locking purposes, though,
> remains an open question in Go. Monitors, as with the Ada rendezvous,
> explicitly address "who has this data locked right now". Go
> doesn't have that.

It's easy to implement an Ada-style rendezvous or a monitor in Go.
The difference is that Go also permits other synchronization
mechanisms.

You're quite right, of course, that Go does not eliminate race
conditions. I do not know of a language that eliminates race
conditions in a satisfactory manner, at least not in the context of a
deliberately non-functional language like Go. I would certainly like
to hear of one. But note that I do not consider the ability to mark a
specific type as requiring, or automatically using, a lock to be
satisfactory, as the idea does not extend to more complex data
structures.

At least Go does have a very strong dynamic race detector
(http://tip.golang.org/doc/articles/race_detector.html). Go is hardly
perfect in this area. But given that perfection has not yet been
shown to be feasible, Go is not bad.

Ian

[Rob Pike]

On Fri, Jan 18, 2013 at 8:13 PM, John Nagle <na...@animats.com> wrote:
> The "do not communicate by sharing memory; instead, share memory by

> communicating” line in "Effective Go" is misleading. Erlang has that
> property. Go doesn't.

We don't claim Go has that property. Instead, we assert that the
language works best if your programs have that property. It's a motto,
not a feature.

-rob

[Kevin Gillette]

Certainly a good point. An additional consideration, however: in any imperative language -- Java, Python, Go, and so on -- regardless of the availability and good-faith use of implicitly synchronized data-structures, data races will still be a possibility. In CPython, as long as the GIL is present, there is no possibility of data corruption, regardless of how many "threads" are mutating any type of container, yet data races can indeed occur.

That reason is one way of justifying Go's approach: it was not out of laziness or ignorance that neither the Go language, nor its stdlib, provides self-synchronized containers: since a programmer must always be mindful of races when writing concurrent code (though such issues are exceptionally easy to avoid in Go), it would have been entirely insufficient to make, for example, a map implicitly concurrent-safe and say "your containers synchronize themselves, so now you can stop worrying." Additionally, Go is often used for non-concurrent programming, or cases where containers are used internally by goroutines, and shared in no way. Because of this and the emphasis on programmer responsibility (as mentioned above), it is hard to argue that the builtin structures should have mandated synchronization, since fine-grained locks cost a lot of runtime overhead when their shared access may need to be protected by higher level locks or channel synchronization anyway.

Go's strategy is: don't give the programmer features that would be readily abused, but at the same time, don't assume the programmer will abuse the minimum set of tools that are really needed by making the runtime beat competent programmers over the head with a stick just to make them wear the same protective gloves that other, safe-in-appearances languages, mandate so that the weakest link in a team can still have a place in the chain.  Go has been noted on several occasions for being both an individually productive language, as well as a language that works well for teams of like-minded programmers, and not only that, but concurrency is extremely easy and readily safe, as long as you know what you're doing (and if you don't know what you're doing, Go's concurrency model is much less of a disaster for novices than a traditional threading model, since unlike explicit threading, csp-style concurrency is trivial to reason about).

[Donovan Hide]

Another frivolous example of a parallel sort that is easier to distribute over multiple CPU's (the standard library sort is quicksort, so doing this isn't actually that useful!):

http://play.golang.org/p/R4nLlE69EZ

If you were unable to share memory then you'd have to copy each slice of data as you descended up the recursive stack. Shared memory is useful when you do things concurrently on the same data and channels are a good tool to guard against doing two things to the same part at the same time. Slices and also good at guarding, because you can impose limits by reslicing and thereby partition work to different goroutines.

I think Go and its library is an excellent toolkit for trying out different concurrent ideas quickly and with few lines of code. Yes, you can write code that races and deadlocks, but it's a lot easier to find the problems than stepping through a thread in gdb with scheduler-locking on :-)

[Jan Mercl]

On Sat, Jan 19, 2013 at 12:03 PM, Donovan Hide <donov...@gmail.com> wrote:
> the standard library sort is quicksort

FYI: tip is auto-switching between {heap,insertion,quick}sort.

-j

[Donovan Hide]

FYI: tip is auto-switching between {heap,insertion,quick}sort.

Not sure that was a tip innovation:

http://golang.org/src/pkg/sort/sort.go#L163

The point I was making was simply that doing a parallel sort, like in the example, would only be useful for an algorithm that gains from data being pre-sorted,  ie. mergesort, timsort, ....

[Kevin Gillette]

Even if the assumption that the algo would be used on a system with multiple cpu's does not hold up (or the algorithm never gets more than one of those), the overhead cost of those goroutines with a large enough work unit will be negligible.

[Thomas Bushnell, BSG]

No. Access and visibility are not the same thing.

--

[John Nagle]

On 1/18/2013 10:45 PM, Rob Pike wrote:
> On Fri, Jan 18, 2013 at 8:13 PM, John Nagle <na...@animats.com> wrote:
>> The "do not communicate by sharing memory; instead, share memory by

>> communicating� line in "Effective Go" is misleading. Erlang has that

>> property. Go doesn't.
>
> We don't claim Go has that property. Instead, we assert that the
> language works best if your programs have that property. It's a motto,
> not a feature.

This is what "Effective Go" says:

"Concurrent programming in many environments is made difficult by the
subtleties required to implement correct access to shared variables. Go

encourages a different approach in which shared values are passed around
on channels and, in fact, never actively shared by separate threads of

execution. Only one goroutine has access to the value at any given time.
Data races cannot occur, by design. To encourage this way of thinking we
have reduced it to a slogan:

Do not communicate by sharing memory; instead, share memory by
communicating."

Again, this is what is claimed for Go:

"ONLY ONE GOROUTINE HAS ACCESS TO THE VALUE AT ANY GIVEN TIME. DATA
RACES CANNOT OCCUR, BY DESIGN."

That statement is false.

The author of Effective Go has a bright future writing advertising
copy.

John Nagle

[Kevin Gillette]

Put a semicolon immediately before the passage you capitalized, and then you'll see it's describing not the language, but characteristics of the ”approach” we're encouraging. Such an approach is facilitated by the language, not mandated.

[Ian Lance Taylor]

On Jan 19, 2013 7:56 AM, "John Nagle" <na...@animats.com> wrote:
>
> On 1/18/2013 10:45 PM, Rob Pike wrote:
> > On Fri, Jan 18, 2013 at 8:13 PM, John Nagle <na...@animats.com> wrote:
> >> The "do not communicate by sharing memory; instead, share memory by

> >> communicating”  line in "Effective Go" is misleading.  Erlang has that

> >> property.  Go doesn't.
> >
> > We don't claim Go has that property. Instead, we assert that the
> > language works best if your programs have that property. It's a motto,
> > not a feature.
>
> This is what "Effective Go" says:
>
> "Concurrent programming in many environments is made difficult by the
> subtleties required to implement correct access to shared variables. Go
> encourages a different approach in which shared values are passed around
> on channels and, in fact, never actively shared by separate threads of
> execution. Only one goroutine has access to the value at any given time.
> Data races cannot occur, by design. To encourage this way of thinking we
> have reduced it to a slogan:
>
>     Do not communicate by sharing memory; instead, share memory by
> communicating."
>
> Again, this is what is claimed for Go:
>
> "ONLY ONE GOROUTINE HAS ACCESS TO THE VALUE AT ANY GIVEN TIME. DATA
> RACES CANNOT OCCUR, BY DESIGN."
>
> That statement is false.
>
> The author of Effective Go has a bright future writing advertising
> copy.

You are misreading the plain meaning of the text ("Go encourages a different approach," not "enforces").  Why?

Ian

[minux]

On Sun, Jan 20, 2013 at 1:55 AM, John Nagle <na...@animats.com> wrote:

On 1/18/2013 10:45 PM, Rob Pike wrote:
> On Fri, Jan 18, 2013 at 8:13 PM, John Nagle <na...@animats.com> wrote:
>> The "do not communicate by sharing memory; instead, share memory by

>> communicating”  line in "Effective Go" is misleading.  Erlang has that

>> property.  Go doesn't.
>
> We don't claim Go has that property. Instead, we assert that the
> language works best if your programs have that property. It's a motto,
> not a feature.

This is what "Effective Go" says:

"Concurrent programming in many environments is made difficult by the
subtleties required to implement correct access to shared variables. Go

encourages a different approach in which shared values are passed around
on channels and, in fact, never actively shared by separate threads of

execution. Only one goroutine has access to the value at any given time.
Data races cannot occur, by design. To encourage this way of thinking we
have reduced it to a slogan:

    Do not communicate by sharing memory; instead, share memory by

communicating."

Again, this is what is claimed for Go:

"ONLY ONE GOROUTINE HAS ACCESS TO THE VALUE AT ANY GIVEN TIME. DATA
RACES CANNOT OCCUR, BY DESIGN."

That statement is false.

You're interpreting sentences out of their context.

That sentence doesn't claim Go automatically guarantee that, it says that by using

the aforementioned techniques, only one goroutine has access to the value at any

given time.

I'm really confused about what are you trying to arguing for.

[Jan Mercl]

21 hours late forward to list :-(

---------- Forwarded message ----------
From: Jan Mercl <0xj...@gmail.com>
Date: Fri, Jan 18, 2013 at 9:17 PM
Subject: Re: [go-nuts] Go channel race condition safety
To: na...@animats.com


On Fri, Jan 18, 2013 at 8:56 PM, John Nagle <na...@animats.com> wrote:
> On 1/18/2013 10:37 AM, Jan Mercl wrote:

>> On Fri, Jan 18, 2013 at 7:25 PM, John Nagle <na...@animats.com> wrote:
>>> How did that happen?
>>
>> The example you are dissecting (shown here:
>> http://golang.org/doc/effective_go.html#channels) is not an example of
>> any concurrent access to `list`.
>
> The same variable is visible in two goroutines at the same time.
> That's concurrent access.

Concurrent access cannot exist without access. Visibile != accessed.
You probably mean, that the two goroutines _may_ perform concurrent
access. Of course. Go's memory model is shared memory and as I said
before, you can shoot yourself into the foot. IOW, it's easy to crash
a Go program. Would the language (type and memory safe) be also race
conditions safe, it would incur some nonzero run time performance
penalties. Which are a waste of resources when not actually needed. As
in the example we are discussing. It's a design choice of the Go
authors and as any language design choice - it's a compromise. No free
lunches exist.

>> Instead, this example, and it is explicitly written in the surrounding
>> text, exhibits how to do two _mutually unrelated_, _no memory sharing_
>> tasks concurrently and how to _synchronize one with the completion of
>> the other_ in an idiomatic way.
>
> Wrong. "list" is shared between two goroutines. It happens
> not to be used by both of them at the same time, but it's visible
> to both.

Never concurrently. So it's safe. Actually non mutating concurrent
access is safe too, BTW. And synchronized concurrent mutating too.
Concurrency is not evil per se. Bad concurrent code is the problem. Or
bad tool to handle it which put a too much burder on the coder to make
it right. In Go it's much simpler than in, say C or Java.
Locking/unlocking/mutexes/thred-join, wait... This way there are so
many ways to deadlock and have next to zero ideas why. Reasoning about
channels is easier, still people ask many questions on the list - some
of the questions are quite lame.

> To do this with no memory sharing, you'd send the entire
> array over a channel, and get a sorted array back over a channel.
> That would be doing this with "_no memory sharing_". Like this:

That's a misconception. "Don't X by sharing memory..." doesn't mean
there should be no shared memory anywhere. But one should not
concurrently mutate things w/o synchronization (not specific to Go,
BTW).

> func sorttask(inchan chan []string, outchan chan []string) {
> list := <- inchan // data received from sending task
> sort.Strings(list) // sort
> outchan <- list // results returnd to sending task
> }
>
> func dosort(in []string) []string {
> inchan := make(chan []string)
> outchan := make(chan []string)
> go sorttask(inchan, outchan)
> inchan <- in // data sent to sort task, sort starts
> result := <- outchan // wait for data from sort task
> return result
> }
>

> That demonstrates "Do not communicate by sharing memory; instead, share

> memory by communicating." The example in "Effective Go" does
> not.

This demonstrates a serious over engineering wrt what the linked
example tried to communicate.

> Incidentally, don't be afraid of the "overhead" of copying data.
> It's less than you would expect on modern x86 CPUs, unless the compiled
> code is very bad. When you copy but use the data immediately, you don't
> get cache misses and don't wait for the writeback to main RAM.
> Short copies tend to be done entirely in the L1 cache. People
> obsess over copying overhead, especially for message-passing
> microkernels, but it just isn't that high in practice. I used
> to write real-time code for QNX, where everything is done by
> message passing. There's a measurable overhead, but it's
> maybe 5-10% of total CPU time in practice. (Mach has
> higher overhead for historical reasons.)

If I pass things above simple numbers/booleans through a channel, I
pass pointers to such more complex data. Then one just doesn't touch
that pointer afterwards on the sending side. As well as on the
receiving side the pointer is used only when received from a channel.
In such way the (concept of) ownership is safely _transferred_. The
remaining part of the safe concurrent _solution_ is simply a
discipline. In Go that discipline is easy to reason about, so it's not
a big deal. And again, it _is_ a compromise. And also already set in
stone, you know ;-)

-j

[André Moraes]

On Fri, Jan 18, 2013 at 6:02 PM, John Nagle <na...@animats.com> wrote:
> On 1/18/2013 10:37 AM, Jan Mercl wrote:
>> On Fri, Jan 18, 2013 at 7:25 PM, John Nagle <na...@animats.com> wrote:
>>> How did that happen?
>>
>> The example you are dissecting (shown here:
>> http://golang.org/doc/effective_go.html#channels) is not an example of
>> any concurrent access to `list`.
>
> The same variable is visible in two goroutines at the same time.
> That's concurrent access.

No, and this is a BIG NO.

This is an example that "concurrent access CAN HAPPEN". You can't see
the code for "DoSomethingForAWhile()" and the text explains that no
access to list will happen.

In order to have concurrent access you MUST FIRST ACCESS the memory,
which isn't happening.

>> Instead, this example, and it is explicitly written in the surrounding
>> text, exhibits how to do two _mutually unrelated_, _no memory sharing_
>> tasks concurrently and how to _synchronize one with the completion of
>> the other_ in an idiomatic way.
>
> Wrong. "list" is shared between two goroutines. It happens
> not to be used by both of them at the same time, but it's visible
> to both.

You can have two process, running in the same machine, all memory is
visible to everyone (you just need a bug in kernel). But you don't
keep saying that every process is sharing memory or doing concurrent
access to the same memory address.

>
> To do this with no memory sharing, you'd send the entire
> array over a channel, and get a sorted array back over a channel.
> That would be doing this with "_no memory sharing_". Like this:
>
> func sorttask(inchan chan []string, outchan chan []string) {
> list := <- inchan // data received from sending task
> sort.Strings(list) // sort
> outchan <- list // results returnd to sending task
> }
>
> func dosort(in []string) []string {
> inchan := make(chan []string)
> outchan := make(chan []string)
> go sorttask(inchan, outchan)
> inchan <- in // data sent to sort task, sort starts
> result := <- outchan // wait for data from sort task
> return result
> }
>
> That demonstrates "Do not communicate by sharing memory; instead, share
> memory by communicating." The example in "Effective Go" does
> not.

In fact, the array used as store to the slice are shared by everybody
with pointers to that array. So an append operation in one goroutine
can affect the other one (if the append uses the same array).

>
> Incidentally, don't be afraid of the "overhead" of copying data.
> It's less than you would expect on modern x86 CPUs, unless the compiled
> code is very bad. When you copy but use the data immediately, you don't
> get cache misses and don't wait for the writeback to main RAM.
> Short copies tend to be done entirely in the L1 cache. People
> obsess over copying overhead, especially for message-passing
> microkernels, but it just isn't that high in practice. I used
> to write real-time code for QNX, where everything is done by
> message passing. There's a measurable overhead, but it's
> maybe 5-10% of total CPU time in practice. (Mach has
> higher overhead for historical reasons.)

If you prefer to copy memory, use array's instead of slices, and
structs instead of pointer to structs. Go can do that too.

--
André Moraes
http://amoraes.info

[Ziad Hatahet]

On Fri, Jan 18, 2013 at 10:43 PM, Ian Lance Taylor <ia...@google.com> wrote:

  But given that perfection has not yet been
shown to be feasible, Go is not bad.

Ian

 

Wouldn't you consider using unique pointers, or immutable types to be "closer to perfection" than the status quo that Go employs?

--
Ziad

[Kevin Gillette]

I'd have done: http://play.golang.org/p/-WKC4gnvyg (only half the number of goroutines are needed to achieve precisely the same effect). This (and the original) does have the unfortunate aspect that the 'merge' does not know that the input consists of two already sorted sub-sequences.

[Kevin Gillette]

Those sacrifice control, and can be emulated through voluntary use of other techniques already available in Go. Self-discipline is an excellent substitute for manacles; if a programmer is incapable of exercising self-discipline, then use of other languages may be a far better choice.

[Ziad Hatahet]

On Sat, Jan 19, 2013 at 11:16 AM, Kevin Gillette <extempor...@gmail.com> wrote:

Those sacrifice control, and can be emulated through voluntary use of other techniques already available in Go. Self-discipline is an excellent substitute for manacles; if a programmer is incapable of exercising self-discipline, then use of other languages may be a far better choice.

I agree that self discipline is very important; however, things do tend to get messy in large code bases (which Go seems to target by described as being "scalable"). Otherwise, why is it okay for the compiler/language to disallow unused variables, but not provide any mechanism for disallowing calls to mutation methods?

I can see how it is possible to emulate to a certain extent immutable types in Go, but how would you emulate unique pointers?

--
Ziad

 

[Jan Mercl]

On Sat, Jan 19, 2013 at 8:57 PM, Ziad Hatahet <hat...@gmail.com> wrote:
> I agree that self discipline is very important; however, things do tend to
> get messy in large code bases (which Go seems to target by described as
> being "scalable"). Otherwise, why is it okay for the compiler/language to
> disallow unused variables, but not provide any mechanism for disallowing
> calls to mutation methods?

Because the later is equivalent to the halting problem?

-j

[John Nagle]

On 1/19/2013 11:16 AM, Kevin Gillette wrote:> Those sacrifice control,

and can be emulated through voluntary use of other
> techniques already available in Go. Self-discipline is an excellent
> substitute for manacles; if a programmer is incapable of exercising
> self-discipline, then use of other languages may be a far better choice.

That's a classic view. Hoare and Dijkstra are the leaders of the
"Programming is hard" (and Programmers should Suffer for their Art)
school. Contrast "Programming is hard, let's go scripting", which
is a quote from Larry Wall, of Perl fame.

Too much code to be written to have much of it written by people
with the theoretical background to get it right from basic principles.
The language has to keep them out of trouble. The consequences of
mistakes must be obvious, rather than subtle.

Go is being promoted as something as easy to use as Javascript,
Perl, or Python. But it's not yet as safe. This is a problem.

John Nagle

[Ziad Hatahet]

On Sat, Jan 19, 2013 at 11:59 AM, Jan Mercl <0xj...@gmail.com> wrote:

Because the later is equivalent to the halting problem?

-j

See C++'s const, D's const/immutable, and Rust's immutable references.

--
Ziad

[Jan Mercl]

On Sat, Jan 19, 2013 at 9:05 PM, John Nagle <na...@animats.com> wrote:
> Go is being promoted as something as easy to use as Javascript,
> Perl, or Python. But it's not yet as safe. This is a problem.

Go is type-safe (but it can be bypassed).
Go is memory-safe (but it can bypassed).
Go is not bad-coders safe (and they cannot be avoided).

-j

[Kevin Gillette]

JavaScript has only recently in its history (since the invention of firebug and other equivalents) started becoming something that you can call "easy to use", though that property for that language in particular breaks down at an exponential rate relative to code volume. Go is mostly geared at being easy to write, but easier to read. Of the three you mentioned, only (sensible) python has a reasonable chance of claiming to be readily readable; js can usually be read by the original programmer, but often not by anyone else (often a side effect of the callback-based programming), and perl is widely regarded as being a write-once-read-never language (though self-discipline can mitigate this, though culturally, the propensity for obfuscation in perl is often taken to be a badge of honor by those who accept it).

I can't imagine how you'd possibly expect to defend the claim that "Go is not yet as safe as Javascript, Perl, or Python"

[Kevin Gillette]

I believe Jan was referring to disallowing calls to mutation methods, in general, in a language with a shared memory model.

[Jan Mercl]

On Sat, Jan 19, 2013 at 9:14 PM, Ziad Hatahet <hat...@gmail.com> wrote:
>
> On Sat, Jan 19, 2013 at 11:59 AM, Jan Mercl <0xj...@gmail.com> wrote:
>>
>> Because the later is equivalent to the halting problem?
>

> See C++'s const, D's const/immutable, and Rust's immutable references.

Let me re-quote the context:

> ... but not provide any mechanism for disallowing
> calls to mutation methods?

Which is orthogonal to const/immutable modifiers.

-j

[minux]

On Sun, Jan 20, 2013 at 4:05 AM, John Nagle <na...@animats.com> wrote:

   Go is being promoted as something as easy to use as Javascript,
Perl, or Python.  But it's not yet as safe.  This is a problem.

That's the price to pay for a practical system programming language.

If a system language has pointers, then you can always shoot yourself

in the foot by dereference the null pointer, and thus you can say it's

not a safe programming language as Javascript, Perl or Python are.

Yet, pointers are essential for a system programming language.

Nobody is saying Go is safe language in this regard (in fact, more than one

people have already pointed this out in this thread), so what's your point?

One more point, where did you get the illusion that "Go is being promoted as

something as easy to use Javascript, Perl, or Python."?

In fact, golang.org/doc says:

"It's a fast, statically typed, compiled language that *feels like* a dynamically

typed, interpreted language."

I don't believe any official Go documents claim that.

[minux]

On Sun, Jan 20, 2013 at 4:14 AM, Ziad Hatahet <hat...@gmail.com> wrote:

On Sat, Jan 19, 2013 at 11:59 AM, Jan Mercl <0xj...@gmail.com> wrote:

Because the later is equivalent to the halting problem?

See C++'s const, D's const/immutable, and Rust's immutable references.

But do they solve the whole problem of writing concurrent software?

If not, why does Go have to adopt these incomplete solutions?

Maybe there are better solutions in the future, why not wait and see?

[Kevin Gillette]

Since Go is memory safe, a nil pointer deref is not 'unsafe' anymore than trying to call a method at runtime that isn't defined on an object in one of those other languages, or any number of their runtime errors that would have been caught at compile time in Go. Pointers in Go are extremely safe compared to pointers in languages like C.

[Ian Lance Taylor]

They might help, sure. But they don't solve the problem. Whether to
add them to Go requires considering whether the benefits they bring
are worth the additional complexity in the language.

In my opinion, unique pointers are not particularly easy to use
correctly. Using them requires a certain programming discpline--and
if you already have that discipline, then you don't need them. The
benefit they bring is dynamic enforcement of the required discipline.
It's a real benefit. On the other hand, a language like Go is not
going to require that all pointers be unique. So unique pointers
would be an additional concept to Go. Do they carry the weight of the
additional complexity in a relatively simple language? I don't know.

I personally would be happy to have immutable objects in Go. Right
now you can implement them by not exporting them from a package, but
it's somewhat awkward. I'm not sure about immutable types. I think
it's clear that Go should not have a const type qualifier, much less a
mutable qualifier. I don't know how to add immutable types without
getting into those difficulties.

Again, these additional concepts would not mean that Go programs were
free of race conditions. There are many incremental improvements we
can make to the language, and each improvement carries a cost in
complexity. The language is relatively simple and relatively small,
and that is in itself a goal worth striving for.

Ian

[Ziad Hatahet]

On Sat, Jan 19, 2013 at 12:31 PM, minux <minu...@gmail.com> wrote:

But do they solve the whole problem of writing concurrent software?

If not, why does Go have to adopt these incomplete solutions?

Maybe there are better solutions in the future, why not wait and see?

True, but I would not really call them "incomplete"; hopefully a step in the right direction. I am hoping once languages that adopt those features become more widespread, we will have empirical results on which to base conclusions.

On Sat, Jan 19, 2013 at 12:22 PM, minux <minu...@gmail.com> wrote:

> That's the price to pay for a practical system programming language.

> If a system language has pointers, then you can always shoot yourself

> in the foot by dereference the null pointer, and thus you can say it's

> not a safe programming language as Javascript, Perl or Python are.

Unless the systems programming language does away with null pointers in the first place ;) Rust is taking this approach.

> Yet, pointers are essential for a system programming language.

Pointers most likely are, but null pointers are probably not.

--
Ziad

[Steven Blenkinsop]

On Sunday, 20 January 2013, Ziad Hatahet wrote:

Unless the systems programming language does away with null pointers in the first place ;) Rust is taking this approach.

Most languages that get rid of those pesky null pointers can still throw index out of bounds, in my experience. Such languages aren't somehow safer, they just change one particular runtime check into a compile time check, while leaving other runtime checks in place. Whether you perform a check at compile time or runtime has nothing to do with memory safety.

Because of the difficulty in statically ensuring the necessary invariants to make their system memory safe without it being too restrictive, the Rust devs are now making it so that the mutability of managed pointers is checked at runtime. Misusing managed pointers will be able to cause a crash at runtime, and for reasons somewhat more complex than whether a pointer is null. Ultimately, it's *always* about tradeoffs.

[John Nagle]

On 1/19/2013 1:18 PM, Kevin Gillette wrote:
> Since Go is memory safe,

It's not, when there is concurrency. See

http://research.swtch.com/gorace

for a detailed discussion of the failure of memory safety in
concurrent Go programs. There's an example program you can run.

John Nagle

[Jan Mercl]

False statement. The Go language _is_ memory safe. The specific
implementation discussed _is not_ and it is very clearly written in
the article _you_ referenced. Actually as soon as in the _third_
sentence:

[Q]
Go is defined to be a safe language. Indices into array or string
references must be in bounds; there is no way to reinterpret the bits
of one type as another, no way to conjure a pointer out of thin air;
and there is no way to release memory, so no chance of “dangling
pointer” errors and the associated memory corruption and instability.

[B]In the current Go implementations, though, there are two ways to
break through these safety mechanisms.[/B] The first and more direct
way is to use package unsafe, specifically unsafe.Pointer. The second,
less direct way is to use a data race in a multithreaded program.
[/Q]

("emphasizes" mine)

I wonder how you could have missed that.

-j

[Kevin Gillette]

I think it's still easy to miss a lot of these semantics when learning Go. When I first looked into Go just over a year ago, after a few hours of browsing through golang.org documents and linked articles, it wasn't even clear that gccgo was separate from gc. Also, the wider realm of Go does have some aspects that are without spec and implementation defined, such as gofmt, and I had to do quite a big of digging to figure out how GOPATH worked. We've certainly improved, but we've still got a ways to go in terms of consolidating and organizing documentation before these concerns can be fully approachable to newcomers.

[Patrick Mylund Nielsen]

The fact that GOMAXPROCS > 1 is potentially unsafe is not very clear, indeed.

--
 
 

[John Nagle]

On 1/19/2013 9:37 PM, Ian Lance Taylor wrote:
> On Sat, Jan 19, 2013 at 11:46 AM, John Nagle <na...@animats.com> wrote:
>> On 1/19/2013 10:25 AM, Ian Lance Taylor wrote:
>>> On Jan 19, 2013 8:18 AM, "John Nagle" <na...@animats.com> wrote:

> We've thought quite a bit about how we could avoid race conditions.
> We have not thought of a way to do it without sacrificing other
> essential aspects of the language. If you have suggestions, let us
> know.
...

> "Do not communicate by sharing memory; instead, share memory by

communicating" is presented (as) a slogan...

OK. Let's take it seriously, as an enforced feature, and see
where that takes us.

There are two main reasons sharing memory across concurrency
boundaries are considered useful - for performance, and for
explicit shared state. Let's look at the performance issue
first.

If you don't need shared state, copying all the data being
sent across concurrency boundaries works fine. The Python
multiprocessing system does that, even on the same CPU.
The overhead is high, but the functionality is usable.

That could be done in Go. Just do a deep copy of
anything sent on a channel, or passed into a goroutine.
This would break some programs, especially ones based
on the examples in "Effective Go". A slightly different
style is required, but it's not harder, just different.
Like this, for the sort example:

//
// Sort array of strings in background
//

func sorttask(inchan chan []string, outchan chan []string) {
list := <- inchan

sort.Strings(list)
outchan <- list // This would be a deep copy
}

func dosort() []string {

inchan := make(chan []string)
outchan := make(chan []string)

strs := make([]string, 0) // build up a string locally
strs = append(strs,"Hello")
strs = append(strs,"to")
strs = append(strs,"the")
strs = append(strs,"World")
go sorttask(inchan, outchan)
inchan <- in // This would be a deep copy.
result := <- outchan
return result
}

Now we have soundness, but it's cost us some copying.
Can those copies be optimized out? Yes.

The optimization needed here is like tail recursion.
If the last access to a reference before it goes out of
scope is a send, then it need not be copied. In
the example above, both deep copies can be optimized out.

From the programmer perspective, this optimization is
invisible. As with tail recursion, it's valuable for
programmers to know this is going on, and it should
be guaranteed to the programmer that this happens in the
simple cases.

This covers one of the major use cases in server-side
programming - a program makes multiple requests to
other servers and databases to collect data to build
up a reply page. Making those requests in parallel is necessary
for performance. The reply is usually much bigger than the
query, so copying it is undesirable.

The concurrent code which services the requests has no further need of
the data once it's been passed back to the requester. So
the last act of each service goroutine should be to send the
big result on the reply channel. It won't have to be copied.
There's no performance penalty for the safe approach.

So that's a way of addressing the performance issue.

Accessing shared state is tougher. But Go gives us some
tools for that. Channels are explicitly concurrency-safe,
and it's permitted to pass a channel over a channel.
So you can do proxy-type operations, where a concurrent
operation is passed channels by which it can communicate
with some some central state. This is kind of clunky,
but sound. Perhaps it could be packaged in some way
that makes it look more like a function call. Take
a look at the Python multiprocessing module

http://docs.python.org/2/library/multiprocessing.html#module-multiprocessing

"16.6.1.4. Sharing state between processes".

That provides two mechanisms - proxy objects, and atomic maps.

Some programmer-friendly way to do proxy objects, where there
are really two channels but it looks like a function call,
could substitute for shared state and mutexes.

Atomic maps are worth having available. Not all maps need to
be atomic, but atomic map types don't have to be deep-copied and
can be shared. So atomic maps become the preferred mechanism
for storing shared state. (However, data put into an atomic
map may have to be deep-copied. This prevents leaking a
reference over a concurrency boundary).

This is a true "share memory by communicating" approach.
One with less overhead, no race conditions, and no need
for user mutexes.

Comments?

John Nagle

[minux]

On Tue, Jan 22, 2013 at 2:45 AM, John Nagle <na...@animats.com> wrote:

Now we have soundness, but it's cost us some copying.
Can those copies be optimized out?  Yes.

The optimization needed here is like tail recursion.
If the last access to a reference before it goes out of
scope is a send, then it need not be copied.  In
the example above, both deep copies can be optimized out.

From the programmer perspective, this optimization is
invisible.  As with tail recursion, it's valuable for
programmers to know this is going on, and it should
be guaranteed to the programmer that this happens in the
simple cases.

No. IMO, not guaranteed optimization == no optimization at all or

even worse.

If we can't make the guarantee to make this kind of optimization always

happen, what should the programmer with performances in mind do?

either he tries to work around the compiler inefficiency (this ties the code

to one particular compiler implementation, because the work around might

not be valid in another implementation), or he just bypasses the restriction

and use unsafe operation to get the non-deep-copy semantics he wants.

Both of the outcomes are bad, and more importantly, IMO, it's even worse

than we make no enforcement thus no thus guarantee at all.

For example, the C standard doesn't guarantee tail recursion elimination,

so what happens? To write portable code, we are forced to assume that

tail recursions aren't eliminated at all, thus this view discourages the usage

of tail recursions. Alternatively, we stick to one compiler that does this (for

example, GCC, however, IIRC, even GCC doesn't guarantee that).

That's why Scheme mandate tail recursion elimination because it's truly

essential to Lisp.

Is this feature essential enough to make all the potential compiler writers

willing to make the guarantee? I certainly doubt that.

This covers one of the major use cases in server-side
programming - a program makes multiple requests to

Go is a general purpose programming language. It's not at all tied to programming

in the server-side.

Also, not all server-side processing follows the pattern of bigger reply than

request, think, for example, the video uploading stage of youtube.

I certainly don't agree to make Go more appealing to some programmers

while make it painfully slow for programmers in other fields.

This is not Go. We don't mandate a single true way of thinking

(because there isn't, or there will be already languages doing that.

for example, I think Erlang fits your description well)

[Donovan Hide]

I've used the Python multiprocessing package a lot for web-scraping and found it to be very clunky indeed :-) Python is so bad at freeing resources that the module has a maxtasksperchild for each Pool to kill the process after a certain number of tasks:

http://docs.python.org/2/library/multiprocessing.html#module-multiprocessing.pool

The whole idea of using a complete new process to bypass the GIL highlight the shortcoming of Python as a concurrent language. The proxies and atomic maps provided by multiprocessing are themselves guarded by a separate Manager process. I don't know the mechanics of how exactly the memory is shared between the processes, but I doubt it is as efficient as passing a pointer to a struct through a channel with a mutex field to guard it.

So borrowing ideas from multiprocessing doesn't seem like a great starting point. Erlang is a more interesting comparison point because you can't actually change a variable in a function, which gives you the absolute safety you seem to demand. But then you have to live with a functional programming style, which is good for some things but not others.

I think a lot of your examples you show indicate you might not have played around with Go too much. It might be better to pose the real problem you are trying to solve and them I'm sure the collective intelligence of this mailing list would definitely offer you a panoply of different solutions to your task at hand :-)

                                John Nagle

--

[John Nagle]

On 1/21/2013 11:19 AM, Donovan Hide wrote:
> I've used the Python multiprocessing package a lot for web-scraping and
> found it to be very clunky indeed :-)

Agreed. The performance is awful. It's interesting from a
functionality standpoint that they made it work at all.

> The whole idea of using a complete new process to bypass the GIL highlight
> the shortcoming of Python as a concurrent language.

It's a technical solution to a political problem in the Python
community. Python needs the GIL so that you can change anything at
any time from any thread. In Python, you can monkey-patch running
code from another thread. Supporting this makes concurrency very
difficult. Not supporting it upsets Python's little tin god.

> So borrowing ideas from multiprocessing doesn't seem like a great starting
> point. Erlang is a more interesting comparison point because you can't
> actually change a variable in a function, which gives you the absolute
> safety you seem to demand. But then you have to live with a functional
> programming style, which is good for some things but not others.

After about twenty programming languages, and watching the mistakes
go by, I'm disappointed with Go. Go is touted as having a safe
solution to efficient concurrency. It doesn't. We need such
a language. We have more concurrent hardware out there now than
concurrent software that can use it. But it's very easy to screw
up concurrent code, and it's very difficult to debug.

Erlang is interesting because it's used to run big real-world
telephone switches. That's a high-reliability application that's
very parallel and is mostly control and I/O, not computation.
It's not just an academic language. But it's functional, and
that's a hard transition for many programmers.

Go is a good sequential language, but the concurrency is
not well designed. It's good old Hoare bounded buffers,
mutexes the programmer can sprinkle around, and a freeze-the
world garbage collector. That's adequate, but no more error
resistant than Java or C#. Go needs to offer a big win
over those alternatives.

John Nagle

[Patrick Mylund Nielsen]

Go makes it easier to play it safe, but it does not guarantee it. I don't know that you could do what you're asking and keep the language familiar to people who know traditional "imperative" languages. (Depending on your definition of imperative, even something like Haskell could be classified as an excellent imperative, concurrent language when living in the IO and STM monads, but it is hardly familiar or anywhere near easy to pick up for C/C++/Python/JavaScript people.)

In any case, you're right that the adage in effective Go might give people the wrong impression, but this discussion is no longer constructive. There's nothing that can/will be done in Go 1 to change the semantics.

                                John Nagle

--

[John Nagle]

On 1/21/2013 11:16 AM, minux wrote:
> On Tue, Jan 22, 2013 at 2:45 AM, John Nagle <na...@animats.com> wrote:
>
>> Now we have soundness, but it's cost us some copying.
>> Can those copies be optimized out? Yes.
>>
>> The optimization needed here is like tail recursion

...

> No. IMO, not guaranteed optimization == no optimization at all or
> even worse.
>

> If we can't make the guarantee to make this kind of optimization ...

> than we make no enforcement thus no thus guarantee at all.

The Scheme specification does mandate tail recursion. See

http://people.csail.mit.edu/jaffer/r5rs_5.html#SEC23

"3.5 Proper tail recursion

There are other examples in less widely used languages.

John Nagle

[John Nagle]

On 1/21/2013 12:19 PM, Patrick Mylund Nielsen wrote:
> Go makes it easier to play it safe, but it does not guarantee it. I don't
> know that you could do what you're asking and keep the language familiar to
> people who know traditional "imperative" languages.

That's the problem I'm trying to solve. Having solved some tougher
problems in the past, it doesn't look impossible. Just hard.

We don't have to go to something exotic like a functional language
or single assignment or single ownership pointers to fix this.

Javascript programmers are already used to Java's pseudo-concurrency
model based on callbacks. That works out surprisingly well, even though
the Javascript crowd tends to use global variables to communicate with
callbacks when they should be using closures. It might be helpful to
have a way to to turn the "send on channel, wait for reply on another
channel" idiom into something that looks like a Javascript callback.
That may be unnecessary, but it's an option if the idiom is too
complex for most users.

Screwups on language safety in a new design are unacceptable. We
already have a collection of bad languages, and the CERT security
advisories that come from them. When you really blow it, it
looks like this:

http://bits.blogs.nytimes.com/2013/01/14/department-of-homeland-security-disable-java-unless-it-is-absolutely-necessary/

�Unless it is absolutely necessary to run Java in Web browsers, disable
it (Java). This will help mitigate other Java vulnerabilities that may
be discovered in the future.� - Department of Homeland Security

> In any case, you're right that the adage in effective Go might give people
> the wrong impression, but this discussion is no longer constructive.
> There's nothing that can/will be done in Go 1 to change the semantics.

�Too often we enjoy the comfort of opinion without the discomfort of
thought.�

John Nagle

[Patrick Mylund Nielsen]

JFK. Funny. That's my favorite quote.

To clarify: http://golang.org/doc/go1compat.html Go 1 will be here for years, and existing code must continue to compile and run as expected for that time. No harm in thinking about it, but nothing will be done to make a change that would prevent sharing memory, even if a lot of people are for it. That's why this discussion can't do much more.

On Mon, Jan 21, 2013 at 4:19 PM, John Nagle <na...@animats.com> wrote:

On 1/21/2013 12:19 PM, Patrick Mylund Nielsen wrote:
> Go makes it easier to play it safe, but it does not guarantee it. I don't
> know that you could do what you're asking and keep the language familiar to
> people who know traditional "imperative" languages.

    That's the problem I'm trying to solve.  Having solved some tougher
problems in the past, it doesn't look impossible.  Just hard.

    We don't have to go to something exotic like a functional language
or single assignment or single ownership pointers to fix this.

    Javascript programmers are already used to Java's pseudo-concurrency
model based on callbacks.  That works out surprisingly well, even though
the Javascript crowd tends to use global variables to communicate with
callbacks when they should be using closures.  It might be helpful to
have a way to to turn the "send on channel, wait for reply on another
channel" idiom into something that looks like a Javascript callback.
That may be unnecessary, but it's an option if the idiom is too
complex for most users.

    Screwups on language safety in a new design are unacceptable.  We
already have a collection of bad languages, and the CERT security
advisories that come from them.  When you really blow it, it
looks like this:

http://bits.blogs.nytimes.com/2013/01/14/department-of-homeland-security-disable-java-unless-it-is-absolutely-necessary/

“Unless it is absolutely necessary to run Java in Web browsers, disable

it (Java). This will help mitigate other Java vulnerabilities that may

be discovered in the future.” - Department of Homeland Security

> In any case, you're right that the adage in effective Go might give people
> the wrong impression, but this discussion is no longer constructive.
> There's nothing that can/will be done in Go 1 to change the semantics.

 “Too often we enjoy the comfort of opinion without the discomfort of
thought.”

                                John Nagle

--

[Donovan Hide]

Javascript programmers are already used to Java's pseudo-concurrency
model based on callbacks.  That works out surprisingly well, even though
the Javascript crowd tends to use global variables to communicate with
callbacks when they should be using closures.  It might be helpful to
have a way to to turn the "send on channel, wait for reply on another
channel" idiom into something that looks like a Javascript callback.
That may be unnecessary, but it's an option if the idiom is too
complex for most users.

You seem to be describing a channel that copies the input when it receives it, does stuff and then returns the copy on the other. The channel keyword does not do a deep copy, and probably never will, but you can easily block until a copy has been made and return a channel for the copy to be sent back over:

http://play.golang.org/p/0RQYS--7Z1

You seem to be talking about optimising the compiler for tail recursion and enforcing rigid rules to stop programmers stabbing themselves in the face. I think the main problem is that all the good practise patterns aren't in one single place. The wiki has some good ones, but most of the concurrent patterns seem to be dotted around in various presentations in different places:

https://code.google.com/p/go-wiki/w/list

http://talks.golang.org/

http://talks.golang.org/2012/concurrency.slide (In particular)

I think the truth is you can do everything you have talked about in Go, it's just not enforced that you do :-)

[Donovan Hide]

 It might be helpful to
have a way to to turn the "send on channel, wait for reply on another
channel" idiom into something that looks like a Javascript callback.

http://play.golang.org/p/cfdqgzpBWX

:-)

[Thomas Bushnell, BSG]

On Mon, Jan 21, 2013 at 12:02 PM, John Nagle <na...@animats.com> wrote:

    After about twenty programming languages, and watching the mistakes
go by, I'm disappointed with Go.  Go is touted as having a safe
solution to efficient concurrency.  It doesn't.  We need such
a language.  We have more concurrent hardware out there now than
concurrent software that can use it.  But it's very easy to screw
up concurrent code, and it's very difficult to debug.

I'm sorry, but the "touting" simply doesn't exist. You have fundamentally misunderstood the statements that have been made.

First, what is Go? It is a language with particular characteristics. The statement "Do not communicate by sharing memory;

instead, share memory by communicating" is not one of the characteristics of Go. More about that statement later. The language Go, and its standard library, have a pretty full set of concurrency operations, including mutexes, condition variables, atomic integers, and channels. You should feel free to use whichever of them addresses a particular problem. In addition, the memory model of Go is shared, and its consistency model depends on use of the standard concurrency operations.

The designers of Go believe that CSP is a great idea, and correct use of CSP can make many problems simpler, and provide easier to understand code which also avoids many classic pitfalls. They do not claim that it is a "solution" if by that you mean that somehow they prevent people from writing deadlocks or race conditions. The language does not promise this, and never did.

So what about that motto? It is a statement that, when you have shared memory and both mutexes and channels, you should often organize your work not around the idea of concurrent access to the same data, mediated by locks, in order to communicate between threads; instead, they advise using channels to communicate, and sharing data in that way.

Your first objection was somehow that the sharing model was not just like Erlang's (which essentially has no sharing, but then since it's also got only immutable data, it's not clear whether that means anything anyway). But the statement was not "do not share memory", it was "do not _communicate_ by sharing memory", instead, "share memory by communicating": that is, if you have to goroutines which operate on the same data object, pass that object (or, usually, a pointer to it) around between the goroutines.

You have taken a misunderstanding, a misreading, a confusion, and some misstatements, all of your own doing, and then criticized the language, in a thread that soaks up rather too much energy.

Thomas

[Thomas Bushnell, BSG]

On Mon, Jan 21, 2013 at 1:19 PM, John Nagle <na...@animats.com> wrote:

    We don't have to go to something exotic like a functional language
or single assignment or single ownership pointers to fix this.

You cannot simultaneously pretend to the knowledge of a large number of languages, including Erlang, and then also say that functional languages or single assignment languages are "exotic".

I look forward to your language design. Please show us--once it's done--and let this list continue to be about Go.

Thomas

[John Nagle]

Nice. That's a good example to have around, one that will
look familiar to Javascript programmers.

Hm. Would it be useful to write Go in a "never block, always
call back" style? Should I/O libraries be written that way?

John Nagle

[Ian Lance Taylor]

On Mon, Jan 21, 2013 at 10:45 AM, John Nagle <na...@animats.com> wrote:
>
> This is a true "share memory by communicating" approach.
> One with less overhead, no race conditions, and no need
> for user mutexes.

I am not persuaded that your proposed solutions have less overhead.

Also, in order to enforce your solutions in the language, you must get
rid of mutable global variables (except perhaps for channels and,
given your suggestion that maps be atomic, for maps). That's a pretty
fundamental change to Go.

So we are really talking about a fundamentally different language.
Since you don't like Go, I agree that a fundamentally different
language is the approach to take. I encourage you to pursue it.

Ian

[Patrick Mylund Nielsen]

Please no. One of the major reasons I use Go is that the async is transparent. Assuming you're dealing with a file or network connection, you just block. In a http request handler, you just handle the request, doing whatever blocking or CPU-intensive operation you want. Need input from a client? Just do input, err := getInput(sock) and block. It's an absolute bounty to the programmer.

Continuations are not really relevant to the discussion of avoiding race conditions/memory sharing, IMO. Languages that are safe and use continuations are usually safe because they don't have, or don't use concurrent semantics, not because they're using continuations. JavaScript style, Python's Twisted, et al, are born out of deficiencies in the language/runtime, IMHO, not because they provide an intuitive API or programming model.

                                John Nagle


--

[Kevin Gillette]

You could do so successfully (Go is no less capable at closure-based callback programming than JavaScript), though pretty much  though since JavaScript is pretty much universally single-threaded (or must use implicit locks otherwise, due to the language model), you must be careful, when translating callback-based JS to callback-based Go, to synchronize writes to shared variables.

Also, that style wouldn't be too popular among the people who are already happily writing concurrent code since channels were baked into the language to specifically avoid that which the chief gophers consider annoyances, like explicit threading and callback-based event programming. The reason "share memory by communicating" is so powerful here is that the very mechanism that facilitates communication is what also makes it safe (if you adhere to the principle entirely regarding writes -- all "shared writes" would be changed into channel sends), whereas callback-based event programming with shared mutable variables requires two mechanisms: one for event-dispatch/communication (callbacks), and one for safety (locks or "lock channels" [where the communicated data is meaningless except to perform synchronization).

Go style does indeed favor the use of callbacks in some cases, but almost never for events. See, for example, http://golang.org/pkg/strings/#FieldsFunc -- to write that using channels would cater less to the functional style which those functions lend themselves to, and the concurrent functions would probably take more code and may be somewhat slower, besides which, a sequential scan of this kind doesn't generally benefit from concurrency.

[Patrick Mylund Nielsen]

To be clear, I am not arguing against continuations/first class functions, but the kind of callback spaghetti where the entire program is a long chain of functions to callbacks that are prevalent in e.g. JavaScript.

[Øyvind Teig]

I always thought that the occam 2 channels were great, but a little stiff. But I loved and used them for years, and have implemented them in safety critical embedded sw. But I have often felt I was on a "channel island" [1]. Then the Kent people developed the academic occam-pi with even more usable channels, but with parallel usage rules enforced, or rather - not removed. Then came Go and I was thrilled, but perplexed when I saw that there were no parallel usage rules. None defined, none enforced. I can even send in a gorotine but if the channel is full I can take out a message from the receiving side. This is about as nice and as useful as operations on pointers.

For Go it's all patterns and little enforcement. I tend to bring my occam style into it,  the "chief gophers" theirs, and the channels shine with only slowly ackquired authority. I guess we would respect them like we respect pointers and arithmetic on them: somewhat scary. So, locks may too often become safe land..

I certainly hope that channels will become first rate Go citizens, so that programmers will befriend them. This excellent thread hints otherwise. I would not want the occam 2 channels in Go, I would want Go channels. I have asked myself: did the Go designers make (Suez) channels for ships or (Pacific) channels for everything?

/aclassifier

[1] - http://www.teigfam.net/oyvind/pub/pub_details.html#CSP:arriving_at_the_CHANnel_island

[2] - https://groups.google.com/forum/?fromgroups=#!topic/golang-nuts/qa2p0PRY0WE

[roger peppe]

On 21 January 2013 18:45, John Nagle <na...@animats.com> wrote:

> That could be done in Go. Just do a deep copy of
> anything sent on a channel, or passed into a goroutine.

A deep copy is not a trivial operation since data structures
can have self-references.

Consider a data structure like this:

type Graph struct {
Nodes []*Node
}

type Node struct {
Text string
Position image.Point
Arcs []*Node
}

Say I've got some number of large graphs and I want to
run a layout algorithm over them.

If I want to do this concurrently, I can do something like this:

func (g *Graph) Layout() {
[.... complex algorithm]
}

func layout(graphs []*Graph) {
var wg sync.WaitGroup
for _, g := range graphs {
g := g
wg.Add(1)
go func() {
g.Layout()
wg.Done()
}()
}
wg.Wait()
}

This is just fine, assuming graphs don't share nodes.

We're not even using channels here - ownership is
implicit in the fact we've started a goroutine with a given
Graph.

If this required a deep copy, it
a) wouldn't work, because the layout algorithm would be unable
to change the nodes in place.
b) would be much less efficient, even if we did the copy
in each direction, because of the copying overhead. Each copy would need
two passes through the data and len(g.Nodes) allocations.

The point I'm trying to make is that *thinking* in terms of ownership
of data is a useful way to make it easier to reason about concurrent
programs.

We can look at the code above and verify by eye that it's race
free, assuming the different graphs don't share data,
a property that we can also make easy to verify.

I've found this approach scales quite well, and one reason may
be that it's relatively rare for packages to export a channel-based
API. Packages often use channels internally, but they export
functions or methods that hide that fact.

When a package *does* export a channel-based interface
(almost exclusively a package will send to its client,
not the other way around), the object passed over the channel either
a) has no references (and is thus inherently safe)
or b) has methods which are all safe to use concurrently
or c) is genuinely transferring ownership - the sender
will never refer to the value again.

When each layer of the system conforms to the above
conventions, it's not hard to verify the correctness
of the whole system by looking at each component
individually. Complexity due to concurrency becomes additive
rather than multiplicative.

I think that's the real power of the "share memory by communicating"
idea.

> --
>
>

[Øyvind Teig]

The usage rules of occam also verified shared arrays and would analyze segments of arrays.

Each PROCess was allowed a unique segment FROM x FOR y. If the compiler was not able

to analyze this statically, it some times gave a warning that it instead had inserted 

run-time checks. This strategy may be unwanted for Go, but if something along the

line is not possible, then safety is prioritized below something else.

If this required a deep copy, it
a) wouldn't work, because the layout algorithm would be unable
to change the nodes in place.
b) would be much less efficient, even if we did the copy
in each direction, because of the copying overhead. Each copy would need
two passes through the data and len(g.Nodes) allocations.

The point I'm trying to make is that *thinking* in terms of ownership
of data is a useful way to make it easier to reason about concurrent
programs.

Absolutely!

We can look at the code above and verify by eye that it's race
free, assuming the different graphs don't share data,
a property that we can also make easy to verify.

Perhaps an eye after a cup of coffee, perhaps not a tired eye.

Isn't programming is too important to rely on the eye only?

I've found this approach scales quite well, and one reason may
be that it's relatively rare for packages to export a channel-based
API. Packages often use channels internally, but they export
functions or methods that hide that fact.

There are probably good reasons for the above, but to me the below looks like real

channel-based or Process Oriented Programming, where the module (if is has

any concurrency) would be a black-box goroutine with channels as the the

only interface. Perhaps not even parameters..  

When a package *does* export a channel-based interface
(almost exclusively a package will send to its client,
not the other way around), the object passed over the channel either
a)  has no references (and is thus inherently safe)
or b) has methods which are all safe to use concurrently
or c) is genuinely transferring ownership - the sender
will never refer to the value again.

When each layer of the system conforms to the above
conventions, it's not hard to verify the correctness
of the whole system by looking at each component
individually. Complexity due to concurrency becomes additive
rather than multiplicative.

Great convention. But not enforced. 

[minux]

On Tue, Jan 22, 2013 at 4:24 AM, John Nagle <na...@animats.com> wrote:

On 1/21/2013 11:16 AM, minux wrote:
> On Tue, Jan 22, 2013 at 2:45 AM, John Nagle <na...@animats.com> wrote:
>
>> Now we have soundness, but it's cost us some copying.
>> Can those copies be optimized out?  Yes.
>>
>> The optimization needed here is like tail recursion

...

> No. IMO, not guaranteed optimization == no optimization at all or
> even worse.
>

> If we can't make the guarantee to make this kind of optimization ...

> than we make no enforcement thus no thus guarantee at all.

The Scheme specification does mandate tail recursion.  See

http://people.csail.mit.edu/jaffer/r5rs_5.html#SEC23

You didn't read all of my post.

I just mentioned that below.

[minux]

Wonderful summary, thanks.

roger, do you have plans to transform it as a blog post or something

so that it could be added to the Articles collection of the go community wiki?

[John Nagle]

On 1/21/2013 10:41 PM, Patrick Mylund Nielsen wrote:
> To be clear, I am not arguing against continuations/first class functions,
> but the kind of callback spaghetti where the entire program is a long chain
> of functions to callbacks that are prevalent in e.g. JavaScript.

Concurrent code with blocking is in some ways cleaner than the
Javascript callback thing. I originally didn't like Javascript's
callback-oriented style. But it's been amazingly successful in
allowing mediocre programmers to do I/O parallelism without
creating timing problems.

Imposing that structure on Go would be a mistake. Making
Go equally resistant to race conditions would not be.

John Nagle

[John Nagle]

On 1/22/2013 1:33 AM, �yvind Teig wrote:

> kl. 09:58:18 UTC+1 tirsdag 22. januar 2013 skrev rog f�lgende:
>>
>> On 21 January 2013 18:45, John Nagle <na...@animats.com <javascript:>>

>> wrote:
>>> That could be done in Go. Just do a deep copy of
>>> anything sent on a channel, or passed into a goroutine.
>>
>> A deep copy is not a trivial operation since data structures
>> can have self-references.

True. And every LISP implementation has a copier that solves
that problem.

I'm not suggesting that deep copying is desirable. One
alternative is simply to forbid sending references to non-atomic
objects over channels or into goroutines. That's the same
restriction you face when you send something to another computer
or process, where the data has to marshalled and serialized.
But we could lighten up a bit and offer an automatic deep copy
to make life easier for the programmer.

As I pointed out previously, for some common cases the
copy can be optimized out. It's a lot like tail recursion.

>> We're not even using channels here - ownership is
>> implicit in the fact we've started a goroutine with a given
>> Graph.

> This is just fine, assuming graphs don't share nodes.

Which is hard to verify at compile time.

(It's not impossible. There are ways to prove single
ownership. If each node has a backlink, a depth, and multiple
forward links, and you have an invariant that the forward
and backlinks must match, you can prove that a tree is not a DAG
and has a unique root. But that takes more formal verification
machinery than one can expect in compilers.)

> The usage rules of occam also verified shared arrays and would analyze
> segments of arrays.

Occam was interesting. It was intended for the highly distributed
Inmos Transputer, which was a non-shared-memory multiprocessor.
In non-shared memory systems, you can't avoid the shared-data problem.
The designers of Occam had to solve it.

> This strategy may be unwanted for Go, but if something
> along the line is not possible, then safety is prioritized below something else.

That's the point I'm making.

> We can look at the code above and verify by eye that it's race
>> free, assuming the different graphs don't share data,
>> a property that we can also make easy to verify.
>
> Perhaps an eye after a cup of coffee, perhaps not a tired eye.
> Isn't programming is too important to rely on the eye only?

Good point.

Where the code itself does not contain some constraint, a
later maintenance programmer may break that constraint. Large
systems tend not to converge to a zero-bugs state, and that's
one of the main reasons.

In particular, constraints that must hold between code
that's physically distant in source are not likely to be
maintained during maintenance. Race conditions tend to be
in that category. That's why I'm arguing that the language
should handle them correctly.

John Nagle