From 9525c26bf19318bed72d3bc3b99dceac5217102f Mon Sep 17 00:00:00 2001 From: Francois-Xavier Coudert Date: Sun, 26 Dec 2021 11:59:14 +0100 Subject: [PATCH] Fortran: speed up decimal output of integers libgfortran/ChangeLog: PR libfortran/98076 * runtime/string.c (itoa64, itoa64_pad19): New helper functions. (gfc_itoa): On targets with 128-bit integers, call fast 64-bit functions to avoid many slow divisions. gcc/testsuite/ChangeLog: PR libfortran/98076 * gfortran.dg/pr98076.f90: New test. --- gcc/testsuite/gfortran.dg/pr98076.f90 | 293 ++++++++++++++++++++++++++++++++++ libgfortran/runtime/string.c | 65 +++++++- 2 files changed, 353 insertions(+), 5 deletions(-) create mode 100644 gcc/testsuite/gfortran.dg/pr98076.f90 diff --git a/gcc/testsuite/gfortran.dg/pr98076.f90 b/gcc/testsuite/gfortran.dg/pr98076.f90 new file mode 100644 index 0000000..d1288a4 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/pr98076.f90 @@ -0,0 +1,293 @@ +! { dg-do run } +! { dg-require-effective-target fortran_large_int } +! +! Check that we can print large integer values + +program test + implicit none + ! 128-bit integer kind + integer, parameter :: k = selected_int_kind(38) + + character(len=39) :: s + character(len=100) :: buffer + integer(kind=k) :: n + integer :: i + + ! Random checks + do i = 1, 1000 + call random_digits(s) + read(s,*) n + write(buffer,'(I0.38)') n + print *, s + print *, buffer + if (adjustl(buffer) /= adjustl(s)) stop 2 + end do + + ! Systematic check + call check(0_k, "0") + call check(1_k, "1") + call check(9_k, "9") + call check(10_k, "10") + call check(11_k, "11") + call check(99_k, "99") + call check(100_k, "100") + call check(101_k, "101") + call check(999_k, "999") + call check(1000_k, "1000") + call check(1001_k, "1001") + call check(9999_k, "9999") + call check(10000_k, "10000") + call check(10001_k, "10001") + call check(99999_k, "99999") + call check(100000_k, "100000") + call check(100001_k, "100001") + call check(999999_k, "999999") + call check(1000000_k, "1000000") + call check(1000001_k, "1000001") + call check(9999999_k, "9999999") + call check(10000000_k, "10000000") + call check(10000001_k, "10000001") + call check(99999999_k, "99999999") + call check(100000000_k, "100000000") + call check(100000001_k, "100000001") + call check(999999999_k, "999999999") + call check(1000000000_k, "1000000000") + call check(1000000001_k, "1000000001") + call check(9999999999_k, "9999999999") + call check(10000000000_k, "10000000000") + call check(10000000001_k, "10000000001") + call check(99999999999_k, "99999999999") + call check(100000000000_k, "100000000000") + call check(100000000001_k, "100000000001") + call check(999999999999_k, "999999999999") + call check(1000000000000_k, "1000000000000") + call check(1000000000001_k, "1000000000001") + call check(9999999999999_k, "9999999999999") + call check(10000000000000_k, "10000000000000") + call check(10000000000001_k, "10000000000001") + call check(99999999999999_k, "99999999999999") + call check(100000000000000_k, "100000000000000") + call check(100000000000001_k, "100000000000001") + call check(999999999999999_k, "999999999999999") + call check(1000000000000000_k, "1000000000000000") + call check(1000000000000001_k, "1000000000000001") + call check(9999999999999999_k, "9999999999999999") + call check(10000000000000000_k, "10000000000000000") + call check(10000000000000001_k, "10000000000000001") + call check(99999999999999999_k, "99999999999999999") + call check(100000000000000000_k, "100000000000000000") + call check(100000000000000001_k, "100000000000000001") + call check(999999999999999999_k, "999999999999999999") + call check(1000000000000000000_k, "1000000000000000000") + call check(1000000000000000001_k, "1000000000000000001") + call check(9999999999999999999_k, "9999999999999999999") + call check(10000000000000000000_k, "10000000000000000000") + call check(10000000000000000001_k, "10000000000000000001") + call check(99999999999999999999_k, "99999999999999999999") + call check(100000000000000000000_k, "100000000000000000000") + call check(100000000000000000001_k, "100000000000000000001") + call check(999999999999999999999_k, "999999999999999999999") + call check(1000000000000000000000_k, "1000000000000000000000") + call check(1000000000000000000001_k, "1000000000000000000001") + call check(9999999999999999999999_k, "9999999999999999999999") + call check(10000000000000000000000_k, "10000000000000000000000") + call check(10000000000000000000001_k, "10000000000000000000001") + call check(99999999999999999999999_k, "99999999999999999999999") + call check(100000000000000000000000_k, "100000000000000000000000") + call check(100000000000000000000001_k, "100000000000000000000001") + call check(999999999999999999999999_k, "999999999999999999999999") + call check(1000000000000000000000000_k, "1000000000000000000000000") + call check(1000000000000000000000001_k, "1000000000000000000000001") + call check(9999999999999999999999999_k, "9999999999999999999999999") + call check(10000000000000000000000000_k, "10000000000000000000000000") + call check(10000000000000000000000001_k, "10000000000000000000000001") + call check(99999999999999999999999999_k, "99999999999999999999999999") + call check(100000000000000000000000000_k, "100000000000000000000000000") + call check(100000000000000000000000001_k, "100000000000000000000000001") + call check(999999999999999999999999999_k, "999999999999999999999999999") + call check(1000000000000000000000000000_k, "1000000000000000000000000000") + call check(1000000000000000000000000001_k, "1000000000000000000000000001") + call check(9999999999999999999999999999_k, "9999999999999999999999999999") + call check(10000000000000000000000000000_k, "10000000000000000000000000000") + call check(10000000000000000000000000001_k, "10000000000000000000000000001") + call check(99999999999999999999999999999_k, "99999999999999999999999999999") + call check(100000000000000000000000000000_k, "100000000000000000000000000000") + call check(100000000000000000000000000001_k, "100000000000000000000000000001") + call check(999999999999999999999999999999_k, "999999999999999999999999999999") + call check(1000000000000000000000000000000_k, "1000000000000000000000000000000") + call check(1000000000000000000000000000001_k, "1000000000000000000000000000001") + call check(9999999999999999999999999999999_k, "9999999999999999999999999999999") + call check(10000000000000000000000000000000_k, "10000000000000000000000000000000") + call check(10000000000000000000000000000001_k, "10000000000000000000000000000001") + call check(99999999999999999999999999999999_k, "99999999999999999999999999999999") + call check(100000000000000000000000000000000_k, "100000000000000000000000000000000") + call check(100000000000000000000000000000001_k, "100000000000000000000000000000001") + call check(999999999999999999999999999999999_k, "999999999999999999999999999999999") + call check(1000000000000000000000000000000000_k, "1000000000000000000000000000000000") + call check(1000000000000000000000000000000001_k, "1000000000000000000000000000000001") + call check(9999999999999999999999999999999999_k, "9999999999999999999999999999999999") + call check(10000000000000000000000000000000000_k, "10000000000000000000000000000000000") + call check(10000000000000000000000000000000001_k, "10000000000000000000000000000000001") + call check(99999999999999999999999999999999999_k, "99999999999999999999999999999999999") + call check(100000000000000000000000000000000000_k, "100000000000000000000000000000000000") + call check(100000000000000000000000000000000001_k, "100000000000000000000000000000000001") + call check(999999999999999999999999999999999999_k, "999999999999999999999999999999999999") + call check(1000000000000000000000000000000000000_k, "1000000000000000000000000000000000000") + call check(1000000000000000000000000000000000001_k, "1000000000000000000000000000000000001") + call check(9999999999999999999999999999999999999_k, "9999999999999999999999999999999999999") + call check(10000000000000000000000000000000000000_k, "10000000000000000000000000000000000000") + call check(10000000000000000000000000000000000001_k, "10000000000000000000000000000000000001") + call check(99999999999999999999999999999999999999_k, "99999999999999999999999999999999999999") + call check(100000000000000000000000000000000000000_k, "100000000000000000000000000000000000000") + call check(100000000000000000000000000000000000001_k, "100000000000000000000000000000000000001") + call check(109999999999999999999999999999999999999_k, "109999999999999999999999999999999999999") + + call check(-1_k, "-1") + call check(-9_k, "-9") + call check(-10_k, "-10") + call check(-11_k, "-11") + call check(-99_k, "-99") + call check(-100_k, "-100") + call check(-101_k, "-101") + call check(-999_k, "-999") + call check(-1000_k, "-1000") + call check(-1001_k, "-1001") + call check(-9999_k, "-9999") + call check(-10000_k, "-10000") + call check(-10001_k, "-10001") + call check(-99999_k, "-99999") + call check(-100000_k, "-100000") + call check(-100001_k, "-100001") + call check(-999999_k, "-999999") + call check(-1000000_k, "-1000000") + call check(-1000001_k, "-1000001") + call check(-9999999_k, "-9999999") + call check(-10000000_k, "-10000000") + call check(-10000001_k, "-10000001") + call check(-99999999_k, "-99999999") + call check(-100000000_k, "-100000000") + call check(-100000001_k, "-100000001") + call check(-999999999_k, "-999999999") + call check(-1000000000_k, "-1000000000") + call check(-1000000001_k, "-1000000001") + call check(-9999999999_k, "-9999999999") + call check(-10000000000_k, "-10000000000") + call check(-10000000001_k, "-10000000001") + call check(-99999999999_k, "-99999999999") + call check(-100000000000_k, "-100000000000") + call check(-100000000001_k, "-100000000001") + call check(-999999999999_k, "-999999999999") + call check(-1000000000000_k, "-1000000000000") + call check(-1000000000001_k, "-1000000000001") + call check(-9999999999999_k, "-9999999999999") + call check(-10000000000000_k, "-10000000000000") + call check(-10000000000001_k, "-10000000000001") + call check(-99999999999999_k, "-99999999999999") + call check(-100000000000000_k, "-100000000000000") + call check(-100000000000001_k, "-100000000000001") + call check(-999999999999999_k, "-999999999999999") + call check(-1000000000000000_k, "-1000000000000000") + call check(-1000000000000001_k, "-1000000000000001") + call check(-9999999999999999_k, "-9999999999999999") + call check(-10000000000000000_k, "-10000000000000000") + call check(-10000000000000001_k, "-10000000000000001") + call check(-99999999999999999_k, "-99999999999999999") + call check(-100000000000000000_k, "-100000000000000000") + call check(-100000000000000001_k, "-100000000000000001") + call check(-999999999999999999_k, "-999999999999999999") + call check(-1000000000000000000_k, "-1000000000000000000") + call check(-1000000000000000001_k, "-1000000000000000001") + call check(-9999999999999999999_k, "-9999999999999999999") + call check(-10000000000000000000_k, "-10000000000000000000") + call check(-10000000000000000001_k, "-10000000000000000001") + call check(-99999999999999999999_k, "-99999999999999999999") + call check(-100000000000000000000_k, "-100000000000000000000") + call check(-100000000000000000001_k, "-100000000000000000001") + call check(-999999999999999999999_k, "-999999999999999999999") + call check(-1000000000000000000000_k, "-1000000000000000000000") + call check(-1000000000000000000001_k, "-1000000000000000000001") + call check(-9999999999999999999999_k, "-9999999999999999999999") + call check(-10000000000000000000000_k, "-10000000000000000000000") + call check(-10000000000000000000001_k, "-10000000000000000000001") + call check(-99999999999999999999999_k, "-99999999999999999999999") + call check(-100000000000000000000000_k, "-100000000000000000000000") + call check(-100000000000000000000001_k, "-100000000000000000000001") + call check(-999999999999999999999999_k, "-999999999999999999999999") + call check(-1000000000000000000000000_k, "-1000000000000000000000000") + call check(-1000000000000000000000001_k, "-1000000000000000000000001") + call check(-9999999999999999999999999_k, "-9999999999999999999999999") + call check(-10000000000000000000000000_k, "-10000000000000000000000000") + call check(-10000000000000000000000001_k, "-10000000000000000000000001") + call check(-99999999999999999999999999_k, "-99999999999999999999999999") + call check(-100000000000000000000000000_k, "-100000000000000000000000000") + call check(-100000000000000000000000001_k, "-100000000000000000000000001") + call check(-999999999999999999999999999_k, "-999999999999999999999999999") + call check(-1000000000000000000000000000_k, "-1000000000000000000000000000") + call check(-1000000000000000000000000001_k, "-1000000000000000000000000001") + call check(-9999999999999999999999999999_k, "-9999999999999999999999999999") + call check(-10000000000000000000000000000_k, "-10000000000000000000000000000") + call check(-10000000000000000000000000001_k, "-10000000000000000000000000001") + call check(-99999999999999999999999999999_k, "-99999999999999999999999999999") + call check(-100000000000000000000000000000_k, "-100000000000000000000000000000") + call check(-100000000000000000000000000001_k, "-100000000000000000000000000001") + call check(-999999999999999999999999999999_k, "-999999999999999999999999999999") + call check(-1000000000000000000000000000000_k, "-1000000000000000000000000000000") + call check(-1000000000000000000000000000001_k, "-1000000000000000000000000000001") + call check(-9999999999999999999999999999999_k, "-9999999999999999999999999999999") + call check(-10000000000000000000000000000000_k, "-10000000000000000000000000000000") + call check(-10000000000000000000000000000001_k, "-10000000000000000000000000000001") + call check(-99999999999999999999999999999999_k, "-99999999999999999999999999999999") + call check(-100000000000000000000000000000000_k, "-100000000000000000000000000000000") + call check(-100000000000000000000000000000001_k, "-100000000000000000000000000000001") + call check(-999999999999999999999999999999999_k, "-999999999999999999999999999999999") + call check(-1000000000000000000000000000000000_k, "-1000000000000000000000000000000000") + call check(-1000000000000000000000000000000001_k, "-1000000000000000000000000000000001") + call check(-9999999999999999999999999999999999_k, "-9999999999999999999999999999999999") + call check(-10000000000000000000000000000000000_k, "-10000000000000000000000000000000000") + call check(-10000000000000000000000000000000001_k, "-10000000000000000000000000000000001") + call check(-99999999999999999999999999999999999_k, "-99999999999999999999999999999999999") + call check(-100000000000000000000000000000000000_k, "-100000000000000000000000000000000000") + call check(-100000000000000000000000000000000001_k, "-100000000000000000000000000000000001") + call check(-999999999999999999999999999999999999_k, "-999999999999999999999999999999999999") + call check(-1000000000000000000000000000000000000_k, "-1000000000000000000000000000000000000") + call check(-1000000000000000000000000000000000001_k, "-1000000000000000000000000000000000001") + call check(-9999999999999999999999999999999999999_k, "-9999999999999999999999999999999999999") + call check(-10000000000000000000000000000000000000_k, "-10000000000000000000000000000000000000") + call check(-10000000000000000000000000000000000001_k, "-10000000000000000000000000000000000001") + call check(-99999999999999999999999999999999999999_k, "-99999999999999999999999999999999999999") + call check(-100000000000000000000000000000000000000_k, "-100000000000000000000000000000000000000") + call check(-100000000000000000000000000000000000001_k, "-100000000000000000000000000000000000001") + call check(-109999999999999999999999999999999999999_k, "-109999999999999999999999999999999999999") + +contains + + subroutine check (i, str) + implicit none + integer(kind=k), intent(in), value :: i + character(len=*), intent(in) :: str + + character(len=100) :: buffer + write(buffer,*) i + if (adjustl(buffer) /= adjustl(str)) stop 1 + end subroutine + + subroutine random_digits (str) + implicit none + integer, parameter :: l = 38 + character(len=l+1) :: str + real :: r + integer :: i, d + + str = "" + do i = 2, l+1 + call random_number(r) + d = floor(r * 10) + str(i:i) = achar(48 + d) + end do + + call random_number(r) + if (r > 0.5) then + str(1:1) = '-' + end if + end subroutine +end diff --git a/libgfortran/runtime/string.c b/libgfortran/runtime/string.c index 835027a..0ccd731 100644 --- a/libgfortran/runtime/string.c +++ b/libgfortran/runtime/string.c @@ -23,6 +23,7 @@ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see . */ #include "libgfortran.h" +#include #include #include @@ -169,6 +170,38 @@ find_option (st_parameter_common *cmp, const char *s1, gfc_charlen_type s1_len, } +/* Fast helper function for a positive value that fits in uint64_t. */ + +static inline char * +itoa64 (uint64_t n, char *p) +{ + while (n != 0) + { + *--p = '0' + (n % 10); + n /= 10; + } + return p; +} + + +#if defined(HAVE_GFC_INTEGER_16) +# define TEN19 ((GFC_UINTEGER_LARGEST) 1000000 * (GFC_UINTEGER_LARGEST) 1000000 * (GFC_UINTEGER_LARGEST) 10000000) + +/* Same as itoa64(), with zero padding of 19 digits. */ + +static inline char * +itoa64_pad19 (uint64_t n, char *p) +{ + for (int k = 0; k < 19; k++) + { + *--p = '0' + (n % 10); + n /= 10; + } + return p; +} +#endif + + /* Integer to decimal conversion. This function is much more restricted than the widespread (but @@ -195,11 +228,33 @@ gfc_itoa (GFC_UINTEGER_LARGEST n, char *buffer, size_t len) p = buffer + GFC_ITOA_BUF_SIZE - 1; *p = '\0'; - while (n != 0) +#if defined(HAVE_GFC_INTEGER_16) + /* On targets that have a 128-bit integer type, division in that type + is slow, because it occurs through a function call. We avoid that. */ + + if (n <= UINT64_MAX) + /* If the value fits in uint64_t, use the fast function. */ + return itoa64 (n, p); + else { - *--p = '0' + (n % 10); - n /= 10; + /* Otherwise, break down into smaller bits by division. Two calls to + the uint64_t function are not sufficient for all 128-bit unsigned + integers (we would need three calls), but they do suffice for all + values up to 2^127, which is the largest that Fortran can produce + (-HUGE(0_16)-1) with its signed integer types. */ + static_assert(sizeof(GFC_UINTEGER_LARGEST) <= 2 * sizeof(uint64_t)); + + GFC_UINTEGER_LARGEST r; + r = n % TEN19; + n = n / TEN19; + assert (r <= UINT64_MAX); + p = itoa64_pad19 (r, p); + + assert(n <= UINT64_MAX); + return itoa64 (n, p); } - - return p; +#else + /* On targets where the largest integer is 64-bit, just use that. */ + return itoa64 (n, p); +#endif } -- 2.7.4