Friday coding challenge

[Dave Cheney]

Hello,

Can you write a type that implements the following interface without
using the sync package ?

// A Future represents some work to be performed.
type Future interface {
// Result returns the result of the work as an error, or nil if the work
// was performed successfully.
// Implementers must observe these invariants
// 1. There may be multiple concurrent callers to Result, or Result may
// be called many times in sequence, it must always return the same
// value.
// 2. Result blocks until the work has been performed.
Result() error
}

Cheers

Dave

[Péter Szilágyi]

A few questions:

1. How long are tasks expected to run? Or arbitrarily long?
   
2. I guess re-implementing the sync primitives doesn't count :P
3. Can you give a sample task?

Cheers,

  Peter

Dave

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Dave Cheney]

The actual task is an os/exec.Command invocation. Don't worry about commands that never finish, assume that is not a problem.

You can reimplement the sync primitives if you like, but you can't use sync, or unsafe, or syscall.

[Péter Szilágyi]

http://play.golang.org/p/XuTPRqAzlo :)

[Dave Cheney]

Very nice. I think that is pretty close, but receiving from a channel is not a happens before operation so I'm not sure the memory model guarantees that r.done will be correctly published. The same goes for r.result. 

[Dave Cheney]

Also, why do you create a buffered channel on line 20?

[Péter Szilágyi]

I'm sending in one value in New to let one thread pass. If it's not buffered, then New will block since there's no reader on the other side.

[Jan Mercl]

On Fri, Apr 19, 2013 at 3:19 PM, Dave Cheney <da...@cheney.net> wrote:

Not tested at all, might be totally broken because of that:
http://play.golang.org/p/EVhkdzbV8q

-j

[Jan Mercl]

On Fri, Apr 19, 2013 at 4:06 PM, Jan Mercl <0xj...@gmail.com> wrote:

It is broken. V2: http://play.golang.org/p/tCA7SWQAN_

-j

[Dave Cheney]

Ahh, I see how. Remember that the invariants don't require that the caller of Result _trigger_ the work, only block until its result is available. 

[Jan Mercl]

On Fri, Apr 19, 2013 at 4:09 PM, Jan Mercl <0xj...@gmail.com> wrote:

It is broken again. V3: http://play.golang.org/p/VC8T7ncgb-

-j

PS: Sorry, I'll not send more versions even if it's broken again. My apologies.

[Péter Szilágyi]

Ok, then: http://play.golang.org/p/HpidEfnars :), this was my first version but though I'd modify it to start only when requested.

[steve wang]

package main

import (

    "errors"

    "fmt"

    "math/rand"

)

type Future interface {

    Result() error

}

type TaskResult chan error

func (ch TaskResult) Result() (err error) {

    defer func() {

        if err != nil {

            ch <- err

        }

    }()

    return <-ch

}

func RunTask() Future {

    ch := make(chan error, 1)

    go func() {

        if rand.Intn(100) > 50 {

            ch <- nil

            return

        }

        ch <- errors.New("FAILED")

    }()

    return TaskResult(ch)

}

func main() {

    for i := 0; i < 10; i++ {

        fmt.Println(RunTask().Result())

[Dave Cheney]

Sorry, I think all three of those versions are broken. I can't see how multiple callers to Result can receive the same 'sticky' value. Also, v2 and v3 may contain a data race.

[steve wang]

package main

import (

    "errors"

    "fmt"

    "math/rand"

)

type Future interface {

    Result() error

}

type TaskResult chan error

func (ch TaskResult) Result() (err error) {

    defer func() {

        ch <- err

[Dave Cheney]

That one really dose have a data race. 

[Péter Szilágyi]

(Sorry, wrong button, sent private accidentally)

Why?

[Stephen Day]

Protects result with request and response channel:

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

[Dave Cheney]

Very nice, but I think your solution is prone to deadlocks, do you need a non blocking send in the defer in TaskResult.Result? Also, nil is a perfectly valid value for Result to return, and if you don't refill ch, the next caller to Result will block forever. 

--

[Matt Harden]

http://play.golang.org/p/l_V0Bkc0-9

[Dave Cheney]

The receive on line 27 does not imply a happens before relationship with the assignment to r.result on line 20. 

[Péter Szilágyi]

The receive won't conclude until after the assignment is done and the channel closed on line 21.

[Matt Kane's Brain]

I think this will do it: http://play.golang.org/p/v2XbURrUl5 Can't brain enough to write tests. 

On Fri, Apr 19, 2013 at 10:26 AM, <cos...@gmail.com> wrote:

Peter's solution, a little simpler:
http://play.golang.org/p/qUDPHEWQwG

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
matt kane's brain
twitter: the_real_mkb / nynexrepublic
http://hydrogenproject.com

[Maxim Khitrov]

I'm pretty sure that it does:

"The closing of a channel happens before a receive that returns a zero
value because the channel is closed."

http://golang.org/ref/mem

[Péter Szilágyi]

If by any chance you missed it, I turned the channel back into non-buffered in the second version.

[Dave Cheney]

So each Future comes with the cost of an eternal goroutine to keep callers stocked with values? Is there any way to avoid that overhead, not to mention memory leak?

--

[Dave Cheney]

I think we've been here before, I wasn't part of the discussion, but I remember reading it. The close happens before the receive, obviously, but that has no relationship to the assignment to r.result.

[Péter Szilágyi]

Well, the assignment happens before the close. :P Is there some specific language feature that allows the runtime to swap the two ops? Shouldn't the assignment on line 20 always terminate before proceeding to line 21?

[Dave Cheney]

I think we have a winner folks. This is certainly the simplest
solution presented thus far.

[Péter Szilágyi]

Not until you tell me why my solution doesn't work :P

[Maxim Khitrov]

Péter's code is exactly the same as the example on that page when the
following note is taken into account:

"In the previous example, replacing c <- 0 with close(c) yields a
program with the same guaranteed behavior."

[minux]

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

untested.

[Matt Harden]

This is better because calls to Result() don't have to wait for each other:

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

[Dave Cheney]

Sorry, I believe this does not work for the same reason as Peter's
example; there is no happens before relationship between a channel
closure and an assignment to another member of a type.

On Sat, Apr 20, 2013 at 12:26 AM, <cos...@gmail.com> wrote:
> Peter's solution, a little simpler:
> http://play.golang.org/p/qUDPHEWQwG
>
>

[steve wang]

I have given a revised version which fixed the bug of not refilling ch with nil.

As to deadlock, I don't think it will happen as ch is a buffered channel.

[Dave Cheney]

Sorry, I think this solution is not correct because closing fu.ch does
not correctly publish fu.err.

[Matt Harden]

IMHO Peter's solution works and is basically the same as my latest submission; he got there first, but mine is a little shorter.

[Dave Cheney]

I'm looking for the reference now. Please don't take this too
seriously, it was just a bit of fun.

On Sat, Apr 20, 2013 at 12:46 AM, Péter Szilágyi <pet...@gmail.com> wrote:
> Please provide some reference to that behavior.

[Péter Szilágyi]

Please provide some reference to that behavior.

On Fri, Apr 19, 2013 at 4:43 PM, Dave Cheney <da...@cheney.net> wrote:

[Dave Cheney]

If anyone wants to play part two of this game, entitled "search the
golang-nuts and golang-dev mailing lists for the previous discussion",
here are some keywords, "channel" "send" "close" "happens before"

There was a discussion related to making sync.Once use a structure
similar to the one being discussed, but there is a better one when rsc
comes in a sweeps the pool.

On Sat, Apr 20, 2013 at 12:49 AM, Péter Szilágyi <pet...@gmail.com> wrote:
> No problem, I'm just not giving my solution up without a fight :D
>
> The other reason why mine should be better:
>
> BenchmarkPeter 50000000 52.6 ns/op
> BenchmarkMatt 20000000 130 ns/op
>
> http://play.golang.org/p/eqGa0yAtn1
>
> :D

[Péter Szilágyi]

No problem, I'm just not giving my solution up without a fight :D

The other reason why mine should be better:

BenchmarkPeter  50000000                52.6 ns/op

BenchmarkMatt   20000000               130 ns/op

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

:D

[Dave Cheney]

My apologies, you were correct, deadlock is not possible, your version
is similar to Matt's

result := <- ch
ch <- result
return result.

[Dave Cheney]

That sounds fair, I guess the discussion has moved from the design of
Future implementations to: does sending a value through a channel
imply a happens before relationship with an unrelated variable. I wish
I could find the damn mailing list thread.

[James Bardin]

Ah, that thread was called: 

 "suggestion: limiting a sync.WorkGroup"

(how do you permalink to a thread?)

[Péter Szilágyi]

Quoting the memory specs: http://tip.golang.org/ref/mem

"Within a single goroutine, the happens-before order is the order expressed by the program."

[James Bardin]

On Fri, Apr 19, 2013 at 10:58 AM, James Bardin <j.ba...@gmail.com> wrote:
>
>  "suggestion: limiting a sync.WorkGroup"
>
> (how do you permalink to a thread?)

Link: https://groups.google.com/d/msg/golang-nuts/Ug1DhZGGqTk/tjKg9sMTdlcJ

[Dave Cheney]

Thanks James, I have no idea how to permalink on the new new google
groups, however in that thread Kyle links to the one I was talking
about, https://groups.google.com/forum/#!msg/golang-dev/ShqsqvCzkWg/Kg30VPN4QmUJ

[minux]

On Fri, Apr 19, 2013 at 10:46 PM, Dave Cheney <da...@cheney.net> wrote:

Sorry, I think this solution is not correct because closing fu.ch does
not correctly publish fu.err.

How about this:

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

if close is happening after the assignment to fu.err, it will be a violation of

defer semantics. (let's ignore the case when the provided work function itself

panics)

[Dave Cheney]

Sure, but we are talking about one setting the value of X, the closing
channel Y, then another goroutine receiving from channel Y, then
checking the value of X. IMO, that quote does not apply in this
instance.

[Maxim Khitrov]

How is that different from the following example on http://golang.org/ref/mem?

var c = make(chan int, 10)
var a string

func f() {
a = "hello, world"
c <- 0 // can be safely replaced with close
}

func main() {
go f()
<-c
print(a)

[Péter Szilágyi]

As I interpret it, since set and close happen in the same go routine, order is guaranteed, thus teh set should be guaranteed to finish and only afterwards proceed with the close. On a side note, I read in on thread that channel operations are "memory-fenced", but I can't find an exact quote in the specs.

[Costin Chirvasuta]

"Within a single goroutine, the happens-before order is the order
expressed by the program."

This implies:
a. setting X happens before closing Y
c. receving from channel Y happens before checking X

"The closing of a channel happens before a receive that returns a zero
value because the channel is closed."

This implies the remaining
b. closing Y happens before receiving from Y

Am I missing something?

[Dave Cheney]

This is the crux of the argument, as I understand it channel sends are
not a memory barrier. The value passed through a channel is correctly
published, but unlike sync.Mutex.Lock(), other values set before a
channel send are not guarented to be correctly published.

For your example, from the POV of a thread of execution r.result is
assigned before the close(r.ch), but in a multithreaded world with
writeback caches and speculative execution, it is not guarented that
other threads will observe the write to r.result.

[Dave Cheney]

Maxim, I'm not sure. My reading of the spec says that other goroutines
are not guaranteed to observe the write to a although the intel memory
model tends to ensure this does happen.

[Kamil Kisiel]

Any reason something like this doesn't work?

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

[Dave Cheney]

It's rather late in AU now, so please excuse me while I duck out. I
don't really have anything more constructive to add on the subject of
the happens before relationship, but I'm sure the debate will continue
overnight.

Thank you for your participation, I think on reflection Peter was the
first to a solution, followed by Matt and Steve. I did like Matt's
first suggestion, it was the cleanest from my POV.

Thank you again, and I look forward to participating in your coding
challenges (not a very subtle hint)

Cheers

Dave

[Maxim Khitrov]

I don't think you can achieve the sort of synchronization between a
close and a receive without a memory barrier. This post by Dmitry
provides a good summary of how memory barriers work:

http://www.1024cores.net/home/lock-free-algorithms/so-what-is-a-memory-model-and-how-to-cook-it/applied-ordering

I think that close has to behave as a store-release and receive has to
behave as a load-acquire. Otherwise, you can't synchronize between the
two goroutines.

[Péter Szilágyi]

Thanks for the contest, was an interesting problem :) Hopefully we can figure out an "official" proof whether or not memory is synced up. Good night!

[minux]

On Fri, Apr 19, 2013 at 11:00 PM, minux <minu...@gmail.com> wrote:

On Fri, Apr 19, 2013 at 10:46 PM, Dave Cheney <da...@cheney.net> wrote:

Sorry, I think this solution is not correct because closing fu.ch does
not correctly publish fu.err.

How about this:

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

if close is happening after the assignment to fu.err, it will be a violation of

defer semantics. (let's ignore the case when the provided work function itself

panics)

Still incorrect, now I see the problem. Although this assignment must happen before

the close of channel, other goroutine might not see this order as happen-before

order is not total.

Or put it another way, in theory, Go channel operations are not memory barriers

according the Go memory model document.

[roger peppe]

yes. that's my "don't look at anyone else's solution, first thing that
comes to mind" solution:

type Future chan error

func NewFuture(f func() error) Future {
w := make(work, 1)
go func() {
w <- f()
}()
return w
}

func (f Future) Result() error {
err := <-w
w <-= err
return err
}

On 19 April 2013 16:41, Burke Libbey <bu...@libbey.me> wrote:
> I came up with basically the same thing as Kamil, I think:
> http://play.golang.org/p/P71Yz7GIsx
>
> Republishing to the channel feels a bit gross, but I believe it's safe.
>
> -b

[minux]

On Sat, Apr 20, 2013 at 12:43 AM, <gordon...@gmail.com> wrote:

On Friday, April 19, 2013 11:51:55 AM UTC-4, minux wrote:

Still incorrect, now I see the problem. Although this assignment must happen before

the close of channel, other goroutine might not see this order as happen-before

order is not total.

You are correct that the order is not total; unsynchronized goroutines have no hb relationships between them.

But the order _is_ transitive:  if A hb B and B hb C then A hb C.  Otherwise I am my own grandpa, end of the world, cats and dogs living together...

you switched observer here.

observer 1: A hb B (the gorutine that closes ch)

observer 2: B hb C (the goroutine that <-ch)

from the standpoint of observer 2, A might not happen before C.

Concretely:

fu.err = f()      happens before   close(fu.ch),

close(fu.ch)    happens before     <-fu.ch, and

<-fu.ch           happens before     return fu.err

and you can see where this is going...

Or put it another way, in theory, Go channel operations are not memory barriers

according the Go memory model document.

I guess they must be. 

nothing in the memory model guarantee that.

[Costin Chirvasuta]

From the "Do chans provide full sequential consistency or just what MM
says?" thread I understand that even though reordering may occur in
the same goroutine operations may not be inserted between the "origin"
and "destination" of a "happens-before" arc (although they can be
moved out). So in order to use a "happens-before" relation you need to
use this "fence" by putting what you want to happen earlier before of
the "origin" of a "happens-before" and what you want to happen later
after a "destination". In Peter's example
the "happens-before" relation is "close before read". r.result is
written to before close so it can't be moved after it and r.result is
accessed after read so it can't moved before it.

Very interesting contest and reading. Thank you!

[minux]

On Sat, Apr 20, 2013 at 1:54 AM, <gordon...@gmail.com> wrote:

You are confusing the notion of observer.  From the memory model:
"The Go memory model specifies the conditions under which reads of a variable in one goroutine can be guaranteed to observe values produced by writes to the same variable in a different goroutine."

There is only one read (return fu.err) and it is guaranteed to observe the write (fu.err = f()) because of the transitivity of hb-relationships that I described.

ok, let's try another simpler example.

a = 1; b = 2; // goroutine 1, assignment to a happens before assignment to b, this is the usual order.

from another goroutine, it might find b = 2 but a != 1. This is the first example in golang.org/ref/mem.

This demonstrate that the observer plays an important role in hb relationships, and after switching

observer, a hb relation might not hold.

the essential question is still: whether channel communication operations also act as memory barriers.

i don't see any memory barriers in the implementation of channel (in fact, the 3 memory barrier

instructions are not even implemented for ARM).

specifically,

if channel close provides memory barrier, then the assignment hb. close(ch) for observer 1 also

hold for observer 2 (the <-ch goroutine), then you could use transitivity of hb. relationship for

observer 2 to conclude that assignment hb. <-ch.

[Gordon Klaus]

It can be a confusing topic.  You had me doubting myself  :)  So I went back and re-read the MM.

It's worth noting that the example under http://golang.org/ref/mem#tmp_6 is basically identical to the code we're talking about.  I think somebody already mentioned this.

(more inline:)

On Fri, Apr 19, 2013 at 2:54 PM, minux <minu...@gmail.com> wrote:

On Sat, Apr 20, 2013 at 1:54 AM, <gordon...@gmail.com> wrote:

You are confusing the notion of observer.  From the memory model:
"The Go memory model specifies the conditions under which reads of a variable in one goroutine can be guaranteed to observe values produced by writes to the same variable in a different goroutine."

There is only one read (return fu.err) and it is guaranteed to observe the write (fu.err = f()) because of the transitivity of hb-relationships that I described.

ok, let's try another simpler example.

a = 1; b = 2; // goroutine 1, assignment to a happens before assignment to b, this is the usual order.

from another goroutine, it might find b = 2 but a != 1. This is the first example in golang.org/ref/mem.

Such observed re-orderings can only occur when there is not synchronization.  That is, a reader of a and b can see them re-ordered only if the reader is executing concurrently with their writes.  As soon as you introduce synchronization, some of this concurrency goes away.

This demonstrate that the observer plays an important role in hb relationships, and after switching

observer, a hb relation might not hold.

Right, the observer is important.  But in your Future code, there is only one observer (the read: return f.err) and only one thing to observe (the write: f.err = f()).  From the point of view of this observer, the channel receive happens before the variable read (because the program order is preserved within a goroutine), the channel close happens before the channel receive (channel synchronization), and the variable write happens before the channel close (program order again).

the essential question is still: whether channel communication operations also act as memory barriers.

i don't see any memory barriers in the implementation of channel (in fact, the 3 memory barrier

instructions are not even implemented for ARM).

I don't know anything about memory barrier instructions.  It's strange that they don't appear in the channel implementation; are they really necessary?

[Skip Tavakkolian]

Kamil and Burke had the same approach.  This looks like a correct solution to me.

[Kyle Lemons]

I haven't read any of the play links in the thread yet, but I see a lot of discussion about "happens before" and using close() to synchronize data.  The first thing to point out here that close() has the semantics of a channel send.

The decision, as far as I remember it, was that channels do not guarantee full sequential consistency.  The biggest loss of sequential consistency comes when you start using buffered channels.  Dmitry explains some allowable reorderings in this post.  You can still stay well within the memory model though with an implementation like this:

type result struct {

  ready chan struct{}

  err error

}

func (r *result) Result() error {

  <-r.ready // A

  return r.err // B

}

func Run(f func() error) Future {

  r := &result{

    ready: make(chan struct{}),

  }

  go func() {

    defer close(r.ready) // C

    r.err = f() // D

  }()

  return r

}

D happens before C, C happens before A, A happens before B.

The problematic part of closes as described in this post was not that they don't synchronize data, but that they don't synchronize with each other; they do synchronize with the corresponding receives.