2026-08-26

An alternative to utoa in C

tpl2c's runtime writes integers with one small function, hc_utoa. It takes two digits at a time from a table of the pairs "00" to "99", the trick Andrei Alexandrescu describes in Three Optimization Tips for C++. My first version computed each pair with a % and a / by 100. Getting the remainder from the quotient made it faster under gcc and TinyCC, and changed nothing under clang.

I rebuilt both versions for this article and timed them on one x86-64 machine under Debian 13, with gcc 14.2 and clang 19.1 at -O2, and TinyCC 0.9.27. Times are in nanoseconds per call, the best of five runs of at least 0.2 seconds on one core. Two runs of the same build can differ by up to 20%. The Open Watcom listings come from wcc386 -ox. I did not time Open Watcom.

The loop

The digits are written backwards, from the end of a buffer, so the length does not have to be known first. The first version:

while (v >= 100) {
    unsigned k = (unsigned)(v % 100) * 2;
    v /= 100;
    *--end = hc_pairs[k + 1];
    *--end = hc_pairs[k];
}

Taking two digits at a time already halves the iterations, but each pair still has a % and a / by 100. The second version divides once and gets the remainder from the quotient:

while (v >= 100) {
    hc_umax  q = v / 100; /* the one division: the remainder comes from q */
    unsigned k = (unsigned)(v - q * 100) * 2;
    v = q;
    *--end = hc_pairs[k + 1];
    *--end = hc_pairs[k];
}

gcc and clang

Neither emits a division here, before or after. A division by a constant becomes a multiplication by its inverse, and both compilers share that one multiplication between the % and the /. Here is gcc's loop on x86-64 after the change:

.L3:
    mov     rcx, rdx
    shr     rdx, 2
    sub     rdi, 2
    mov     rax, rdx
    mul     r8                     ; r8 = 0x28F5C28F5C28F5C3
    mov     eax, ecx
    shr     rdx, 2                 ; q = ((v >> 2) * M) >> 66 = v / 100
    imul    esi, edx, 100
    sub     eax, esi               ; r = v - q * 100
    lea     eax, 1[rax+rax]
    movzx   eax, WORD PTR -1[r9+rax]
    mov     WORD PTR [rdi], ax     ; both digits in one 16-bit store
    cmp     rcx, 9999
    ja      .L3

What changed under gcc is the remainder. The old loop rebuilt q * 100 in 64 bits with an and, an add, an lea and a sal, and the loop had 20 instructions. Since the result is cast to unsigned, the new one computes it with one 32-bit imul, in 14 instructions. clang already used an imul for the old source.

On x86-32, where unsigned long has 32 bits, gcc multiplies by 0x51EB851F, which is 2³⁷/100 rounded up, and shifts by 5. The loop is the same before and after the change; this is the old one:

.L3:
    mov     eax, ecx
    mov     edi, ecx
    sub     ebx, 2
    mul     esi                    ; esi = 0x51EB851F
    shr     edx, 5                 ; q = (v * M) >> 37
    imul    eax, edx, 100
    sub     edi, eax               ; r = v - q * 100
    mov     eax, ecx
    mov     ecx, edx
    movzx   edx, WORD PTR hc_pairs[edi+edi]
    mov     WORD PTR [ebx], dx
    cmp     eax, 9999
    ja      .L3

TinyCC and Open Watcom

These two do not turn a division by a constant into a multiplication, and they do not see that % and / by the same number can share one div. Here is Watcom's 32-bit loop before the change:

L$2:
    mov     ebx,64H
    mov     eax,ecx
    xor     edx,edx
    div     ebx                    ; v % 100
    mov     eax,ecx
    lea     ebx,[edx+edx]
    mov     ecx,64H
    xor     edx,edx
    div     ecx                    ; v / 100, a second div

and after it, with one div and an imul for the remainder:

L$2:
    mov     eax,ecx
    xor     edx,edx
    div     edi                    ; edi = 64H
    mov     edx,eax
    imul    eax,edi                ; q * 100
    sub     ecx,eax                ; r

TinyCC does the same, at 32 and at 64 bits: two div per pair before, one after.

Timings

Under tcc, a quarter to a third faster from four digits on, and 13% at 19 digits. Under gcc, a quarter faster from eight digits. Under clang, the differences are within the 20% two runs can vary.

Under tcc the loop still pays one div per pair, and 19 digits take ten times as long as under gcc. Writing the multiplication by the inverse in C would remove it, but on 64 bits that needs the high half of a 64 by 64 bit product, and C89 has no type to hold it.