From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
 id 4BD7D3858D35; Thu, 16 Dec 2021 21:40:09 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4BD7D3858D35
From: "fxcoudert at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libfortran/98076] Increase speed of integer I/O
Date: Thu, 16 Dec 2021 21:40:09 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libfortran
X-Bugzilla-Version: 11.0
X-Bugzilla-Keywords: missed-optimization
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: fxcoudert at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: 
Message-ID: <bug-98076-4-wONeHDvwH7@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-98076-4@http.gcc.gnu.org/bugzilla/>
References: <bug-98076-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-BeenThere: gcc-bugs@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-bugs mailing list <gcc-bugs.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Dec 2021 21:40:09 -0000

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

--- 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 !=3D 0)
    {
      *--p =3D '0' + (n % 10);
      n /=3D 10;
    }
  return p;
}


Then the logic inside gfc_itoa is reworked like this:

%%%%%%%%%%

  *p =3D '\0';

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

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

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

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

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

  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 =3D 2^127 - 1. That's because
(2^127 - 1) / 10^19 is smaller than UINT64_MAX =3D 2^64 - 1.

We would need three calls if we wanted to output values up to UINT128_MAX =
=3D
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.=