From 864c1f28794dae6e361bbff8efbd63a0245a90c2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= Date: Sat, 11 Oct 2014 10:06:48 +0100 Subject: [PATCH 1/4] seq: support inf last item more generally/efficiently * src/seq.c (main): Call seq_fast for infinite last value. This implicitly avoids format conversion on the 999999 -> 1000000 transition. * src/seq.c (seq_fast): Generalize the buffer handling, and adjust to handle the "inf" last value specifics. * tests/misc/seq-precision.sh: A new test. * tests/local.mk: Reference the new test. --- src/seq.c | 85 ++++++++++++++++++++++++++++++++------------- tests/local.mk | 1 + tests/misc/seq-precision.sh | 27 ++++++++++++++ 3 files changed, 88 insertions(+), 25 deletions(-) create mode 100755 tests/misc/seq-precision.sh diff --git a/src/seq.c b/src/seq.c index c8c0492..e8d4f18 100644 --- a/src/seq.c +++ b/src/seq.c @@ -411,52 +411,84 @@ trim_leading_zeros (char const *s) static bool seq_fast (char const *a, char const *b) { + bool inf = STREQ (b, "inf"); + /* Skip past any leading 0's. Without this, our naive cmp function would declare 000 to be larger than 99. */ a = trim_leading_zeros (a); b = trim_leading_zeros (b); size_t p_len = strlen (a); - size_t q_len = strlen (b); - size_t n = MAX (p_len, q_len); - char *p0 = xmalloc (n + 1); - char *p = memcpy (p0 + n - p_len, a, p_len + 1); - char *q0 = xmalloc (n + 1); - char *q = memcpy (q0 + n - q_len, b, q_len + 1); - - bool ok = cmp (p, p_len, q, q_len) <= 0; + size_t q_len = inf ? 0 : strlen (b); + + /* Allow for at least 31 digits without realloc. + 1 more than p_len is needed for the inf case. */ + size_t inc_size = MAX (MAX (p_len + 1, q_len), 31); + + /* Copy input strings (incl NUL) to end of new buffers. */ + char *p0 = xmalloc (inc_size + 1); + char *p = memcpy (p0 + inc_size - p_len, a, p_len + 1); + char *q; + char *q0; + if (! inf) + { + q0 = xmalloc (inc_size + 1); + q = memcpy (q0 + inc_size - q_len, b, q_len + 1); + } + else + q = q0 = NULL; + + bool ok = inf || cmp (p, p_len, q, q_len) <= 0; if (ok) { - /* Buffer at least this many numbers per fwrite call. - This gives a speed-up of more than 2x over the unbuffered code + /* Reduce number of fwrite calls which is seen to + give a speed-up of more than 2x over the unbuffered code when printing the first 10^9 integers. */ - enum {N = 40}; - char *buf = xmalloc (N * (n + 1)); - char const *buf_end = buf + N * (n + 1); + size_t buf_size = MAX (BUFSIZ, (inc_size + 1) * 2); + char *buf = xmalloc (buf_size); + char const *buf_end = buf + buf_size; - char *z = buf; + char *bufp = buf; /* Write first number to buffer. */ - z = mempcpy (z, p, p_len); + bufp = mempcpy (bufp, p, p_len); /* Append separator then number. */ - while (cmp (p, p_len, q, q_len) < 0) + while (inf || cmp (p, p_len, q, q_len) < 0) { - *z++ = *separator; + *bufp++ = *separator; incr (&p, &p_len); - z = mempcpy (z, p, p_len); + + /* Double up the buffers when needed for the inf case. */ + if (p_len == inc_size) + { + inc_size *= 2; + p0 = xrealloc (p0, inc_size + 1); + p = memmove (p0 + p_len, p0, p_len + 1); + + if (buf_size < (inc_size + 1) * 2) + { + size_t buf_offset = bufp - buf; + buf_size = (inc_size + 1) * 2; + buf = xrealloc (buf, buf_size); + buf_end = buf + buf_size; + bufp = buf + buf_offset; + } + } + + bufp = mempcpy (bufp, p, p_len); /* If no place for another separator + number then output buffer so far, and reset to start of buffer. */ - if (buf_end - (n + 1) < z) + if (buf_end - (p_len + 1) < bufp) { - fwrite (buf, z - buf, 1, stdout); - z = buf; + fwrite (buf, bufp - buf, 1, stdout); + bufp = buf; } } /* Write any remaining buffered output, and the terminator. */ - *z++ = *terminator; - fwrite (buf, z - buf, 1, stdout); + *bufp++ = *terminator; + fwrite (buf, bufp - buf, 1, stdout); IF_LINT (free (buf)); } @@ -593,7 +625,8 @@ main (int argc, char **argv) } } - if (first.precision == 0 && step.precision == 0 && last.precision == 0 + if (first.precision == 0 && step.precision == 0 + && (! isfinite (last.value) || last.precision == 0) && 0 <= first.value && step.value == 1 && 0 <= last.value && !equal_width && !format_str && strlen (separator) == 1) { @@ -601,7 +634,9 @@ main (int argc, char **argv) char *s2; if (asprintf (&s1, "%0.Lf", first.value) < 0) xalloc_die (); - if (asprintf (&s2, "%0.Lf", last.value) < 0) + if (! isfinite (last.value)) + s2 = xstrdup ("inf"); /* Ensure "inf" is used. */ + else if (asprintf (&s2, "%0.Lf", last.value) < 0) xalloc_die (); if (*s1 != '-' && *s2 != '-' && seq_fast (s1, s2)) diff --git a/tests/local.mk b/tests/local.mk index 7b8c91e..d60f6cf 100644 --- a/tests/local.mk +++ b/tests/local.mk @@ -236,6 +236,7 @@ all_tests = \ tests/misc/test.pl \ tests/misc/seq.pl \ tests/misc/seq-long-double.sh \ + tests/misc/seq-precision.sh \ tests/misc/head.pl \ tests/misc/head-elide-tail.pl \ tests/tail-2/tail-n0f.sh \ diff --git a/tests/misc/seq-precision.sh b/tests/misc/seq-precision.sh new file mode 100755 index 0000000..afbdc72 --- /dev/null +++ b/tests/misc/seq-precision.sh @@ -0,0 +1,27 @@ +#!/bin/sh +# Test for output with appropriate precision + +# Copyright (C) 2015 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src +print_ver_ seq + +# Integer only. Before v8.24 this would switch output format +seq 999999 inf | head -n2 > out || fail=1 +printf "%s\n" 999999 1000000 > exp || framework_failure_ +compare exp out || fail=1 + +Exit $fail -- 2.4.1 From 2905e57f4dba51f28e4543ecd572a53831a1ac80 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= Date: Tue, 23 Jun 2015 22:48:25 +0100 Subject: [PATCH 2/4] seq: use consistent output format with hex integers * src/seq.c (scan_arg): Set precision to 0 for hex constants (while avoiding hex floats). This will use then use the fast path for these arguments. Note we also set the precision of inf to 0 here, which ensures we use consistent precision on output where possible. * tests/misc/seq-precision.sh: Add corresponding test cases. --- src/seq.c | 17 ++++++++++------- tests/misc/seq-precision.sh | 26 +++++++++++++++++++++++++- 2 files changed, 35 insertions(+), 8 deletions(-) diff --git a/src/seq.c b/src/seq.c index e8d4f18..95e6cd6 100644 --- a/src/seq.c +++ b/src/seq.c @@ -147,15 +147,18 @@ scan_arg (const char *arg) while (isspace (to_uchar (*arg)) || *arg == '+') arg++; - ret.width = strlen (arg); + ret.width = 0; ret.precision = INT_MAX; + char const *decimal_point = strchr (arg, '.'); + if (! decimal_point && ! strchr (arg, 'p') /* not a hex float */) + ret.precision = 0; + if (! arg[strcspn (arg, "xX")] && isfinite (ret.value)) { - char const *decimal_point = strchr (arg, '.'); - if (! decimal_point) - ret.precision = 0; - else + ret.width = strlen (arg); + + if (decimal_point) { size_t fraction_len = strcspn (decimal_point + 1, "eE"); if (fraction_len <= INT_MAX) @@ -625,8 +628,8 @@ main (int argc, char **argv) } } - if (first.precision == 0 && step.precision == 0 - && (! isfinite (last.value) || last.precision == 0) + if ((isfinite (first.value) && first.precision == 0) + && step.precision == 0 && last.precision == 0 && 0 <= first.value && step.value == 1 && 0 <= last.value && !equal_width && !format_str && strlen (separator) == 1) { diff --git a/tests/misc/seq-precision.sh b/tests/misc/seq-precision.sh index afbdc72..37881f5 100755 --- a/tests/misc/seq-precision.sh +++ b/tests/misc/seq-precision.sh @@ -19,9 +19,33 @@ . "${srcdir=.}/tests/init.sh"; path_prepend_ ./src print_ver_ seq -# Integer only. Before v8.24 this would switch output format +# Integer only. Before v8.24 these would switch output format + seq 999999 inf | head -n2 > out || fail=1 printf "%s\n" 999999 1000000 > exp || framework_failure_ compare exp out || fail=1 +seq 0xF423F 0xF4240 > out || fail=1 +printf "%s\n" 999999 1000000 > exp || framework_failure_ +compare exp out || fail=1 + +# Ensure consistent precision for inf +seq 1 .1 inf | head -n2 > out || fail=1 +printf "%s\n" 1.0 1.1 > exp || framework_failure_ +compare exp out || fail=1 + +# Ensure standard output methods with inf start +seq inf inf | head -n2 | uniq > out || fail=1 +test "$(wc -l < out)" = 1 || fail=1 + +# Ensure auto precision for hex float +seq 1 0x1p-1 2 > out || fail=1 +printf "%s\n" 1 1.5 2 > exp || framework_failure_ +compare exp out || fail=1 + +# Ensure consistent precision for hex +seq 1 .1 0x2 | head -n2 > out || fail=1 +printf "%s\n" 1.0 1.1 > exp || framework_failure_ +compare exp out || fail=1 + Exit $fail -- 2.4.1 From 6850a62fe95b77c8c2f4dd7491f3a71c75bc2dce Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= Date: Tue, 23 Jun 2015 22:51:24 +0100 Subject: [PATCH 3/4] seq: handle exponents more consistently src/seq.c (scan_arg): Set precision and width _after_ exponentiation. For example, this will make '1.1e1 12' and '11 1.2e1' equivalent. One can still set the precision by specifying extra precision on the start value, or more naturally with a precision on a step value. * tests/misc/seq-precision.sh: Add new cases. --- src/seq.c | 15 +++++++++++++-- tests/misc/seq-precision.sh | 18 ++++++++++++++++++ 2 files changed, 31 insertions(+), 2 deletions(-) diff --git a/src/seq.c b/src/seq.c index 95e6cd6..2426c4d 100644 --- a/src/seq.c +++ b/src/seq.c @@ -147,20 +147,24 @@ scan_arg (const char *arg) while (isspace (to_uchar (*arg)) || *arg == '+') arg++; + /* Default to auto width and precision. */ ret.width = 0; ret.precision = INT_MAX; + /* Use no precision (and possibly fast generation) for integers. */ char const *decimal_point = strchr (arg, '.'); if (! decimal_point && ! strchr (arg, 'p') /* not a hex float */) ret.precision = 0; + /* auto set width and precision for decimal inputs. */ if (! arg[strcspn (arg, "xX")] && isfinite (ret.value)) { + size_t fraction_len = 0; ret.width = strlen (arg); if (decimal_point) { - size_t fraction_len = strcspn (decimal_point + 1, "eE"); + fraction_len = strcspn (decimal_point + 1, "eE"); if (fraction_len <= INT_MAX) ret.precision = fraction_len; ret.width += (fraction_len == 0 /* #. -> # */ @@ -174,7 +178,8 @@ scan_arg (const char *arg) if (e) { long exponent = strtol (e + 1, NULL, 10); - ret.precision += exponent < 0 ? -exponent : 0; + ret.precision += exponent < 0 ? -exponent + : - MIN (ret.precision, exponent); /* Don't account for e.... in the width since this is not output. */ ret.width -= strlen (arg) - (e - arg); /* Adjust the width as per the exponent. */ @@ -189,6 +194,12 @@ scan_arg (const char *arg) ret.width++; exponent = -exponent; } + else + { + if (decimal_point && ret.precision == 0 && fraction_len) + ret.width--; /* discount space for '.' */ + exponent -= MIN (fraction_len, exponent); + } ret.width += exponent; } } diff --git a/tests/misc/seq-precision.sh b/tests/misc/seq-precision.sh index 37881f5..c4e4b4f 100755 --- a/tests/misc/seq-precision.sh +++ b/tests/misc/seq-precision.sh @@ -48,4 +48,22 @@ seq 1 .1 0x2 | head -n2 > out || fail=1 printf "%s\n" 1.0 1.1 > exp || framework_failure_ compare exp out || fail=1 +# Ensure consistent handling of precision/width for exponents + +seq 1.1e1 12 > out || fail=1 +printf "%s\n" 11 12 > exp || framework_failure_ +compare exp out || fail=1 + +seq 11 1.2e1 > out || fail=1 +printf "%s\n" 11 12 > exp || framework_failure_ +compare exp out || fail=1 + +seq -w 1.1e4 | head -n1 > out || fail=1 +printf "%s\n" 00001 > exp || framework_failure_ +compare exp out || fail=1 + +seq -w 1.10000e5 1.10000e5 > out || fail=1 +printf "%s\n" 110000 > exp || framework_failure_ +compare exp out || fail=1 + Exit $fail -- 2.4.1 From 2d6e837828569ca83bdf263e0575d8d3032390fe Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= Date: Wed, 15 Oct 2014 02:18:35 +0100 Subject: [PATCH 4/4] factor: avoid interspersed lines for parallel runs * src/factor.c (n_out): A new global variable to track how much data has been written to stdout. (print_factors_single): Use n_out to determine whether to flush the current (and previous) lines. * tests/misc/factor-parallel.sh: Add a new test. * tests/local.mk: Reference the new test. * NEWS: Mention the bug fix. --- NEWS | 3 +++ src/factor.c | 24 +++++++++++++++++++++--- tests/local.mk | 1 + tests/misc/factor-parallel.sh | 34 ++++++++++++++++++++++++++++++++++ 4 files changed, 59 insertions(+), 3 deletions(-) create mode 100755 tests/misc/factor-parallel.sh diff --git a/NEWS b/NEWS index 99a9301..9aa35ad 100644 --- a/NEWS +++ b/NEWS @@ -24,6 +24,9 @@ GNU coreutils NEWS -*- outline -*- file types, a warning is issued for source directories with duplicate names, or with -H the directory is copied again using the symlink name. + factor avoids writing partial lines, thus supporting parallel operation. + [the bug dates back to the initial implementation] + head, od, split, tac, tail, and wc no longer mishandle input from files in /proc and /sys file systems that report somewhat-incorrect file sizes. diff --git a/src/factor.c b/src/factor.c index f27bf22..5b7ae22 100644 --- a/src/factor.c +++ b/src/factor.c @@ -2323,13 +2323,15 @@ strto2uintmax (uintmax_t *hip, uintmax_t *lop, const char *s) return err; } +static size_t n_out; /* How much data we've written to stdout. */ + static void print_uintmaxes (uintmax_t t1, uintmax_t t0) { uintmax_t q, r; if (t1 == 0) - printf ("%"PRIuMAX, t0); + n_out += printf ("%"PRIuMAX, t0); else { /* Use very plain code here since it seems hard to write fast code @@ -2338,7 +2340,7 @@ print_uintmaxes (uintmax_t t1, uintmax_t t0) r = t1 % 1000000000; udiv_qrnnd (t0, r, r, t0, 1000000000); print_uintmaxes (q, t0); - printf ("%09u", (unsigned int) r); + n_out += printf ("%09u", (unsigned int) r); } } @@ -2350,6 +2352,7 @@ print_factors_single (uintmax_t t1, uintmax_t t0) print_uintmaxes (t1, t0); putchar (':'); + n_out++; factor (t1, t0, &factors); @@ -2358,15 +2361,29 @@ print_factors_single (uintmax_t t1, uintmax_t t0) { char buf[INT_BUFSIZE_BOUND (uintmax_t)]; putchar (' '); - fputs (umaxtostr (factors.p[j], buf), stdout); + char *umaxstr = umaxtostr (factors.p[j], buf); + fputs (umaxstr, stdout); + n_out += strlen (umaxstr) + 1; } if (factors.plarge[1]) { putchar (' '); + n_out++; print_uintmaxes (factors.plarge[1], factors.plarge[0]); } putchar ('\n'); + n_out++; + + /* Assume the stdout buffer is > this value. + Flush here to avoid partial lines being output. + Flushing every line has too much overhead. + TODO: Buffer internally and avoid stdio. */ + if (n_out >= 512) + { + fflush (stdout); + n_out = 0; + } } /* Emit the factors of the indicated number. If we have the option of using @@ -2422,6 +2439,7 @@ print_factors (const char *input) mp_factor_clear (&factors); mpz_clear (t); putchar ('\n'); + fflush (stdout); return true; #else error (0, 0, _("%s is too large"), quote (input)); diff --git a/tests/local.mk b/tests/local.mk index d60f6cf..3cd8f92 100644 --- a/tests/local.mk +++ b/tests/local.mk @@ -282,6 +282,7 @@ all_tests = \ tests/misc/expand.pl \ tests/misc/expr.pl \ tests/misc/factor.pl \ + tests/misc/factor-parallel.sh \ tests/misc/false-status.sh \ tests/misc/fold.pl \ tests/misc/groups-dash.sh \ diff --git a/tests/misc/factor-parallel.sh b/tests/misc/factor-parallel.sh new file mode 100755 index 0000000..8cec630 --- /dev/null +++ b/tests/misc/factor-parallel.sh @@ -0,0 +1,34 @@ +#!/bin/sh +# Test for complete lines on output + +# Copyright (C) 2015 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src +print_ver_ factor + + +odd() { LC_ALL=C sed '/[24680]$/d'; } +primes() { LC_ALL=C sed 's/.*: //; / /d'; } + +# Before v8.24 the number reported here would vary +# Note -u not supplied to split, increased batching of quickly processed items. +# As processing cost increases it becomes advantageous to use -u to keep +# the factor processes supplied with data. +nprimes=$(seq 1e6 | odd | split -nr/4 --filter='factor' | primes | wc -l) + +test "$nprimes" = '78498' || fail=1 + +Exit $fail -- 2.4.1