This is the mail archive of the
libc-alpha@sources.redhat.com
mailing list for the glibc project.
reduce runtime divisions in strtol
- From: Richard Henderson <rth at redhat dot com>
- To: libc-alpha at sources dot redhat dot com
- Date: Wed, 24 Mar 2004 18:12:16 -0800
- Subject: reduce runtime divisions in strtol
I happened to notice this curious spike in (1) divisions of -1,
and (2) divisions by 10. During the course of gcc compiling
one file, this happens 44784 times.
As it happens, large(st) number divided by small number has
worst-case runtime characteristics, so it'd be really nice to
avoid...
r~
2004-03-24 Richard Henderson <rth@redhat.com>
* sysdeps/generic/strtol_l.c (__strtol_l): Use tables for lookup
of cutoff, cutlim, and jmax.
Index: sysdeps/generic/strtol_l.c
===================================================================
RCS file: /cvs/glibc/libc/sysdeps/generic/strtol_l.c,v
retrieving revision 1.5
diff -c -p -d -r1.5 strtol_l.c
*** sysdeps/generic/strtol_l.c 14 Mar 2004 20:54:42 -0000 1.5
--- sysdeps/generic/strtol_l.c 25 Mar 2004 02:01:09 -0000
*************** INTERNAL (__strtol_l) (nptr, endptr, bas
*** 325,340 ****
#endif
end = NULL;
! cutoff = STRTOL_ULONG_MAX / (unsigned LONG int) base;
! cutlim = STRTOL_ULONG_MAX % (unsigned LONG int) base;
overflow = 0;
i = 0;
c = *s;
if (sizeof (long int) != sizeof (LONG int))
{
unsigned long int j = 0;
! unsigned long int jmax = ULONG_MAX / base;
for (;c != L_('\0'); c = *++s)
{
--- 325,369 ----
#endif
end = NULL;
! /* Avoid runtime division; lookup cutoff and limit. */
! {
! #define F(x) STRTOL_ULONG_MAX / x
! static const unsigned LONG int cutoff_tab[] = {
! F(2), F(3), F(4), F(5), F(6), F(7), F(8), F(9), F(10),
! F(11), F(12), F(13), F(14), F(15), F(16), F(17), F(18), F(19), F(20),
! F(21), F(22), F(23), F(24), F(25), F(26), F(27), F(28), F(29), F(30),
! F(31), F(32), F(33), F(34), F(35), F(36)
! };
! #undef F
! #define F(x) STRTOL_ULONG_MAX % x
! static const unsigned char cutlim_tab[] = {
! F(2), F(3), F(4), F(5), F(6), F(7), F(8), F(9), F(10),
! F(11), F(12), F(13), F(14), F(15), F(16), F(17), F(18), F(19), F(20),
! F(21), F(22), F(23), F(24), F(25), F(26), F(27), F(28), F(29), F(30),
! F(31), F(32), F(33), F(34), F(35), F(36)
! };
! #undef F
!
! cutoff = cutoff_tab[base - 2];
! cutlim = cutlim_tab[base - 2];
! }
overflow = 0;
i = 0;
c = *s;
if (sizeof (long int) != sizeof (LONG int))
{
+ #define F(x) ULONG_MAX / x
+ static const unsigned long int jmax_tab[] = {
+ F(2), F(3), F(4), F(5), F(6), F(7), F(8), F(9), F(10),
+ F(11), F(12), F(13), F(14), F(15), F(16), F(17), F(18), F(19), F(20),
+ F(21), F(22), F(23), F(24), F(25), F(26), F(27), F(28), F(29), F(30),
+ F(31), F(32), F(33), F(34), F(35), F(36)
+ };
+ #undef F
+
unsigned long int j = 0;
! unsigned long int jmax = jmax_tab[base - 2];
for (;c != L_('\0'); c = *++s)
{