# 1BRC in Crystal **URL:** \ **Category:** News\ **Created:** [February 1, 2024, 4:37am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467 "2024-02-01T04:37:32Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 1, 2024, 4:37am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/1 "2024-02-01T04:37:32Z")
While Gunnar Morling originally posed [The One Billion Row Challenge](https://www.morling.dev/blog/one-billion-row-challenge/) for Java developers, over time folks have started implementing it in different languages which are [showcased here](https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell). When reviewing the results in Java I ran across [one implementation in C](https://github.com/gunnarmorling/1brc/discussions/46) that made me wonder what I could do with Crystal. **My implementation in Crystal is here:** [GitHub - nogginly/1brc.cr: Implementation of the "One Billion Rows Challenge" using Crystal.](https://github.com/nogginly/1brc.cr) I’ve been inspired by the many contributions at 1BRC and over time have incorporated several ideas. The following is a list of the different ways in which I’ve been able to speed up the Crystal implementation (`1brc_parallel.cr` in the repo): - unrolling parsing for the temperature - chunking the parsing into parallel work - using Crystal’s fibers and enabling multithreading - use operators that ignore overflow checking I did not however do the following which a lot of show & tell contributions: - ~~did not use memory mapping for the file since (a) Crystal limits arrays to Int32 indices, (b) the most memory I have is 16GB~~ _(see update below)_ - did not use vector processing or any other CPU-specific optimization Regardless, to Crystal’s credit, my parallel implementation runs faster than some of the top contenders when I compared them on my laptops. I’d love to know if there’s something more I can do to improve the performance. I’ve included my initial serial implementations as well. ### Update, Feb 2 I’ve added a `Pointer`-based variant called `1brc_parallel_ptr` which runs 5% faster than `1brc_parallel` which uses `Bytes`. ### Update, Feb 4 I added page-aligned buffer variants (`1brc_parallel2` and `1brc_parallel_ptr2`) and on a whim decided to benchmark them agains the prior forms. The variations include a change to the chunk sizing, all but last chunk have the same size, and the last chunk is smaller (remainder of a division). These changes improved the overall performance. ## Update, Feb 5 - I’ve added a version that uses `mmap` for loading the file, which turns out to improve performance on Linux but not so much on macOS. - On a PC with AMD Ryzen 7 7735HS CPU, 16 cores, 32 GB, and running Linux, comparing with some other `1brc` contenders there’s still room to do. See the [TODO](https://forum.crystal-lang.org/TODO.md) list for changes so far and possible further improvements. ## Update, Feb 7 - Figured out why macOS was performing poorly with `mmap` … memory! With only 16GB of RAM memory mapping a 13GB file (1B row) was causing problems (likely swapping). - I switched to a 500 row (6.5GB) file which is large enough to be comparable while small enough to fit … and voila! The `mmap` variant outperforms all others on macOS. - In addition I implement a specialized `FxHashMap` (inspired by the `merykitty` implementation) after digging into the FxHash function ([details here](https://nnethercote.github.io/2021/12/08/a-brutally-effective-hash-function-in-rust.html)) in the Rust compiler. - In the repo you will find three `b` variants which all use the new `FxHashMap`; in the the [TODO](https://github.com/nogginly/1brc.cr/blob/main/TODO.md#fxhashmap-is-faster) you can see the comparison where the `b` variants beat all their predecessors. Relative performance is now as follows, with my implementation now _only_ 🙂 1.87x slower (vs 2.58x as of two days ago). ```txt dannyvankooten/analyze ran 1.02 ± 0.13 times faster than serkan-ozal 1.18 ± 0.03 times faster than merykittyunsafe 1.87 ± 0.01 times faster than 1brc_parallel_mmap2b 32 24 <---- 2.58 ± 0.05 times faster than 1brc_parallel_mmap2 32 24 ``` ---
**Author:** ![sdogruyol](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/sdogruyol/32/38_2.png) [@sdogruyol](https://forum.crystal-lang.org/u/sdogruyol)\ **Post date:** [February 1, 2024, 11:06am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/2 "2024-02-01T11:06:28Z")
Wow this is awesome, I wanted to do it myself but no time. Thanks a lot! ---
**Author:** ![straight-shoota](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/straight-shoota/32/36_2.png) [@straight-shoota](https://forum.crystal-lang.org/u/straight-shoota)\ **Post date:** [February 1, 2024, 11:54am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/3 "2024-02-01T11:54:25Z")
Overcommiting on threads seems very odd. I would expect optimal saturation when the number of Crystal threads equals the number of hardware threads, thus the OS doesn’t need to shuffle and all threads can power through. The number of fibers can be higher to take advantage of waiting time while reading from disk. Since all fibers are reading from the same file, I wouldn’t overdo it though. You could decrease the number of fibers and have each fiber run a loop to tackle the next piece of work when it has finished one task. This should be more efficient than massively overcommiting on fibers but limit their concurrency by passing buffers forward. Memory mapping might indeed offer a quite a substantial performance increase. > [@nogginly](#): > > did not use memory mapping for the file since (a) Crystal limits arrays to Int32 indices, (b) the most memory I have is 16GB What’s the problem with that? You don’t need to map the entire file at once. You can load individual slices, each up to `Int32::MAX` (or `part_size`). A smaller suggestion which might have some impact or not that much: `Slice#[]` has an implicit range check. If you are sure the index is valid, you can use pointer arithmetics directly to avoid the check. This is similar to overflowing operators. ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 1, 2024, 11:22pm UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/4 "2024-02-01T23:22:06Z")
> [@straight-shoota](#): > > You don’t need to map the entire file at once. You can load individual slices, each up to `Int32::MAX` (or `part_size`). Right, good point. I “assumed” I had to map it all and didn’t actually look into how it worked. And there’s so much good stuff in your overall note, I’m going to start a TODO list in the repo and start making new versions. 🙏 ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 2, 2024, 4:32am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/5 "2024-02-02T04:32:11Z")
> [@straight-shoota](#): > > Overcommiting on threads seems very odd. I would expect optimal saturation when the number of Crystal threads equals the number of hardware threads, thus the OS doesn’t need to shuffle and all threads can power through. It does feel odd, and I remember the exact moment when I put in a high thread count as a lark while trying to figure out how to get higher multi-core utilization and couldn’t believe the result. There’s some pipelining effect happening because of the pattern of “IO burst followed by long pure in-memory compute” that seems to favour queuing a lot of work. When I have some more time I’ll dig into it. In the meantime I’ve put up more data (for i7 running on battery) showing the way performance reponds to thread count and chunk count (i.e. buffer division) [here in the repo](https://github.com/nogginly/1brc.cr/blob/main/perfdata/DATA_1brc_parallel.md). ---
**Author:** ![Bonarc](https://avatars.discourse-cdn.com/v4/letter/b/7ab992/32.png) [@Bonarc](https://forum.crystal-lang.org/u/Bonarc)\ **Post date:** [February 2, 2024, 5:52am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/6 "2024-02-02T05:52:47Z")
The current fastest implementation is in C# from what I know. Have you had a chance to run that on your laptop? ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 2, 2024, 6:13am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/7 "2024-02-02T06:13:36Z")
I have not run that. I have been using the Java submissions `merykitty` and `merrykitty_unsafe` by Quan Anh Mai, - which per Gunnar run in 03.210s and 02.367s respectively on his benchmarking system, - and run in 15.149s and 14.917s on my M1 Macbook Based on that, my implementation, running in 8.646s on the M1, is about 40% faster. ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 2, 2024, 6:18am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/8 "2024-02-02T06:18:14Z")
> [@straight-shoota](#): > > A smaller suggestion which might have some impact or not that much: `Slice#[]` has an implicit range check. If you are sure the index is valid, you can use pointer arithmetics directly to avoid the check. Done. ---
**Author:** ![Bonarc](https://avatars.discourse-cdn.com/v4/letter/b/7ab992/32.png) [@Bonarc](https://forum.crystal-lang.org/u/Bonarc)\ **Post date:** [February 2, 2024, 6:28am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/9 "2024-02-02T06:28:43Z")
[It’s here if you wanna try](https://github.com/buybackoff/1brc?tab=readme-ov-file). The author also made an extended input and I believe is keeping a leaderboard that you could add yours to ---
**Author:** ![yxhuvud](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/yxhuvud/32/27_2.png) [@yxhuvud](https://forum.crystal-lang.org/u/yxhuvud)\ **Post date:** [February 2, 2024, 4:58pm UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/10 "2024-02-02T16:58:45Z")
> [@straight-shoota](#): > > The number of fibers can be higher to take advantage of waiting time while reading from disk What? No. Reading from disk is a blocking operation and will block the thread until done. To get around that you need to use either a threadpool with more threads, or io\_uring. That is assuming Linux is used. I’m not aware of what async possibilities of reading files asyncronously there are on mac or windows. (if we want to deep dive into implementation specifics, the implementation use `wait_readable` for disk io as well, but files are **always** readable - it is the actual `read`ing that is blocking and take time. This is a big difference to how network sockets work. It is also one of the main reasons it would be neat to have a io\_uring based event machine) ---
**Author:** ![straight-shoota](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/straight-shoota/32/36_2.png) [@straight-shoota](https://forum.crystal-lang.org/u/straight-shoota)\ **Post date:** [February 2, 2024, 5:26pm UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/11 "2024-02-02T17:26:18Z")
Oh yeah. You’re right. File IO is indeed blocking (by default; most of the time). I was indeed misled by the mindset of sockets. ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 4, 2024, 6:31pm UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/12 "2024-02-04T18:31:48Z")
A question - Since IO read is blocking in a thread, it seems to make sense why I’m seeing better performance by running so many fibers relative to the threads; is that a reasonable conclusion? A discovery - I’ve been playing with `mmap` using a test app and was surprised to find it didn’t help on macOS. So I switched to a Linux machine and ran my test programs and … drum roll … `mmap` won hands down. - Essentially, using `mmap` is a win for Linux and not so much for macOS in the situation where I’m chunking one big file and scanning it concurrently. I hope to have an `mmap`-based version of my Crystal `1brc` app soon. ---
**Author:** ![jgaskins](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jgaskins/32/2449_2.png) [@jgaskins](https://forum.crystal-lang.org/u/jgaskins)\ **Post date:** [February 4, 2024, 10:11pm UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/13 "2024-02-04T22:11:56Z")
> [@nogginly](#): > > I’ve been playing with `mmap` using a test app Do you have any good links for using `mmap` from Crystal? I’ve been curious for a while, but haven’t found anything good. ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 5, 2024, 12:19am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/14 "2024-02-05T00:19:00Z")
After some research (aka Duck Duck Fu) I discovered that Crystal stdlib already has definitions for the `mmap` API under `LibC`. So, using [man mmap](https://www.man7.org/linux/man-pages/man2/mmap.2.html) as a reference to using the API, I was able to get the following very simply program opening a file and loading it via `mmap`: ```cr file = File.new(ARGV.first, "r") # mmap 1K of the file starting at offset 0 ptr = LibC.mmap(nil, 1024, LibC::PROT_READ, LibC::MAP_PRIVATE, file.fd, 0) byteptr = Pointer(UInt8).new(ptr.address) # cast to byte pointer buf = Bytes.new(byteptr, 1024, read_only: true) # wrap with a Slice(UInt8) # do stuff STDOUT.write_string(buf) # clean up LibC.munmap(ptr, 1024) ``` This is just to illustrate how to use it. When you compile and run this with a file argument, it will - open the file - `mmap` first 1K of the file to a pointer - cast and wrap it into a `Bytes` slice - print out the 1K - clean up the mapping Also note: - I used `PROT_READ` but if you want to use `mmap` to then modify the file you’ll need to OR `PROT_WRITE`. - I used `MAP_PRIVATE` for exclusive use, but if you want to share etc, there are other `MAP_**` options in the man page that are also available. ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 6, 2024, 3:32am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/15 "2024-02-06T03:32:43Z")
Posted latest update after adding an `mmap`-based implementation. Turns out `mmap` improves performance on Linux, but not so much on macOS. Since the challenge’s target was Linux, I’ll continue to test and post results for that OS. As yo ucan see from my comparisons, I’m still notdoing as well as I would like. The `merykitty_unsafe` Java app running on Open JDK 21 is beating my app hands down. To help figure out what was taking up time I commented out the code where I use a `Hash` to store the stats and look them up by name. Without `Hash` map use … ```txt % time ./run.sh 1brc_parallel_mmap 64 8 ./run.sh 1brc_parallel_mmap 64 8 17.58s user 0.66s system 1276% cpu 1.429 total ``` With `Hash` map use … ```txt % time ./run.sh 1brc_parallel_mmap 64 8 ./run.sh 1brc_parallel_mmap 64 8 45.62s user 0.76s system 1443% cpu 3.214 total ``` That’s a ~2.24 x more time when storing the data, and an obvious candidate for my next attempts. ---
**Author:** ![nogginly](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/nogginly/32/1795_2.png) [@nogginly](https://forum.crystal-lang.org/u/nogginly)\ **Post date:** [February 12, 2024, 3:08am UTC](https://forum.crystal-lang.org/t/1brc-in-crystal/6467/16 "2024-02-12T03:08:50Z")
### Updated, Feb 11 - Switched to long word bitmasking for parsing the name - A small improvement by itself, my best is up to 1.74x slower from previous best at 1.84x slower. - Posting results because I’m starting to see parallelism match the availables cores. - Btw, for me at least, there is no significant different between my two best results; given the way the file is read in parallel and in chunks, using `mmap` or not doesn’t make a big difference. - This is notable only because it might mean the non-`mmap` version, which uses ~1GB of runtime RAM, is going to do well regardless of file size. > I realise there are even faster C#/C/SIMD/etc versions out there. And I haven’t run the official GraalVM-based Java winner yet either. At this point `serkan-ozal` is my goal. 😄 | relative | command | Lang | mean (s) | stddev | | --- | --- | --- | --- | --- | | 1.0x | _serkan-ozal_ | _Java_ | _1.1661091954200002_ | 0.10359078275160513 | | | dannyvankooten/analyze | C | 1.24137285062 | 0.003261490844545827 | | | merykittyunsafe.sh | Java | 1.34270993842 | 0.036888174169103186 | | | merykitty.sh | Java | 1.51770504842 | 0.021277280568716347 | | **1.74x slower** | **1brc\_parallel\_ptr4 16 48** | **Crystal** | **2.03081785402** | 0.06009663760371807 | | 1.77x slower | 1brc\_parallel\_mmap2b 16 32 | Crystal | 2.06915509142 | 0.01875921473395469 |