[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
master d35d5c7 1/3: Improve doprnt performance
|
From: |
Paul Eggert |
|
Subject: |
master d35d5c7 1/3: Improve doprnt performance |
|
Date: |
Sat, 24 Oct 2020 17:00:19 -0400 (EDT) |
branch: master
commit d35d5c7ecde9b5003c3b21f773570800542664fa
Author: Paul Eggert <eggert@cs.ucla.edu>
Commit: Paul Eggert <eggert@cs.ucla.edu>
Improve doprnt performance
This patch implements some of my suggestions in Bug#8545,
with further changes suggested by Eli Zaretskii (Bug#43439).
* src/doprnt.c: Improve comments.
(SIZE_BOUND_EXTRA): Now at top level, for parse_format_integer.
(parse_format_integer): New static function, containing some of
the old doprnt. Fix a bug that caused doprnt to infloop on
formats like "%10s" that Emacs does not use. We could simplify
doprnt further if we dropped support for these never-used formats.
(doprnt_nul): New function.
(doprnt): Use it. Change doprnt API to exit when either it finds NUL
or reaches the character specified by FORMAT_END. In the typical case
where FORMAT_END is null, take just one pass over FORMAT, not two.
Assume C99 to make code clearer. Do not use malloc or alloca to
allocate a copy of the format FMTCPY; instead, use a small fixed-size
array FMTSTAR, and use '*' in that array to represent width and
precision, passing them as separate int arguments. Use eassume to
pacify GCC in switch statements.
---
src/doprnt.c | 230 ++++++++++++++++++++++++++++++++++-------------------------
1 file changed, 132 insertions(+), 98 deletions(-)
diff --git a/src/doprnt.c b/src/doprnt.c
index ceadf3b..07c4d8d 100644
--- a/src/doprnt.c
+++ b/src/doprnt.c
@@ -28,6 +28,7 @@ along with GNU Emacs. If not, see
<https://www.gnu.org/licenses/>. */
. For %s and %c, when field width is specified (e.g., %25s), it accounts for
the display width of each character, according to char-width-table. That
is, it does not assume that each character takes one column on display.
+ Nor does it assume that each character is a single byte.
. If the size of the buffer is not enough to produce the formatted string in
its entirety, it makes sure that truncation does not chop the last
@@ -42,12 +43,14 @@ along with GNU Emacs. If not, see
<https://www.gnu.org/licenses/>. */
Emacs can handle.
OTOH, this function supports only a small subset of the standard C formatted
- output facilities. E.g., %u and %ll are not supported, and precision is
- ignored %s and %c conversions. (See below for the detailed documentation of
- what is supported.) However, this is okay, as this function is supposed to
- be called from `error' and similar functions, and thus does not need to
- support features beyond those in `Fformat_message', which is used
- by `error' on the Lisp level. */
+ output facilities. E.g., %u is not supported, precision is ignored
+ in %s and %c conversions, and %lld does not necessarily work and
+ code should use something like %"pM"d with intmax_t instead.
+ (See below for the detailed documentation of what is supported.)
+ However, this is okay, as this function is supposed to be called
+ from 'error' and similar C functions, and thus does not need to
+ support all the features of 'Fformat_message', which is used by the
+ Lisp 'error' function. */
/* In the FORMAT argument this function supports ` and ' as directives
that output left and right quotes as per ‘text-quoting style’. It
@@ -61,19 +64,21 @@ along with GNU Emacs. If not, see
<https://www.gnu.org/licenses/>. */
%e means print a `double' argument in exponential notation.
%f means print a `double' argument in decimal-point notation.
%g means print a `double' argument in exponential notation
- or in decimal-point notation, whichever uses fewer characters.
+ or in decimal-point notation, depending on the value;
+ this is often (though not always) the shorter of the two notations.
%c means print a `signed int' argument as a single character.
%% means produce a literal % character.
- A %-sequence may contain optional flag, width, and precision specifiers, and
- a length modifier, as follows:
+ A %-sequence other than %% may contain optional flags, width, precision,
+ and length, as follows:
%<flags><width><precision><length>character
where flags is [+ -0], width is [0-9]+, precision is .[0-9]+, and length
is empty or l or the value of the pD or pI or PRIdMAX (sans "d") macros.
- Also, %% in a format stands for a single % in the output. A % that
- does not introduce a valid %-sequence causes undefined behavior.
+ A % that does not introduce a valid %-sequence causes undefined behavior.
+ ASCII bytes in FORMAT other than % are copied through as-is;
+ non-ASCII bytes should not appear in FORMAT.
The + flag character inserts a + before any positive number, while a space
inserts a space before any positive number; these flags only affect %d, %o,
@@ -99,7 +104,9 @@ along with GNU Emacs. If not, see
<https://www.gnu.org/licenses/>. */
For %e, %f, and %g sequences, the number after the "." in the precision
specifier says how many decimal places to show; if zero, the decimal point
- itself is omitted. For %s and %S, the precision specifier is ignored. */
+ itself is omitted. For %d, %o, and %x sequences, the precision specifies
+ the minimum number of digits to appear. Precision specifiers are
+ not supported for other %-sequences. */
#include <config.h>
#include <stdio.h>
@@ -115,7 +122,50 @@ along with GNU Emacs. If not, see
<https://www.gnu.org/licenses/>. */
another macro. */
#include "character.h"
+/* Enough to handle floating point formats with large numbers. */
+enum { SIZE_BOUND_EXTRA = DBL_MAX_10_EXP + 50 };
+
+/* Parse FMT as an unsigned decimal integer, putting its value into *VALUE.
+ Return the address of the first byte after the integer.
+ If FMT is not an integer, return FMT and store zero into *VALUE. */
+static char const *
+parse_format_integer (char const *fmt, int *value)
+{
+ int n = 0;
+ bool overflow = false;
+ for (; '0' <= *fmt && *fmt <= '9'; fmt++)
+ {
+ overflow |= INT_MULTIPLY_WRAPV (n, 10, &n);
+ overflow |= INT_ADD_WRAPV (n, *fmt - '0', &n);
+ }
+ if (overflow || min (PTRDIFF_MAX, SIZE_MAX) - SIZE_BOUND_EXTRA < n)
+ error ("Format width or precision too large");
+ *value = n;
+ return fmt;
+}
+
+/* Like doprnt, except FORMAT must not contain NUL bytes and
+ FORMAT_END must be non-null. Although this function is never
+ exercised in current Emacs, it is retained in case some future
+ Emacs version contains doprnt callers that need such formats.
+ Having a separate function helps GCC optimize doprnt better. */
+static ptrdiff_t
+doprnt_nul (char *buffer, ptrdiff_t bufsize, char const *format,
+ char const *format_end, va_list ap)
+{
+ USE_SAFE_ALLOCA;
+ ptrdiff_t fmtlen = format_end - format;
+ char *fmt = SAFE_ALLOCA (fmtlen + 1);
+ memcpy (fmt, format, fmtlen);
+ fmt[fmtlen] = 0;
+ ptrdiff_t nbytes = doprnt (buffer, bufsize, fmt, NULL, ap);
+ SAFE_FREE ();
+ return nbytes;
+}
+
/* Generate output from a format-spec FORMAT,
+ terminated at either the first NUL or (if FORMAT_END is non-null
+ and there are no NUL bytes between FORMAT and FORMAT_END)
terminated at position FORMAT_END.
(*FORMAT_END is not part of the format, but must exist and be readable.)
Output goes in BUFFER, which has room for BUFSIZE chars.
@@ -131,12 +181,12 @@ ptrdiff_t
doprnt (char *buffer, ptrdiff_t bufsize, const char *format,
const char *format_end, va_list ap)
{
+ if (format_end && !memchr (format, 0, format_end - format))
+ return doprnt_nul (buffer, bufsize, format, format_end, ap);
+
const char *fmt = format; /* Pointer into format string. */
char *bufptr = buffer; /* Pointer into output buffer. */
- /* Enough to handle floating point formats with large numbers. */
- enum { SIZE_BOUND_EXTRA = DBL_MAX_10_EXP + 50 };
-
/* Use this for sprintf unless we need something really big. */
char tembuf[SIZE_BOUND_EXTRA + 50];
@@ -150,103 +200,91 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
char *big_buffer = NULL;
enum text_quoting_style quoting_style = text_quoting_style ();
- ptrdiff_t tem = -1;
- char *string;
- char fixed_buffer[20]; /* Default buffer for small formatting. */
- char *fmtcpy;
- int minlen;
- char charbuf[MAX_MULTIBYTE_LENGTH + 1]; /* Used for %c. */
- USE_SAFE_ALLOCA;
-
- if (format_end == 0)
- format_end = format + strlen (format);
-
- fmtcpy = (format_end - format < sizeof (fixed_buffer) - 1
- ? fixed_buffer
- : SAFE_ALLOCA (format_end - format + 1));
bufsize--;
/* Loop until end of format string or buffer full. */
- while (fmt < format_end && bufsize > 0)
+ while (*fmt && bufsize > 0)
{
char const *fmt0 = fmt;
char fmtchar = *fmt++;
if (fmtchar == '%')
{
- ptrdiff_t size_bound = 0;
ptrdiff_t width; /* Columns occupied by STRING on display. */
enum {
pDlen = sizeof pD - 1,
pIlen = sizeof pI - 1,
- pMlen = sizeof PRIdMAX - 2
+ pMlen = sizeof PRIdMAX - 2,
+ maxmlen = max (max (1, pDlen), max (pIlen, pMlen))
};
enum {
no_modifier, long_modifier, pD_modifier, pI_modifier, pM_modifier
} length_modifier = no_modifier;
static char const modifier_len[] = { 0, 1, pDlen, pIlen, pMlen };
- int maxmlen = max (max (1, pDlen), max (pIlen, pMlen));
int mlen;
+ char charbuf[MAX_MULTIBYTE_LENGTH + 1]; /* Used for %c. */
- /* Copy this one %-spec into fmtcpy. */
- string = fmtcpy;
+ /* Width and precision specified by this %-sequence. */
+ int wid = 0, prec = -1;
+
+ /* FMTSTAR will be a "%*.*X"-like version of this %-sequence.
+ Start by putting '%' into FMTSTAR. */
+ char fmtstar[sizeof "%-+ 0*.*d" + maxmlen];
+ char *string = fmtstar;
*string++ = '%';
- while (fmt < format_end)
+
+ /* Copy at most one instance of each flag into FMTSTAR. */
+ bool minusflag = false, plusflag = false, zeroflag = false,
+ spaceflag = false;
+ for (;; fmt++)
{
- *string++ = *fmt;
- if ('0' <= *fmt && *fmt <= '9')
+ *string = *fmt;
+ switch (*fmt)
{
- /* Get an idea of how much space we might need.
- This might be a field width or a precision; e.g.
- %1.1000f and %1000.1f both might need 1000+ bytes.
- Parse the width or precision, checking for overflow. */
- int n = *fmt - '0';
- bool overflow = false;
- while (fmt + 1 < format_end
- && '0' <= fmt[1] && fmt[1] <= '9')
- {
- overflow |= INT_MULTIPLY_WRAPV (n, 10, &n);
- overflow |= INT_ADD_WRAPV (n, fmt[1] - '0', &n);
- *string++ = *++fmt;
- }
-
- if (overflow
- || min (PTRDIFF_MAX, SIZE_MAX) - SIZE_BOUND_EXTRA < n)
- error ("Format width or precision too large");
- if (size_bound < n)
- size_bound = n;
+ case '-': string += !minusflag; minusflag = true; continue;
+ case '+': string += !plusflag; plusflag = true; continue;
+ case ' ': string += !spaceflag; spaceflag = true; continue;
+ case '0': string += !zeroflag; zeroflag = true; continue;
}
- else if (! (*fmt == '-' || *fmt == ' ' || *fmt == '.'
- || *fmt == '+'))
- break;
- fmt++;
+ break;
}
+ /* Parse width and precision, putting "*.*" into FMTSTAR. */
+ if ('1' <= *fmt && *fmt <= '9')
+ fmt = parse_format_integer (fmt, &wid);
+ if (*fmt == '.')
+ fmt = parse_format_integer (fmt + 1, &prec);
+ *string++ = '*';
+ *string++ = '.';
+ *string++ = '*';
+
/* Check for the length modifiers in textual length order, so
that longer modifiers override shorter ones. */
for (mlen = 1; mlen <= maxmlen; mlen++)
{
- if (format_end - fmt < mlen)
- break;
if (mlen == 1 && *fmt == 'l')
length_modifier = long_modifier;
- if (mlen == pDlen && memcmp (fmt, pD, pDlen) == 0)
+ if (mlen == pDlen && strncmp (fmt, pD, pDlen) == 0)
length_modifier = pD_modifier;
- if (mlen == pIlen && memcmp (fmt, pI, pIlen) == 0)
+ if (mlen == pIlen && strncmp (fmt, pI, pIlen) == 0)
length_modifier = pI_modifier;
- if (mlen == pMlen && memcmp (fmt, PRIdMAX, pMlen) == 0)
+ if (mlen == pMlen && strncmp (fmt, PRIdMAX, pMlen) == 0)
length_modifier = pM_modifier;
}
+ /* Copy optional length modifier and conversion specifier
+ character into FMTSTAR, and append a NUL. */
mlen = modifier_len[length_modifier];
- memcpy (string, fmt + 1, mlen);
- string += mlen;
+ string = mempcpy (string, fmt, mlen + 1);
fmt += mlen;
*string = 0;
- /* Make the size bound large enough to handle floating point formats
+ /* An idea of how much space we might need.
+ This might be a field width or a precision; e.g.
+ %1.1000f and %1000.1f both might need 1000+ bytes.
+ Make it large enough to handle floating point formats
with large numbers. */
- size_bound += SIZE_BOUND_EXTRA;
+ ptrdiff_t size_bound = max (wid, prec) + SIZE_BOUND_EXTRA;
/* Make sure we have that much. */
if (size_bound > size_allocated)
@@ -257,48 +295,49 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
sprintf_buffer = big_buffer;
size_allocated = size_bound;
}
- minlen = 0;
+ int minlen = 0;
+ ptrdiff_t tem;
switch (*fmt++)
{
default:
- error ("Invalid format operation %s", fmtcpy);
+ error ("Invalid format operation %s", fmt0);
-/* case 'b': */
- case 'l':
case 'd':
switch (length_modifier)
{
case no_modifier:
{
int v = va_arg (ap, int);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case long_modifier:
{
long v = va_arg (ap, long);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case pD_modifier:
signed_pD_modifier:
{
ptrdiff_t v = va_arg (ap, ptrdiff_t);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case pI_modifier:
{
EMACS_INT v = va_arg (ap, EMACS_INT);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case pM_modifier:
{
intmax_t v = va_arg (ap, intmax_t);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
+ default:
+ eassume (false);
}
/* Now copy into final output, truncating as necessary. */
string = sprintf_buffer;
@@ -311,13 +350,13 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
case no_modifier:
{
unsigned v = va_arg (ap, unsigned);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case long_modifier:
{
unsigned long v = va_arg (ap, unsigned long);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case pD_modifier:
@@ -325,15 +364,17 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
case pI_modifier:
{
EMACS_UINT v = va_arg (ap, EMACS_UINT);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
case pM_modifier:
{
uintmax_t v = va_arg (ap, uintmax_t);
- tem = sprintf (sprintf_buffer, fmtcpy, v);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, v);
}
break;
+ default:
+ eassume (false);
}
/* Now copy into final output, truncating as necessary. */
string = sprintf_buffer;
@@ -344,18 +385,15 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
case 'g':
{
double d = va_arg (ap, double);
- tem = sprintf (sprintf_buffer, fmtcpy, d);
+ tem = sprintf (sprintf_buffer, fmtstar, wid, prec, d);
/* Now copy into final output, truncating as necessary. */
string = sprintf_buffer;
goto doit;
}
case 'S':
- string[-1] = 's';
- FALLTHROUGH;
case 's':
- if (fmtcpy[1] != 's')
- minlen = atoi (&fmtcpy[1]);
+ minlen = minusflag ? -wid : wid;
string = va_arg (ap, char *);
tem = strnlen (string, STRING_BYTES_BOUND + 1);
if (tem == STRING_BYTES_BOUND + 1)
@@ -432,14 +470,12 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
string = charbuf;
string[tem] = 0;
width = strwidth (string, tem);
- if (fmtcpy[1] != 'c')
- minlen = atoi (&fmtcpy[1]);
+ minlen = minusflag ? -wid : wid;
goto doit1;
}
case '%':
/* Treat this '%' as normal. */
- fmt0 = fmt - 1;
break;
}
}
@@ -450,13 +486,13 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char
*format,
src = uLSQM, srclen = sizeof uLSQM - 1;
else if (quoting_style == CURVE_QUOTING_STYLE && fmtchar == '\'')
src = uRSQM, srclen = sizeof uRSQM - 1;
- else if (quoting_style == STRAIGHT_QUOTING_STYLE && fmtchar == '`')
- src = "'", srclen = 1;
else
{
- while (fmt < format_end && !CHAR_HEAD_P (*fmt))
- fmt++;
- src = fmt0, srclen = fmt - fmt0;
+ if (quoting_style == STRAIGHT_QUOTING_STYLE && fmtchar == '`')
+ fmtchar = '\'';
+ eassert (ASCII_CHAR_P (fmtchar));
+ *bufptr++ = fmtchar;
+ continue;
}
if (bufsize < srclen)
@@ -479,8 +515,6 @@ doprnt (char *buffer, ptrdiff_t bufsize, const char *format,
xfree (big_buffer);
*bufptr = 0; /* Make sure our string ends with a '\0' */
-
- SAFE_FREE ();
return bufptr - buffer;
}