1BRC in Elixir #93
Replies: 36 comments 145 replies
-
|
I was planning to do it in Erlang just for the fun of it, I'll keep you posted on my progress. :) |
Beta Was this translation helpful? Give feedback.
-
|
@IceDragon200 Did you get your 1brc challenge completed? I managed in 141 seconds on Apple M1 Pro with OTP 26 using plain Erlang. I'll try and push a solution later tonight after some cleaning up :-) I know that I still have a bottleneck at a specific place, I just don't know how to fix it just yet 😅 |
Beta Was this translation helpful? Give feedback.
-
|
No, it overheated, this is 10+ year old hardware fyi, I haven't had the time to look into it to see where I'm losing most of my cycles yet |
Beta Was this translation helpful? Give feedback.
-
|
@onno-vos-dev Did you ever get your implementation uploaded? |
Beta Was this translation helpful? Give feedback.
-
|
@IceDragon200 I was stuck in life and work and never pushed to GitHub 😥 Now I'm on vacation so it'll have to wait until Sunday/Monday depending on your timezone 👍 Will update here once I do 👌 |
Beta Was this translation helpful? Give feedback.
-
|
I'm trying something with Flow as this is almost the same scenario from their docs. defmodule VanillaFlow do
def run() do
filename = "./data/measurements.txt"
parent = self()
File.stream!(filename, :line)
|> Flow.from_enumerable()
|> Flow.map(fn line ->
[ws, temp] = :binary.split(line, ";")
temp = :binary.split(temp, "\n") |> List.first() |> :erlang.binary_to_float()
[ws, temp]
end)
|> Flow.partition()
|> Flow.reduce(fn -> :ets.new(:words, []) end, fn [ws, temp], ets -> # ETS
case :ets.lookup(ets, ws) do
[] ->
:ets.insert(ets, {ws, {temp, temp, temp}})
[{_, {current_min, current_mean, current_max}}] ->
:ets.insert(ets, {ws, {min(current_min, temp), (current_mean + temp) / 2, max(current_max, temp)}})
end
ets
end)
|> Flow.on_trigger(fn ets ->
:ets.give_away(ets, parent, [])
{[ets], :new_reduce_state_which_wont_be_used} # Emit the ETS
end)
|> Enum.to_list()
# then tab2list...
end
end |
Beta Was this translation helpful? Give feedback.
-
|
Love this. Did you see the docs suggestion to avoid a single large file as a stream? streams = for file <- File.ls!("dir/with/files") do
File.stream!("dir/with/files/#{file}", read_ahead: 100_000)
end
streams
|> Flow.from_enumerables()might lead to some small gains. |
Beta Was this translation helpful? Give feedback.
-
|
The single file source is indeed a huge bottleneck when using |
Beta Was this translation helpful? Give feedback.
-
|
Found an old post from 2007 about file processing in erlang. They were also referencing some 1 million (not billion) rows problem which seemed to take 6-7 seconds on their hardware. How far we've come :) |
Beta Was this translation helpful? Give feedback.
-
|
I contributed an Erlang benchmark to https://github.com/PlummersSoftwareLLC/Primes, mostly for fun, and when I posted about it in the Erlanger slack describing the dismal performance (compared to Rust), people were almost arguing that I shouldn't have done it because that is not what Erlang is good for. Like I had shown Erlang in bad light, or something. |
Beta Was this translation helpful? Give feedback.
-
|
Pure Erlang solution which runs in 130s on the full 1B input: https://github.com/jesperes/erlang_1brc/blob/main/src/aggregate.erl. Almost all the time is spent inside |
Beta Was this translation helpful? Give feedback.
-
|
It's always nice to see erlang so I can learn about modules I wouldn't otherwise use and Unfortunately on my hardware, I'm already losing 30s on just reading the file with no processing, could you share your hardware specs for comparison? |
Beta Was this translation helpful? Give feedback.
-
|
Cool!
The parsing can probably be faster with some pattern matching. In elixir, it could look like this: defmodule Parsers do
# Generates a function that takes binary strings representing numbers from -99 to 99
# and returns the corresponding integer. The numbers may be followed by more binary information such as
# a newline character that will be ignored.
@compile {:inline, temp2float: 1, split: 1}
for int <- 0..99 do
for dec <- 0..9 do
str_int = Integer.to_string(int)
str_dec = Integer.to_string(dec)
the_match = "#{str_int}.#{str_dec}"
float_val = String.to_float("#{str_int}.#{str_dec}")
def temp2float(<<"-", unquote(the_match), _>>), do: -unquote(float_val)
def temp2float(<<unquote(the_match), _>>), do: unquote(float_val)
def temp2float(<<"-", unquote(the_match)>>), do: -unquote(float_val)
def temp2float(unquote(the_match)), do: unquote(float_val)
end
end
# Generates a function that takes binary strings and splits them in 2 parts:
# - the first part can have max length of 100 bytes and is delimited by a semicolon.
# - the second part is a float number that may be followed by a newline character.
for x <- 1..100 do
ws_length_in_bits = x * 8
def split(<<ws::bitstring-size(unquote(ws_length_in_bits)), ";", temp::binary>>),
do: {ws, temp}
end
end |
Beta Was this translation helpful? Give feedback.
-
|
Or you could just do fixed-point integers (just like jesperen): defp binary_to_fixed_point(<<?-, d2, d1, ?., d01>>) do
-(char_to_num(d2) * 100 + char_to_num(d1) * 10 + char_to_num(d01))
end
defp binary_to_fixed_point(<<?-, d1, ?., d01>>) do
-(char_to_num(d1) * 10 + char_to_num(d01))
end
defp binary_to_fixed_point(<<d2, d1, ?., d01>>) do
char_to_num(d2) * 100 + char_to_num(d1) * 10 + char_to_num(d01)
end
defp binary_to_fixed_point(<<d1, ?., d01>>) do
char_to_num(d1) * 10 + char_to_num(d01)
endOn the topic of |
Beta Was this translation helpful? Give feedback.
-
|
I'm going to take a look inside |
Beta Was this translation helpful? Give feedback.
-
|
The 130s figure is on a i7-10610U CPU, so it is pretty spiffy but no monster. |
Beta Was this translation helpful? Give feedback.
-
|
We should be able to go faster if we could read the file concurrently. That's what the Java implementations are doing after all. Does anyone know if we could use Erlang's pread/2 to achieve that? |
Beta Was this translation helpful? Give feedback.
-
|
pread won't work unless you know the position of chunks/lines ahead of time I think You can drop down to |
Beta Was this translation helpful? Give feedback.
-
|
I'm using loop(FD) -> loop(FD, <<>>).
loop(FD, PrevBuf) ->
{ok, NewBuf} = prim_file:read(FD, ?BUFSIZE),
[First, Rest] = binary:split(NewBuf, <<"\n">>),
Chunk = <<PrevBuf/binary, First/binary>>,
process_chunk(Chunk), %% Chunk is now a binary with a whole number of lines
loop(FD, Rest). |
Beta Was this translation helpful? Give feedback.
-
|
I've tried both |
Beta Was this translation helpful? Give feedback.
-
|
I use pread in my approach and chop off the last bit of the binary that doesn't form a full line and append it to the next chunk. This allows me to decouple reading and processing and do both in parallel. "Unfortunately" I went on vacation before I could clean it up and push my solution so it'll have to wait a week. In essence though the flow is as followed: Most time was spent in binary_to_float/1 so curious how much improvements @jesperes float parsing brings to my approach. Will try that next week when I'm back at home 👍 |
Beta Was this translation helpful? Give feedback.
-
|
I'm doing something similar. The original caller process starts N "pipelines", and then goes on reading the input file in chunks, and sending the chunks to one of the N pipelines in a round-robin fashion. Each of the processing pipelines consists of two processes, one which calls |
Beta Was this translation helpful? Give feedback.
-
|
How do you account for a partial line at the end of a chunk going to one pipeline and the rest of that line going to the next pipeline? |
Beta Was this translation helpful? Give feedback.
-
|
Read a chunk (N bytes) and then immediately read a line afterwards, append the result to your chunk before sending it to the worker (that's what I did at least) {:ok, blob} = IO.read(file, count)
{:ok, line} = IO.read_line(file)
blob = <<blob::binary, line::binary>>You will of course have to check if you've reached the end of the file in both cases, but that's the gist of it |
Beta Was this translation helpful? Give feedback.
-
|
Well, finally finished my first run: 17 minutes, I think I can do better even with my potato hardware, I'll have new results in... 20 minutes: Good news: down to 8 minutes, https://github.com/IceDragon200/1brc_ex/blob/master/src/1brc.workers.blob.maps.chunk_to_worker.exs on my hardware |
Beta Was this translation helpful? Give feedback.
-
Well, I knew about the |
Beta Was this translation helpful? Give feedback.
-
|
I found out about prim_file because of jesperes, I tried looking it up from the docs as well but it was nowhere to be found, but I do have elixir and erlang's sources locally available so I usually just read them there |
Beta Was this translation helpful? Give feedback.
-
|
I'm running your (IceDragon200) version on my machine, and it's taking about half the time as mine. I don't know how much more I'll work on it because each change basically turns it into your version. |
Beta Was this translation helpful? Give feedback.
-
|
Ah, whoops, how off was it? decimals or whole numbers off? EDIT: Fixing it made it a tad bit faster now, since I don't do a rolling average (which doesn't work with multiple processes, so I'll keep that in mind next time) |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, it is worth keeping in mind that you can process the lines in any order you want, and then do the final computation of the mean at the end. |
Beta Was this translation helpful? Give feedback.
-
For chunks C1, C2, C3, ... Cn, I split C2 once at |
Beta Was this translation helpful? Give feedback.
-
|
One problem with input.split('\n').fold(...)so that you can fold over the binaries without having to construct a (huge) list first. |
Beta Was this translation helpful? Give feedback.
-
|
Could you try |
Beta Was this translation helpful? Give feedback.
-
|
Well, no, because (I mean, I could write my own fold-method which splits on line at a time, which I presume is what |
Beta Was this translation helpful? Give feedback.
-
|
Even though the challenge is about using "just java" or Elixir/Erlang in this case, this Explorer solution seemed quite interesting to me. defmodule WithExplorer do
# Results
# [
# 1_000_000_000: 675483.000ms,
# 500_000_000: 58244.713ms,
# 100_000_000: 10321.046ms,
# 50_000_000: 5104.949ms,
# ]
require Explorer.DataFrame
alias Explorer.{DataFrame, Series}
@filename "./data/measurements.txt"
def run() do
parent = self()
results = @filename
|> DataFrame.from_csv!(header: false, delimiter: ";", eol_delimiter: "\n")
|> DataFrame.group_by("column_1")
|> DataFrame.summarise(min: Series.min(column_2), mean: Series.mean(column_2), max: Series.max(column_2))
|> DataFrame.arrange(column_1)
# This could be improved... Would be nice to do it inside Explorer
for idx <- 0..(results["column_1"] |> Series.to_list() |> length() |> Kernel.-(1)) do
"#{results["column_1"][idx]}=#{results["min"][idx]}/#{:erlang.float_to_binary(results["mean"][idx], decimals: 2)}/#{results["max"][idx]}"
end
end
endThe eager backend scaled linearly up to about 7GB (500 mil lines) using all my cores. Something happens with larger files that will make my machine do a lot of disk IO, and the 1 billion version performs ~6x slower. |
Beta Was this translation helpful? Give feedback.
-
|
Another Elixir implementation, which has been my first program in this language. It takes about 12 minutes with 1B rows on an ultra-low-voltage processor that is 7 years old. |
Beta Was this translation helpful? Give feedback.
-
|
I love the implementation, but unfortunately it's not fast... very concise though. Here are the stats on my hardware: |
Beta Was this translation helpful? Give feedback.
-
|
Another Erlang implementation: https://github.com/Kartstig/1brc_erl Takes ~80s on my Threadripper 1950X However, I haven't utilized |
Beta Was this translation helpful? Give feedback.
-
|
So good news: I think it completed on my system, I had to kill everything not needed outside of my desktop environment (i3 btw), I haven't checked the stats yet though, I'll have an update in an hour or so |
Beta Was this translation helpful? Give feedback.
-
|
@Kartstig Good news, I have the test repo up https://github.com/IceDragon200/1brc_erl_ex_test/tree/master Bad news: I deleted the results (while fixing up the repo) before updating the table, I'm stupid, so we'll have to wait another hour or so for the results, again... |
Beta Was this translation helpful? Give feedback.
-
|
@IceDragon200 I tried running it. Got through all the submodues, but I had some issue with the symlink: I ran them one by one moving the file into each directory manually live a caveman: @andypho - Slow, but barely noticed any memory usage. Was very light on my cores @IceDragon200 - Quick. Used all my cores and a good chunk of memory @Kartstig - Lots of memory usage :). Probably too much core activity @rparcus @rrcook - Moderate Core usage. @stevensonmt - Light core usage @mnfloresv - Light core usage |
Beta Was this translation helpful? Give feedback.
-
|
Cool, thanks for running those. I'm clearly not concurrent enough but have several ideas for how to improve it. I assumed Task.async_stream with max_concurrency of the number of cores would max out the system without any other manual manipulation but I guess it does not. |
Beta Was this translation helpful? Give feedback.
-
|
Updated the table And that's weird with the symlinks, worked fine on both of my machines are you running this on linux? rparcus has multiple implementations, the one I usually pull the stats from is the with_explorer one, the other two were attempts without it, he last said to disregard that specific implementation due to a race condition though. Did I miss anything else? |
Beta Was this translation helpful? Give feedback.
-
|
@jesperes Could you provide a bash script to run your code, I'm putting together a table with the current times using my hardware for comparison I just have no idea how to run yours |
Beta Was this translation helpful? Give feedback.
-
|
I've done some improvements and incorporated some fixes from @garazdawi. There is a script which can be run using Feel free to update the table at the top when/if you get around to rerunning it. |
Beta Was this translation helpful? Give feedback.
-
|
Oh, I didn't realize that there was a scaffolding project. I'll make a PR to it to update the submodule for my implementation. |
Beta Was this translation helpful? Give feedback.
-
|
@jesperes re-ran the benchmark, but the numbers are about the same |
Beta Was this translation helpful? Give feedback.
-
|
Okay, everyone I've tried gathering some concrete numbers from my hardware (and almost killed it in the process) running everyone's implementation. I think we can all appreciate a single piece of hardware running it and giving somewhat consistent numbers yes? You can check the primary comment for your implementation, some times and my comments about it, for everyone who's new, you can link your implementation by simply commenting and I'll get it up within an hour of seeing it, usually. |
Beta Was this translation helpful? Give feedback.
-
|
Could you check this one also? https://github.com/rparcus/ex_1brc/blob/main/lib/entries/10_with_explorer.ex Related chat: https://elixirforum.com/t/performance-with-explorer-scales-linearly-with-size-and-then-suddenly-degrades-on-large-file/60987 |
Beta Was this translation helpful? Give feedback.
-
|
Sure, give me however long it takes to run, and I'll probably need to enable :lazy yeah EDIT.1: Very promising, 4 seconds on 50M rows, but it doesn't output the result so I can't verify if it's correct EDIT.3: One moment, enabled collect, trying again, modified output: IO.write "{"
for idx <- 0..(results["column_1"] |> Series.to_list() |> length() |> Kernel.-(1)) do
min = :erlang.float_to_binary(results["min"][idx], decimals: 2)
mean = :erlang.float_to_binary(results["mean"][idx], decimals: 2)
max = :erlang.float_to_binary(results["max"][idx], decimals: 2)
"#{results["column_1"][idx]}=#{min}/#{mean}/#{max}"
end
|> Enum.intersperse(", ")
|> IO.write()
IO.write "}"EDIT.4: 4.7s on 50M rows, OOM on 1B rows |
Beta Was this translation helpful? Give feedback.
-
|
GIve mine a try please, https://github.com/rrcook/brc After you git clone, 'mix deps.get', 'mix escript.build' then './brc measurements.txt'. I have timing built in, it will tell you the number of milliseconds after the output. |
Beta Was this translation helpful? Give feedback.
-
|
Sure thing, I'm waiting on the others to finish, then I'll add yours to the list, had to change computers since I need all my resources. EDIT: Added your repo to the tests, need to rerun everything because I deleted it in my infinite wisdom |
Beta Was this translation helpful? Give feedback.
-
|
@rparcus Broke one of your new implementations: |
Beta Was this translation helpful? Give feedback.
-
|
Wow your new system has more cores than mine^^. At the bottom of the file, where that function is generated, there is a comment about this. Could you bump the number up to be equal or greater than the number of cores you have? |
Beta Was this translation helpful? Give feedback.
-
|
Strange, I only have 6 cores / 12 threads, you'd think that would fit in the range you have there |
Beta Was this translation helpful? Give feedback.
-
Okay, I have more than I thought I did, what is going on here |
Beta Was this translation helpful? Give feedback.
-
|
I thought a bit about it and I think that there is a race condition issue with the implementation :( Please disregard :( |
Beta Was this translation helpful? Give feedback.
-
|
Everyone, the Ryzen numbers are up... and while I want to chalk it up to bias hardware being bias... look at the numbers yourself (gosh I look good up there) The most surprising is @rparcus was able to claim the 50M spot, but his implementation seems to have fallen apart at the 1B test. I have no idea why, considering the intel test smoked everyone else, so I'd like to believe it has something to do with the Intel vs AMD optimizations in the nifs themselves. Other implementations did, as expected with faster hardware, same thing, just faster. |
Beta Was this translation helpful? Give feedback.
-
|
Any idea what's going on with the memory use here: with the 1B run using LESS memory than the 50M? |
Beta Was this translation helpful? Give feedback.
-
|
2nd place for the non-Explorer implementations, I'll take it. |
Beta Was this translation helpful? Give feedback.
-
|
@rrcook My implementation scales by the number of logical processors, which I just learned was not 12 but 32, so it's actually 128 workers instead of 48 that chewed up chunks of 16Mb, so it likely under-performed (which is scary to think about) @stevensonmt It's a fairly stable implementation, it could just be BEAM being BEAM, these are just rough estimates I feel 1B |
Beta Was this translation helpful? Give feedback.
-
|
@garazdawi Results are up, considering your low CPU and low memory footprint, I really wish I could have ran jesperen's original version as well for comparison, that is some amazing performance, makes me think I could squeeze some more out of my own implementation right now. Bonus points: the 50M completed in under 6s on my intel cpu when I was testing the test scripts, the only other implementation that did that was @rparcus explorer |
Beta Was this translation helpful? Give feedback.
-
|
Ah, so I'll just use your repo for his results then, give me a moment, could you shed some light on why the implementation is this fast though? |
Beta Was this translation helpful? Give feedback.
-
|
My implementation is faster than Jesper's because I use bit syntax instead of binary:split. Using bit syntax does not build the huge list that is otherwise generated. I also avoid a copy of the binary by not joining the chunk binaries before sending them to the process. I haven't looked at the other implementations here, so can't say what makes the difference there. |
Beta Was this translation helpful? Give feedback.
-
|
Ah, I see it now, it's faster because all it has to do is scan the string and then count how many bits/bytes it needs to extract before the semicolon, completely avoiding the list construction from binary.split You can safely slice the string without creating a new copy, brilliant, I'll try it in my implementation and see if that improves performance on my intel system |
Beta Was this translation helpful? Give feedback.
-
|
@garazdawi, I'm having a hard time following your code (b/c I'm pretty unfamiliar with Erlang mostly) but I think I'm doing something similar in my newer approach with macros in Elixir. Is this what you mean by "use bit syntax instead of binary:split"? |
Beta Was this translation helpful? Give feedback.
-
|
My first version did something similar to that, but I realised that I could do it simpler, so the latest version is just a simple loop. |
Beta Was this translation helpful? Give feedback.
-
|
Updated Ryzen times for: @IceDragon200 @garazdawi and @jesperes Also rerunning the entire suite to see if the figures change drastically, I think garazdawi's code wasn't JIT-ed at the time of testing hence the slower time |
Beta Was this translation helpful? Give feedback.
-
|
@stevensonmt Ran and updated (figures are about the same), you accidentally committed a massive log file though, not sure if that was intended |
Beta Was this translation helpful? Give feedback.
-
|
That's bizarre. I'm consistently getting 30 seconds on my 4 cores for 50M. Can't imagine what's happening to make it slower with more cores. I will try to see what's going on with the log file. I think lexical crashed and that's probably the log file. So yeah lexical crashed and kept trying to restart. Thanks for pointing that out. Also I see the difference in our timing methods now, which explains why I'm so far off in my estimates. I was going off running
I'm not sure what accounts for the huge discrepancy. Starting the VM and cleaning up the tables are the only things not captured in the |
Beta Was this translation helpful? Give feedback.
-
|
I just hand timed a run and the wall-clock time it takes is apparently equivalent to what
I feel like I'm taking crazy pills over here. That 121.72 is somewhat close to the number of cores * the 33.357 total. Is there some bug in These numbers are all for a 50M row data file. I ran @IceDragon200's implementation and got
while my most recent iteration is getting
so I would expect mine to run at maybe 10-15 seconds on the machine that's getting 3s for his implementation. This is really puzzling to me. |
Beta Was this translation helpful? Give feedback.
-
|
Let's unfold it: Honestly I think it's fine, btw I used GNU time for the tests |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for the explanation, but what seems crazy to me is that you got a slower time on better hardware (I assume your table is reporting wall-clock time). I also used GNU time when I ran them.
And yes, my reaction time is not great on the stopwatch, lol. BTW, I don't expect you to troubleshoot this or anything. I just don't like not understanding what could be responsible for the differences. |
Beta Was this translation helpful? Give feedback.
-
|
Even if :prim_file is not thread safe, one can use a semaphore to regulate access and let each worker read its own chunk with :prim_file. A worker process could:
I thought it would be faster because we don't need to pass partial chunks of binaries around between process, but turns out that it's about 30% slower than something similar to what @IceDragon200's implementation does, where one process reads and all other workers parse. My lesson learned here is:
|
Beta Was this translation helpful? Give feedback.
-
|
Managed to tidy up my implementation a bit and push it (1brc) and create a PR to add my implementation @IceDragon200 👍 See: IceDragon200/1brc_erl_ex_test#1 It's not the cleanest code I ever wrote but I don't believe that was part of the challenge here 😅 I'm using @jesperes Float parsing but otherwise the structure is fairly similar to what the others have tried. Interestingly enough my approach beats @garazdawi (by a hair 😅) by using plain Here are the results from my Mac M1 Pro: Versions used for testing: 50M Results:
1B Results:
|
Beta Was this translation helpful? Give feedback.
-
|
Oh wow! Interesting to see it perform that much slower on Ryzen HW compared to my M1 😱 Guess I got some more work to do to steal that first place 😅 |
Beta Was this translation helpful? Give feedback.
-
|
What was the error? Just thinking about this the problem might be that my repo includes the executable compiled on my machine which would be incompatible with your Mac. Did you run the test with |
Beta Was this translation helpful? Give feedback.
-
|
Yeah I was surprised too, I ran it three times to be sure, it's pretty much the same figure, heck I ran my implementation first to ensure the disk was warmed up (clocked in at 2 minutes instead of 46 seconds like it normally does), but your implementation always runs at around 1 minute, so not sure what's going on there |
Beta Was this translation helpful? Give feedback.
-
|
@stevensonmt You changed the main function right? So it no longer takes the second parameter, the test scaffold needed updating so I'll fix that EDIT: Okay your new results are up |
Beta Was this translation helpful? Give feedback.
-
|
Thanks! Still a little disappointing but at least it's close to what I'm getting for the 50M on four cores. Thanks again for doing these runs! I'm curious if I'm interpreting the results correctly. Since it's maxing out at <400% CPU usage on a 6-core CPU, I'm guessing either something in my code limits the concurrency or the concurrent tasks complete so quickly that it's never using all cores to the max. Is that accurate? Just curious if I'm doing something to limit it to only 4 cores by accident and I don't catch it b/c all my machines are only 4 cores since the CPU usage is almost the same:
I noticed I was using a chunk size about 5x more than what @IceDragon200 uses. I reduced it from 80M bytes to 10M and my times are now consistently under 18 seconds for 50M lines on my 4 core CPU. Not sure how to predict the optimal chunk size baed on available hardware. |
Beta Was this translation helpful? Give feedback.
-
|
I have pushed a PR with two optimizations:
|
Beta Was this translation helpful? Give feedback.
-
|
I'd be happy if you'd ping me whenever you rerun this, but no hurry. :) |
Beta Was this translation helpful? Give feedback.
-
|
@jesperes Wish fulfilled |
Beta Was this translation helpful? Give feedback.
-
|
Awesome, thanks! |
Beta Was this translation helpful? Give feedback.
-
|
This is seriously impressive |
Beta Was this translation helpful? Give feedback.
-
|
Fun thing: I ran this on my Windows gaming rig (i5-12400F 32GB), and got the blazingly fast runtime of 13.5s (!). |
Beta Was this translation helpful? Give feedback.
-
|
@IceDragon200 just merged my latest version. See: IceDragon200/1brc_erl_ex_test#4 Results on my Mac M1 Pro compared to the fastest previous solution from Jesperes. a 17.2% improvement on the 1B results. For some reason its a slower on the 50M results. Something that I'm looking into tonight 👍 50M results:
1B results:
Very excited to see how this'll do on Ryzen and if we can get an "official" sub 10 second time on the board 😅 |
Beta Was this translation helpful? Give feedback.
-
|
Great! With 10k entries, the Erlang process dictionary seem to be the bottle neck. ETS scales better in that regard. |
Beta Was this translation helpful? Give feedback.
-
|
@IceDragon200 Created IceDragon200/1brc_erl_ex_test#9 in order to address my crash 👍 @jesperes You're getting a name_clash crash as your hashing function apparently isn't unique enough (something you mentioned to me before) 😞 @mneumann I ran mine through the 1B 10k test and process dictionary still outperforms ETS by about 3x (3.23x on my M1 Pro). To be clear, I don't think we should start using process dictionary instead of ETS in production systems (there has to be strong reasons to rely on process dict instead of some other storage) but for the sake of the 1brc it still performs well and while being 64% slower, it still handles it well.
For shits and giggles I also tried a 1B with 41.342 weather stations (all names from the csv present in this repo) to see if process dictionary finally caves in. 🔨
While both of are are definitely slower, process dictionary still takes the crown 👑 While process dictionary is 2.28x slower with that many more keys, ETS is only 1.27x slower so ETS takes the crown on that front 🤴
Combined set of default 1B, 1B with 10k keys and 1B with 41.342 keys sorted by time. Funny to see how much memory spiked with 41.342 weather stations on my solution 😅 And how stable yours is 🎉 🥇
(Disclaimer: Each of these sets was run while I had other windows open such as Slack, Spotify and Chrome which eat a little bit of CPU despite me being hands-off from my keyboard this means slightly higher times than on idle) |
Beta Was this translation helpful? Give feedback.
-
|
@onno-vos-dev Are you saying that Process dictionary is always faster than ETS? On my machine, it's 2x slower in the 10k weather stations case. Maybe I am doing something wrong :). Btw, I created an adaptive solution that can start using a Process dict and then upgrades on-the-fly to a ETS when a certain threshold (number of keys) is reached. As it is super generic, it is slightly slower than the specialized version, but not significantly :). I now also support monadic-style Map storage backends :). |
Beta Was this translation helpful? Give feedback.
-
|
@mneumann I don't think Process dictionary is always faster per sé. It might be that if I tweak my solution to use ETS that on the 10k approach, I get better times on ETS. I'll try that out tonight 👍 I think process dictionary probably suffers when dealing with larger process dictionaries especially since they're updated as often as they are 👍 I should have been more clear on this in my above statements. I'll get back to you tonight 👍 How does a map perform? I have memories and experiments of Advent of Code experiments where maps performed poorly on larger number of keys. Would be curious to see how it performs here. |
Beta Was this translation helpful? Give feedback.
-
|
When thinking about this problem early on I thought that maybe using persistent_term + counter would be an option. Though I don't know how to make max or min work with those, but doing the average should be easy enough. |
Beta Was this translation helpful? Give feedback.
-
|
Upon request I have ran the 10k weather station test, results are under the default 420 (heh) weather station tests, since this test takes much longer to run, I won't be updating it frequently |
Beta Was this translation helpful? Give feedback.
-
|
Here are the 1B Results on 224 core Intel Xeon:
The machine is behind an http proxy that denied access to some packages that rparcus uses which is why those did not work. This is run using Erlang 26.2.1 and latest main Elixir. |
Beta Was this translation helpful? Give feedback.
-
|
@garazdawi Wow, I'm surprised mine is at 35 seconds 😱 Are you sure it's using the latest version of the submodule? 🤔 It should be on par with Jesperes and yours 🤔 I have a hard time understanding why it's so much slower 🐌 And thank you for running these on this sort of hardware! 🙇♂️ |
Beta Was this translation helpful? Give feedback.
-
|
I was surprised as well. I ran |
Beta Was this translation helpful? Give feedback.
-
|
Interesting as that commit should be fine. It's funny how it was 2x slower than on the Ryzen hardware 😅 I'll have to do some thinking on this one if the 2nd run is similar 😄 |
Beta Was this translation helpful? Give feedback.
-
|
Here are the 1B Results:
roughly the same on this run. |
Beta Was this translation helpful? Give feedback.
-
|
Updated my solution now, and replaced some shitty home-grown hash function with Fnv32 (thanks @onno-vos-dev) and stole some spawn options from him too. :) |
Beta Was this translation helpful? Give feedback.
-
|
Results updated for both standard and 10k dataset (congrats on having the fastest standard implementation, kind of hard to beat an NIF in the 10k test) |
Beta Was this translation helpful? Give feedback.
-
|
@jesperes Did the spawn options make any difference in performance? I quickly tried some of these out, but did not see a signification change. Or are they only useful when the solution uses a lot memory to disable GC? |
Beta Was this translation helpful? Give feedback.
-
|
Yes, the spawn options actually do seem to make a difference, at least in my case. I saw 37s -> 31s, or something in that range. |
Beta Was this translation helpful? Give feedback.
-
|
The |
Beta Was this translation helpful? Give feedback.
-
|
In case anyone is interested, feel free to rip out my (half-baked) PropEr test (PR: onno-vos-dev/1brc#4) and throw it at your solution 😄 It found some bugs for me and some really interesting ones... Apparently the FNV32a hash for |
Beta Was this translation helpful? Give feedback.
-
|
Updated results, looks like you lost some performance generally, but it's still fast even with 10k cities |
Beta Was this translation helpful? Give feedback.
-
|
I would have expected to have lost a bit of performance but really wanted to get PropEr to not have to do any special things. Now it's my turn again to try and speed things back up while maintaining correctness through the support of PropEr 😅 😄 Thank you for running the results again! ❤️ |
Beta Was this translation helpful? Give feedback.
-
|
After a huge amount of fighting trying to come up with a variant of the FNV32 Hash which was both fast and produced unique results, I finally managed! 🎉 See details in: onno-vos-dev/1brc#5 which includes a list of 128k unique cities (those with a population over 1000 inhabitants) with a unit test to ensure uniqueness across all of them. With a runtime of |
Beta Was this translation helpful? Give feedback.
-
|
Updated standard and 10k results, an improvement in times, but positions haven't really changed |
Beta Was this translation helpful? Give feedback.
-
|
Thank you! It's a start 😄 At least I'm confident at my PropEr test as well as the unit test and I can change things now and ensure things don't break going forward ❤️ Thanks for re-running and updating the results! |
Beta Was this translation helpful? Give feedback.
-
|
@mneumann Results updated with mneumann/1brc-elixir@efb7aae |
Beta Was this translation helpful? Give feedback.
-
|
Hi everyone, new idea on top of what already worked well: It does pretty well on my machine for the 420 test, and should be close to the top solutions without using dependencies. Didn't test for 10k... |
Beta Was this translation helpful? Give feedback.
-
Can share tmr, in about a few hours. I have printed and formatted one but am already in bed now. |
Beta Was this translation helpful? Give feedback.
-
|
Okay all tests completed for the new implementation, you've somehow won the lottery in all cases, so congrats |
Beta Was this translation helpful? Give feedback.
-
|
Wow @rparcus I tried doing some runtime code generation but it definitely wasn't faster so I scrapped that idea! Cool to see you managed to make it work! Will have to see how you did it 😄 |
Beta Was this translation helpful? Give feedback.
-
|
@jesperes Excerpt of how the generated code looks like. Surprisingly similar to my approach which I now have to dust off again... 😅 def process_lines(<<\"Whitehorse\", ?;, rest::binary>>) do
get_temp(rest, 411)
end
def process_lines(<<\"Ouagadougou\", ?;, rest::binary>>) do
get_temp(rest, 412)
end
def process_lines(<<>>), do: :ok
def idx(0), do: \"Austin\"
def idx(1), do: \"Baghdad\"
def idx(2), do: \"Kano\"
def idx(3), do: \"Dhaka\"
def idx(4), do: \"Burnie\" |
Beta Was this translation helpful? Give feedback.
-
|
Great work @rparcus! 🎉 👍 🥇 Couldn't resist and pick up my generator again and figure out why it was so slow. Looking at your approach @rparcus the big difference was your usage of A bit of trickery and cleaning up later and rolling my own Sadly, still not faster than @jesperes approach on my laptop at least 😢 For some reason @jesperes is able to squeeze out an additional 150% CPU... generate_and_compile(LkupTable) ->
Start = init_module(),
ProcessLines = process_lines(LkupTable),
End = remaining_parts_of_module(),
Full = <<Start/binary, ProcessLines/binary, End/binary>>,
{ok, Tokens, _} = erl_scan:string(binary_to_list(Full)),
{_, ParsedForms} = lists:foldl(fun(Token, {TokenAcc, FormsAcc}) ->
case Token of
{dot,_} ->
FormTokens = lists:reverse([Token | TokenAcc]),
{ok, Forms} = erl_parse:parse_form(FormTokens),
{[], [Forms | FormsAcc]};
Token ->
{[Token | TokenAcc], FormsAcc}
end
end, {[], []}, Tokens),
{ok, brc_workers, Bin} = compile:forms(lists:reverse(ParsedForms)),
{module, brc_workers} = code:load_binary(brc_workers, "nofile", Bin).Results on my Mac M1 Pro: 50M Results:
1B Results:
|
Beta Was this translation helpful? Give feedback.
-
Implementations
https://github.com/IceDragon200/1brc_erl_ex_test
AMD Ryzen 5 2600 / 32Gb DDR4 IceDragon200
Standard Data Set (420 weather stations)
50 Million
1 Billion
10k City Data Set
50 Million
1 Billion
RETIRED: Intel i7-2710QE @ 2.10Ghz / 16Gb DDR3 IceDragon200
This has been retired, if your implementation is not listed here, it's because I've stopped testing on my poor laptop, check the Ryzen section for your updated figure.
Dirty System - While under normal usage
Clean System - Nothing else running with it
AMD Threadripper 1950X @ ?Ghz / 94.2Gb DDR4 Kartstig
Wait a minute, how did you get these numbers?
tl;dr i7-2710QE capped at 2.10Ghz, and 16Gb of DDR3 RAM, only 4Gb is readily available for benching on a Lenovo E520. The hardware is 10+ years old.
All implementations were ran on a dirty system (that is, it's actively doing other work, mostly just firefox running so I can check this discussion), I'm currently listening to music which should be a low cpu and low disk job.
Hardware is a 10+ year old laptop CPU, more specifically a i7-2710QE running at a max clock of 2.10Ghz, turbo is disable to avoid overheating since the Lenovo E520 it's currently sitting in was not designed for it.
They are all ran with:
time your_main_entry_pointI always run the 50M test first, so your code will at least compile during that window, it will be ran twice, since all currently listed implementations can finish in under a minute
OOM?
Out-Of-Memory, I have 16Gb of memory, only 4~9Gb is usually free, so that means all of these implementations needed to run under 4Gb at worst, if your implementation OOMs, I will mark it as such no further comment.
Okay, so you sabotaged it for your own implementation!
No, I am aware of my system's constraints and appropriately reduced the amount of work it had to do in order to work within those constraints, relying on the disk and hammering the CPU instead of the memory, all implementations are ran with the same constraints, I try not to use the computer while it's benching, outside of listening to music to pass the time (come on, 18 minutes is a lot of nothing to do you know).
How do I get my implementation listed?
Just comment in this discussion with a link to it, I'll check and try to run it, just be aware of what I'm benchmarking it on.
Okay, I have an implementation!
Great, if it doesn't process 50M rows in under 2 minutes I'm not doing the 1B row test, I'm not wasting time or compute on that (and to be fair, I treat all of my implementations the same)
Okay, I made changes, can I get a re-test?
Sure, just comment that you did and I'll re-test it.
Related or Good reads
Current Status
After much trial and error and gathering knowledge from everyone's methods, I finally have a fast-enough implementation (there may be more room for improvement):
https://github.com/IceDragon200/1brc_ex/blob/master/src/1brc.workers.blob.maps.chunk_to_worker.exs
This completes in under 7 minutes on an i7-2710QE @ 2.10Ghz (turbo was disabled to maintain a safe operating temp, this laptop was not designed for the CPU after all).
Originally the code was idiomatic elixir, but there are a few things:
Filevs:prim_file- if you run the original code under:eperf, one would notice the countlessfilerelated modules being called through standardElixir.Fileor erlang's:file, while I'm not entirely sure why it has so many processes involved, it likely has to do with concurrent access. The short solution is to cut out all of it and drop down to:prim_fileit is likely not concurrently safe, but chances are you're already chewing through the file on a single process as fast as you can, this removes around 2 to 3 layers of indirection and sends:binary.split/2- is major the bottleneck, it's unclear if there is a way to make it faster at this pointFloat.parse/1vs:erlang.binary_to_float/1vs just doing it yourself -Float.parsewas much slower than expected, until one looks into it's implementation, since Float.parse needs to handle's elixir's niceities, it introduced additional parsing overhead:erlang.binary_to_float/1, is much faster, if you don't need all the nice elixir things (e.g. underscores)IO.read_line/1is a terrible idea, it is wasteful if one understands how reading line works internally, at the very bottom of it all is:prim_file, a read_line must read a chunk into a prim_buffer and then each character scanned to look for the newline, the result is then returned, this is great, if you didn't have 3+ function calls between each line read and the same scanning over and over and over again.No longer relevant original post
Not exactly the fastest, erlang/elixir has trouble with heavy IO applications in general.
I only tested it against 50 million rows vs the 1 billion, the former completes in around a minute (specifically the
1brc.workers.stream.exsothers are 2x to 8x slower), since it pretty much scales linearly from what I've seen, I estimate it would take 20 minutes to complete on my hardware (i.e. Intel Core i7-2710QE).As of this writing my poor laptop's fan is screaming at me while I run the 1 billion line test.
I tried four different implementations, anything with the
reducesuffix is 4x slower than itsstreamcounterpart.The fastest implementation I have so far is the
1brc.workers.stream.exson my system it uses 32 workers/erlang-processes (that is 8 logical processors x 4) by taking batches of 100'000 rows at a time for each worker it keeps them quite busy anything less and they end up idling.Each implementation is mostly self contained outside of the output module which is shared across all four for writing the final result to console/STDIO
If anyone with slightly more recent hardware would be willing to provide some better numbers that would be swell.
Beta Was this translation helpful? Give feedback.
All reactions