Effective Go's semaphore example

[Sameer Ajmani]

I have a couple of questions about this example in Effective Go:

var sem = make(chan int, MaxOutstanding)



func handle(r *Request) {


    sem <- 1    // Wait for active queue to drain.


    process(r)  // May take a long time.


    <-sem       // Done; enable next request to run.


}



func Serve(queue chan *Request) {


    for {


        req := <-queue


        go handle(req)  // Don't wait for handle to finish.


    }


}

1) Since this blocks on the semaphore inside the goroutine, nothing prevents this program from creating an arbitrary number of goroutines as requests arrive.  It seems like we'd instead want to apply backpressure by only consuming requests off queue when we have resources available.  Specifically, why isn't "sem <- 1" on the line before "req := <- queue" ?

2) Suppose we want to bound request processing to 1GB of RAM, and our average RAM use per request is 10 KB.  This yields MaxOutstanding = 100K.  A chan int with 100K buffer takes up quite a bit of RAM -- wouldn't a traditional semaphore be more appropriate at this scale?  I don't see a Semaphore class in sync; there's just runtime.Semaquire and Semrelease.

-- 

Sameer

[Rob 'Commander' Pike]

On 22/05/2011, at 12:22 PM, Sameer Ajmani wrote:

I have a couple of questions about this example in Effective Go:

var sem = make(chan int, MaxOutstanding)



func handle(r *Request) {


    sem <- 1    // Wait for active queue to drain.


    process(r)  // May take a long time.


    <-sem       // Done; enable next request to run.


}



func Serve(queue chan *Request) {


    for {


        req := <-queue


        go handle(req)  // Don't wait for handle to finish.


    }


}

1) Since this blocks on the semaphore inside the goroutine, nothing prevents this program from creating an arbitrary number of goroutines as requests arrive.  It seems like we'd instead want to apply backpressure by only consuming requests off queue when we have resources available.  Specifically, why isn't "sem <- 1" on the line before "req := <- queue" ?

An exercise for the reader, perhaps worth mentioning there.  However, the example that follows already shows one way to throttle.

2) Suppose we want to bound request processing to 1GB of RAM, and our average RAM use per request is 10 KB.  This yields MaxOutstanding = 100K.  A chan int with 100K buffer takes up quite a bit of RAM -- wouldn't a traditional semaphore be more appropriate at this scale?  I don't see a Semaphore class in sync; there's just runtime.Semaquire and Semrelease.

Package sync could perhaps use a semaphore.  WaitGroup is close but not quite.

-rob

[Gustavo Niemeyer]

> Package sync could perhaps use a semaphore.  WaitGroup is close but not
> quite.

A higher-level semaphore would be useful indeed, but for the proposed
problem we have sync.Cond which might suit his problem quite well,
perhaps better than a semaphore.

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

--
Gustavo Niemeyer
http://niemeyer.net
http://niemeyer.net/blog
http://niemeyer.net/twitter

[Sameer Ajmani]

Could the compiler optimize the implementation chan struct{} to store just its buffer length, and no elements?  (This assumes that all instances of type struct{} are interchangeable, which isn't true if you take their addresses.)  chan struct{} can then be used efficiently as a semaphore or to let senders trigger events on receivers that require no additional information beyond the channel identity (e.g., I've used a channel called "failover" to trigger failover in a replicated storage client; the values passed on the channel were immaterial).

S

 

-rob

--
Sameer

[Rob 'Commander' Pike]

A struct{} is zero bytes long, so a hundred of them will still be zero bytes long.  Unless I'm mistaken, you have your semaphore.

-rob

[Steven]

On Sunday, May 22, 2011, Rob 'Commander' Pike <r...@google.com> wrote:
>
> On May 22, 2011, at 11:25 PM, Sameer Ajmani wrote:
>
>
> On Sat, May 21, 2011 at 10:34 PM, Rob 'Commander' Pike <r...@google.com> wrote:
>
>
>
> On 22/05/2011, at 12:22 PM, Sameer Ajmani wrote:
> I have a couple of questions about this example in Effective Go:
>
> var sem = make(chan int, MaxOutstanding)
>
> func handle(r *Request) {

>     sem <- 1A struct{} is zero bytes long, so a hundred of them will still be zero bytes long.  Unless I'm mistaken, you have your semaphore.
> -rob
>
>

A struct{} has size one so that they all have distinct addresses. This
doesn't matter inside a channel, so it would certainly be possible to
optimize, but it isn't a given.

[bflm]

On May 22, 9:05 pm, Steven <steven...@gmail.com> wrote:
> A struct{} has size one so that they all have distinct addresses.

Sizeof(struct{}) == 1 (one)? I haven't checked, but that would
surprise me a lot.

[Steven]

Again, it's so that each element in a []struct{} or a struct{x, y
struct{}} has a different address.

[Rob 'Commander' Pike]

Indeed, I stand corrected, and surprised.

-rob

[peterGo]

bflm,

On May 22, 3:24 pm, bflm <befelemepesev...@gmail.com> wrote:
> Sizeof(struct{}) == 1 (one)? I haven't checked, but that would
> surprise me a lot.

It's easy to see that it's true. For example,

package main

import (
"fmt"
"unsafe"
)

func main() {
var s struct {
e struct{}
f struct{}
}
fmt.Printf("%v\n%d %d %d\n%p %p %p\n",
s,
unsafe.Sizeof(s), unsafe.Sizeof(s.e), unsafe.Sizeof(s.f),
&s, &s.e, &s.f)
}

Output:
{{} {}}
2 1 1
0xf840000040 0xf840000040 0xf840000041

Peter

[Steven]

On Sat, May 21, 2011 at 10:44 PM, Gustavo Niemeyer <gus...@niemeyer.net> wrote:

> Package sync could perhaps use a semaphore.  WaitGroup is close but not
> quite.

A higher-level semaphore would be useful indeed, but for the proposed
problem we have sync.Cond which might suit his problem quite well,
perhaps better than a semaphore.

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

Of course, this is implemented with runtime.Semacquire/runtime.Semrelease, so you could just implement a plain old semaphore using those. But the doc comment warns not to use them directly. Is there any particular reason not to implement your own synchronization primitives using them?  

[Gustavo Niemeyer]

> Of course, this is implemented with runtime.Semacquire/runtime.Semrelease,
> so you could just implement a plain old semaphore using those. But the doc
> comment warns not to use them directly. Is there any particular reason not
> to implement your own synchronization primitives using them?

Such warnings generally mean the feature is an implementation detail
that may be removed behind your back.

[Keith Rarick]

On Sun, May 22, 2011 at 12:38 PM, Steven <stev...@gmail.com> wrote:
> Again, it's so that each element in a []struct{} or a struct{x, y
> struct{}} has a different address.

That's understandable but It's a little unfortunate
to have a surprise like this.

As an alternative solution, would it be possible to
prohibit taking the address of a zero-length value?
Then it's okay for Sizeof(struct{}{}) (as well as
Sizeof([10]struct{}{})) to be 0. I'm sure this idea will
turn up its own problems, but it feels a little more
consistent to me.

kr

[Rob 'Commander' Pike]

Perhaps, but in return you get the possibility of two items of different types being at the same address. That sounds like another recipe for confusion.

-rob

[chris dollin]

It would be nice if map[Whatever]struct{} didn't use any space for
the struct{}.

(That kind of map is useful as a set -- you don't read the value, you
use the ,ok idiom.)

Chris{}

--
Chris "allusive" Dollin

[Sameer Ajmani]

Do we want to encourage Go programmers to chan struct{} for channels that are used purely for synchronization (e.g., as semaphores, barriers, beacons, or signals), in preference to using chan int / chan bool / chan byte?  If so, we should change the example in Effective Go, as new programmers will take their lead from there.

S

 

-rob

--
Sameer

[Keith Rarick]

On Mon, May 23, 2011 at 1:58 AM, Rob 'Commander' Pike <r...@google.com> wrote:
> Perhaps, but in return you get the possibility of two items of different types being at the same address.  That sounds like another recipe for confusion.

We already have that possibility.

var t struct{ a int }
println(&t)
println(&t.a)

Maybe I misunderstood what you mean.

kr

[Rob 'Commander' Pike]

No, I misunderstood what I meant. Sigh.

-rob

[Steven]

On Sunday, May 22, 2011, Keith Rarick <k...@xph.us> wrote:
> On Sun, May 22, 2011 at 12:38 PM, Steven <stev...@gmail.com> wrote:
>> Again, it's so that each element in a []struct{} or a struct{x, y
>> struct{}} has a different address.
>
> That's understandable but It's a little unfortunate
> to have a surprise like this.
>
> As an alternative solution, would it be possible to
> prohibit taking the address of a zero-length value?
> Then it's okay for Sizeof(struct{}{}) (as well as
> Sizeof([10]struct{}{})) to be 0. I'm sure this idea will
> turn up its own problems, but it feels a little more
> consistent to me.
>

> kr

I guess from a logical perspective that makes sense. I mean, how can
you take the address of nothing? I doubt I'll be able to prove to an
elitist door that I am a heavy-duty philosopher by holding a pointer
to data and a pointer to no data at the same time (potentially obscure
reference ftw).

The question I'd ask, though, is can you have a *struct{} at all, or
is it an illegal type? I can imagine using `new` to allocate pointers
to no data, essentially to get a unique value. I remember
container/loop used this technique (they used a *byte, actually, which
means allocating a superfluous byte) to determine whether a given
element belonged to a given loop instance, but then the mechanism was
abandoned when a bug was fixed. Perhaps, mirroring size zero types
being non-addressable, pointers to size zero types would be
non-dereferenceable.

The downside I see of making logical rules around size-zero types is
that it seems like a weird linguistic edge case that would complicate
the spec. I suppose, though, that it's an edge case that could be made
useful, rather than useless, to those who use it correctly, and that
the compiler would quickly disabuse anyone of any mistaken notions
should they stumble upon it unawares.

[Russ Cox]

> Do we want to encourage Go programmers to chan struct{} for channels that
> are used purely for synchronization (e.g., as semaphores, barriers, beacons,
> or signals), in preference to using chan int / chan bool / chan byte?

chan bool is fine. c <- true is easier to read than c <- struct{}{}.
Often the chan expands to carry real data soon enough anyway.

Russ

[Russ Cox]

> I guess from a logical perspective that makes sense. I mean, how can
> you take the address of nothing? I doubt I'll be able to prove to an
> elitist door that I am a heavy-duty philosopher by holding a pointer
> to data and a pointer to no data at the same time (potentially obscure
> reference ftw).
>
> The question I'd ask, though, is can you have a *struct{} at all, or
> is it an illegal type? I can imagine using `new` to allocate pointers
> to no data, essentially to get a unique value. I remember
> container/loop used this technique (they used a *byte, actually, which
> means allocating a superfluous byte) to determine whether a given
> element belonged to a given loop instance, but then the mechanism was
> abandoned when a bug was fixed. Perhaps, mirroring size zero types
> being non-addressable, pointers to size zero types would be
> non-dereferenceable.
>
> The downside I see of making logical rules around size-zero types is
> that it seems like a weird linguistic edge case that would complicate
> the spec. I suppose, though, that it's an edge case that could be made
> useful, rather than useless, to those who use it correctly, and that
> the compiler would quickly disabuse anyone of any mistaken notions
> should they stumble upon it unawares.

It may be fun to philosophize but there's only one answer here.
Whether the size of struct{} should be 0 or 1 is an implementation
detail, but there is no doubt that struct{} and *struct{} should be
allowed.

interface{} is okay; *interface{} is okay;
struct{} is okay; *struct{} is okay.
for{} is okay, select{} is okay, switch{} is okay,
if true {} is okay, i = 0 is okay.

Allowing the zero case in a manner continuous with the other cases
is always preferable to disallowing it, which creates a big discontinuity
in the behavior of the construct.

Russ

[Steven]

Yes, that's basically what I'd figured. Maybe I should stop trying to
impress the elitist door :). It just means that, practically,
stateless types have to have size 1 in all addressable situations. I
certainly can envision some ways to avoid this, but I can't see any
implementation using them, since they'd represent a discontinouity in
the rest of the implementation without much actual gain.

[chris dollin]

On 24 May 2011 16:07, Steven <stev...@gmail.com> wrote:

> Yes, that's basically what I'd figured. Maybe I should stop trying to
> impress the elitist door :). It just means that, practically,
> stateless types have to have size 1 in all addressable situations.

I really can't see that that's necessary. Let empty structs have
size zero and let's see if there are any real problems. Since
you can't distinguish them based on their component values,
or even on the possibility of changing those values, having
them sharing the same address doesn't seem to me to be
that much of a hazard.

Chris

(Awaiting wet fish, or egg, or maybe an ashmap.)

--
Chris "allusive" Dollin

[Steven]

It breaks the guarantee that &x != &y for any two distinct variables,
fields, or array elements x and y of the same type (ie. that are
comparable), which I feel would be another case of keeping the zero
case continuous with the general case. It means they won't be distinct
for the purposes of a map, for example. It would certainly be fine for
a struct{} to share memory with any value of a different type. For
example, in struct{b byte, s struct{}}, s and b can have the same
address without any repercussions on the semantics of the language,
outside of using unsafe. But this is the kind of optimization that I
doubt a compiler would make. I suppose if you have a [1000000]struct{b
byte, s struct{}}, it would be worth it, but this is hardly a regular
occurrence.

[Sameer Ajmani]

I'm concerned about the case when these channels have large buffers, e.g., when channels are used as semaphores or leaky-bucket rate limiters.  If the answer is "don't use channels for this," that's fine, but we ought to be clear on that (and provide sync.Semaphore and time.RateLimiter).

 

Russ

--
Sameer

[Russ Cox]

On Tue, May 24, 2011 at 12:34, Sameer Ajmani <sam...@google.com> wrote:
> I'm concerned about the case when these channels have large buffers, e.g.,
> when channels are used as semaphores or leaky-bucket rate limiters.  If the
> answer is "don't use channels for this," that's fine

Channels are for communication.
The buffer is allocated the same way it would for a slice.
I don't think we should optimize the "not communicating" case.
Some day there will be a sync.Semaphore.

Russ

[Sameer Ajmani]

Then we should change the example in Effective Go, since that encourages non-communicating uses of channels.

 

Russ

--
Sameer

[Russ Cox]

>> Channels are for communication.
>> The buffer is allocated the same way it would for a slice.
>> I don't think we should optimize the "not communicating" case.
>> Some day there will be a sync.Semaphore.
>
> Then we should change the example in Effective Go, since that encourages
> non-communicating uses of channels.

I think it's okay to have eye-opening examples in Effective Go.
It doesn't have to be a style guide. Also which example do you
mean? The leaky buffer is communicating values (a semaphore
does not) and for a 100-element buffer it's fine to use up 800
bytes of memory.

Russ

[Sameer Ajmani]

The semaphore example is the one I mean.  While it's fine at 100 values, it's less fine at 10,000 or 1M values.  When we have servers that support thousands of QPS, we might expect to see semaphores with limits in the 10K range.  It seems wasteful to spend 80KB of RAM when 8 bytes will do.  sync.Semaphore would address this.

The leaky buffer is fine; the buffer is a freelist of recycled values, so it makes sense to pay for the space to store these values.  I mentioned a "leaky-bucket rate limiter", which is different: I want to have a channel that emits values at a fixed rate (like time.Ticker) but also has a buffer to support short bursts.  I can create this trivially by composing time.Ticker with a buffered channel, but again I don't really *need* the buffered values.  I just need the count and synchronization that the channel provides.

A third example is using a channel as a barrier; again, no values are needed.  sync.WaitGroup() addresses this case directly, and as you said earlier, this case usually evolves to pass values anyway.

S

 

Russ

--
Sameer

[Michael Shields]

On Tue, May 24, 2011 at 8:46 AM, Steven <stev...@gmail.com> wrote:

It breaks the guarantee that &x != &y for any two distinct variables,
fields, or array elements x and y of the same type (ie. that are
comparable), which I feel would be another case of keeping the zero
case continuous with the general case. It means they won't be distinct
for the purposes of a map, for example.

Does Go actually have such a guarantee, or is it an implementation detail?  C does have this guarantee, but I can't find it in to Go language spec. 

[Russ Cox]

> Does Go actually have such a guarantee, or is it an implementation detail?
>  C does have this guarantee, but I can't find it in to Go language spec.

The spec does not have such a guarantee.
It's unclear to me whether it's something we'd want to specify.
Certainly the reasoning behind making the size 1 was to
ensure that &x[0] != &x[1] but in a language without pointer
arithmetic maybe that doesn't matter as much. We've been
led down the wrong path by C intuitions before. :-)

Russ

[Rob 'Commander' Pike]

I was surprised and confused by this, as my earlier messages showed. However, I do think there could be trouble if we allow a zero-sized element to an array such as a channel buffer. (What happens with x++ to get to the next element, for instance?) As you point out, though, I may just be confused by experience born of intuition.

-rob

[Russ Cox]

> I was surprised and confused by this, as my earlier messages showed.  However

> I do think there could be trouble if we allow a zero-sized element to an array such
> as a channel buffer.  (What happens with x++ to get to the next element, for instance?)

That x++ assumes that there's a C pointer x to increment,
but in fact the C channel code, since it is generic for any
possible channel element type, must use explicit math to
find the element: (byte)ch->base + ch->elemsize*i.
So in this case it wouldn't be a problem. We might run
into other problems of course, but I don't think the channel
math is one of them. It's a low-priority experiment but it
would be interesting to see what breaks, if someone else
wants to do some compiler+runtime hacking.

Russ

[Russ Cox]

> find the element: (byte)ch->base + ch->elemsize*i.

s/byte/byte*/ of course

[Steven]

> For an operand x of type T, the address operation &x generates a pointer of type *T to x. [...] For an operand x of pointer type *T, the pointer indirection *x denotes the value of type T pointed to by x.

In order for this to be true, for any value of non-zero size, &x[0] !=
&x[1], since two subsequent elements in an array cannot occupy the
same slot in memory. The only case where this can be and is ambiguous
is when values have size zero. This is what I meant, though
"guarantee" is perhaps too strong a word. I just meant that it would
break with what is definitely true for all non-zero-sized values in a
way that is potentially very confusing. To make this problem go away,
a size was assigned to values with no memory requirement, which is
practical, but academically dissatisfying and occasionally
inconvenient and unexpected.

[Steven]

I would like to add that either this *should* be a guarantee, or else
the implementation shouldn't go out of it's way to prop up incorrect
code. If it's easier to implement Go with no zero-sized values, that's
fine, but if the only justification is to save potential confusion,
then it should either go into the spec, or be discarded completely. If
it's left undefined, then it's enough of an unexpected edge case that
it should be mentioned (for variable definitions of "should", subject
to the discretion of experienced language designers, batteries sold
separately, some assembly required).

[Nigel Tao]

A related notion is that two slices refer to the same underlying array
only if the address of the (cap(s)-1)'th elements are equal. IIUC
there isn't any other way to check this. However, this is not
guaranteed by the spec.

It's not "if and only if", though. If you had a variable x of type
[3]struct{y [1] int} then &x[2] == &x[2].y[0].

I don't think allowing zero-sized structs changes the truth of the
"if" or "only if" claims.

I might be wrong, but I think it does become "if and only if" when you
also require the two slices to have the same type. Allowing zero-sized
structs will "break" this, but I don't know if this will matter in
practice. For example, you could possibly want to use such a
backed-by-the-same-array test during image composition, to check if a
source and destination image overlap and need to composited
right-to-left and/or bottom-to-top instead of in the natural order.
Allowing zero-sized pixels could theoretically give you a wrong
ordering, but wouldn't matter in practice.

Alternatively, you could just compare element addresses directly
instead of looking at the (cap(s)-1)th element's address, but that's
also not guaranteed by the spec...

FWIW, I prefer chan struct{} over chan bool to indicate that the value
communicated doesn't matter, only the act of communicating, but I seem
to be in the minority.

[Russ Cox]

> It's not "if and only if", though. If you had a variable x of type
> [3]struct{y [1] int} then &x[2] == &x[2].y[0].

That won't compile.

[Steven]

On Tue, May 24, 2011 at 10:08 PM, Nigel Tao <nige...@golang.org> wrote:

A related notion is that two slices refer to the same underlying array
only if the address of the (cap(s)-1)'th elements are equal. IIUC
there isn't any other way to check this. However, this is not
guaranteed by the spec.

It's not "if and only if", though. If you had a variable x of type
[3]struct{y [1] int} then &x[2] == &x[2].y[0].

&x[2] and &x[2].y[0] aren't comparable. Certainly, if you convert them to uintptr they are, but then you're venturing into the realm of unsafe, where anything is possible. Within the language constructs of Go, &x[2] != &x[2].y[0]. The compiler won't let you make such a silly comparison, but you can bypass this by doing interface{}(&x[2]) != interface{}(&x[2].y[0]). This clearly evaluates to false.

I don't think allowing zero-sized structs changes the truth of the
"if" or "only if" claims.

I might be wrong, but I think it does become "if and only if" when you
also require the two slices to have the same type.

The language requires this.

 

Allowing zero-sized structs will "break" this, but I don't know if this will matter in
practice. For example, you could possibly want to use such a
backed-by-the-same-array test during image composition, to check if a
source and destination image overlap and need to composited
right-to-left and/or bottom-to-top instead of in the natural order.

Hardly useful if your image consists of dataless pixels.

 

Allowing zero-sized pixels could theoretically give you a wrong
ordering, but wouldn't matter in practice.

Alternatively, you could just compare element addresses directly
instead of looking at the (cap(s)-1)th element's address, but that's
also not guaranteed by the spec...



FWIW, I prefer chan struct{} over chan bool to indicate that the value
communicated doesn't matter, only the act of communicating, but I seem
to be in the minority.

Syntactic weight comes in here. `done <- struct{}{}` is heavier and harder to decode than `done <- true`. Also, `done <- true` contains the words "done" and "true", which, even though the "true" is meaningless to the software, is a useful mnemonic for what the statement means.

[Steven]

On Tuesday, May 24, 2011, Steven <stev...@gmail.com> wrote:
> ...interface{}(&x[2]) != interface{}(&x[2].y[0]). This clearly evaluates to false.

s/false/true

Accidental double negative.

[Sameer Ajmani]

On May 24, 10:22 pm, Steven <steven...@gmail.com> wrote:

When used in a buffered channel, all instances of struct{} are
equivalent, so we can use a single mnemonically-named instance:

var acquire = struct{}{}
...
semaphore <- acquire

var signal = struct{}{}
...
done <- signal