Ganzzahl-Division 128/128 bzw. 64/64 mit LLVM/clang vs. GCC vs. ...

[Stefan Kanthak]

Benutzt hier jemand mit clang erzeugte Programme, die Ganzzahl-Arithmetik
betreiben, insbesondere 64/64-bit Divisionen auf 32-bit Prozessoren oder
128/128-bit Divisionen auf 64-bit Prozessoren?

Anders gefragt: wer verwendet die von LLVM/clang verbrochenen und in den
Bibliotheken clang_rt.builtins-*.a gelieferten Funktionen __udivmoddi4()
bzw. __udivmodti4(), und die diese aufrufenden Funktionen __udiv[dt]i3(),
__umod[dt]i3(), __divmod[dt]i4(), __div[dt]i3(), __mod[dt]i3()?

<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/udivmoddi4.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/udivdi3.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/umoddi3.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/divdi3.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/moddi3.c>

<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/udivmodti4.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/udivti3.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/umodti3.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/divti3.c>
<https://github.com/llvm-mirror/compiler-rt/raw/master/lib/builtins/modti3.c>

JFTR: clang sowie GCC diese generieren Funktionsaufrufe fuer Operationen
128/128-bit und 128%128-bit bzw. 64/64-bit und 64%64-bit.
<https://gcc.gnu.org/onlinedocs/gccint/Integer-library-routines.html>

"money quote" von <https://compiler-rt.llvm.org/index.html>:

| The builtins library provides optimized implementations of this and
| other low-level routines, either in target-independent C form, or as
| a heavily-optimized assembly.


Auf 32-bit (Intel oder AMD) Prozessoren moege er/sie/es folgendes Programm
sowohl mit clang als auch mit GCC und -O3 -m32 uebelsetzen, dann ausfuehren
und die (von der Groesse der Operanden abhaengigen) Laufzeiten vergleichen:

--- 64-bit-on-32.c ---
// Copyright (C) 2018-2020, Stefan Kanthak <stefan....@nexgo.de>

#include <stdint.h>
#include <stdio.h>
#include <time.h>

extern
uint64_t __udivmoddi4(uint64_t dividend, uint64_t divisor, uint64_t *remainder);

__attribute__((noinline))
uint64_t __unopdi4(uint64_t dividend, uint64_t divisor, uint64_t *remainder)
{
if (remainder != NULL)
*remainder = divisor;

return dividend;
}

static inline
uint64_t lfsr64l(void)
{
// 64-bit linear feedback shift register (Galois form) using
// primitive polynomial 0xAD93D23594C935A9 (CRC-64 "Jones"),
// initialised with 2**64 / golden ratio

static uint64_t lfsr = 0x9E3779B97F4A7C15;
const uint64_t sign = (int64_t) lfsr >> 63;

return lfsr = (lfsr << 1) ^ (0xAD93D23594C935A9 & sign);
}

static inline
uint64_t lfsr64r(void)
{
// 64-bit linear feedback shift register (Galois form) using
// primitive polynomial 0x2B5926535897936B (CRC-64 "Jones"),
// initialised with bit-vector of prime numbers: 2**n == prime

static uint64_t lfsr = 0x28208A20A08A28AC;
const uint64_t mask = 0 - (lfsr & 1);

return lfsr = (lfsr >> 1) ^ (0x2B5926535897936B & mask);
}

int main(void)
{
clock_t t0, t1, t2, tt;
uint32_t m, n;
uint64_t left, right = ~0, remainder;
volatile uint64_t quotient;

for (m = 0; m < 32; m += m + 1)
{
t0 = clock();

for (n = 500000000; n > 0; n--)
{
left = lfsr64l();
left >>= left & m;
quotient = __unopdi4(left, right, NULL);
right = lfsr64r();
right >>= right & m;
quotient = __unopdi4(left, right, &remainder);
}

t1 = clock();

for (n = 500000000; n > 0; n--)
{
left = lfsr64l();
left >>= left & m;
quotient = __udivmoddi4(left, right, NULL);
right = lfsr64r();
right >>= right & m;
quotient = __udivmoddi4(left, right, &remainder);
}

t2 = clock();
tt = t2 - t0;
t2 -= t1;
t1 -= t0;
t0 = t2 - t1;

printf("\n"
"__unopdi4() %4lu.%06lu 0\n"
"__udivmoddi4() %4lu.%06lu %4lu.%06lu\n"
" %4lu.%06lu nano-seconds\n",
t1 / CLOCKS_PER_SEC, (t1 % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC,
t2 / CLOCKS_PER_SEC, (t2 % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC,
t0 / CLOCKS_PER_SEC, (t0 % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC,
tt / CLOCKS_PER_SEC, (tt % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC);
}
}
--- EOF ---

Wer noch schneller/hoeher/weiter messen will speichert den Assembler-
Quelltext <https://skanthak.homepage.t-online.de/integer.html#as-3> als
"as-3.s", verfuettert ihn zusammen mit "64-bit-on-32.c" wie folgt an clang
(oder GCC), fuehrt das Programm as-3 aus und vergleicht die Laufzeiten mit
den vorher gemessenen:

clang -m32 -O3 -o as-3 as-3.s 64-bit-on-32.c
./as-3


Auf 64-bit (Intel oder AMD) Prozessoren moege er/sie/es folgendes Programm
sowohl mit clang als auch mit GCC und -O3 -m64 uebelsetzen, dann ausfuehren
und die (von der Groesse der Operanden abhaengigen) Laufzeiten vergleichen:

--- 128-bit-on-64.c ---
// Copyright (C) 2018-2020, Stefan Kanthak <stefan....@nexgo.de>

#include <stdint.h>
#include <stdio.h>
#include <time.h>

extern
__uint128_t __udivmodti4(__uint128_t dividend, __uint128_t divisor, __uint128_t *remainder);

__attribute__((noinline))
__uint128_t __unopti4(__uint128_t dividend, __uint128_t divisor, __uint128_t *remainder)
{
if (remainder != NULL)
*remainder = divisor;

return dividend;
}

static inline
__uint128_t lfsr128l(void)
{
// 128-bit linear feedback shift register (Galois form) using
// primitive polynomial 0x5DB2B62B0C5F8E1B:D8CCE715FCB2726D,
// initialised with 2**128 / golden ratio

const __uint128_t poly = (__uint128_t) 0x5DB2B62B0C5F8E1B << 64 | 0xD8CCE715FCB2726D;
static __uint128_t lfsr = (__uint128_t) 0x9E3779B97F4A7C15 << 64 | 0xF39CC0605CEDC834;
const __uint128_t sign = (__int128_t) lfsr >> 127;

return lfsr = (lfsr << 1) ^ (poly & sign);
}

static inline
__uint128_t lfsr128r(void)
{
// 128-bit linear feedback shift register (Galois form) using
// primitive polynomial 0xB64E4D3FA8E7331B:D871FA30D46D4DBA,
// initialised with bit-vector of prime numbers: 2**n == prime

const __uint128_t poly = (__uint128_t) 0xB64E4D3FA8E7331B << 64 | 0xD871FA30D46D4DBA;
static __uint128_t lfsr = (__uint128_t) 0x800228A202088288 << 64 | 0x28208A20A08A28AC;
const __uint128_t mask = 0 - (lfsr & 1);

return lfsr = (lfsr >> 1) ^ (poly & mask);
}

int main(void)
{
clock_t t0, t1, t2, tt;
uint32_t m, n;
__uint128_t left, right = ~0, remainder;
volatile __uint128_t quotient;

for (m = 0; m < 64; m += m + 1)
{
t0 = clock();

for (n = 500000000; n > 0; n--)
{
left = lfsr128l();
left >>= left & m;
quotient = __unopti4(left, right, NULL);
right = lfsr128r();
right >>= right & m;
quotient = __unopti4(left, right, &remainder);
}

t1 = clock();

for (n = 500000000; n > 0; n--)
{
left = lfsr128l();
left >>= left & m;
quotient = __udivmodti4(left, right, NULL);
right = lfsr128r();
right >>= right & m;
quotient = __udivmodti4(left, right, &remainder);
}

t2 = clock();
tt = t2 - t0;
t2 -= t1;
t1 -= t0;
t0 = t2 - t1;

printf("\n"
"__unopti4() %4lu.%06lu 0\n"
"__udivmodti4() %4lu.%06lu %4lu.%06lu\n"
" %4lu.%06lu nano-seconds\n",
t1 / CLOCKS_PER_SEC, (t1 % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC,
t2 / CLOCKS_PER_SEC, (t2 % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC,
t0 / CLOCKS_PER_SEC, (t0 % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC,
tt / CLOCKS_PER_SEC, (tt % CLOCKS_PER_SEC) * 1000000u / CLOCKS_PER_SEC);
}
}
--- EOF ---

JFTR: fuer GROSSE Dividenden und KLEINE Divisoren werden die Zeiten
NOCH schlechter (bis Faktor 30 gegenueber GCC)!

Wer noch schneller/hoeher/weiter messen will speichert die Assembler-
Quelltexte <https://skanthak.homepage.t-online.de/integer.html#as-1>
und <https://skanthak.homepage.t-online.de/integer.html#as-2> als
"as-1.s" sowie "as-2.s", verfuettert sie zusammen mit "128-bit-on-64.c"
wie folgt an clang (oder GCC), fuehrt die Programme as-1 und as-2 aus
und vergleicht die Laufzeiten mit den vorher gemessenen:

clang -m64 -O3 -o as-1 as-1.s 128-bit-on-64.c
clang -m64 -O3 -o as-2 as-2.s 128-bit-on-64.c
./as-1
./as-2

Stefan
--
<https://www.duden.de/rechtschreibung/Kanthaken>