Skip to content

Latest commit

 

History

History
41 lines (32 loc) · 1.95 KB

README.md

File metadata and controls

41 lines (32 loc) · 1.95 KB
Raw

1brc-simd

Process 1 billion row of text data as fast as possible

https://www.morling.dev/blog/one-billion-row-challenge/

Discussion thread: gunnarmorling/1brc#138

Use sha256sum to check that output is same as reference output a55d0d9d02661c33538f2e11bb86f1825a5f015d6dd3645416ec71bc50099ee5 result.txt

The output should contain 1 end-line characters New line characters might cause problems. If sha256sum is different, check content of file.

I used this file (generated by ./create_measurements.sh 1000000000) to test: https://drive.google.com/file/d/1HEyNw4M453n0tnuaAm9nwaCiLydQYnpo/view?usp=sharing

To test the 10K dataset, download the file below then cat measurements.txt >> measurements_10k.txt 5 times: https://drive.google.com/file/d/1T-G9iPJ0L4hAt3U7FEig025B7SCxj6aX/view?usp=sharing

To run, just download the file above, extract, then ./run.sh To run with a different number of threads, just ./run.sh 32

This code use a trick to practically disable hyperthreading. To force the code to run at max number of threads, use: ./run.sh N N, where N is output of nproc --all Sometimes it's faster, sometimes it's worse.

Main indeas:

  • Unsigned int overflow hashing: cheapest hash method possible.
  • SIMD to find multiple separator ; and loop through them
  • SIMD hashing
  • SIMD for string comparison in hash table probing
  • ILP trick (each thread process 2 different lines at a time)
  • Parse number as int instead of float
  • Notice properties of actual data
    • 99% of station names has length <= 16, use compiler hint + implement SIMD for this specific case. If length > 16, use a fallback => still meet requirements of MAX_KEY_LENGTH = 100
    • -99.9 <= temperature <= 99.9 guaranteed, use special code using this property
  • Use mmap for fast file reading
  • Use multithreading for both parsing the file, and aggregating the data
  • Other random tricks (intentional ordering of variable assignments)