code review 881042: Reworked k-nucleotide benchmark to use goroutines/cha...

Reworked k-nucleotide benchmark to use goroutines/channels for parallelism.
	    Goes from ~12s to ~7.7 on my two-core machine.
        I'm not sure if the goal is to have the Go programs here work the same as the C
        versions or to have them do what is most efficient; this change assumes the latter.

[Kyle C, 2010-04-02 00:11:22]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[r2, 2010-04-02 04:03:15]

As long as it gets the right answer honestly (which is a relative term, I know)
any algorithm will do.  It must produce the same output as the C program.

However, I would like to keep parallel implementations separate from sequential
because they are heavily processor-dependent and are properly consider a
different exercise.    Compare spectral-norm.go with spectral-norm-parallel.go,
for instance.

-rob

On Apr 1, 2010, at 5:11 PM, consalus@gmail.com wrote:

> Reviewers: golang-dev_googlegroups.com,
> 
> Message:
> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
> 
> I'd like you to review this change.
> 
> 
> Description:
> 		Reworked k-nucleotide benchmark to use goroutines/channels for
> parallelism.
> 	    Goes from ~12s to ~7.7 on my two-core machine.
>        I'm not sure if the goal is to have the Go programs here work
> the same as the C
>        versions or to have them do what is most efficient; this change
> assumes the latter.
> 
> Please review this at http://codereview.appspot.com/881042/show
> 
> Affected files:
>  M test/bench/k-nucleotide.go
> 
> 
> Index: test/bench/k-nucleotide.go
> ===================================================================
> --- a/test/bench/k-nucleotide.go
> +++ b/test/bench/k-nucleotide.go
> @@ -44,8 +44,6 @@
> 	"sort"
> )
> 
> -var in *bufio.Reader
> -
> func count(data string, n int) map[string]int {
> 	counts := make(map[string]int)
> 	top := len(data) - n
> @@ -80,16 +78,14 @@
> 	kn := make(kNucArray, len(m))
> 	i := 0
> 	for k, v := range m {
> -		kn[i].name = k
> -		kn[i].count = v
> +		kn[i] = kNuc{k, v}
> 		i++
> 	}
> 	sort.Sort(kn)
> 	return kn
> }
> 
> -func print(m map[string]int) {
> -	a := sortedArray(m)
> +func printKnucs(a kNucArray) {
> 	sum := 0
> 	for _, kn := range a {
> 		sum += kn.count
> @@ -97,10 +93,11 @@
> 	for _, kn := range a {
> 		fmt.Printf("%s %.3f\n", kn.name, 100*float64(kn.count)/float64(sum))
> 	}
> +	fmt.Print("\n")
> }
> 
> func main() {
> -	in = bufio.NewReader(os.Stdin)
> +	in := bufio.NewReader(os.Stdin)
> 	three := []byte(">THREE ")
> 	for {
> 		line, err := in.ReadSlice('\n')
> @@ -127,14 +124,32 @@
> 	}
> 	str := string(data[0:j])
> 
> -	print(count(str, 1))
> -	fmt.Print("\n")
> -
> -	print(count(str, 2))
> -	fmt.Print("\n")
> +	var arr1, arr2 kNucArray
> +	countsdone := make(chan bool)
> +	go func() {
> +		arr1 = sortedArray(count(str, 1))
> +		countsdone <- true
> +	}()
> +	go func() {
> +		arr2 = sortedArray(count(str, 2))
> +		countsdone <- true
> +	}()
> 
> 	interests := []string{"GGT", "GGTA", "GGTATT", "GGTATTTTAATT",
"GGTATTTTAATTTATAGT"}
> -	for _, s := range interests {
> -		fmt.Printf("%d %s\n", countOne(str, s), s)
> +	results := make([]chan string, len(interests))
> +	for i, s := range interests {
> +		ch := make(chan string)
> +		results[i] = ch
> +		go func(result chan string, ss string) {
> +			result <- fmt.Sprintf("%d %s\n", countOne(str, ss), ss)
> +		}(ch, s)
> 	}
> +	<-countsdone
> +	<-countsdone
> +	printKnucs(arr1)
> +	printKnucs(arr2)
> +	for _, rc := range results {
> +		fmt.Print(<-rc)
> +	}
> +
> }
> 
> 
> 
> 
> -- 
> To unsubscribe, reply using "remove me" as the subject.

[rsc, 2010-04-02 04:13:38]

I'd also like to have the C and Go versions of the
same program be somewhat comparable, so that
comparing their runtime compares the compilers fairly.
For example, when I converted reverse complement
to a better algorithm I also updated the C program.
It sounds like this one should be a separate file.
If you hg cp k-nucleotide.go k-nucleotide-parallel.go
then you can edit the latter and the diffs will display
nicely in the code review.  You'll want to edit the
test script to run it too.

Thanks.
Russ

[Kyle C, 2010-04-02 17:38:23]

On 2010/04/02 04:13:38, rsc wrote:
> I'd also like to have the C and Go versions of the
> same program be somewhat comparable, so that
> comparing their runtime compares the compilers fairly.
> For example, when I converted reverse complement
> to a better algorithm I also updated the C program.
> It sounds like this one should be a separate file.
> If you hg cp k-nucleotide.go k-nucleotide-parallel.go
> then you can edit the latter and the diffs will display
> nicely in the code review.  You'll want to edit the
> test script to run it too.

Currently, the test script doesn't appear to run the other "-parallel"  variant.
Should I add both to the script?
> 
> Thanks.
> Russ
>

[Kyle C, 2010-04-02 17:39:23]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

Please take another look.

[Kyle C, 2010-04-03 00:14:40]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc1, 2010-04-06 05:31:39]

LGTM

thanks

[rsc, 2010-04-06 05:32:41]

*** Submitted as http://code.google.com/p/go/source/detail?r=d927697df300 ***

test/bench: add k-nucleotide-parallel

R=rsc
CC=golang-dev
http://codereview.appspot.com/881042

Committer: Russ Cox <rsc@golang.org>