Go vs Elixir, didn't work out so well for Go :-(

[TR NS]

I recently wrote a program that uses a genetic algorithm to determine the most ergonomic layout of a keyboard (a rather esoteric type of keyboard that I am working on). I originally wrote the program in Ruby, but it was very slow. So I decided to rewrite in another language. After some investigation I decided to write it twice, once in Go and then in Elixir. I thought it would a good way to get a feel for both of these new languages and to directly see how they compare.

Going into the project I fully expected the Go program to be the fastest and the Elixir program to be easier to write. Turns out I was dead wrong on both counts. The Go program I was able to knock out in just over a day. it was pretty easy. The Elixir program on the other hand took me 4 times that to work out. Functional programming can be a real mind bender! However the Elixir program could churn out results at a rate 20x faster than the Go program!!! The Go program was still faster than the Ruby, but not nearly by such a large margin.

Honestly I am rather disappointed. I really liked coding in Go. But the performance gain isn't enough to make it worth while. And I can't understand why it is so slow either. I surmised perhaps the Elixir code was taking advantage of my dual core processor, where as the Go code was not, but I still find that hard to account for a 20x difference.

So I thought I'd ask, if anyone has the patience to look over the code, perhaps there is something I am doing terribly wrong that explains it?

One thing I am looking at doing that might help is utilzing go routines. I suspect that will help some, but I doubt it will help 20 fold. Unfortunately I am finding that a little tricker than I thought it would be too, to go back and insert the use of go routines.

You can see all the code here: https://github.com/tabcomputing/corpus  (FYI the Ruby version is a little out of data compared to the other two).

Appreciate any insights.

[Jan Mercl]

On Mon, Aug 26, 2013 at 12:25 AM, TR NS <tran...@gmail.com> wrote:
> So I thought I'd ask, if anyone has the patience to look over the code,
> perhaps there is something I am doing terribly wrong that explains it?

Might be useful: http://blog.golang.org/profiling-go-programs

-j

[Dave Cheney]

Please try profiling your program. You may find this package useful,
github.com/davecheney/profile.

I suspect the bottleneck is math/rand, it usually is.

> --
> 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.

[Rémy Oudompheng]

Le 26 août 2013 00:25, "TR NS" <tran...@gmail.com> a écrit :
>
> I recently wrote a program that uses a genetic algorithm to determine the most ergonomic layout of a keyboard (a rather esoteric type of keyboard that I am working on). I originally wrote the program in Ruby, but it was very slow. So I decided to rewrite in another language. After some investigation I decided to write it twice, once in Go and then in Elixir. I thought it would a good way to get a feel for both of these new languages and to directly see how they compare.
>
> Going into the project I fully expected the Go program to be the fastest and the Elixir program to be easier to write. Turns out I was dead wrong on both counts. The Go program I was able to knock out in just over a day. it was pretty easy. The Elixir program on the other hand took me 4 times that to work out. Functional programming can be a real mind bender! However the Elixir program could churn out results at a rate 20x faster than the Go program!!! The Go program was still faster than the Ruby, but not nearly by such a large margin.
>
> Honestly I am rather disappointed. I really liked coding in Go. But the performance gain isn't enough to make it worth while. And I can't understand why it is so slow either. I surmised perhaps the Elixir code was taking advantage of my dual core processor, where as the Go code was not, but I still find that hard to account for a 20x difference.
>

Your Go code is highly unidiomatic and inefficient. The array.go file shouldn't even exist.

> So I thought I'd ask, if anyone has the patience to look over the code, perhaps there is something I am doing terribly wrong that explains it?

I think you should wait and be more experienced in both languages before doing a comparison: benchmarks are biased if you know a language better than the other.

Eliminate quadratic algorithms, use appropriate data structures. Use maps wisely.

> One thing I am looking at doing that might help is utilzing go routines. I suspect that will help some, but I doubt it will help 20 fold. Unfortunately I am finding that a little tricker than I thought it would be too, to go back and insert the use of go routines.

No, goroutines don't improve efficiency. They just bother more CPUs.

> You can see all the code here: https://github.com/tabcomputing/corpus  (FYI the Ruby version is a little out of data compared to the other two).
>
> Appreciate any insights.
>

[Kyle Lemons]

Highlights:

- Run gofmt.

- Make your code goinstallable -- that is, import it as "github.com/tabcomputing/corpus/go/keyboard" not "corpus/keyboard"

- Ditch the arrays.go file -- those are crazily inefficient or unnecessary in pretty much every case.

- Use "sync".Once instead of your cache thing

- Use rand.NewSource (one per goroutine), so you don't have a lock to fight with

- Use Perm for your shuffling

- load_words takes a max param but doesn't use it...

- use testing.Benchmark and ReportAllocs to test out some of your inner loops to evaluate their performance and memory allocation

- the stdlib style of Go uses CamelCase; no underscores in variable names and no all caps consts.

- comments start with the name of the function.  See effective go for comment style.

- `v := []T{}` followed by an append is usually written as `var v []T` which leverages the nil slice handling of append.

- if you have an if clause that returns, outdent the else

- for something like this, making types and methods for things like a population can often make code read more clearly.

- splitting things up into separate files for one method or one struct often makes it harder to follow, not easier.

- also:

Instead of writing something like

  fmt.Printf("%2s %2s %2s  %2s %2s %2s  %2s %2s %2s\n", iface(lay[0:9])...)

  ...

write 

  for i, v := range lay {

    fmt.Printf("%2s", v)

    switch i%9 {

      case 2, 5:

        fmt.Printf("  ")

      case 8:

        fmt.Printf("\n")

      default:

        fmt.Printf(" ")

    }

  }

or use text/tabwriter to columnate for you automagically.

[TR NS]

On Sunday, August 25, 2013 6:35:19 PM UTC-4, Dave Cheney wrote:

Please try profiling your program. You may find this package useful,
github.com/davecheney/profile.

Hmm... all I got was:

    (pprof) top10
    Total: 56402 samples
       56402 100.0% 100.0%    56402 100.0% etext
 
Also, I tried `gv` and `web` and got:

    sh: 1: dot: not found
    go tool pprof: signal: broken pipe

[Dave Cheney]

You'll need to install ghostscript to use gv/pdf/web. Having said
that, I don't think you've profiled correctly, there is no function
called etext in your supplied program, did you profile the correct
thing ?

[TR NS]

On Sunday, August 25, 2013 7:59:48 PM UTC-4, Kyle Lemons wrote:

Thanks for the suggestions. A couple follow-ups:

Highlights:

- Run gofmt.

- Make your code goinstallable -- that is, import it as "github.com/tabcomputing/corpus/go/keyboard" not "corpus/keyboard"

- Ditch the arrays.go file -- those are crazily inefficient or unnecessary in pretty much every case.

Do you mean there are other ways to do all of these things?

- find index of element in array
- determine if element is a member of an array
- detect duplicates elements
- swap two elements in an array given two indexes
 

- Use "sync".Once instead of your cache thing

- Use rand.NewSource (one per goroutine), so you don't have a lock to fight with

- Use Perm for your shuffling

Ok. `rand.Perm(myList.size)`, not how do I apply this random list of indexes to `myList` no get the shuffled list? Do I still need to iterate over the indexes and build-up a new array or is there something built-in I can use?
 

[TR NS]

On Monday, August 26, 2013 9:06:30 AM UTC-4, Dave Cheney wrote:

You'll need to install ghostscript to use gv/pdf/web. Having said
that, I don't think you've profiled correctly, there is no function
called etext in your supplied program, did you profile the correct
thing ?

Ah. I profiled the wrong binary.  Thanks!

[TR NS]

On Monday, August 26, 2013 9:09:56 AM UTC-4, TR NS wrote:

Ok. `rand.Perm(myList.size)`, not how do I apply this random list of indexes to `myList` no get the shuffled list? Do I still need to iterate over the indexes and build-up a new array or is there something built-in I can use?
 

Sorry, make that `rand.Perm(len(myList))`, and s/not/now/.

[mortdeus]

Use concurrency.

[James Bardin]

That gives you a slice of random ints. You either buildup a new slice if you don't care about the copy, or access the original through the random indexes. I'm fairly certain that your randomize function does not have even an distribution.

[mortdeus]

In general the problem is that you used the same mindset that you would use in other languages when implementing your software's design.

If your software doesnt look look alot like these pkgs https://github.com/golang/glog https://github.com/golang/groupcache, then you probably arent going to end up with an impressive solution to your problem. An idiomatic go development mentality is something that gradually grows on you after using the language for awhile. Until then experiment  with your software's design and start throwing away code. Go is a fun language to take apart and put back together again. 

[egon]

On Monday, August 26, 2013 4:09:56 PM UTC+3, TR NS wrote:

On Sunday, August 25, 2013 7:59:48 PM UTC-4, Kyle Lemons wrote:

Thanks for the suggestions. A couple follow-ups:

Highlights:

- Run gofmt.

- Make your code goinstallable -- that is, import it as "github.com/tabcomputing/corpus/go/keyboard" not "corpus/keyboard"

- Ditch the arrays.go file -- those are crazily inefficient or unnecessary in pretty much every case.

Do you mean there are other ways to do all of these things?

- find index of element in array
- determine if element is a member of an array
- detect duplicates elements

probably you should be using maps where needed, if you are using these operations very often...  e.g. "duplicates(child []string)" is a O(N^2) in the worst case, use something like:

func duplicates(child []string) []string {

dup := []string{}

seen := make(map[string]bool)

for _, c := range child {

if seen[c] {

dup = append(dup, c)

}

seen[c] = true

}

return dup

}

Also the duplicates check in "mutate" seems redundant, if you only swap two items, it shouldn't generate duplicates. The "swap" makes multiple copies in "mutate", just make a single copy, and then move keys around.

similarly all the indexes_... things can be converted to maps.... if you additionally before hand create a reverse "letter -> index" map, you'll probably get additional performance boost.

- swap two elements in an array given two indexes

 

a[first], a[second] = a[second], a[first]

 

In summary, it seems you are using inappropriate structures in your program. You should be using/scoring/manipulating "map[string]int" and/or "[]string" depending on the situation... for some operations one is better, for some the other... 

[Kyle Lemons]

If you take a step back, I think you'll find that you can represent each population as a member slice that never changes and an index slice that chooses which members are present in that population.  You can probably add extra fields to that struct that make it so that the other operations (e.g. membership, dedup) are O(1) or unnecessary.

--

[TR NS]

On Monday, August 26, 2013 4:09:42 PM UTC-4, Kyle Lemons wrote:

If you take a step back, I think you'll find that you can represent each population as a member slice that never changes and an index slice that chooses which members are present in that population.  You can probably add extra fields to that struct that make it so that the other operations (e.g. membership, dedup) are O(1) or unnecessary.

Nice idea. I will apply that. Thanks.

I point out however, I can apply the same optimization to my Elixir code. So I am still wondering why there is such a huge difference in speed between the two. --They are after all essentially the same program.

[Kyle Lemons]

One thing that Go has over a lot of other languages that have objects or classes is that a value takes up only as much space as its data.  That being said though, sure: a lot of optimizations you make in Go will apply to other languages too.  I find that the language tends to encourage good practices in a lot of different ways. 

[Michael Jones]

Often the "same idea" in two languages is demanding two very different implementations. It may be the same to the programmer, but the times reported for execution are a direct statement by the slower one of "ouch, I don't like doing it this way."

On Tue, Aug 27, 2013 at 2:03 PM, TR NS <tran...@gmail.com> wrote:

They are after all essentially the same program

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[atila...@gmail.com]

If it helps, my first and only Go project was a genetic algorithm framework:

https://github.com/atilaneves/genomego

Atila

[branimir....@gmail.com]

Culprit is index (strings,string) function.
Tink in this direction:

type Keyboard struct {
  Layout layout
  Score  int 
}

type layout struct {
  val []string
  index map[string]int
}

I have speed up more then three times program in this way.
slowest thing in program is following:
func score_letter(layout layout, letter, last string) float64 {
  score := scores[Base]

  if is_primary(layout, letter)    { score = score + scores[Primary]    }
  if is_point(layout, letter)      { score = score + scores[Point]      }
  if is_nonpoint(layout, letter)   { score = score + scores[NonPoint]   }
  if is_pinky(layout, letter)      { score = score + scores[Pinky]      }
  if is_horizontal(layout, letter) { score = score + scores[Horizontal] }
  if is_vertical(layout, letter)   { score = score + scores[Vertical]   }
  if is_doubletap(layout, letter)  { score = score + scores[DoubleTap] }
  if is_distant(layout, letter)    { score = score + scores[Distant] }

  if last != "" && is_concomitant(layout, last, letter) {
    score = score + scores[Concomitant]
  }

  return weigh(letter, score)
}
I have converted map to array and consts and that gave me another second or two...