6 ms·
I'm doing Advent on Discord with a former coworker this year. This morning we compared the performance of his solution in Rust to my solution in Go. His was ru
by NAHWheatCracker 3y ago
I'm doing Advent on Discord with a former coworker this year.
This morning we compared the performance of his solution in Rust to my solution in Go. His was running 2-4x faster than mine but we couldn't figure out why and it seemed so straight forward that we assumed Rust was just that much faster.
I had assumed strings.Split would return sub-slices of the original string until I read this post. Sure enough, I rewrite it using strings.Index and manually creating sub-slices and now it's comparable, albeit less readable.
Looking at the standard library source doesn't make it clear to me why this even works. strings.Split is appending sub-slices of the input string to the return value. I don't understand where the allocations are coming from, but I'm just not knowledgeable enough about go slices.
- SPBS 3y agostrings.Split does return subslices of the original string. It's not making a copy of the string. Allocations still have to be made for slice that holds the result of strings.Split. That's where the allocations are coming from.
- saghm 3y agoFrom looking into Rust's implementation of the iterator that's returned when splitting a string (which takes a bit of mental parsing, given the heavy use of macros: https://doc.rust-lang.org/src/core/str/iter.rs.html#731-747 https://doc.rust-lang.org/src/core/str/iter.rs.html#731-747), it seems like it has a reference to the original string and an index that it increments until it finds the next pattern to "split" on. This seems like something that would be pretty easy to do in Go as well, except Go doesn't really have any standard iterator API from what I can tell. This seems like a pretty clear argument for why having one is preferable to just returning slices everywhere though; even if you end up wanting to iterator through everything immediately, you avoid allocating unless you actually have to. In Rust, you can do this by just calling `collect` on the iterator, and although I suspect whoever implemented this API for Go wouldn't like the "magic" of it generically supporting collecting into whatever container you want, it feels like even just having an iterator with a method to collect into a slice and nothing else would be preferable.
- masklinn 3y ago> it feels like even just having an iterator with a method to collect into a slice and nothing else would be preferable. Most langages just have constructors or factory functions from iterator (or even iterable) to container. It’s a less generic (especially if constructors and functions are segregated) and / or efficient but otherwise works fine. No need for the iterator whatever (protocol, interface, trait) to have specific knowledge of individual collections.
- pstuart 3y agoThere's going to be experimental support for built-in iteration in 1.22: https://github.com/golang/go/issues/61897 https://github.com/golang/go/issues/61897
- ikiris 3y agoWhy are you even making strings to begin with most of the time?
- NAHWheatCracker 3y agoI'm not sure what you're suggesting, the input in Advent of Code is usually meant to be treated as ASCII text, so strings are quite natural.
- ikiris 3y agostrings are immutable sequences of runes in go. Every time you make one its an allocation and time. You asked about speed differences between rust and go and not understanding where allocations are coming from, and are doing mostly unnessecary string allocation work for whats been the first 3 days of this year's AoC. At no point have I used strings this year so far.
- NAHWheatCracker 3y agoI have been using bufio.Scanner.Text() for reading my input files, but I suppose most of what I've done could use bufio.Scanner.Bytes().
- NAHWheatCracker 3y agoFWIW, I moved away from bufio.Scanner and now I just do one os.ReadFile() call to get the whole thing as bytes and wrote a little function to break it into lines. I'm not using strings anymore and I eeked out a bit of performance for all three days.
- marcus_holmes 3y agoI love me some Go, but it is a gripe I have with the language; slice (and by extension string) allocation is opaque. There's no way of determining if two slices share the same underlying array, and no easy way of determining if an operation on a string will either cause the underlying array to be altered or cause the runtime to allocate a new array for the slice.