[Bug libfortran/98076] New: Increase speed of integer I/O

[Bug libfortran/98076] New: Increase speed of integer I/O

[tkoenig at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

            Bug ID: 98076
           Summary: Increase speed of integer I/O
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libfortran
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

Currently, we use GFC_INTEGER_LARGEST for a lot of integer I/O.

One place where things could be improved is gfc_itoa:

const char *
gfc_itoa (GFC_INTEGER_LARGEST n, char *buffer, size_t len)
{
...
  GFC_UINTEGER_LARGEST t;
...
  t = n;
  if (n < 0)
    {
      negative = 1;
      t = -n; /*must use unsigned to protect from overflow*/
    }
...

  while (t != 0)
    {
      *--p = '0' + (t % 10);
      t /= 10;
    }

Currently, the quotient / remainder calculation is expanded into
a libcall.  This could be done by the improved remainder calculation
from PR97459 with the calculation of the quotient by multiplicative
inverse, and by switching to a smaller datatype once the value fits in
there.  Both can and should be combined, of course.

[Bug libfortran/98076] Increase speed of integer I/O

[tkoenig at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |11.0
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |tkoenig at gcc dot gnu.org
           Severity|normal                      |enhancement
   Target Milestone|---                         |11.0
   Last reconfirmed|                            |2020-12-01
             Status|UNCONFIRMED                 |ASSIGNED
           Keywords|                            |missed-optimization

[Bug libfortran/98076] Increase speed of integer I/O

[tkoenig at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|tkoenig at gcc dot gnu.org         |unassigned at gcc dot gnu.org
             Status|ASSIGNED                    |NEW

[Bug libfortran/98076] Increase speed of integer I/O

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.0                        |11.2

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.1 has been released, retargeting bugs to GCC 11.2.

[Bug libfortran/98076] Increase speed of integer I/O

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.2                        |11.3

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.2 is being released, retargeting bugs to GCC 11.3

[Bug libfortran/98076] Increase speed of integer I/O

[anlauf at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

anlauf at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.3                        |---

--- Comment #3 from anlauf at gcc dot gnu.org ---
Not a regression, so removing target milestone.

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fxcoudert at gcc dot gnu.org

--- Comment #4 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Benchmarking of the formatting of 100 million times a value of the order of
medium-sized number (INT_MAX/2) by gfc_itoa. On the 64-bit target I have at
hand (aarch64-apple-darwin), depending on whether the function is implemented
as:

__int128 : 3.91 seconds
int64_t  : 0.86 seconds
int32_t  : 0.84 seconds

__int128 relies on a function call of the division (___divti3), others don't.
This would allow for a very simple optimisation, that does not require to
change the current I/O workflow, i.e., passing all integer values as the
largest type (usually int128_t):

- have a fast itoa64() function that takes an uint64_t arg
- have gfc_itoa() call itoa64() if the argument fits
- otherwise, divide by a large power of ten, and recursively apply itoa64()

For small values, itoa64() will be called once per gfc_itoa() call. Worst case
behaviour (very large 128-bit values) is 2 division calls to itoa64(), which is
still faster than doing the 38 128-bit divisions in the current version.

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #5 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Consider this:

/* Fast helper function for a positive value that fits in uint64_t.  */
char *itoa64 (uint64_t n, char *p)
{
  while (n != 0)
    {
      *--p = '0' + (n % 10);
      n /= 10;
    }
  return p;
}


Then the logic inside gfc_itoa is reworked like this:

%%%%%%%%%%

  *p = '\0';

#if 1
  i (t <= UINT64_MAX) {
    p = toa64(t, p);
  } else {
    unsigned __int128 r;

#define TEN19 ((unsigned __int128) 1000000 * (unsigned __int128) 1000000 *
(unsigned __int128) 10000000)

    r = t % TEN19;
    t = t / TEN19;
    p = itoa64(r, p);

    assert(t <= UINT64_MAX);
    p = itoa64(t, p);
  }
#else
  while (t != 0)
    {
      *--p = '0' + (t % 10);
      t /= 10;
    }
#endif

  if (negative)
    *--p = '-';

  return p;

%%%%%%%%%%

where the "#if 1" branch is the new code, and the "#else" branch is the old
code. Unless I'm mistaken, two calls to itoa64() are sufficient to guarantee
that we can output all values up to INT128_MAX = 2^127 - 1. That's because
(2^127 - 1) / 10^19 is smaller than UINT64_MAX = 2^64 - 1.

We would need three calls if we wanted to output values up to UINT128_MAX =
2^128 - 1, but we don't: Fortran only deals with signed integers.



Benchmark of this code, for formatting of 10 millions numbers into a buffer:

- formatting 1042:       old code 0.31 seconds, new code 0.06 seconds
- formatting INT32_MAX:  old code 0.88 seconds, new code 0.07 seconds
- formatting INT64_MAX:  old code 1.77 seconds, new code 0.16 seconds
- formatting INT128_MAX: old code 3.74 seconds, new code 0.49 seconds


It remains to be seen how much of the actual Fortran I/O is bound by
gfc_itoa(). But the benchmarking is interesting enough that it ought to be
tried in a real example inside libgfortran, which is what I will do next.

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #6 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Integrating this quick patch into libgfortran, here are the timings to make a
formatted write of 10 million integers into a string.

- very small value (1), negligible speedup (2.273s to 2.248s)
- small value (1042), speedup of 28% (3.224s to 2.350s)
- huge(0_8), speed up of 50% (5.914s to 2.560s)
- huge(0_16), speed up of 83% (19.46s to 3.31s)

Conclusion: this looks quite interesting!


diff --git a/libgfortran/runtime/string.c b/libgfortran/runtime/string.c
index 536a9cd3f2b..844ff6e65ce 100644
--- a/libgfortran/runtime/string.c
+++ b/libgfortran/runtime/string.c
@@ -25,6 +25,7 @@ see the files COPYING3 and COPYING.RUNTIME respectively.  If
not, see
 #include "libgfortran.h"
 #include <string.h>
 #include <strings.h>
+#include <assert.h>


 /* Given a fortran string, return its length exclusive of the trailing
@@ -169,6 +170,19 @@ 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 char *
+itoa64 (uint64_t n, char *p)
+{
+  while (n != 0)
+    {
+      *--p = '0' + (n % 10);
+      n /= 10;
+    }
+  return p;
+}
+
+
 /* gfc_itoa()-- Integer to decimal conversion.
    The itoa function is a widespread non-standard extension to
    standard C, often declared in <stdlib.h>.  Even though the itoa
@@ -202,11 +216,24 @@ gfc_itoa (GFC_INTEGER_LARGEST n, char *buffer, size_t
len)
   p = buffer + GFC_ITOA_BUF_SIZE - 1;
   *p = '\0';

-  while (t != 0)
-    {
-      *--p = '0' + (t % 10);
-      t /= 10;
-    }
+  if (t <= UINT64_MAX) {
+    /* If the value fits in uint64_t, use the fast function. */
+    p = itoa64(t, p);
+  } else {
+    /* Otherwise, break down into smaller bits by division. Two calls to the
+       uint64_t function are sufficient for all 128-bit signed integer
+       values, up to 2^127 - 1. */
+#define TEN19 ((GFC_UINTEGER_LARGEST) 1000000 * (GFC_UINTEGER_LARGEST) 1000000
* (GFC_UINTEGER_LARGEST) 10000000)
+    static_assert(sizeof(GFC_UINTEGER_LARGEST) <= 2 * sizeof(uint64_t));
+
+    GFC_UINTEGER_LARGEST r;
+    r = t % TEN19;
+    t = t / TEN19;
+    p = itoa64(r, p);
+
+    assert(t <= UINT64_MAX);
+    p = itoa64(t, p);
+  }

   if (negative)
     *--p = '-';

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #7 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Created attachment 52023
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52023&action=edit
First patch to speed up gfc_itoa()

There was a bug in the previous patch (when we write out the low decimal part
of a big number, we need to zero-pad). Here is a full patch that bootstraps and
regtests, as well as a new test for big integer I/O.

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #8 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Patch posted at https://gcc.gnu.org/pipermail/fortran/2021-December/057219.html

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #9 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
After my patch, measurements seem to indicate the output of integers is mostly
bound the library overhead. Inspection of the various itoa/btoa/otoa/xtoa
functions seems to show they're reasonably efficient.

Reading of integers is still quite inefficient. The function read_decimal()
always works with the largest integer kind, performing additions and
multiplications by 10. This is, I think, available in hardware (not library
call).

read_radix() is probably also quite inefficient. It is written in a completely
generic fashion, although it operates on fixed radices (2, 8 or 16); such
multiplications could be done by bit shift. Even if we told the compilers that
the radix was 2, 8 or 16 in each case (three functions), it would optimise the
multiplications into bit shifts itself.

[Bug libfortran/98076] Increase speed of integer I/O

[ro at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

Rainer Orth <ro at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ro at gcc dot gnu.org

--- Comment #10 from Rainer Orth <ro at gcc dot gnu.org> ---
This patch broke (at least) Solaris bootstrap:

/vol/gcc/src/hg/master/local/libgfortran/runtime/string.c: In function
'gfc_itoa':
/vol/gcc/src/hg/master/local/libgfortran/runtime/string.c:245:73: error: macro
"static_assert" requires 2 arguments, but only 1 given
  245 |       static_assert(sizeof(GFC_UINTEGER_LARGEST) <= 2 *
sizeof(uint64_t));
      |                                                                        
^
In file included from
/vol/gcc/src/hg/master/local/libgfortran/runtime/string.c:26:
/usr/include/assert.h:25: note: macro "static_assert" defined here
   25 | #define static_assert(a, b) _Static_assert(a, b)
      |
/vol/gcc/src/hg/master/local/libgfortran/runtime/string.c:245:7: error:
'static_assert' undeclared (first use in this function)
  245 |       static_assert(sizeof(GFC_UINTEGER_LARGEST) <= 2 *
sizeof(uint64_t));
      |       ^~~~~~~~~~~~~
/vol/gcc/src/hg/master/local/libgfortran/runtime/string.c:245:7: note: each
undeclared identifier is reported only once for each function it appears in
make[6]: *** [Makefile:2765: string.lo] Error 1

According to https://en.cppreference.com/w/c/language/_Static_assert, the
one-arg
form of _Static_assert/static_assert is new since C23, while Solaris <assert.h>
only supports the two-arg form.

[Bug libfortran/98076] Increase speed of integer I/O

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #11 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Hi Rainer,

Apologies for that, apparently I got confused between the keyword and the macro
form. Can you confirm that bootstrapped is fixed if you change it to

     static_assert(sizeof(GFC_UINTEGER_LARGEST) <= 2 * sizeof(uint64_t),
                   "integer too large");

? If so, I will commit the patch to fix it immediately.

[Bug libfortran/98076] Increase speed of integer I/O

[ro at CeBiTec dot Uni-Bielefeld.DE]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98076

--- Comment #12 from ro at CeBiTec dot Uni-Bielefeld.DE <ro at CeBiTec dot Uni-Bielefeld.DE> ---
> --- Comment #11 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
> Hi Rainer,
>
> Apologies for that, apparently I got confused between the keyword and the macro
> form. Can you confirm that bootstrapped is fixed if you change it to
>
>      static_assert(sizeof(GFC_UINTEGER_LARGEST) <= 2 * sizeof(uint64_t),
>                    "integer too large");
>
> ? If so, I will commit the patch to fix it immediately.

I've had an equivalent patch in my tree which just completed the build
successfully and is into make check.  So I'd say the patch is good to
go.

Thanks.
        Rainer