Hello,
Attached is an updated version.
Pádraig Brady wrote, On 03/06/2013 08:24 PM:
> On 03/06/2013 11:50 PM, Assaf Gordon wrote:
>> Attached is a suggestion to implement reservoir-sampling in shuf:
>> When the expected output of lines is known, it will not load the entire file
>> into memory - allowing shuffling very large inputs.
>>
Regarding comments:
>> {"-debug", no_argument, NULL, DEV_DEBUG_OPTION},
> no need to keep this, for final commit.
Yes, I'll remove this once the code is acceptable.
>> prepare_shuf_lines (struct linebuffer *in_lines, size_t n, char ***out_lines,
>
> I've not looked into the details, but it would
> be nice to avoid the memcpy/conversion here
>
I've removed the conversion function, and instead added a new function to
output the lines directly.
>> static size_t
>> read_input_reservoir_sampling (FILE *in, char eolbyte, char ***pline, size_t
>> k,
>> struct randint_source *s)
<...>
>> struct linebuffer *rsrv = XCALLOC (k, struct linebuffer); /* init
>> reservoir*/
>
> Since this change is mainly about efficient mem usage we should probably
> handle
> the case where we have small inputs but large k. This will allocate (and
> zero)
> memory up front. The zeroing will defeat any memory overcommit configured on
> the
> system, but it's probably better to avoid the large initial commit and realloc
> as required (not per line, but per 1K lines maybe).
>
I'm not quite sure about this:
The "reservoir-sampling" path can only be used when the user explicitly ask to
limit output lines.
I would naively assume that if a user explicitly asked to limit the output to
1,000,000 lines, he/she expects large input as well.
And so the (edge?) case of asking for a large number of output lines, but
supplying very small number of input lines is rare.
Wouldn't you agree? or is there a different typical usage case?
Also, the allocation only allocates an array of "struct linebuffer" (on 64bit
systems, 24 bytes).
So even asking for 1M lines will allocate 24MB of RAM - not "too much" on
modern machines.
----
The second attached patch is experimental - it tries to assess the randomness
of 'shuf' output by running it 1,000 times and checking if the output is (very
roughly) uniformly distributed.
I don't know if there were attempts in the past to unit-test randomness (and
then decided not to do it) - or if this was just never considered worth-while
(or too error prone).
Comments are welcomed,
-gordon
>From 1adfd08cd3a52c373932b0f1039755a240d2c0b8 Mon Sep 17 00:00:00 2001
From: Assaf Gordon <[email protected]>
Date: Thu, 7 Mar 2013 01:57:57 -0500
Subject: [PATCH 1/2] shuf: add (expensive) test for randomness
To run manually:
make check TESTS=tests/misc/shuf-nonrandomess.sh \
SUBDIRS=. RUN_VERY_EXPENSIVE_TESTS=yes
* tests/misc/shuf-randomness.sh: run 'shuf' repeatedly, and check if the
output is uniformly distributed "enough".
* tests/local.mk: add new test script.
---
tests/local.mk | 1 +
tests/misc/shuf-randomness.sh | 186 +++++++++++++++++++++++++++++++++++++++++
2 files changed, 187 insertions(+), 0 deletions(-)
create mode 100755 tests/misc/shuf-randomness.sh
diff --git a/tests/local.mk b/tests/local.mk
index 607ddc4..d3923f8 100644
--- a/tests/local.mk
+++ b/tests/local.mk
@@ -313,6 +313,7 @@ all_tests = \
tests/misc/shred-passes.sh \
tests/misc/shred-remove.sh \
tests/misc/shuf.sh \
+ tests/misc/shuf-randomness.sh \
tests/misc/sort.pl \
tests/misc/sort-benchmark-random.sh \
tests/misc/sort-compress.sh \
diff --git a/tests/misc/shuf-randomness.sh b/tests/misc/shuf-randomness.sh
new file mode 100755
index 0000000..3e35cca
--- /dev/null
+++ b/tests/misc/shuf-randomness.sh
@@ -0,0 +1,186 @@
+#!/bin/sh
+# Test shuf for somewhat uniform randomness
+
+# Copyright (C) 2013 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 <http://www.gnu.org/licenses/>.
+
+. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src
+print_ver_ shuf
+getlimits_
+
+# Don't run these tests by default.
+very_expensive_
+
+# Number of trails
+T=1000
+
+# Number of categories
+N=100
+REQUIRED_CHI_SQUARED=200 # Be extremely leniet:
+ # don't require "great" goodness of fit
+ # even for our assumed 99 degrees of freedom
+
+# K - when testing reservoir-sampling, print K lines
+K=20
+REQUIRED_CHI_SQUARED_K=50 # Be extremely leniet:
+ # don't require "great" goodness of fit
+ # even for our assumed 19 degrees of freedom
+
+
+
+# The input: many zeros followed by 1 one
+(yes 0 | head -n $((N-1)) ; echo 1 ) > in || framework_failure_
+
+
+is_uniform()
+{
+ # Input is assumed to be a string of $T spaces-separated-values
+ # between 1 and $N
+ LINES="$1"
+
+ # Convert spaces to new-lines
+ LINES=$(echo "$LINES" | tr ' ' '\n' | sed '/^$/d') || framework_failure_
+
+ # Requre exactly $T values
+ COUNT=$(echo "$LINES" | wc -l)
+ test "$COUNT" -eq "$T" || framework_failure_
+
+ # HIST is the histogram of counts per categories
+ # ( categories are between 1 and $N )
+ HIST=$(echo "$LINES" | sort -n | uniq -c)
+
+ #DEBUG
+ #echo "HIST=$HIST" 1>&2
+
+ ## Calculate Chi-Squared
+ CHI=$( echo "$HIST" |
+ awk -v n=$N -v t=$T '{ counts[$2] = $1 }
+ END {
+ exptd = ((1.0)*t)/n
+ chi = 0
+ for (i=1;i<=n;++i)
+ {
+ if (i in counts)
+ obs = counts[i]
+ else
+ obs= 0;
+ chi += ((obs-exptd)*(obs-exptd))/exptd
+ }
+ printf "%7.0f\n", chi
+ }' ) || framework_failure_
+ #DEBUG
+ #echo "CHI = $CHI" 1>&2
+
+ # If CHI is "small enough" assume uniformity.
+ test "$CHI" -le "$REQUIRED_CHI_SQUARED" && return 0
+
+ # assume not uniform "enough"
+ return 1
+}
+
+is_uniform_k()
+{
+ K="$1"
+ LINES="$2"
+
+ # Convert spaces to new-lines
+ LINES=$(echo "$LINES" | tr ' ' '\n' | sed '/^$/d') || framework_failure_
+
+ # HIST is the histogram of counts per categories
+ # There should be K numeric categories (e.g 1/2/3/4/5 for K=5)
+ # and one X category (when the first K results from 'shuf' didn't
+ # contain "1").
+ HIST=$(echo "$LINES" | sort | uniq -c) || framework_failure_
+
+
+ #DEBUG
+ #echo "HIST=$HIST" 1>&2
+
+ ## Calculate Chi-Squared
+ CHI=$( echo "$HIST" |
+ awk -v n=$N \
+ -v t=$T \
+ -v k=$K \
+ '{ counts[$2] = $1 }
+ END {
+ # each of the first K categories is expected
+ # to appear as if they are uniformaly distributed
+ exptd_k = ((1.0)*t)/n
+
+ chi = 0
+ # Sum chi-squared for the K categories
+ for (i=1;i<=k;++i)
+ {
+ if (i in counts)
+ obs = counts[i]
+ else
+ obs= 0;
+ chi += ((obs-exptd_k)*(obs-exptd_k))/exptd_k
+ }
+
+ # Print Chi-Squared
+ printf "%7.0f\n",chi
+ }' ) || framework_failure_
+ #DEBUG
+ #echo "CHI = $CHI" 1>&2
+
+ # If CHI is "small enough" assume uniformity.
+ test "$CHI" -le "$REQUIRED_CHI_SQUARED_K" && return 0
+
+ # assume not uniform "enough"
+ return 1
+}
+
+
+##
+## Step 1:
+## Run a control: the "1"s in the input file should not be uniformly distributed
+##
+LINE=$(cat in | sed -n '/1/=') || framework_failure_
+for loop in $(seq $T) ;
+do
+ LINES="$LINES $LINE"
+done
+is_uniform "$LINES" && framework_failure_
+
+##
+## Step 2:
+## Shuffle the input files $T times.
+## The resulting position (=line number) of the "1" should be uniformly distributed.
+## This tests the "load entire file" control flow in the C code.
+LINES=""
+for loop in $(seq $T) ;
+do
+ LINE=$(shuf in | sed -n '/1/=') || framework_failure_
+ LINES="$LINES $LINE"
+done
+is_uniform "$LINES" ||
+ { fail=1 ; echo "step 2 failed - not uniformly distributed?" 1>&2 ; }
+
+##
+## Step 3:
+## Shuffle the input files $T times, selecting the first K lines.
+## This tests the "reservoir sampling" control flow in the C code.
+LINES=""
+for loop in $(seq $T) ;
+do
+ LINE=$(shuf -n $K in | sed -n '/1/=') || framework_failure_
+ LINES="$LINES $LINE"
+done
+is_uniform_k "$K" "$LINES" ||
+ { fail=1 ; echo "step 3 failed - not uniformly distributed?" 1>&2 ; }
+
+
+Exit $fail
--
1.7.7.4
>From d6d6e11fe399495fc1e7834ebd3e0cec94a7e044 Mon Sep 17 00:00:00 2001
From: Assaf Gordon <[email protected]>
Date: Wed, 6 Mar 2013 18:25:49 -0500
Subject: [PATCH 2/2] shuf: use reservoir-sampling when possible
Reservoir Sampling enables selecting K random lines from a very large
(or unknown-sized) input:
http://en.wikipedia.org/wiki/Reservoir_sampling
* src/shuf.c: Use reservoir-sampling when the number of output lines
is known (by using '-n X' parameter).
read_input_reservoir_sampling() - read lines from input file, and keep
only K lines in memory, replacing lines with decreasing probability.
write_permuted_output_reservoir() - output permuted reservoir lines.
main() - if the number of lines is known, use reservoir-sampling
instead of reading entire input file.
---
src/shuf.c | 144 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 files changed, 138 insertions(+), 6 deletions(-)
diff --git a/src/shuf.c b/src/shuf.c
index 71ac3e6..7c5d16c 100644
--- a/src/shuf.c
+++ b/src/shuf.c
@@ -25,6 +25,7 @@
#include "error.h"
#include "fadvise.h"
#include "getopt.h"
+#include "linebuffer.h"
#include "quote.h"
#include "quotearg.h"
#include "randint.h"
@@ -81,7 +82,8 @@ With no FILE, or when FILE is -, read standard input.\n\
non-character as a pseudo short option, starting with CHAR_MAX + 1. */
enum
{
- RANDOM_SOURCE_OPTION = CHAR_MAX + 1
+ RANDOM_SOURCE_OPTION = CHAR_MAX + 1,
+ DEV_DEBUG_OPTION
};
static struct option const long_opts[] =
@@ -92,11 +94,31 @@ static struct option const long_opts[] =
{"output", required_argument, NULL, 'o'},
{"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
{"zero-terminated", no_argument, NULL, 'z'},
+ {"-debug", no_argument, NULL, DEV_DEBUG_OPTION},
{GETOPT_HELP_OPTION_DECL},
{GETOPT_VERSION_OPTION_DECL},
{0, 0, 0, 0},
};
+/* debugging for developers. Enables devmsg(). */
+static bool dev_debug = false;
+
+/* Like error(0, 0, ...), but without an implicit newline.
+ Also a noop unless the global DEV_DEBUG is set.
+ TODO: Replace with variadic macro in system.h or
+ move to a separate module. */
+static inline void
+devmsg (char const *fmt, ...)
+{
+ if (dev_debug)
+ {
+ va_list ap;
+ va_start (ap, fmt);
+ vfprintf (stderr, fmt, ap);
+ va_end (ap);
+ }
+}
+
static bool
input_numbers_option_used (size_t lo_input, size_t hi_input)
{
@@ -135,6 +157,87 @@ next_line (char *line, char eolbyte, size_t n)
return p + 1;
}
+static size_t
+read_input_reservoir_sampling (FILE *in, char eolbyte, size_t k,
+ struct randint_source *s,
+ struct linebuffer **out_rsrv)
+{
+ size_t n_lines=0;
+ struct linebuffer line;
+ struct linebuffer *rsrv = XCALLOC (k, struct linebuffer); /* init reservoir*/
+
+ devmsg ("--reservoir_sampling--\n");
+
+ initbuffer (&line);
+ while (readlinebuffer_delim (&line, in, eolbyte)!=NULL)
+ {
+ if ( n_lines < k )
+ {
+ /* Read first K lines into reservoir */
+
+ if (dev_debug)
+ {
+ fprintf (stderr,"filling reservoir, input line %zu of %zu: '",
+ n_lines+1, k);
+ fwrite (line.buffer, sizeof (char), line.length-1, stderr);
+ fprintf (stderr, "'\n");
+ }
+
+ rsrv[n_lines] = line;
+ initbuffer (&line); /* next line-read will allocate a new buffer */
+
+
+ }
+ else
+ {
+ /* Read the rest of the lines, with decreasing probability of updating
+ the reservoir */
+ randint j = randint_choose (s, n_lines+1);
+ if ( j < k )
+ {
+ if (dev_debug)
+ {
+ fprintf (stderr,"Replacing reservoir sample %zu with " \
+ "line %zu '", j, n_lines);
+ fwrite (line.buffer, sizeof (char), line.length-1, stderr);
+ fprintf (stderr, "'\n");
+ }
+
+ rsrv[j] = line;
+ initbuffer (&line);/* next line-read will allocate a new buffer */
+
+ }
+ }
+
+ ++n_lines;
+ }
+ freebuffer (&line);
+
+ /* no more input lines, or an input error */
+ if (ferror (in))
+ error (EXIT_FAILURE, errno, _("read error"));
+
+ *out_rsrv = rsrv;
+ return MIN (k, n_lines);
+}
+
+static int
+write_permuted_output_reservoir (size_t n_lines, struct linebuffer *lines,
+ size_t const *permutation)
+{
+ size_t i;
+
+ for (i = 0; i < n_lines; i++)
+ {
+ const struct linebuffer *p = &lines[permutation[i]];
+ if (fwrite (p->buffer, sizeof (char),
+ p->length, stdout) != p->length)
+ return -1;
+ }
+
+ return 0;
+}
+
/* Read data from file IN. Input lines are delimited by EOLBYTE;
silently append a trailing EOLBYTE if the file ends in some other
byte. Store a pointer to the resulting array of lines into *PLINE.
@@ -209,14 +312,17 @@ main (int argc, char **argv)
char *random_source = NULL;
char eolbyte = '\n';
char **input_lines = NULL;
+ bool use_reservoir_sampling = false;
int optc;
int n_operands;
char **operand;
size_t n_lines;
- char **line;
+ char **line = NULL;
+ struct linebuffer *reservoir = NULL;
struct randint_source *randint_source;
size_t *permutation;
+ int i;
initialize_main (&argc, &argv);
set_program_name (argv[0]);
@@ -295,6 +401,10 @@ main (int argc, char **argv)
eolbyte = '\0';
break;
+ case DEV_DEBUG_OPTION:
+ dev_debug = true;
+ break;
+
case_GETOPT_HELP_CHAR;
case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
default:
@@ -341,8 +451,16 @@ main (int argc, char **argv)
fadvise (stdin, FADVISE_SEQUENTIAL);
- n_lines = read_input (stdin, eolbyte, &input_lines);
- line = input_lines;
+ if (head_lines != SIZE_MAX)
+ {
+ use_reservoir_sampling = true;
+ n_lines = SIZE_MAX; /* unknown number of input lines, for now */
+ }
+ else
+ {
+ n_lines = read_input (stdin, eolbyte, &input_lines);
+ line = input_lines;
+ }
}
head_lines = MIN (head_lines, n_lines);
@@ -352,6 +470,15 @@ main (int argc, char **argv)
if (! randint_source)
error (EXIT_FAILURE, errno, "%s", quotearg_colon (random_source));
+ if (use_reservoir_sampling)
+ {
+ /* Instead of reading the entire file into 'line',
+ use reservoir-sampling to store just "head_lines" random lines. */
+ n_lines = read_input_reservoir_sampling (stdin, eolbyte,
+ head_lines, randint_source,
+ &reservoir);
+ }
+
/* Close stdin now, rather than earlier, so that randint_all_new
doesn't have to worry about opening something other than
stdin. */
@@ -363,8 +490,13 @@ main (int argc, char **argv)
if (outfile && ! freopen (outfile, "w", stdout))
error (EXIT_FAILURE, errno, "%s", quotearg_colon (outfile));
- if (write_permuted_output (head_lines, line, lo_input, permutation, eolbyte)
- != 0)
+
+ if (use_reservoir_sampling)
+ i = write_permuted_output_reservoir (n_lines, reservoir, permutation);
+ else
+ i = write_permuted_output (head_lines, line, lo_input,
+ permutation, eolbyte);
+ if (i != 0)
error (EXIT_FAILURE, errno, _("write error"));
#ifdef lint
--
1.7.7.4
