1BRC in Crystal

[nogginly]

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

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) in the Rust compiler.
• In the repo you will find three b variants which all use the new FxHashMap; in the the TODO 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).

  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

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 list for changes so far and possible further improvements.

  command	Lang	mean	stddev
  merykittyunsafe	Java	1.38626720956	0.01020137999217643
  merykitty	Java	1.52302498056	0.024776606613417875
  dannyvankooten/analyze	C	1.26986208056	0.0027637210575434737
  1brc_parallel_mmap 64 8	Crystal	3.22288731556	0.047787448027210376

  Relative performance was as follows:

    dannyvankooten/analyze ran
      1.09 ± 0.01 times faster than merykittyunsafe
      1.20 ± 0.02 times faster than merykitty
      2.54 ± 0.04 times faster than 1brc_parallel_mmap 64 8

Update, Feb 4

• I added page-aligned buffer variants (1brc_parallel2 and 1brc_parallel_ptr2)
• On a whim decided to benchmark them agains the prior forms.
• This included a change to the chunk sizing, and in these variants all but last chunk have the same size and the last chunk is smaller.
• These changes improved the overall performance.

Update Feb 2, 2024

• Added 1brc_parallel_ptr which uses Pointer instead of Slice to parse the buffer, essentially eliminating index bounds checking. While unsafe normally, the code is careful about the index maths.
• If you're on Linux, run shards build -Dpreview_mt to build the binaries
• See README section here for benchmarks using different thread count and buffer division values on M1 Macbook.

Original post

My implementation in Crystal is here: https://github.com/nogginly/1brc.cr

I've been inspired by the many contributions and over time have incorporated 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

I have not done the following (yet):

• 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
• did not optimize the Hash map use, which turns out to be the biggest bottleneck after latest update

See post in Crystal forum for some discussion and updates.

[Fryguy]

@nogginly Can you update the OP post with the various timings?

[nogginly]

See latest update (Feb 5) above.

[nogginly]

FYI, I've re-arranged the post to move the oldest posts to the bottom and recent ones to the top.