Question about Chan.c selectgo function
47 views
Skip to first unread message
Andy Frances
Jan 12, 2011, 1:58:09 PM1/12/11
to golang-nuts
Hi Folks:
I apologise for this being a little off the beaten Go track....
A few months back I wrote stackless.py (Stackless Python module for PyPy - A Python written in Python) version that implemented select. However I used the libthread.c and Rob Pike's "Implementation of Newsqueak" as the references. This seems to be the best place to discuss how the select algorithm works.
Right now I want to experiment with the select algorithm.
I am looking at the selectgo function of chan.c. Once again, I don't quite understand what the purpose of the sorting to get the locking order. I am also a bit confused over the use of the prime numbers. Is Pike's one pass technique still being used? If we are choosing any ready one at random, why does the locking order matter?
The reason I am asking is that I was thinking of adding a timestamp to channel operations, as opposed to using the one pass algorithm in the Newsqueak paper. In the case of finding ready channels in a set of select chanels, the one with the lowest timestamp would be chosen (or I could ensure that operations are entered in temporal order). I don't see why this approach would not be fair since the scheduler ensures that a chatty coroutine does not monopolise. What am I missing?
I am also interested in a notion from complex event processing (C.E.P) called "orderly observation." That is if event A causes event B, then the timestamp of event A is lower than event B. Again, I am not sure if non-determinism is good to have if I want to support this property. So I am interested in a select that provides better support for this.
The second thing I am interested in testing is a lazier teardown in the select. Essentially I would pass a hint to select for situations where I have
while(True) {
select {
}
}
The last thing is to adapt select to support a form of join pattern.
Cheers,
Andrew
I apologise for this being a little off the beaten Go track....
A few months back I wrote stackless.py (Stackless Python module for PyPy - A Python written in Python) version that implemented select. However I used the libthread.c and Rob Pike's "Implementation of Newsqueak" as the references. This seems to be the best place to discuss how the select algorithm works.
Right now I want to experiment with the select algorithm.
I am looking at the selectgo function of chan.c. Once again, I don't quite understand what the purpose of the sorting to get the locking order. I am also a bit confused over the use of the prime numbers. Is Pike's one pass technique still being used? If we are choosing any ready one at random, why does the locking order matter?
The reason I am asking is that I was thinking of adding a timestamp to channel operations, as opposed to using the one pass algorithm in the Newsqueak paper. In the case of finding ready channels in a set of select chanels, the one with the lowest timestamp would be chosen (or I could ensure that operations are entered in temporal order). I don't see why this approach would not be fair since the scheduler ensures that a chatty coroutine does not monopolise. What am I missing?
I am also interested in a notion from complex event processing (C.E.P) called "orderly observation." That is if event A causes event B, then the timestamp of event A is lower than event B. Again, I am not sure if non-determinism is good to have if I want to support this property. So I am interested in a select that provides better support for this.
The second thing I am interested in testing is a lazier teardown in the select. Essentially I would pass a hint to select for situations where I have
while(True) {
select {
}
}
The last thing is to adapt select to support a form of join pattern.
Cheers,
Andrew
Nigel Tao
Jan 12, 2011, 6:02:57 PM1/12/11
to Andy Frances, golang-nuts
On 13 January 2011 05:58, Andy Frances <af.sta...@gmail.com> wrote:
> I am looking at the selectgo function of chan.c. Once again, I don't quite
> understand what the purpose of the sorting to get the locking order.
> I am looking at the selectgo function of chan.c. Once again, I don't quite
> understand what the purpose of the sorting to get the locking order.
Sorting the locks is for deadlock avoidance. It ensures that all
threads try to acquire locks in the same order.
I don't have any answers for your other questions. Sorry.
Russ Cox
Jan 14, 2011, 2:57:08 PM1/14/11
to Andy Frances, golang-nuts
> The second thing I am interested in testing is a lazier teardown in the
> select. Essentially I would pass a hint to select for situations where I
> have
>
> while(True) {
> select {
> }
> }
> select. Essentially I would pass a hint to select for situations where I
> have
>
> while(True) {
> select {
> }
> }
I think you could make this a little more efficient but you would still
have to make sure the other branches could not be selected while
one was running. So you'd run the risk of leaving dead communications
offerings on the channel queues, and if there were many selects
on the same channel the opposite operation would have to scan
through those queues instead of being O(1). But that's probably
less likely.
So far select hasn't been a bottleneck for us.
Russ
Eoghan Sherry
Jan 18, 2011, 7:05:15 PM1/18/11
to Andy Frances, golang-nuts
On 12 January 2011 13:58, Andy Frances <af.sta...@gmail.com> wrote:
> I am looking at the selectgo function of chan.c. Once again, I don't quite
> understand what the purpose of the sorting to get the locking order. I am
> also a bit confused over the use of the prime numbers. Is Pike's one pass
> technique still being used? If we are choosing any ready one at random, why
> does the locking order matter?
> I am looking at the selectgo function of chan.c. Once again, I don't quite
> understand what the purpose of the sorting to get the locking order. I am
> also a bit confused over the use of the prime numbers. Is Pike's one pass
> technique still being used? If we are choosing any ready one at random, why
> does the locking order matter?
The case selection algorithm is different from the one used in
squint. Using a random initial offset o and a random p relatively
prime to sel->ncase (gdc(p,sel->ncase)==1), the cases are visted
in the order (o+i*p)%sel->ncase for i from 0 to n-1.
This isn't always fair. See,
http://code.google.com/p/go/issues/detail?id=1425
http://codereview.appspot.com/4037043/
Eoghan
Andy Frances
Jan 18, 2011, 10:50:56 PM1/18/11
to r...@golang.org, golang-nuts
Hi Russ and Nigel:
goroutine S
select {
case a = <- chanA:
....
case b = <- chanB:
....
case c = <- chanC:
goroutine R
chanA <- someValue;
Russ, thanks for the answer. Assuming no tear down, I am trying to imagine the scenarios where another branch (case b) is selected while one is running (i.e, case a)? 1) A channel is shared by a goroutine in another scheduler (or m in is referred to in proc.c). 2) The goroutine running the branch has yielded (less likely). Anyhow in both situations the goroutine is executing.
Maybe this is messy (and hopefully I am not mistaking Plan9 with Go) but perhaps the algorithm could work in the following fashion: when R executes, it sees S on chanB's receive queue (since we haven't tore down the remaining queues) . However R also checks the state of S. If S is running, it removes S from the receive queue but it also places itself on chanB's send queue and suspends. The next time S executes the select, it will detect chanB as ready and the select algorithm proceeds as normal.
What am I missing?
On Fri, Jan 14, 2011 at 2:57 PM, Russ Cox <r...@golang.org> wrote:
> The second thing I am interested in testing is a lazier teardown in theI think you could make this a little more efficient but you would still
> select. Essentially I would pass a hint to select for situations where I
> have
>
> while(True) {
> select {
> }
> }
have to make sure the other branches could not be selected while
one was running.
goroutine S
select {
case a = <- chanA:
....
case b = <- chanB:
....
case c = <- chanC:
goroutine R
chanA <- someValue;
Russ, thanks for the answer. Assuming no tear down, I am trying to imagine the scenarios where another branch (case b) is selected while one is running (i.e, case a)? 1) A channel is shared by a goroutine in another scheduler (or m in is referred to in proc.c). 2) The goroutine running the branch has yielded (less likely). Anyhow in both situations the goroutine is executing.
Maybe this is messy (and hopefully I am not mistaking Plan9 with Go) but perhaps the algorithm could work in the following fashion: when R executes, it sees S on chanB's receive queue (since we haven't tore down the remaining queues) . However R also checks the state of S. If S is running, it removes S from the receive queue but it also places itself on chanB's send queue and suspends. The next time S executes the select, it will detect chanB as ready and the select algorithm proceeds as normal.
What am I missing?
So you'd run the risk of leaving dead communications
offerings on the channel queues, and if there were many selects
on the same channel the opposite operation would have to scan
through those queues instead of being O(1). But that's probably
less likely.
So far select hasn't been a bottleneck for us.
Russ you may be right about it not being worth the effort.
Cheers,
Andrew
Cheers,
Andrew
Russ Cox
Jan 19, 2011, 10:10:58 AM1/19/11
to Andy Frances, golang-nuts
> What am I missing?
Perhaps nothing; my point was only that the bookkeeping gets messy.
Russ
Andy Frances
Jan 19, 2011, 1:28:23 PM1/19/11
to Eoghan Sherry, golang-nuts
Hi Eoghan:
Thanks for the explanation. I'll go through the code again. However I am curious about
why this algorithm is needed. Why isn't simply processing chanops in a first come first
serve fashion fair, if one has a round-robin scheduler also? Again is the randomness an
artifact of Newsqueak or in keeping with the non-determinism of CSP?
Cheers,
Andrew
Rob 'Commander' Pike
Jan 19, 2011, 1:35:22 PM1/19/11
to Andy Frances, Eoghan Sherry, golang-nuts
On Jan 19, 2011, at 10:28 AM, Andy Frances wrote:
> Hi Eoghan:
>
> Thanks for the explanation. I'll go through the code again. However I am curious about
> why this algorithm is needed. Why isn't simply processing chanops in a first come first
> serve fashion fair, if one has a round-robin scheduler also? Again is the randomness an
> artifact of Newsqueak or in keeping with the non-determinism of CSP?
Non-determinism helps stop you writing bad code that depends on scheduling order.
-rob
messi
Jan 19, 2011, 10:48:31 PM1/19/11
to golang-nuts
I am new to Non-determinism. Below program is written in the Go way to
generate randomness, is it ok? I'm wide open to criticism.
package main
import (
"time"
"runtime"
"flag"
"log"
"fmt"
"big"
)
type SC struct {
s string
pos int
}
type Next struct {
isFirst bool
}
var (
KEYLENGTH = flag.Int("l", 32, "length")
RandType = flag.String("t", "int", "Return Types")
c = make(chan *SC)
next = make(chan *Next, 1)
randString string
Chars []byte
zero = big.NewInt(0)
)
func Gorand() (iface interface{}) {
runtime.GOMAXPROCS(2)
flag.Parse()
switch *RandType {
case "url", "string":
Chars =
[]byte("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
case "int":
Chars = []byte("0123456789")
}
Start:
next <- &Next{true}
for i := 0; i < *KEYLENGTH; i++ {
i := i
go func() {
for {
select {
case n := <-next:
a := int64(i)
b := time.Nanoseconds() / 1000
X0 := int64(1)
m := int64(1<<47-1)
X1 := (a*X0+b)%m
randChar := string(Chars[X1%int64(len(Chars))])
if n.isFirst == true {
for randChar == "0" {
b = time.Nanoseconds() / 1000
X1 = (a*X0+b)%m
randChar = string(Chars[X1%int64(len(Chars))])
}
}
c <- &SC{randChar, i}
return
}
}
}()
}
keyLength := *KEYLENGTH
for {
select {
case out := <-c:
randString += out.s
keyLength--
if keyLength == 0 {
switch *RandType {
case "url", "string":
return randString
case "int":
randomNum, bool := zero.SetString(randString, 10)
if bool != true {
log.Panicln("cannot convert string
to big.Int. ")
}
return randomNum
}
}
next <- &Next{false}
}
}
return
}
func main() {
*KEYLENGTH = 32
key := Gorand().(*big.Int)
fmt.Print(key)
}
generate randomness, is it ok? I'm wide open to criticism.
package main
import (
"time"
"runtime"
"flag"
"log"
"fmt"
"big"
)
type SC struct {
s string
pos int
}
type Next struct {
isFirst bool
}
var (
KEYLENGTH = flag.Int("l", 32, "length")
RandType = flag.String("t", "int", "Return Types")
c = make(chan *SC)
next = make(chan *Next, 1)
randString string
Chars []byte
zero = big.NewInt(0)
)
func Gorand() (iface interface{}) {
runtime.GOMAXPROCS(2)
flag.Parse()
switch *RandType {
case "url", "string":
Chars =
[]byte("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
case "int":
Chars = []byte("0123456789")
}
Start:
next <- &Next{true}
for i := 0; i < *KEYLENGTH; i++ {
i := i
go func() {
for {
select {
case n := <-next:
a := int64(i)
b := time.Nanoseconds() / 1000
X0 := int64(1)
m := int64(1<<47-1)
X1 := (a*X0+b)%m
randChar := string(Chars[X1%int64(len(Chars))])
if n.isFirst == true {
for randChar == "0" {
b = time.Nanoseconds() / 1000
X1 = (a*X0+b)%m
randChar = string(Chars[X1%int64(len(Chars))])
}
}
c <- &SC{randChar, i}
return
}
}
}()
}
keyLength := *KEYLENGTH
for {
select {
case out := <-c:
randString += out.s
keyLength--
if keyLength == 0 {
switch *RandType {
case "url", "string":
return randString
case "int":
randomNum, bool := zero.SetString(randString, 10)
if bool != true {
log.Panicln("cannot convert string
to big.Int. ")
}
return randomNum
}
}
next <- &Next{false}
}
}
return
}
func main() {
*KEYLENGTH = 32
key := Gorand().(*big.Int)
fmt.Print(key)
}
Russ Cox
Jan 19, 2011, 11:30:52 PM1/19/11
to messi, golang-nuts
You'd be much better off using package rand or package crypto/rand.
Russ
Reply all
Reply to author
Forward
0 new messages