7 ms·

Go code refactoring: the 23x performance hunt

177 points by anastalaz 8y ago

RyanZAG 8y ago
Kind of defeats the purpose of using golang for a task like this. The whole point of golang is using the little greenlet threads, but actually using them in this case is terrible on performance. The remaining performance left behind is all in memory allocation and garbage collection - something you could optimize relatively easily if it were written in C. Such as by using a memory pool, so that you wouldn't need allocations or garbage collection at all. Of course if performance isn't a big issue for your task, then none of this is really important.
- _ph_ 8y ago
  Using Go doesn’t mean you have to use many goroutines or must not do some manual memory management where it is the right thing to do. This article nicely shows how optimizing your program yields more speed than randomly throwing goroutines at it. Finally it does use goroutines for a good effect, but after proper consideration.
- iainmerrick 8y ago
  It's surprising that the per-file Goroutines were so expensive, though. (The original per-line Goroutine, sure, that's excessive if you care about performance.) Just using long-lived workers seems non-idiomatic for Go, but it certainly pays big dividends in this example.
  - RyanZAG 8y ago
    Yes, it does feel that something is wrong somewhere, but I can't find out where. Nobody would be using the idiomatic goroutine-per-task with that kind of overhead, yet it's one of the most common building blocks of golang projects.
  - jerf 8y ago
    Per-file may have had other problems not related to the Go runtime, such as IO contention. I'm not going to check it, but it would be easy to verify that just by using a limited number of them at a time. Spawning a new goroutine in that case is not strictly necessary, but would still be good software engineering. One of the problems I see repeatedly when people try to benchmark things with concurrency is when they don't specify a problem that is CPU-intensive enough, so it ends up blocked on other elements of the machine. For a task like this, I'd expect optimized Go to easily keep up with a conventional hard drive, and with just a bit of work, come within perhaps a factor of 2 or 3 of keeping up with the memory bandwidth on a consumer machine (including the fact that since you're going to read a bit, then write some stuff, you're not going to get the full sequential read performance out of your RAM), not because Go is teh awesomez but because the problem isn't that hard. To get big concurrency wins, you need a problem where the CPU is chewing away at something but isn't constantly hitting RAM or disk or network for it, such that those systems become the bottleneck.
    - val_deleplace 8y ago
      Hi jerf, please note that - the benchmark was designed to repeatedly parse an in-memory byte slice (not the hard drive), thus IO contention is unlikely here ; - concurrency is a big win when IO is a bottleneck : keep processing dozens of things while some of them are waiting for data from network or hdd.
      - jerf 8y ago
        "the benchmark was designed to repeatedly parse an in-memory byte slice (not the hard drive), thus IO contention is unlikely here" You could still be getting IO contention from the RAM system. RAM is not uniformly fast; certain access patterns are much faster than others. "concurrency is a big win when IO is a bottleneck : keep processing dozens of things while some of them are waiting for data from network or hdd." Concurrency is a win when IO is a bottleneck on a single task. Once you've got enough tasks running that all your IO is used up, adding more may not only fail to speed things up, but may slow things down. I'm speaking of situations where you've used up your IO. The tasks you're benchmarking are so easy per-byte that I think there's a good chance you used up your IO, which at this level of optimization, must include a concept of memory as IO. I think you'd be helped by stepping down another layer from the Go VM and thinking more about how the hardware itself works regardless of what code you are running on it. Go can't make the hardware do anything it couldn't physically do, and I'm getting a sense you deeply understand those limits.
  - val_deleplace 8y ago
    Hi iainmerrick, just for info the measured per-file cost didn't include reading from the filesystem. Only the in-memory parsing was taken into account.
- emperorcezar 8y ago
  It only does because the author is testing for their specific environment. At some number of cores, the concurrent calls will produce more performant code than running sequentially. Ideally, in this case I would think one would want to check the number of cores and decide what route to take.
  - scott_s 8y ago
    When the author removed parallelism the first time, I don't think this is the case. Running things in parallel has a cost. That cost often comes in the form of memory allocations and data copies so the unit of work can be stored and shared with another thread, and the synchronization costs of scheduling threads. If that aggregate cost is greater than the computational cost of what you're computing, you'll never win. For the point at which the author removed parallelism, and the sequential code was faster, I think this was the case. The computation was too fine-grain. The author successfully took advantage of parallelism by applying it at a coarser granularity; each thread did more work. At this point, the author also does tune the solution for the execution environment, as he uses a fixed set of go-routines to process a bunch of messages rather than one go-routine per message.
    - val_deleplace 8y ago
      scott_s you're totally right on both points. FWIW I really mean the "take the numbers with a grain of salt" advice, i.e. "Your mileage may vary". What I'm sharing in this article is not a bunch of hard, strong, exact numbers ; It's a journey and an invitation to apply similar reasoning process to your own use case and hardware.
      - scott_s 8y ago
        For the record, I enjoyed your post. It's a great example of what clear-headed performance optimization looks like.
- coldtea 8y ago
  >Kind of defeats the purpose of using golang for a task like this. The whole point of golang is using the little greenlet threads, but actually using them in this case is terrible on performance. The point of Golang is using them intelligently, not merely throwing at any problem like all you've got is a hammer...
- weberc2 8y ago
  I write single-threaded Go all the time, and you can use most of the same optimizations in Go that you could use in C (including pools). It's pretty easy to opt out of GC in Go. And you still keep all of the other benefits of using a modern, higher-level language (security, memory safety, straightforward tooling, etc).
todd8 8y ago
One of the things I like about go is that the path of least resistance is straightforward code. Getting a program working and working correctly while being straightforward is usually the starting point to getting a correct program that runs fast enough. Go's tools for testing and benchmarking and it's compilation speed make it relatively easy it iterate on a program while tuning it. This example was really nicely done; it's a classic problem, parsing input data. Some problems, on the other hand, require a different approach. See for example Knuth's wonderful introduction to boolean satisfiability in The Art of Computer Programing, Vol 4B, see [1]. Here the algorithms are really important to performance. [1] https://www.youtube.com/watch?v=g4lhrVPDUG0 https://www.youtube.com/watch?v=g4lhrVPDUG0
defertoreptar 8y ago
Great article. I was recently optimizing a go program. I was focusing on trying to improve the underlying algorithms, but then I realized after profiling that most of the time was spent creating temporary slices (many, many times). When I changed it to reuse existing slices, I saw a bigger performance gain than all the other effort combined.
- weberc2 8y ago
  Yeah, this is usually what I run into. I once had a recursive algorithm to collect a flat list of nodes in a tree. I found that building slices was the bottleneck, so I changed the signature to `func (t Tree) CountNodes() int` and `func (t Tree) Nodes(outSlice []Node)`, and then I'd call it like: nodes := make([]Node, t.CountNodes()) t.Nodes(nodes) Even though this required me to traverse the tree twice (once to count and the other to populate the list of nodes) the savings were considerable.
- tetha 8y ago
  Yeah, optimization is hard for two reasons: - No the bottleneck is somewhere else. Even considering this rule, it's not where you thought it to be even after discarding your first two ideas. - There is no end to optimization. You can just find the problem, and then move the problem to another part of the code. It's less like capture the flag, and more like hot (or slow) potato. I guess you could be done with optimizations if you've built thoroughly optimized ASICs, because then you can blame electrons for wiggling too slow. But at that point I'd be impressed, a lot.
pcwalton 8y ago
"The execution time is now dominated by the allocation and the garbage collection of small objects (e.g. the Message struct), which make sense because memory management operations are known to be relatively slow." A perfect example of why Go should switch to a generational garbage collector with bump allocation in the nursery, like Java HotSpot, .NET, V8, etc. etc. use. There are consequences to Go's decision to make extreme throughput sacrifices in order to optimize for latency (low pause times) above all else.
- foldr 8y ago
  It's worth noting that Go, unlike Java, can pass objects by value. That makes it less crucial for the GC to be able to deal efficiently with small allocations, since a typical Go program will have considerably fewer of these than a typical Java program.
  - pcwalton 8y ago
    Same with .NET (C#), where the generational hypothesis certainly holds and therefore .NET has a generational garbage collector. It's also pretty bad from an ergonomics (not to mention performance) perspective if the programmer has to manually switch to by-value copying of structs in order to keep escape analysis happy and avoid allocation.
    - foldr 8y ago
      Nonetheless, having copy-by-value semantics available for small objects reduces the need for a generational collector. I'm not sure what you're referring to w.r.t ergonomics. Passing small structs by value should probably be the default choice in Go, and it is not difficult to switch from passing via a pointer to passing by value.
      - yxhuvud 8y ago
        It reduces the need for a collector, any collector, as there will be less garbage. You have not made any arguments that indicate or even hint that the actual share of young objects that will be generated will be reduced.
jeffrallen 8y ago
Go sucks! (First post.)
nefasti 8y ago
Does anyone now profiling tools like that for node.js?
crb002 8y ago
One trick I use is passing data files through the command line "sort", "uniq", and "wc" utilities. Those are great benchmarks to see how off you are from tuned code on your machine.

177 points by anastalaz 8y ago

Kind of defeats the purpose of using golang for a task like this. The whole point of golang is using the little greenlet threads, but actually using them in this case is terrible on performance. The remaining performance left behind is all in memory allocation and garbage collection - something you could optimize relatively easily if it were written in C. Such as by using a memory pool, so that you wouldn't need allocations or garbage collection at all. Of course if performance isn't a big issue for your task, then none of this is really important.

_ph_ 8y ago
Using Go doesn’t mean you have to use many goroutines or must not do some manual memory management where it is the right thing to do. This article nicely shows how optimizing your program yields more speed than randomly throwing goroutines at it. Finally it does use goroutines for a good effect, but after proper consideration.
iainmerrick 8y ago
It's surprising that the per-file Goroutines were so expensive, though. (The original per-line Goroutine, sure, that's excessive if you care about performance.) Just using long-lived workers seems non-idiomatic for Go, but it certainly pays big dividends in this example.
- RyanZAG 8y ago
  Yes, it does feel that something is wrong somewhere, but I can't find out where. Nobody would be using the idiomatic goroutine-per-task with that kind of overhead, yet it's one of the most common building blocks of golang projects.
- jerf 8y ago
  Per-file may have had other problems not related to the Go runtime, such as IO contention. I'm not going to check it, but it would be easy to verify that just by using a limited number of them at a time. Spawning a new goroutine in that case is not strictly necessary, but would still be good software engineering. One of the problems I see repeatedly when people try to benchmark things with concurrency is when they don't specify a problem that is CPU-intensive enough, so it ends up blocked on other elements of the machine. For a task like this, I'd expect optimized Go to easily keep up with a conventional hard drive, and with just a bit of work, come within perhaps a factor of 2 or 3 of keeping up with the memory bandwidth on a consumer machine (including the fact that since you're going to read a bit, then write some stuff, you're not going to get the full sequential read performance out of your RAM), not because Go is teh awesomez but because the problem isn't that hard. To get big concurrency wins, you need a problem where the CPU is chewing away at something but isn't constantly hitting RAM or disk or network for it, such that those systems become the bottleneck.
  - val_deleplace 8y ago
    Hi jerf, please note that - the benchmark was designed to repeatedly parse an in-memory byte slice (not the hard drive), thus IO contention is unlikely here ; - concurrency is a big win when IO is a bottleneck : keep processing dozens of things while some of them are waiting for data from network or hdd.
    - jerf 8y ago
      "the benchmark was designed to repeatedly parse an in-memory byte slice (not the hard drive), thus IO contention is unlikely here" You could still be getting IO contention from the RAM system. RAM is not uniformly fast; certain access patterns are much faster than others. "concurrency is a big win when IO is a bottleneck : keep processing dozens of things while some of them are waiting for data from network or hdd." Concurrency is a win when IO is a bottleneck on a single task. Once you've got enough tasks running that all your IO is used up, adding more may not only fail to speed things up, but may slow things down. I'm speaking of situations where you've used up your IO. The tasks you're benchmarking are so easy per-byte that I think there's a good chance you used up your IO, which at this level of optimization, must include a concept of memory as IO. I think you'd be helped by stepping down another layer from the Go VM and thinking more about how the hardware itself works regardless of what code you are running on it. Go can't make the hardware do anything it couldn't physically do, and I'm getting a sense you deeply understand those limits.
- val_deleplace 8y ago
  Hi iainmerrick, just for info the measured per-file cost didn't include reading from the filesystem. Only the in-memory parsing was taken into account.
emperorcezar 8y ago
It only does because the author is testing for their specific environment. At some number of cores, the concurrent calls will produce more performant code than running sequentially. Ideally, in this case I would think one would want to check the number of cores and decide what route to take.
- scott_s 8y ago
  When the author removed parallelism the first time, I don't think this is the case. Running things in parallel has a cost. That cost often comes in the form of memory allocations and data copies so the unit of work can be stored and shared with another thread, and the synchronization costs of scheduling threads. If that aggregate cost is greater than the computational cost of what you're computing, you'll never win. For the point at which the author removed parallelism, and the sequential code was faster, I think this was the case. The computation was too fine-grain. The author successfully took advantage of parallelism by applying it at a coarser granularity; each thread did more work. At this point, the author also does tune the solution for the execution environment, as he uses a fixed set of go-routines to process a bunch of messages rather than one go-routine per message.
  - val_deleplace 8y ago
    scott_s you're totally right on both points. FWIW I really mean the "take the numbers with a grain of salt" advice, i.e. "Your mileage may vary". What I'm sharing in this article is not a bunch of hard, strong, exact numbers ; It's a journey and an invitation to apply similar reasoning process to your own use case and hardware.
    - scott_s 8y ago
      For the record, I enjoyed your post. It's a great example of what clear-headed performance optimization looks like.
coldtea 8y ago
>Kind of defeats the purpose of using golang for a task like this. The whole point of golang is using the little greenlet threads, but actually using them in this case is terrible on performance. The point of Golang is using them intelligently, not merely throwing at any problem like all you've got is a hammer...
weberc2 8y ago
I write single-threaded Go all the time, and you can use most of the same optimizations in Go that you could use in C (including pools). It's pretty easy to opt out of GC in Go. And you still keep all of the other benefits of using a modern, higher-level language (security, memory safety, straightforward tooling, etc).

todd8 8y ago

One of the things I like about go is that the path of least resistance is straightforward code. Getting a program working and working correctly while being straightforward is usually the starting point to getting a correct program that runs fast enough. Go's tools for testing and benchmarking and it's compilation speed make it relatively easy it iterate on a program while tuning it. This example was really nicely done; it's a classic problem, parsing input data. Some problems, on the other hand, require a different approach. See for example Knuth's wonderful introduction to boolean satisfiability in The Art of Computer Programing, Vol 4B, see [1]. Here the algorithms are really important to performance. [1] https://www.youtube.com/watch?v=g4lhrVPDUG0 https://www.youtube.com/watch?v=g4lhrVPDUG0

defertoreptar 8y ago

Great article. I was recently optimizing a go program. I was focusing on trying to improve the underlying algorithms, but then I realized after profiling that most of the time was spent creating temporary slices (many, many times). When I changed it to reuse existing slices, I saw a bigger performance gain than all the other effort combined.

weberc2 8y ago
Yeah, this is usually what I run into. I once had a recursive algorithm to collect a flat list of nodes in a tree. I found that building slices was the bottleneck, so I changed the signature to `func (t Tree) CountNodes() int` and `func (t Tree) Nodes(outSlice []Node)`, and then I'd call it like: nodes := make([]Node, t.CountNodes()) t.Nodes(nodes) Even though this required me to traverse the tree twice (once to count and the other to populate the list of nodes) the savings were considerable.
tetha 8y ago
Yeah, optimization is hard for two reasons: - No the bottleneck is somewhere else. Even considering this rule, it's not where you thought it to be even after discarding your first two ideas. - There is no end to optimization. You can just find the problem, and then move the problem to another part of the code. It's less like capture the flag, and more like hot (or slow) potato. I guess you could be done with optimizations if you've built thoroughly optimized ASICs, because then you can blame electrons for wiggling too slow. But at that point I'd be impressed, a lot.

pcwalton 8y ago

"The execution time is now dominated by the allocation and the garbage collection of small objects (e.g. the Message struct), which make sense because memory management operations are known to be relatively slow." A perfect example of why Go should switch to a generational garbage collector with bump allocation in the nursery, like Java HotSpot, .NET, V8, etc. etc. use. There are consequences to Go's decision to make extreme throughput sacrifices in order to optimize for latency (low pause times) above all else.

foldr 8y ago
It's worth noting that Go, unlike Java, can pass objects by value. That makes it less crucial for the GC to be able to deal efficiently with small allocations, since a typical Go program will have considerably fewer of these than a typical Java program.
- pcwalton 8y ago
  Same with .NET (C#), where the generational hypothesis certainly holds and therefore .NET has a generational garbage collector. It's also pretty bad from an ergonomics (not to mention performance) perspective if the programmer has to manually switch to by-value copying of structs in order to keep escape analysis happy and avoid allocation.
  - foldr 8y ago
    Nonetheless, having copy-by-value semantics available for small objects reduces the need for a generational collector. I'm not sure what you're referring to w.r.t ergonomics. Passing small structs by value should probably be the default choice in Go, and it is not difficult to switch from passing via a pointer to passing by value.
    - yxhuvud 8y ago
      It reduces the need for a collector, any collector, as there will be less garbage. You have not made any arguments that indicate or even hint that the actual share of young objects that will be generated will be reduced.

jeffrallen 8y ago

Go sucks! (First post.)

nefasti 8y ago

Does anyone now profiling tools like that for node.js?

crb002 8y ago

One trick I use is passing data files through the command line "sort", "uniq", and "wc" utilities. Those are great benchmarks to see how off you are from tuned code on your machine.