6 ms·

The thing is I don't really care if Go implementation is highly optimized for amd64 like memchr is in C which is also written in assembler and optimized for dif

by lossolo 10y ago

The thing is I don't really care if Go implementation is highly optimized for amd64 like memchr is in C which is also written in assembler and optimized for different platforms. What I care is that simple code written by me is faster without going into C/unsafe code myself. So it's correct, fast, simple and I do not pay with my time to figure out how to make it as fast in Rust. This is the point I am making. Of course this is only one example, but still a proof that what OP wrote is not valid in all cases.

burntsushi 10y ago
ripgrep is your proof. Go read the blog post Steve linked. If you still don't believe it, read the code. There's not that much of it. Then compare it with similar tools written in Go, like sift and the platinum searcher. The problem is, searching a file quickly is not as simple as you want to believe. If you show me a naive line by line approah, I'll show you an approach that is much faster but more complex. Top speed requires work, sometimes algorithmic work, regardless of the language you choose.
- lossolo 10y ago
  > If you show me a naive line by line approah, I'll show you an approach that is much faster but more complex. Of course, I did it myself many times. But this is NOT the point, I've already wrote it. The point is that I wrote naive approach in both languages and it's a lot faster in Go. Which is a reply to what OP wrote (don't forget where this discussion started). In this case this is the fact and I don't see any reason to fight with facts if we get bias out of the equation. In other cases? I don't know. What I would expect is that naive searching for one string in haystack to be faster than Go in a language that is performance/zero-cost abstractions oriented like Rust but its false in this case. But it doesn't mean it's false in every case. And to be honest writing that "but they have faster implementation in assembler" is not an excuse at all, you can also write your own, especially if it works so well for those languages that have custom asm for specific platforms. In the end average Joe will not care if it's hand written assembler, he will care that his naive solution using standard library without any magic is just faster.
  - burntsushi 10y ago
    > The point is that I wrote naive approach in both languages and it's a lot faster in Go. I tried your challenge, and the first data point I uncovered contradicts this. Here is the source code of both programs: https://gist.github.com/anonymous/f01fc324ba8cccd690551caa4369751a https://gist.github.com/anonymous/f01fc324ba8cccd690551caa43... --- The Rust program doesn't use unsafe, doesn't explicitly use C code, is shorter than the Go program, faster in terms of CPU time and uses less memory. I ran the following: $ /usr/bin/time -v ./lossolo-go /tmp/OpenSubtitles2016.raw.sample.en the $ /usr/bin/time -v ./target/release/lossolo-rust /tmp/OpenSubtitles2016.raw.sample.en the Both runs report 6,123,710 matching lines (out of 32,722,372 total lines). The corpus is ~1GB and can be downloaded here (266 MB compressed): http://burntsushi.net/stuff/OpenSubtitles2016.raw.sample.en.gz http://burntsushi.net/stuff/OpenSubtitles2016.raw.sample.en.... --- My /tmp is a ramdisk, so the file is in cache and I'm therefore not benchmarking disk reads. My CPU is an Intel i7-6900K. The Go program takes ~6.5 seconds and has a maximum heap usage of 7.7 MB. The Rust program takes ~4.2 seconds and has a maximum heap usage of 6 MB. (As measured by GNU time using `time -v`.) --- IMO, both programs reflect "naive" solutions. The point of me doing this exercise is to show just how silly this is, because now we're going to optimize these programs, but we'll limit ourselves to smallish perturbations in order to put a reasonable bound on the task. If I run the Go program through `perf record`, the top hotspot is runtime.mallocgc. Now, I happen to know from experience that Scanner.Text is going to allocate a new string while Scanner.Bytes will not. I also happen to know that the Go standard library `bytes` package recently got a nice optimization that makes bytes.Contains as fast as strings.Contains: https://github.com/golang/go/commit/44f1854c9dc82d8dba415ef102e93896d57c2c0d https://github.com/golang/go/commit/44f1854c9dc82d8dba415ef1... --- Since reading into a Go `string` doesn't actually do any UTF-8 validation, we don't lose anything by switching to using raw bytes. Knowing this, we can tweak the Go program to great effect: https://gist.github.com/anonymous/c98dc8f6be6d414ae3e7aa6931f1c5f5 https://gist.github.com/anonymous/c98dc8f6be6d414ae3e7aa6931... --- Running the same command as above, we now get a time of ~2.3 seconds and a maximum heap usage of 1.6 MB. That's impressive. Now let's see if we can tweak Rust, which is now twice as slow as the Go program. Running perf, it looks like there's an even split between allocation, searching and UTF-8 validation, with a bit more towards searching. Like the Go program, let's attack allocation. In this case, I happen to know that the `lines` method returns an iterator that yields `String` values, which implies that it's allocating a fresh `String` for every line, just like our Go program was. Can we get rid of that? The BufReader API provides a `read_line` method, which permits the caller to control the `String` allocation. If we use that, our Rust program is tweaked to this: https://gist.github.com/anonymous/a6cf1aa51bf8e26e9dda4c50b002422c https://gist.github.com/anonymous/a6cf1aa51bf8e26e9dda4c50b0... --- It's not quite as symmetrical as a change as we made to the Go program, but it's pretty straight-forward IMO. Running the same command as above, we now get a time of ~3.3 seconds and a maximum heap usage of 6 MB. OK, so we're still slower than the Go program. Looking at the profile again, the time now seems split completely between searching and UTF-8 validation. The allocation doesn't show up at all any more. Is this where you got stuck? The next step from here isn't straight-forward because getting rid of the UTF-8 validation isn't possible to do safely while still using the String/&str search APIs. Notably, Rust's standard library doesn't provide a way to search an `&[u8]` directly using optimized substring search routines. Even if you knew your input was valid UTF-8 before hand, there's no obvious place to insert an unsafe `from_utf8_unchecked` because the BufReader itself is in control of producing the string contents. (You could do this by switching to using `BufReader.read_until` and then transmuting the result into an &str, but that would require unsafe.) Let's take a leap. Rust's regex library has a little known feature that it can actually search the contents of an &[u8]. Rust's regex library isn't part of the standard library, but it is maintained as an official crate by the Rust project. If you know all of this, then it's possible to tweak the Rust program just a bit more to regain the speed lost by UTF-8 checking: https://gist.github.com/anonymous/bfa42d4f86e03695f3c880aaceca2088 https://gist.github.com/anonymous/bfa42d4f86e03695f3c880aace... --- Running the same command as above once again, we now get a time of ~2.1 seconds and a maximum heap usage of 6.5 MB. In sum, we've beaten Go in CPU time, but lost the Battle for Memory and the battle for obviousness. Beating Go required noticing the `read_until` API of BufReader and knowing that 1) Rust's regexes are fast and 2) they can search &[u8] directly. It's not entirely unreasonable, but to be fair, I've done this without explicitly using any unsafe or any C code. None of this process was rocket science. Both the Go and Rust programs were initially significantly sub-optimal because of allocation, but after some light profiling, it was possible to speed up both programs quite a bit. --- Compared to the naive solution, some of our search tools can be a lot faster. Performing the same query on the same corpus: ripgrep 1.13 seconds, 7.7 MB ripgrep 1.35 seconds, mmap GNU grep 1.73 seconds, 2.3 MB ag 1.80 seconds, mmap pt 6.41 seconds, mmap sift 50.21 seconds, 16.6 MB The differences between real search tools and our naive solution actually aren't that big here. The reason why is because of your initial requirement that the query match lots of lines. Lots of matches results in a lot of overhead. If we change the query to a more common type of search that produces very few matches (e.g., `Sherlock Holmes`), then our best naive programs drop down to about ~1.4 seconds, but ripgrep drops to about 200 milliseconds. From here, the next step would be stop parsing lines and start searching the entire buffer directly. (I hope to make even this task very easy by moving some of the searching code inside of ripgrep to an easy to use library.) --- In sum, your litmus test essentially comes down to these trade offs: - Rust provides a rich API for its String/&str types, which are guaranteed to be valid UTF-8. - Rust lacks a rich substring search API in the standard library for Vec<u8>/&[u8] types. Because of this, efficient substring search using only the standard library has an unavoidable UTF-8 validation cost in safe code. - Go doesn't do any kind of UTF-8 checking and provides mirrored substring search APIs between its `bytes` and `strings` packages. - The actual performance of searching in both programs probably boils down to optimized SIMD algorithms. Therefore, once you get past the ability to search each line of a file with minimal allocation, you've basically hit a wall that's probably the same in most mainstream languages. In my opinion, these trade offs strike me as something terribly specific, and it's probably not something that is usefully generalizable. More than that, in the naive case, Rust is doing you a good service by checking that your input is valid UTF-8, which is something that Go doesn't do. I think this could go either way, but I think it's uncontroversial that guaranteeing valid UTF-8 up front like this probably eliminates a few possibly subtle bugs. (I will say that my experience with text encoding in Go has been stellar though.) Most importantly, both languages at least have a path to writing a very fast program, which is often what most folks end up caring about at the end of the day.
caconym_ 10y ago
> but still a proof that what OP wrote is not valid in all cases. You are not proving anything until you post your Go code, which you don't seem to have done (please correct me if I'm wrong, I am legitimately curious to see for myself how Go and Rust stack up against each other for this problem). Until then, all you're doing is making vague claims backed up by precisely zero evidence. Why should anyone take you seriously?
- lossolo 10y ago
  I have posted the code in reply to burntsushi. You can check it out yourself.
neandrake 10y ago
I've seen several of your comments indicate "requiring naive implementation". This seems strange to me. Why require a naive implementation and then be concerned over some slight differences in performance?

by lossolo 10y ago

burntsushi 10y ago

ripgrep is your proof. Go read the blog post Steve linked. If you still don't believe it, read the code. There's not that much of it. Then compare it with similar tools written in Go, like sift and the platinum searcher. The problem is, searching a file quickly is not as simple as you want to believe. If you show me a naive line by line approah, I'll show you an approach that is much faster but more complex. Top speed requires work, sometimes algorithmic work, regardless of the language you choose.

lossolo 10y ago
> If you show me a naive line by line approah, I'll show you an approach that is much faster but more complex. Of course, I did it myself many times. But this is NOT the point, I've already wrote it. The point is that I wrote naive approach in both languages and it's a lot faster in Go. Which is a reply to what OP wrote (don't forget where this discussion started). In this case this is the fact and I don't see any reason to fight with facts if we get bias out of the equation. In other cases? I don't know. What I would expect is that naive searching for one string in haystack to be faster than Go in a language that is performance/zero-cost abstractions oriented like Rust but its false in this case. But it doesn't mean it's false in every case. And to be honest writing that "but they have faster implementation in assembler" is not an excuse at all, you can also write your own, especially if it works so well for those languages that have custom asm for specific platforms. In the end average Joe will not care if it's hand written assembler, he will care that his naive solution using standard library without any magic is just faster.
- burntsushi 10y ago
  > The point is that I wrote naive approach in both languages and it's a lot faster in Go. I tried your challenge, and the first data point I uncovered contradicts this. Here is the source code of both programs: https://gist.github.com/anonymous/f01fc324ba8cccd690551caa4369751a https://gist.github.com/anonymous/f01fc324ba8cccd690551caa43... --- The Rust program doesn't use unsafe, doesn't explicitly use C code, is shorter than the Go program, faster in terms of CPU time and uses less memory. I ran the following: $ /usr/bin/time -v ./lossolo-go /tmp/OpenSubtitles2016.raw.sample.en the $ /usr/bin/time -v ./target/release/lossolo-rust /tmp/OpenSubtitles2016.raw.sample.en the Both runs report 6,123,710 matching lines (out of 32,722,372 total lines). The corpus is ~1GB and can be downloaded here (266 MB compressed): http://burntsushi.net/stuff/OpenSubtitles2016.raw.sample.en.gz http://burntsushi.net/stuff/OpenSubtitles2016.raw.sample.en.... --- My /tmp is a ramdisk, so the file is in cache and I'm therefore not benchmarking disk reads. My CPU is an Intel i7-6900K. The Go program takes ~6.5 seconds and has a maximum heap usage of 7.7 MB. The Rust program takes ~4.2 seconds and has a maximum heap usage of 6 MB. (As measured by GNU time using `time -v`.) --- IMO, both programs reflect "naive" solutions. The point of me doing this exercise is to show just how silly this is, because now we're going to optimize these programs, but we'll limit ourselves to smallish perturbations in order to put a reasonable bound on the task. If I run the Go program through `perf record`, the top hotspot is runtime.mallocgc. Now, I happen to know from experience that Scanner.Text is going to allocate a new string while Scanner.Bytes will not. I also happen to know that the Go standard library `bytes` package recently got a nice optimization that makes bytes.Contains as fast as strings.Contains: https://github.com/golang/go/commit/44f1854c9dc82d8dba415ef102e93896d57c2c0d https://github.com/golang/go/commit/44f1854c9dc82d8dba415ef1... --- Since reading into a Go `string` doesn't actually do any UTF-8 validation, we don't lose anything by switching to using raw bytes. Knowing this, we can tweak the Go program to great effect: https://gist.github.com/anonymous/c98dc8f6be6d414ae3e7aa6931f1c5f5 https://gist.github.com/anonymous/c98dc8f6be6d414ae3e7aa6931... --- Running the same command as above, we now get a time of ~2.3 seconds and a maximum heap usage of 1.6 MB. That's impressive. Now let's see if we can tweak Rust, which is now twice as slow as the Go program. Running perf, it looks like there's an even split between allocation, searching and UTF-8 validation, with a bit more towards searching. Like the Go program, let's attack allocation. In this case, I happen to know that the `lines` method returns an iterator that yields `String` values, which implies that it's allocating a fresh `String` for every line, just like our Go program was. Can we get rid of that? The BufReader API provides a `read_line` method, which permits the caller to control the `String` allocation. If we use that, our Rust program is tweaked to this: https://gist.github.com/anonymous/a6cf1aa51bf8e26e9dda4c50b002422c https://gist.github.com/anonymous/a6cf1aa51bf8e26e9dda4c50b0... --- It's not quite as symmetrical as a change as we made to the Go program, but it's pretty straight-forward IMO. Running the same command as above, we now get a time of ~3.3 seconds and a maximum heap usage of 6 MB. OK, so we're still slower than the Go program. Looking at the profile again, the time now seems split completely between searching and UTF-8 validation. The allocation doesn't show up at all any more. Is this where you got stuck? The next step from here isn't straight-forward because getting rid of the UTF-8 validation isn't possible to do safely while still using the String/&str search APIs. Notably, Rust's standard library doesn't provide a way to search an `&[u8]` directly using optimized substring search routines. Even if you knew your input was valid UTF-8 before hand, there's no obvious place to insert an unsafe `from_utf8_unchecked` because the BufReader itself is in control of producing the string contents. (You could do this by switching to using `BufReader.read_until` and then transmuting the result into an &str, but that would require unsafe.) Let's take a leap. Rust's regex library has a little known feature that it can actually search the contents of an &[u8]. Rust's regex library isn't part of the standard library, but it is maintained as an official crate by the Rust project. If you know all of this, then it's possible to tweak the Rust program just a bit more to regain the speed lost by UTF-8 checking: https://gist.github.com/anonymous/bfa42d4f86e03695f3c880aaceca2088 https://gist.github.com/anonymous/bfa42d4f86e03695f3c880aace... --- Running the same command as above once again, we now get a time of ~2.1 seconds and a maximum heap usage of 6.5 MB. In sum, we've beaten Go in CPU time, but lost the Battle for Memory and the battle for obviousness. Beating Go required noticing the `read_until` API of BufReader and knowing that 1) Rust's regexes are fast and 2) they can search &[u8] directly. It's not entirely unreasonable, but to be fair, I've done this without explicitly using any unsafe or any C code. None of this process was rocket science. Both the Go and Rust programs were initially significantly sub-optimal because of allocation, but after some light profiling, it was possible to speed up both programs quite a bit. --- Compared to the naive solution, some of our search tools can be a lot faster. Performing the same query on the same corpus: ripgrep 1.13 seconds, 7.7 MB ripgrep 1.35 seconds, mmap GNU grep 1.73 seconds, 2.3 MB ag 1.80 seconds, mmap pt 6.41 seconds, mmap sift 50.21 seconds, 16.6 MB The differences between real search tools and our naive solution actually aren't that big here. The reason why is because of your initial requirement that the query match lots of lines. Lots of matches results in a lot of overhead. If we change the query to a more common type of search that produces very few matches (e.g., `Sherlock Holmes`), then our best naive programs drop down to about ~1.4 seconds, but ripgrep drops to about 200 milliseconds. From here, the next step would be stop parsing lines and start searching the entire buffer directly. (I hope to make even this task very easy by moving some of the searching code inside of ripgrep to an easy to use library.) --- In sum, your litmus test essentially comes down to these trade offs: - Rust provides a rich API for its String/&str types, which are guaranteed to be valid UTF-8. - Rust lacks a rich substring search API in the standard library for Vec<u8>/&[u8] types. Because of this, efficient substring search using only the standard library has an unavoidable UTF-8 validation cost in safe code. - Go doesn't do any kind of UTF-8 checking and provides mirrored substring search APIs between its `bytes` and `strings` packages. - The actual performance of searching in both programs probably boils down to optimized SIMD algorithms. Therefore, once you get past the ability to search each line of a file with minimal allocation, you've basically hit a wall that's probably the same in most mainstream languages. In my opinion, these trade offs strike me as something terribly specific, and it's probably not something that is usefully generalizable. More than that, in the naive case, Rust is doing you a good service by checking that your input is valid UTF-8, which is something that Go doesn't do. I think this could go either way, but I think it's uncontroversial that guaranteeing valid UTF-8 up front like this probably eliminates a few possibly subtle bugs. (I will say that my experience with text encoding in Go has been stellar though.) Most importantly, both languages at least have a path to writing a very fast program, which is often what most folks end up caring about at the end of the day.

caconym_ 10y ago

> but still a proof that what OP wrote is not valid in all cases. You are not proving anything until you post your Go code, which you don't seem to have done (please correct me if I'm wrong, I am legitimately curious to see for myself how Go and Rust stack up against each other for this problem). Until then, all you're doing is making vague claims backed up by precisely zero evidence. Why should anyone take you seriously?

lossolo 10y ago
I have posted the code in reply to burntsushi. You can check it out yourself.

neandrake 10y ago

I've seen several of your comments indicate "requiring naive implementation". This seems strange to me. Why require a naive implementation and then be concerned over some slight differences in performance?