1BRC SIMD, targeting both Java and C via Singeli

[dzaima]

https://github.com/dzaima/1brc

Core SIMD logic written in Singeli, from which either Java jdk.incubator.vector usage or C AVX2 intrinsics are generated (repo comes with the code of both pregenerated so Singeli isn't required to run it).

The core hot code is pretty much equivalent between C and Java, so this effectively shows the difference between the codegen of OpenJDK 21 and C (I'm testing on clang-17).

As I only have 8GB RAM, I'm testing on a 100M-record input (i.e. 1.38GB) on my i3-4160 (Haswell, 3.6GHz), configured to run on 2 threads. C takes 0.56s, and Java - 3.3s (14.9s if ran 10 times in a loop in the same VM, simulating 1e9 records).

Some differences between the two:

• C version uses a vpgatherqq to gather four 8-byte segments of the input for temperatures, but, while Java's Vector does have gathers, they're only for aligned loads in same-type arrays, which don't work here (we need to load arbitrary-alignment longs within a byte[]), so it's emulated with four vector loads, stores to a temp buffer, and another load to construct the vector.

• Smaller things include using a max(a-b,0) instead of an unsigned saturating subtract, more manual digit multiplying where C uses a single vpmuldq, and a couple more similar things.

But most of the perf difference should just be that OpenJDK generates less optimal machine code and does bounds checks.

[AlexanderYastrebov]

Great stuff!

Some test cases do not pass though

$ for sample in $(ls $BRCHOME/src/test/resources/samples/*.txt); do echo $(basename $sample); diff <(make run file=$sample | $BRCHOME/t
ocsv.sh) <($BRCHOME/tocsv.sh < ${sample%.txt}.out) ; done
measurements-10000-unique-keys.txt
measurements-10.txt
measurements-1.txt
measurements-20.txt
5c5
< Berlin1️⃣🐝🏎️;-0.3;-0.3;0.0
---
> Berlin1️⃣🐝🏎️;-0.3;-0.3;-0.3
15c15
< Nashville1️⃣🐝🏎️;-4.9;-4.9;0.0
---
> Nashville1️⃣🐝🏎️;-4.9;-4.9;-4.9
measurements-2.txt
measurements-3.txt
measurements-boundaries.txt
1c1
< Bosaso;-99.9;-99.9;0.0
---
> Bosaso;-99.9;-99.9;-99.9
measurements-complex-utf8.txt

[dzaima]

Interesting, will look into that. Didn't test much myself.

[dzaima]

Pushed a fix - missed initialization of the starting max temperature. (and also fixed a C version bug of an some_uint64-1 < 0 not replaced after being ported from Java)

[AlexanderYastrebov]

Could you try it on 1e9 records file?
On my machine (#67) it completes in 10m winning the slowest contest 🤣

real    10m10,581s
user    72m29,993s
sys     0m24,896s

[dzaima]

Huh. Ran it on 1e9 lines, even with HDD speeds it took real 5m39.617s, user 1m44.004s.
For that slow of a result I'd guess that the vector operations failed to JIT to actual SIMD instructions, or something to that effect; your system should have AVX2 though, so I have no clue why that'd be (I'm on openjdk 21.0.1 2023-10-17). Can't really say much though, this is my first time using Java's Vector stuff, or Java microoptimization in general.

[AlexanderYastrebov]

Thank you, the idea is great anyways, maybe something is off on my machine.
time ./a.out completes in 40s

real    0m40,298s
user    2m4,463s
sys     0m9,363s

[lehuyduc]

I ran your code on a 2950X, running at 8 threads (default in your code). Same machine as here #138 , and you can download the file from my repo (13.8 GB, 1B lines)

real	0m20.653s
user	1m24.287s
sys	0m1.592s

[dzaima]

I did check the sums, and they did match mine. Didn't bother with counts, that's much more difficult to screw up if the sums work.

[lehuyduc]

I notice that you use fork() instead of threads. I wonder how that affects munmap time. Will it be evenly divided per child process instead of being linear?

Edit: oh no it seems fork() really allows parallel munmap unlike thread. This will cause an arm race 😭

[dzaima]

I did mention fork-parallel unmapping here; I mmap 32MB chunks too, so I get to start doing some effective-munmap after just going through 32MB, interleaved through the whole execution, separately for each fork. You can change the constexpr bool global_mmap = false; to true to see how timings are impacted by having just one massive mmap before forking instead.

[lehuyduc]

result_dzaima.txt
result_dzaima_10k.txt

I've just benchmarked your code again, with both default + 10K dataset. All thread range from 1 => 32. Commit
fa6db52

Good news: it's super fast now on the default dataset!! It's still slow on the 10K dataset, but I assume it's because you haven't worked on it yet. Also global_mmap = true doesn't decrease any performance.

Bad news: By using fork() instead of threads, your program is getting the exact same speedup as creating a child process, do everything there, then kill the parent process. I tested that by implementing that trick in your code, but there's no speedup. That means, if you want a fair comparison with everyone else, we have to subtract everyone's munmap + free memory time (because if fork() is legal then everyone can just implement this trick and get the same amount of speedup). Actually I'm not sure about this. Like, there's no official rules about this.

void handleSignal(int signum) {
    if (signum == SIGUSR1) {
        printf("Received SIGUSR1 signal. Exiting.\n");
        exit(0);
    }
}

int main(int argc, char* argv[]) {
  signal(SIGUSR1, handleSignal);

  int pid = fork();
  int status;
  if (pid == 0) {
    return do_everything(argc, argv);
  } else {
    waitpid(pid, &status, 0);
  }
}

Amd 2950x
Default dataset

1 thread
real    0m8.806s
user    0m8.299s
sys     0m0.500s

16 thread
real    0m0.663s
user    0m9.501s
sys     0m0.608s

32 thread
real    0m0.549s
user    0m15.816s
sys     0m1.019s

10K dataset

1 thread
real    0m53.456s
user    0m52.469s
sys     0m0.956s

2 thread
real    0m27.355s
user    0m53.389s
sys     0m0.952s

8 thread
real    0m7.107s
user    0m54.899s
sys     0m1.076s

real    0m7.092s
user    0m54.435s
sys     0m1.059s

16 thread <= performs better than 32 threads
real    0m3.927s
user    0m59.005s
sys     0m1.204s

32 thread
real    0m5.938s
user    3m0.619s
sys     0m2.054s```

[dzaima]

Right, I haven't worked at all on the 10k dataset; I'd probably want to make a separate thing for it if I wanted to do it (a trivial thing would be making the hashmap have more than 4096 slots, but then it might slot in a different cache level).
(edit: actually, currently the hashmap size is a dynamic value within the SIMD code, so I could theoretically adapt the hashmap size to the input)

I don't really understand all the munmap business. Is it that the kernel cleans up the fork in the background, potentially after the main program has finished? If so, I don't think that should apply to my solution with global_mmap = false, as each fork, upon completing, has only 32MB mapped; the vast majority of the input is already removed from the address space.