3 ms·

Author here. Just a note that by latency-critical, I'm referring to >10 millisecond latencies. If you can tolerate occasional pauses of 400-500 milliseconds, th

Author here. Just a note that by latency-critical, I'm referring to >10 millisecond latencies. If you can tolerate occasional pauses of 400-500 milliseconds, then the GC wouldn't be a problem. Also note that the GC slowness came from having to scan a fairly large heap (a lot of cached stuff); it could be avoided by storing all that off-heap, but I suspect that would complicate the code significantly. Finally, note that by "at least an order of magnitude worse" I'm comparing it to hyper-optimised C++ that's designed for sub-millisecond latencies, as the C++ server used the same framework used in latency-critical HFT software.

acqq 12y ago
Thanks, more than that, I also know that there are many in-house implementations written in C++ with significantly worse performances than those of the good garbage collected libraries. Sloppy programming can always make slow products. It's still good to know where the limits are and I thank you for the honest report.
Loic 12y ago
Effectively, you need to keep a small heap and if possible have "simple" data structure. In my case, I implemented the Python code of a trie based levenshtein distance algorithm[0]. I used maps because it was basically a direct translation of the Python code. This resulted in millions of maps and oft the index would just stop in the garbage collector for a couple of seconds. I solved it using my own map which is travelled linearly. type SpellCheckerMap struct { Runes []rune Nodes []*SpellCheckerNode } with only few runes, I can just go through the list to find the index of the following node. You save the computation of the map hash key. It is pretty fast, here is an example of a spelling suggestion over a 500,000 words corpus[1]. Basically, the garbage collection cost forced me to think about a better data structure for my case. Maybe not that bad all in all. [0]: http://stevehanov.ca/blog/index.php?id=114 http://stevehanov.ca/blog/index.php?id=114 [1]: https://www.chemeo.com/search?q=asparine https://www.chemeo.com/search?q=asparine
- danieldk 12y ago
  Semi-offtopic: The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can be stored in a flat array/slice). This gives you O(n) time lookups, where n is the length of the word, and reduces much of the redundancy in a dictionary. Words within an edit distance can be found by computing a Levenshtein automaton for the word (which can be done in linear time) and computing the intersection language of the dictionary automaton and the Levenshtein automaton. This approach is fast and very compact. I have a Java implementation: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
  - eric_bullington 12y ago
    Oh, this is very cool. I wonder how many CAT (Computer-Aided Translation) tools out there (many of which are notoriously slow) could be significantly sped up using this approach. I'd bet most of them, although they're almost all closed-source so we will likely never know.
  - Loic 12y ago
    I am a chemical engineer so reading "deterministic acyclic minimized finite state automaton" is sending me back in my first years at university. As I want to implement instant search with part of string matching, this can be very interesting. This is to match "Octane, 2,4,6-trimethyl-" when typing "trimethyl". For the moment I am looking at the Linkedin approach[0]. Sorry for keeping this semi-offtopic thread alive, but these problems are so interesting that I cannot stop. [0]: https://github.com/jamra/gocleo https://github.com/jamra/gocleo
- logicchains 12y ago
  One issue is that the server uses Google Protocol Buffers. The following definition, for instance: message Foo { required string a = 1; required int32 b = 2; optional int64 c = 3; } Generates a struct like: type Foo struct { a *string b *int32 c *int64 } This is not particularly friendly to the garbage collector compared to a POD struct with no pointers.
bjackman 12y ago
Wow, 400-500ms pauses? Is that the case in newer Go versions as well? Seems like that would wipe out viability for a whole load of applications.
- iends 12y ago
  Go is actively working on this. Go 1.5 will have concurrent GC and is shooting to stop the world for only 10ms. You can read more here: https://docs.google.com/document/d/16Y4IsnNRCN43Mx0NZc5YXZLovrHvvLhK_h0KN8woTO4/edit https://docs.google.com/document/d/16Y4IsnNRCN43Mx0NZc5YXZLo...
- _ak 12y ago
  Not really. If you manage your allocations properly, you will never have such long GC pauses. N.B. we use Go for real-time bidding (in the context of programmatic buying of ad space), and can easily respond to 6000 QPS on a single server within a 100ms time frame (from the SSP's POV), with a working set of about 2-3 GB that we constantly keep in memory.
  - chupy 12y ago
    That sounds really nice, but how often does that working set change?
  - pron 12y ago
    Like the author's case, yours sound a much more appropriate choice of Java. Why have you picked Go?
    - apta 12y ago
      Probably hype. There is a lot of hype in the industry, unfortunately.
pron 12y ago
May I ask why you've chosen Go over Java, which is becoming very popular in the HFT industry, even for latency-critical code? The code generation tools are better (what you call "compile time IO"), the IDEs are much better, it has generics which you seem to miss, performance is better (the GCs are state-of-the-art), monitoring is much better, the language is also regular and simple, and you don't have to write inheritance-heavy code if you don't like. As someone who likes both Java and Go, I find it surprising that anyone would choose the latter for long-running server code, especially where performance matters. Go is great for quick command-line apps or very simple services, but when you need to build an important server, Java wins out every time. Certainly for your particular requirements and preferences, Java seems to have all of Go's advantages and (almost) none of the disadvantages.
- Horusiath 12y ago
  Taking from the author's paragraph: - Emacs - Java IDEs may look better, but this doesn't seem to be an issue for author. Also other tools are very mature for such youn language as Go. - Goroutines - Java has no built-in equivalent or one opinionated way of green-threading, only frameworks requiring months of expertise. From perspective of person, who need to switch language quickly this is very discouraging. - No inheritance - Java design patterns are clearly no-no in the described context (they were presented as anti-pattern). - Built-in, effective templating - again one easy path to start with, also powerfull enough to write your own tools if needed. Go is simply easier/faster to start with and most of the performance problems were not GC-bound, so JVMs maturity wasn't such an advantage.
  - pron 12y ago
    > -Goroutines https://github.com/puniverse/quasar https://github.com/puniverse/quasar (I'm the main author) > Built-in, effective templating So does Java (and for a long time): http://docs.oracle.com/javase/7/docs/api/javax/annotation/processing/Processor.html http://docs.oracle.com/javase/7/docs/api/javax/annotation/pr... > and most of the performance problems were not GC-bound The author's complaints were about GC pauses, and besides, Java is faster even for non-GC bound tasks. > Go is simply easier/faster to start with Maybe, but just a little, and mostly because Java has (too?) many libraries to choose from. Even if the differences you highlight are indeed true (a point on which I disagree), those differences are, at best, quite small, while the advantages in Java's favor are much bigger, certainly in those areas that matter to the author.
voidlogic 12y ago
Did you make use of sync.Pool at all for your common garbage generation cases?
- logicchains 12y ago
  Not yet: simplicity was deemed more important than latency for the present, and it was believed that pooling would bring unneeded complexity. If latency becomes an issue then pooling would be the next step taken.
lazyjones 12y ago
> If you can tolerate occasional pauses of 400-500 milliseconds, then the GC wouldn't be a problem. You might want to spend some time optimizing allocations (http://blog.golang.org/profiling-go-programs http://blog.golang.org/profiling-go-programs for some info). I successfully eliminated these pauses in my project by putting data on the stack instead of the heap in critical points of my code. This can be done (though it's ugly) even when the size of particular allocations aren't known at compile time (i.e. use a fixed stack allocation with an appropriate upper limit, check for the limit and go to the heap only if necessary). > I suspect that would complicate the code significantly Maybe if your code has many hot spots with these allocations, but it's worth it to manually optimize these currently.
- logicchains 12y ago
  I had already done a bit of profiling: originally the GC was taking up around 40% of the total running time, and I managed to reduce it to 10% by removing the biggest source of allocations. As it's not latency-critical there wasn't an immediate need for further optimisation.
cespare 12y ago
The GC pause time is mostly proportional to the number of pointers in the heap, not the absolute size. For example, if your heap consists of a single 50GB []byte, the GC pause will be negligible. This means that you can often control the pause time effectively if you are able to reduce the number of pointers in use. I have a server that has a large-ish working heap size (10-30GB) that consists of several very large maps; initially it gave pauses of 2-3 seconds. I got rid of pointer types from the map keys/values and the pause time became a few hundred milliseconds. At this point, the GC pause was mostly caused by internal overflow pointers from the hashmap implementation. I implemented my own pointer-free map type and brought the pauses down to < 1ms. I also filed an issue (https://golang.org/issue/9477 https://golang.org/issue/9477) and Dmitry Vyukov kindly implemented a change so that pointer-free maps are not scanned by the GC. This will be in Go 1.5 and I will delete my custom map.
- logicchains 12y ago
  How did you get around the fact that Go doesn't allow you to modify value-type entries in maps? For instance, if I have a map[int]myFoo, I can't do myMap[24].myParam = 3, I have to create a new myFoo and assign it to myMap[24]. Whereas if I have a map[int]*myFoo, myMap[24].myParam = 3 works fine.

acqq 12y ago

Thanks, more than that, I also know that there are many in-house implementations written in C++ with significantly worse performances than those of the good garbage collected libraries. Sloppy programming can always make slow products. It's still good to know where the limits are and I thank you for the honest report.

Loic 12y ago

Effectively, you need to keep a small heap and if possible have "simple" data structure. In my case, I implemented the Python code of a trie based levenshtein distance algorithm[0]. I used maps because it was basically a direct translation of the Python code. This resulted in millions of maps and oft the index would just stop in the garbage collector for a couple of seconds. I solved it using my own map which is travelled linearly. type SpellCheckerMap struct { Runes []rune Nodes []*SpellCheckerNode } with only few runes, I can just go through the list to find the index of the following node. You save the computation of the map hash key. It is pretty fast, here is an example of a spelling suggestion over a 500,000 words corpus[1]. Basically, the garbage collection cost forced me to think about a better data structure for my case. Maybe not that bad all in all. [0]: http://stevehanov.ca/blog/index.php?id=114 http://stevehanov.ca/blog/index.php?id=114 [1]: https://www.chemeo.com/search?q=asparine https://www.chemeo.com/search?q=asparine

danieldk 12y ago
Semi-offtopic: The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can be stored in a flat array/slice). This gives you O(n) time lookups, where n is the length of the word, and reduces much of the redundancy in a dictionary. Words within an edit distance can be found by computing a Levenshtein automaton for the word (which can be done in linear time) and computing the intersection language of the dictionary automaton and the Levenshtein automaton. This approach is fast and very compact. I have a Java implementation: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
- eric_bullington 12y ago
  Oh, this is very cool. I wonder how many CAT (Computer-Aided Translation) tools out there (many of which are notoriously slow) could be significantly sped up using this approach. I'd bet most of them, although they're almost all closed-source so we will likely never know.
- Loic 12y ago
  I am a chemical engineer so reading "deterministic acyclic minimized finite state automaton" is sending me back in my first years at university. As I want to implement instant search with part of string matching, this can be very interesting. This is to match "Octane, 2,4,6-trimethyl-" when typing "trimethyl". For the moment I am looking at the Linkedin approach[0]. Sorry for keeping this semi-offtopic thread alive, but these problems are so interesting that I cannot stop. [0]: https://github.com/jamra/gocleo https://github.com/jamra/gocleo
logicchains 12y ago
One issue is that the server uses Google Protocol Buffers. The following definition, for instance: message Foo { required string a = 1; required int32 b = 2; optional int64 c = 3; } Generates a struct like: type Foo struct { a *string b *int32 c *int64 } This is not particularly friendly to the garbage collector compared to a POD struct with no pointers.

bjackman 12y ago

Wow, 400-500ms pauses? Is that the case in newer Go versions as well? Seems like that would wipe out viability for a whole load of applications.

iends 12y ago
Go is actively working on this. Go 1.5 will have concurrent GC and is shooting to stop the world for only 10ms. You can read more here: https://docs.google.com/document/d/16Y4IsnNRCN43Mx0NZc5YXZLovrHvvLhK_h0KN8woTO4/edit https://docs.google.com/document/d/16Y4IsnNRCN43Mx0NZc5YXZLo...
_ak 12y ago
Not really. If you manage your allocations properly, you will never have such long GC pauses. N.B. we use Go for real-time bidding (in the context of programmatic buying of ad space), and can easily respond to 6000 QPS on a single server within a 100ms time frame (from the SSP's POV), with a working set of about 2-3 GB that we constantly keep in memory.
- chupy 12y ago
  That sounds really nice, but how often does that working set change?
- pron 12y ago
  Like the author's case, yours sound a much more appropriate choice of Java. Why have you picked Go?
  - apta 12y ago
    Probably hype. There is a lot of hype in the industry, unfortunately.

pron 12y ago

May I ask why you've chosen Go over Java, which is becoming very popular in the HFT industry, even for latency-critical code? The code generation tools are better (what you call "compile time IO"), the IDEs are much better, it has generics which you seem to miss, performance is better (the GCs are state-of-the-art), monitoring is much better, the language is also regular and simple, and you don't have to write inheritance-heavy code if you don't like. As someone who likes both Java and Go, I find it surprising that anyone would choose the latter for long-running server code, especially where performance matters. Go is great for quick command-line apps or very simple services, but when you need to build an important server, Java wins out every time. Certainly for your particular requirements and preferences, Java seems to have all of Go's advantages and (almost) none of the disadvantages.

Horusiath 12y ago
Taking from the author's paragraph: - Emacs - Java IDEs may look better, but this doesn't seem to be an issue for author. Also other tools are very mature for such youn language as Go. - Goroutines - Java has no built-in equivalent or one opinionated way of green-threading, only frameworks requiring months of expertise. From perspective of person, who need to switch language quickly this is very discouraging. - No inheritance - Java design patterns are clearly no-no in the described context (they were presented as anti-pattern). - Built-in, effective templating - again one easy path to start with, also powerfull enough to write your own tools if needed. Go is simply easier/faster to start with and most of the performance problems were not GC-bound, so JVMs maturity wasn't such an advantage.
- pron 12y ago
  > -Goroutines https://github.com/puniverse/quasar https://github.com/puniverse/quasar (I'm the main author) > Built-in, effective templating So does Java (and for a long time): http://docs.oracle.com/javase/7/docs/api/javax/annotation/processing/Processor.html http://docs.oracle.com/javase/7/docs/api/javax/annotation/pr... > and most of the performance problems were not GC-bound The author's complaints were about GC pauses, and besides, Java is faster even for non-GC bound tasks. > Go is simply easier/faster to start with Maybe, but just a little, and mostly because Java has (too?) many libraries to choose from. Even if the differences you highlight are indeed true (a point on which I disagree), those differences are, at best, quite small, while the advantages in Java's favor are much bigger, certainly in those areas that matter to the author.

voidlogic 12y ago

Did you make use of sync.Pool at all for your common garbage generation cases?

logicchains 12y ago
Not yet: simplicity was deemed more important than latency for the present, and it was believed that pooling would bring unneeded complexity. If latency becomes an issue then pooling would be the next step taken.

lazyjones 12y ago

> If you can tolerate occasional pauses of 400-500 milliseconds, then the GC wouldn't be a problem. You might want to spend some time optimizing allocations (http://blog.golang.org/profiling-go-programs http://blog.golang.org/profiling-go-programs for some info). I successfully eliminated these pauses in my project by putting data on the stack instead of the heap in critical points of my code. This can be done (though it's ugly) even when the size of particular allocations aren't known at compile time (i.e. use a fixed stack allocation with an appropriate upper limit, check for the limit and go to the heap only if necessary). > I suspect that would complicate the code significantly Maybe if your code has many hot spots with these allocations, but it's worth it to manually optimize these currently.

logicchains 12y ago
I had already done a bit of profiling: originally the GC was taking up around 40% of the total running time, and I managed to reduce it to 10% by removing the biggest source of allocations. As it's not latency-critical there wasn't an immediate need for further optimisation.

cespare 12y ago

The GC pause time is mostly proportional to the number of pointers in the heap, not the absolute size. For example, if your heap consists of a single 50GB []byte, the GC pause will be negligible. This means that you can often control the pause time effectively if you are able to reduce the number of pointers in use. I have a server that has a large-ish working heap size (10-30GB) that consists of several very large maps; initially it gave pauses of 2-3 seconds. I got rid of pointer types from the map keys/values and the pause time became a few hundred milliseconds. At this point, the GC pause was mostly caused by internal overflow pointers from the hashmap implementation. I implemented my own pointer-free map type and brought the pauses down to < 1ms. I also filed an issue (https://golang.org/issue/9477 https://golang.org/issue/9477) and Dmitry Vyukov kindly implemented a change so that pointer-free maps are not scanned by the GC. This will be in Go 1.5 and I will delete my custom map.

logicchains 12y ago
How did you get around the fact that Go doesn't allow you to modify value-type entries in maps? For instance, if I have a map[int]myFoo, I can't do myMap[24].myParam = 3, I have to create a new myFoo and assign it to myMap[24]. Whereas if I have a map[int]*myFoo, myMap[24].myParam = 3 works fine.