And just like in C, if you want to avoid memory management overhead you can use a slice of structs, integers instead of pointers, and a freelist (if needed). For example, here is a pointerless sparse bit vector:
The article is storing parses in a balanced binary tree, like a packrat memoizing parser.
Here is the fastest balanced search tree in Go. It allocates (and uses Go's garbage collector) but you can easily use a slice of structs with integer index pointers and a freelist instead:
If you're making something requiring CPU optimization as a core feature, you might as well go with one of the fastest languages instead of handicapping your project from Day 1. Go is not considered one of the fastest. It's better for network or filesystem logic that is I/O limited.
The optimization here is using incremental parsing, so that changing parse state goes from O(n) to may-as-well-be-O(1). It's probably linear with tree depth.
Any language is fast enough to do this, certainly Go is. Naive parser combinators written in slow languages can tokenize six-figure LOC files fast enough that the user won't notice.
You’d generally expect Rust and Go to perform about the same for CPU bound workloads. Rust has access to more advanced codegen and optimizations via LLVM, but Go’s garbage collector will often be faster than refcounting (or whatever manual memory management technique your Rust code ends up using). This is especially so given that the GC runs on a separate thread without any additional effort on your part, making it almost ‘free’ in the context of parsers (which tend to be single threaded).
A real world example of this is esbuild. The author posted on HN that his initial Rust implementation was actually somewhat slower than the subsequent Go version.
This is kind of a test of how nuanced your understanding of programming languages can be.
Rust with a bit of effort put into optimization will be faster than Go with a bit of effort put into optimization, it is true. However, you need to double-check your intuition for how big and how consequential the delta is, because I'd guesstimate it as roughly a factor of two, possibly a touch less. It is true that Rust does a crapton more "optimizations", but a lot of those optimizations have diminishing returns.
A factor of 2 may still sound large, but in practice it isn't as large as it sounds, because my qualification "a bit of effort put into optimization" is not redundant. Go with a bit of optimization will probably beat someone's first draft of Rust. Go with a ton of careful optimization will probably beat Rust with a bit of optimization. The raw performance of the two are reasonably close, and smaller than the improvements you can usually get with optimization. So Rust's speed advantage, which is real, generally only matters in cases where you're going to optimize very heavily.
Is this one of them? For that I can give a solid... Maybe! There are times and places where parsing is something you want optimized to within an inch of its life, certainly. However... it isn't all the places, and some of your intuitions may lead you astray if you're not careful; you might think a heavy duty programming language would need a great parser, but if it's going to chew on optimizations for possibly literally 100x the time, it may matter a lot less.
In general, Rust is capable of going faster than Go (again, I'd guestimate about a factor of 2 with isolate tasks where it may be able to go event faster, but that only matters if that's the bulk of your program), but Go is going to be fast enough that that only matters in certain limited places where you're willing to put some non-trivial effort into performance in the first place.
This is in contrast to a comparison between Go/Rust and Python, where even casually written Go/Rust can outpace optimized pure Python, even before we start talking about how much better Go/Rust will be using multiple CPUs. This is because Python is just that slow, and let's not even talk about how slow Python can be if you don't write it to be optimized and you start heavily using all its features without realizing how expensive they are. From the point of view of Python, Go and Rust have very similar performance characteristics. (But then, of course, one must be careful with Python because something like NumPy will blow your socks off when it turns out to not really be Python at all.)
It's a rich, nuanced problem space and should not be approached with sloganeering and "my language is better than yours".
My summary of Go is: It's a slow compiled language... but it is still a compiled language, and it is faster than pretty much everything that isn't, possible exception of LuaJIT, and the delta between slowest compiled and fastest compiled is only ~2-3x, which in the overall space of programming language speed isn't actually that great.
bugfix-66|3 years ago
And just like in C, if you want to avoid memory management overhead you can use a slice of structs, integers instead of pointers, and a freelist (if needed). For example, here is a pointerless sparse bit vector:
https://bugfix-66.com/7256e0772dc3b02d72abf15b171731c933fd44...
The article is storing parses in a balanced binary tree, like a packrat memoizing parser.
Here is the fastest balanced search tree in Go. It allocates (and uses Go's garbage collector) but you can easily use a slice of structs with integer index pointers and a freelist instead:
https://bugfix-66.com/c93e950965804eba90a34e0055985b1c42d5a1...
The above code will perform very similarly to C.
xyzzy4747|3 years ago
samatman|3 years ago
Any language is fast enough to do this, certainly Go is. Naive parser combinators written in slow languages can tokenize six-figure LOC files fast enough that the user won't notice.
foldr|3 years ago
A real world example of this is esbuild. The author posted on HN that his initial Rust implementation was actually somewhat slower than the subsequent Go version.
dymk|3 years ago
jerf|3 years ago
Rust with a bit of effort put into optimization will be faster than Go with a bit of effort put into optimization, it is true. However, you need to double-check your intuition for how big and how consequential the delta is, because I'd guesstimate it as roughly a factor of two, possibly a touch less. It is true that Rust does a crapton more "optimizations", but a lot of those optimizations have diminishing returns.
A factor of 2 may still sound large, but in practice it isn't as large as it sounds, because my qualification "a bit of effort put into optimization" is not redundant. Go with a bit of optimization will probably beat someone's first draft of Rust. Go with a ton of careful optimization will probably beat Rust with a bit of optimization. The raw performance of the two are reasonably close, and smaller than the improvements you can usually get with optimization. So Rust's speed advantage, which is real, generally only matters in cases where you're going to optimize very heavily.
Is this one of them? For that I can give a solid... Maybe! There are times and places where parsing is something you want optimized to within an inch of its life, certainly. However... it isn't all the places, and some of your intuitions may lead you astray if you're not careful; you might think a heavy duty programming language would need a great parser, but if it's going to chew on optimizations for possibly literally 100x the time, it may matter a lot less.
In general, Rust is capable of going faster than Go (again, I'd guestimate about a factor of 2 with isolate tasks where it may be able to go event faster, but that only matters if that's the bulk of your program), but Go is going to be fast enough that that only matters in certain limited places where you're willing to put some non-trivial effort into performance in the first place.
This is in contrast to a comparison between Go/Rust and Python, where even casually written Go/Rust can outpace optimized pure Python, even before we start talking about how much better Go/Rust will be using multiple CPUs. This is because Python is just that slow, and let's not even talk about how slow Python can be if you don't write it to be optimized and you start heavily using all its features without realizing how expensive they are. From the point of view of Python, Go and Rust have very similar performance characteristics. (But then, of course, one must be careful with Python because something like NumPy will blow your socks off when it turns out to not really be Python at all.)
It's a rich, nuanced problem space and should not be approached with sloganeering and "my language is better than yours".
My summary of Go is: It's a slow compiled language... but it is still a compiled language, and it is faster than pretty much everything that isn't, possible exception of LuaJIT, and the delta between slowest compiled and fastest compiled is only ~2-3x, which in the overall space of programming language speed isn't actually that great.