Poor performance of udivmod in zig compiler_rt

[plajjan]

Zig Version

0.10.0

Steps to Reproduce and Observed Behavior

I have a program implemented in Acton (https://github.com/actonlang/acton/), a programming language which generates C and uses zig cc to build an executable. In one particular program, using zig cc leads to a program that is roughly 50x times slower compared to gcc / clang:

kll@Boxy:~/terastream/Programming-Language-Benchmarks/bench/algorithm/edigits$ ~/terastream/acton/dist/bin/actonc 1.act --quiet && time ./1 30000 > /dev/null

real	0m3.255s
user	0m3.260s
sys	0m0.012s
kll@Boxy:~/terastream/Programming-Language-Benchmarks/bench/algorithm/edigits$ ~/terastream/acton/dist/bin/actonc 1.act --quiet --cc $(which gcc) && time ./1 30000 > /dev/null

real	0m0.154s
user	0m0.158s
sys	0m0.013s
kll@Boxy:~/terastream/Programming-Language-Benchmarks/bench/algorithm/edigits$ ~/terastream/acton/dist/bin/actonc 1.act --quiet --cc $(which clang) && time ./1 30000 > /dev/null

real	0m0.150s
user	0m0.152s
sys	0m0.013s
kll@Boxy:~/terastream/Programming-Language-Benchmarks/bench/algorithm/edigits$ 

I recorded some data for a flamegraph, where we can see that we spend most of the time in udivmod. I assume compiler_rt here refers to the zig compiler_rt and not clangs, right? I mean, otherwise it would have been slow with clang too..

As for reproduction, I can certainly add in the Acton program etc but I suspect it would be more convenient with a smaller C program that showcases the problem. However, before I do that, I would like to understand whether this type of bug report is accepted or if it's working as intended? Like is there a performance promise / idea of performance level to reach under which things are considered buggy?

Is there any way to workaround this? Can I somehow tell zig cc to use clangs udivmod?

Expected Behavior

I want my zig cc compiled program to run as fast as when I compile it using clang or gcc.

[daurnimator]

I assume compiler_rt here refers to the zig compiler_rt and not clangs, right?

Yes I would expect so, implementation is at https://github.com/ziglang/zig/blob/master/lib/compiler_rt/udivmod.zig

What target are you using?

[plajjan]

@daurnimator actonc is doing -target x86_64-linux-gnu.2.28. I have also tried with -target x86_64-linux-gnu.2.34. My system is on glibc 2.35 but AFAIK zig cc doesn't support it just yet (#12808). Results are the same regardless of what libc I target!

I have not tried with other OS / CPU arch.

[matu3ba]

lib/compiler_rt/udivmod.zig looks optimized for compatibility rather than performance in comparison to the LLVM function.

If you want to optimize it, I would recommend you to look into 10–9 Unsigned Division by Divisors ≥ 1 and 10–10 Incorporation into a Compiler (Unsigned) in Hacker's Delight, although the printing is fairly hard to decipher.

[matu3ba]

I want my zig cc compiled program to run as fast as when I compile it using clang or gcc.

We dont incorporate intrinsics yet, which are for obvious reasons faster. Especially on division.

[plajjan]

Ok, thanks for the info @matu3ba! Sounds reasonable to optimize for compatibility before performance.

FWIW, we have worked around this in Acton by optimizing the function that (indirectly) calls udivmod. It's a function in BSDNT, a C bigint library, which prints a bigint. It's about 400x faster now by doing a lot less divisions, so the difference in speed of udivmod between clang and zig cc makes much less of a difference. Naturally, I'd still like to see a faster udivmod in zig, but it's much less urgent for us.