summaryrefslogtreecommitdiffhomepage
path: root/coreutils
diff options
context:
space:
mode:
authorRon Yorston <rmy@pobox.com>2021-08-07 09:41:49 +0100
committerDenys Vlasenko <vda.linux@googlemail.com>2021-08-22 15:40:21 +0200
commit8817e285b7ce071a27c366a2a602d3ca162b08ba (patch)
treef3f6e68561420ba8e2f13ea25f81257ed38452f1 /coreutils
parent74c4f356aee9c64978a881e5760055d0e3510a6a (diff)
shuf: speed-up when limited output is requested
A user noted that the following command was slower than they expected: busybox shuf -i "1500000000-$(date +%s)" -n 5 At time of writing the range contains 128 million values. On my system this takes 7.7s whereas 'shuf' from coreutils takes a handful of milliseconds. Optimise BusyBox 'shuf' for cases where -n is specified by stopping shuffling once the required number of lines have been processed. On my system the time for the example is reduced to 0.4s. function old new delta shuf_main 520 540 +20 ------------------------------------------------------------------------------ (add/remove: 0/0 grow/shrink: 1/0 up/down: 20/0) Total: 20 bytes v2: Code shrink. Since outlines <= numlines: - the loop in shuffle_lines() only needs to test the value of outlines; - shuffle_lines() can be called unconditionally. Update timing to allow for the 13 million seconds elapsed since v1. Signed-off-by: Ron Yorston <rmy@pobox.com> Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'coreutils')
-rw-r--r--coreutils/shuf.c29
1 files changed, 15 insertions, 14 deletions
diff --git a/coreutils/shuf.c b/coreutils/shuf.c
index fdbd3e9b2..3b2ba93cf 100644
--- a/coreutils/shuf.c
+++ b/coreutils/shuf.c
@@ -24,7 +24,7 @@
//usage: "\n -i L-H Treat numbers L-H as lines"
//usage: "\n -n NUM Output at most NUM lines"
//usage: "\n -o FILE Write to FILE, not standard output"
-//usage: "\n -z End lines with zero byte, not newline"
+//usage: "\n -z NUL terminated output"
#include "libbb.h"
@@ -39,8 +39,10 @@
/*
* Use the Fisher-Yates shuffle algorithm on an array of lines.
+ * If the required number of output lines is less than the total
+ * we can stop shuffling early.
*/
-static void shuffle_lines(char **lines, unsigned numlines)
+static void shuffle_lines(char **lines, unsigned numlines, unsigned outlines)
{
unsigned i;
unsigned r;
@@ -48,7 +50,7 @@ static void shuffle_lines(char **lines, unsigned numlines)
srand(monotonic_us());
- for (i = numlines-1; i > 0; i--) {
+ for (i = numlines-1; outlines > 0; i--, outlines--) {
r = rand();
/* RAND_MAX can be as small as 32767 */
if (i > RAND_MAX)
@@ -67,7 +69,7 @@ int shuf_main(int argc, char **argv)
char *opt_i_str, *opt_n_str, *opt_o_str;
unsigned i;
char **lines;
- unsigned numlines;
+ unsigned numlines, outlines;
char eol;
opts = getopt32(argv, "^"
@@ -128,24 +130,23 @@ int shuf_main(int argc, char **argv)
fclose_if_not_stdin(fp);
}
- if (numlines != 0)
- shuffle_lines(lines, numlines);
+ outlines = numlines;
+ if (opts & OPT_n) {
+ outlines = xatou(opt_n_str);
+ if (outlines > numlines)
+ outlines = numlines;
+ }
+
+ shuffle_lines(lines, numlines, outlines);
if (opts & OPT_o)
xmove_fd(xopen(opt_o_str, O_WRONLY|O_CREAT|O_TRUNC), STDOUT_FILENO);
- if (opts & OPT_n) {
- unsigned maxlines;
- maxlines = xatou(opt_n_str);
- if (numlines > maxlines)
- numlines = maxlines;
- }
-
eol = '\n';
if (opts & OPT_z)
eol = '\0';
- for (i = 0; i < numlines; i++) {
+ for (i = numlines - outlines; i < numlines; i++) {
if (opts & OPT_i)
printf("%u%c", (unsigned)(uintptr_t)lines[i], eol);
else