Hacker News Reader

Comment by kongin | Hacker News Reader

>… but that’s exactly how conversion to string works, so handrolling an algorithm would likely be around the same speed.

https://github.com/lattera/glibc/blob/master/stdio-common/_i...

It's all bit-shifts, bit-masks and a lot of other hacks to get the maximum performance out of the system you're compiling the code on.

Could I write something with better performance on my system? Yeah, after a week to run tests and write esoteric macros.

View on HN

An optimizing compiler will turn div-by-constant and mod-by-constant into multiplications and bitshifts. For example, the Rust compiler: https://play.rust-lang.org/?version=stable&mode=release&edit... (select "Show assembly" on the top-left button).

    pub fn divmod10(x: u32) -> (u32, u32) {
       (x / 10, x % 10)
    }

generates

    mov ecx, edi
    mov eax, 3435973837
    imul rax, rcx
    shr rax, 35
    lea ecx, [rax + rax]
    lea ecx, [rcx + 4\*rcx]
    sub edi, ecx
    mov edx, edi
    ret

It's still not as efficient since you're breaking on base 10 digit boundaries, not base 2, the most efficient encoding will be base 3, but alas we don't have ternary computers.

But it's a much more compact than that glibc monstrosity is. Sure, the glibc version will win in a micro-benchmark, but micro-benchmarks don't capture the effect on the instruction cache.

https://en.wikipedia.org/wiki/Radix_economy

Using a decimal expansion adds 25% overhead from pure maths. Your cache will be larger if you're working in base ten regardless of what optimizations your compiler does.

Reply on news.ycombinator.com