I threw together an implementation as proof of concept of the things I’ve mentioned above, and, well, maybe don’t listen to me because it’s slow. 130 seconds for 50M lines slow. I think using an ordered_set for the ETS table is the reason because it makes lookups O(logN) instead of O(1). Since there are a lot of lookups it probably makes sense to just use a regular set type for the table and then sort the entries at the end. I will see the memory usage was pretty low, for what that’s worth. Anybody know why adding the encoding: :utf8 option to File.stream!/3 makes it twice as slow but more specifically seems to prevent full utilization of CPU? Without that option the CPU is pegged in all cores from the jump, but with that option the cores bounced around a lot more but averaged around 40-50% use.
stevensonmt
garazdawi
I built an Erlang implementation that does 1B lines in 60 seconds on my slow laptop.
https://github.com/jesperes/erlang_1brc/pull/1
To improve it further, maybe one could use the counters module. So much to do, so little time…
stevensonmt
This proved to be somewhat correct as making that change gets it down to around 95 seconds for 50M lines. Going to try processing lines via pattern matching by hand. Is it fair to optimize based on an assumption that the cities provided in the source for generating the data set are the only ones we need to worry about?
Went ahead and implemented based on the assumption that we only need to worry about the city names provided. This means you can pattern match lines as binaries based on the expected length of the city name. The longest was 26 characters and the shortest 3. Each character is utf8 so match on 26 * 8 down to 3 * 8 in increments of 8. This gets me consistently under 50sec for the 50M rows. Scared to try the billion on my 14yo i5 4 core machine. Think I have room to optimize more by moving away from Float.parse.
https://github.com/stevensonmt/brc/blob/main/lib/brc.ex
blubparadox
Float.parse does add up when doing it a billion times.
I take advantage of it always being one digit after the decimal so I split it around the decimal and basically use integers multiplied by 10 until the end.
Others are doing more complicated but faster pattern matching.
stevensonmt
I wasn’t sure if it was fair to assume the input would be restricted to one decimal place for the temp. I guess if I’m assuming the cities are predetermined I can probably assume that format too.
blubparadox
I think there’s some confusion. I’m not using Agents as a dumb storage technique, only using get and update. I’m using Agents as a low-setup GenServer, using Agent.cast and passing it a module and function atom to use Agent as active workers.