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

["fxcoudert at gcc dot gnu.org" <gcc-bugzilla@gcc.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 = '-';