Do read the answer of the author regarding the performance:
"The throughput of the Go program is quite competitive with the C++ one, although the server’s IO-bound so most of the time is just spent in socket write/read syscalls. The latency is at least an order of magnitude worse, due to Go’s garbage collector, which is amplified by the use of an older Go version. If the server was latency-critical I don’t think it could have been written in Go, at least not until the new GC planned for 1.5 or 1.6 is released (assuming we could upgrade to a newer kernel by the time its released)."
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.
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) 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.
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.
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.
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:
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.
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.
Protocol buffers allows you to reuse the memory of your objects. You can simply reuse the object where you parse your message into. You pool these objects, and you just saved yourself a huge amount of heap allocations.
This would work if we were only using them for messaging, but the protobuffer objects are also used as the datastructure in which the information they contain is stored. This was done in the name of simplicity, to avoid creating a separate internal datastructure for each kind of message.
The flow of data is currently:
various external sources -> merged into protocol buffer struct -> later sent to client
To avoid keeping a heap of protocol buffer structs in the heap, this would need to change to:
various external sources -> merged into some internal datastructure -> later converted into protocol buffer struct and sent to client.
> This would work if we were only using them for messaging, but the protobuffer objects are also used as the datastructure in which the information they contain is stored. This was done in the name of simplicity, to avoid creating a separate internal datastructure for each kind of message.
Did you consider keeping strings (serialized messages) in your cache rather than message objects? I do this in C++ code simply for memory efficiency. Here it would also allow you to avoid these extra pointers.
I believe it's also possible to use variable-size arrays in C or C++ (and end up with a variable-size struct).
Go does allow fixed size arrays in structs, and they're inline in the struct, so `struct { foo [8]uint }` is 32 bytes, whereas `struct { foo []uint }` is 12 bytes and `struct { foo string }` is 8.
Lots of small maps becoming little arrays. The more things change, the more they stay the same. (There is production Smalltalk code from the late 80's running in large multinationals that's basically what you just described.)
> 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 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.
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.
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.
- 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.
> 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.
How do you avoid too many allocations to happen in Java? The GC is certainly slower with more allocated elements but I seldom see any code example in Java which doesn't behave like the allocations don't cost anything. More than that, it seems that the whole language is based on that premise? As I consider the info you already provided a good argument for Java, I hope you can provide some good links.
Java has a generational garbage collector, so short-lived allocations pretty much don't cost anything, and by and large it's exactly the short-lived allocations that are the ones you could have optimized away in e.g. hand-tuned C++.
What about an object being always handled only through the pointer? Does that mean that the array of 10M objects is actually an array of 10M pointers and 10M allocated objects, all of which have to be allocated, deallocated and the travelled through by the garbage collector? And what if it's not an array, but some more complex form? Is there a clean way to group a lot of objects to be treated by the allocator, deallocator and the GC as the single allocation unit? I understand that some language lawyers think that's not important ("just use the 'new,' the VM should care and not you") but for somebody like me who's used to the C level of control and actually cares and measures the performance differences which can result in the different number of servers needed to solve the problem, it really is.
This kind of stuff matters to Java developers, too, as, perhaps surprisingly, Java has become a high-performance language, especially when it comes to concurrency (as it offers low-level support for memory fences, and includes state-of-the-art implementations of concurrent data structures).
As pjmlp said, the issue of "array of structs" is being addressed in Java 10. In the meantime, for contiguous memory allocation, you can make use of off-heap memory (which also helps those "more complex forms"). But the flip side is that Java's memory allocation is a lot faster than C's (i.e. in throughput -- not latency, as there are GC pauses), and most GCs are copying collectors that automatically arrange objects contiguously (though it's far from being good enough for arrays of object, as you need to follow references, and every object carries additional overhead, which is precisely why this is being addressed in Java 10).
Currently not and this is part of the Java 9-10 roadmap.
However all JVMs have state of the art profilers like e.g. Visual VM, Java Flight Recorder and many others that help track down which data structures might need some help.
> How do you avoid too many allocations to happen in Java?
Most of the time you don't need to, because GCs are that good, and escape analysis can avoid heap allocation automatically[1]. You won't get C++ latency, but you'll do better than Go. If you really need to avoid allocations for some reason, you can go off-heap for C++ performance (Java HFT applications do that for the most performance-critical things; it requires more work, but overall, less than C++).
Also, I'm not saying that Java is always the better choice (the JVM needs some time to warm up; Go's runtime is statically compiled into the native binary artifact), but in this particular case it seems to be exactly what the author was asking for, that it's really the obvious choice.
Ah, OK, then. It's as good a reason as any, I guess. You should know though, that Java is now quite popular in HFT circles, especially in the UK, with high-performance libraries and monitoring tools[1] specifically tailored to that industry. In spite of a difference in marketing, you'll find that Java can get you much close to C++ than Go can. You have better control over execution and a runtime of higher quality overall.
Even though Go's runtime is statically linked while Java's isn't, Java is very much a C++ replacement in many circumstances, while Go makes for a terrific Python replacement if you need fast scripts and command line tools (which is why you mostly see Python->Go and C++->Java transitions). Not that Go is always more appropriate than Python or Java is always better suited than C++, but at least those are the common alternatives, and the ones that make the most sense considering the design decisions of those languages.
For you particular needs, I have no doubt you'll find Java to be the more appropriate choice.
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.
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.
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.
"The throughput of the Go program is quite competitive with the C++ one, although the server’s IO-bound so most of the time is just spent in socket write/read syscalls. The latency is at least an order of magnitude worse, due to Go’s garbage collector, which is amplified by the use of an older Go version. If the server was latency-critical I don’t think it could have been written in Go, at least not until the new GC planned for 1.5 or 1.6 is released (assuming we could upgrade to a newer kernel by the time its released)."