Performance Tuning Shell Scripts? Why, yes.

Can I write a command-line that lists open TCP ports as quickly as nmap? No way. But can I make one that's fast? Yes, indeedy.

The trick is to do it all in a single shell command.

I always read Hal Pomeranz's weekly, Command Line Kung Fu blog. Inevitably, either I learn something because he tells me, or I learn something because it gets me thinking about how I might do what he's done differently. (That's not an exclusive-or.)

This week, Hal writes a command-line that looks for open TCP ports.

Here's his command. (For a dramatic reading, see his post.)

for ((i=1; i<65535; i++)) ( echo > /dev/tcp/localhost/$i ) 2>/dev/null && echo $i; done

It isn't fast, and he ends with, "But really, if speed were a factor you'd be using nmap instead."

But can I get it to run faster? At least a little? Why, yes I can.

Replacing this:

for (( i=1; i<65535; i++ ))

by this:

for i in {1..65535}

and this:

echo > /dev/tcp/localhost/$i

by this:

> /dev/tcp/local/host/$i (or even < /dev/tcp/localhost/$i )

make minor improvements.

But a bigger win comes from getting rid of subshells.

The parens around the echo create a subshell, which requires a fork() and an exec(), each time through the loop.

By getting rid of those, and discarding error messages at the end of the loop, all the work takes place right in the parent shell.

How much does that improve things? A lot. Here are the numbers.

$ time nmap -p1-65535 --open localhost

real 0m1.366s

user 0m0.280s

sys 0m0.850s

$ time for (( i=1; i<65535; i++ )) ( echo > /dev/tcp/localhost/$i ) 2>/dev/null && echo $i; done

real 1m55.727s

user 0m12.640s

sys 1m28.200s

$ time for i in {1..65536} ; do >/dev/tcp/localhost/$i && echo $i; done 2>/dev/null

real 0m6.203s

user 0m3.290s

sys 0m2.780s

Tom Christiansen claims he can usually write Perl scripts that run within a factor of 'e' (2.718281828...) of the equivalent C program. Here, I'm only doing half that well, but that's not bad.

Even in the shell, sometimes a little tweak makes a big difference.

I'd offer extra points to the reader who knows an attribution for the quote "Make it work, then make it fast," but that would require readers.

It was, however, Frank Zappa who said, "Speed will turn you into your parents."

Generating Arbitrary Numbers

Sometimes, "arbitrary" and "random" aren't synonyms. Here's an example of how to generate the former without their being the latter.

One nice thing about knowing people who make me think is that it gives me things to post about. For example, Hal Pomeranz, Ed Skoudis, Tim Medin, and Paul Asadoorian have a weekly blog, called Command Line Kung Fu, that compares and contrasts command-line tricks for different operating systems.

I only every use Linux, so I read Hal's stuff and skip the Windows and DOS stuff. Even with this, every week or two Hal's post makes me think, "Wait! Here's something he didn't mention!" (typically because it's slightly off-topic).

In this week's column they generate random time intervals.

Here's Hal's punchline:

[...] in larger enterprises you might have hundreds or thousands of machines that all need to do the same task at a regular interval. Often this task involves accessing some central server-- grabbing a config file or downloading virus updates for example. If a thousand machines all hit the server at exactly the same moment, you've got a big problem. So staggering the start times of these jobs across your enterprise by introducing a random delay is helpful. You could create a little shell script that just sleeps for a random time and then introduce it at the front of all your cron jobs like so:

0 * * * * /usr/local/bin/randsleeper; /path/to/regular/cronjob

(The column sketches how to implement 'randsleeper'.)

Yep. This works fine.

But as it stands, the cronjob could kick off one job at 9:59, and the next one at 10:00. What if I want to spread my machines across the hour, but want each machine to use a fixed timeslot, so the elapsed time between runs is a full hour for any given machine?

Here's one way:

1. Pick an arbitrary machine-specific number, like the IPV6 address, or the MAC address of the ethernet card,
2. Convert it to an integer.
3. Take it mod the time interval.
4. Use that number for the time to start the job.

Here's code to do that, which, as always, I grow, bit-by-bit, on the command line, by getting a little piece right, recalling that piece, and adding another step.

• Step 1:

Get a unique, but arbitrary, machine-specific identifier (the MAC address of the first NIC).

$ ifconfig | awk '/HWaddr/ {print $NF; exit 0}'

00:1e:c9:3d:c0:0c

• Step 2:

Strip the colons

$ ifconfig | awk '/HWaddr/ {print $NF; exit 0}' | sed 's/://g'

001ec93dc00c

And interpret the result as a hex number. (The shell requires hex numbers begin with "0x", so I'll just tack that on.)

$ echo $(( 0x$(ifconfig | awk '/HWaddr/ {print $NF; exit 0}' | sed 's/://g') ))

132225286156

• Step 3:

Mod it by the number of seconds in an hour, to get an arbitrary second.

$ echo $(( 0x$(ifconfig | awk '/HWaddr/ {print $NF; exit 0}' | sed 's/://g') % (60*60) ))

556

• Step 4:

Always sleep until that many seconds after the hour, then kick off the job.

$ crontab -l > Cronjobs

$ echo "0 * * * * sleep \$(( 0x\$(ifconfig | awk '/HWaddr/ {print \$NF; exit 0}' | sed 's/://g') % (60*60) )); /path/to/regular/cronjob" >> Cronjobs

$ crontab Cronjobs

Ta-da.

(For step four, I'd probably actually kick off cron -e and paste the line in; otherwise there are just too many ugly backslashes to get wrong.)

Warning: This will not work if your machines' MAC addresses cluster around the same value, mod 556. :-)

Better Safe Than Sorry: Writing Code that Writes Safer Code

I write code that writes code. A lot. On the command line. It's safer.

Hal Pomeranz and co-conspirators have another fine post up about command-line programming. In it, they write a clever loop to rename a list of numbered attachments.

Here's Hal's code:

$ cat id-to-filename.txt | while read id file; do mv attachment.$id "$file"; done

(His input file is a two-column list, like this:

$ cat id-to-filename.txt

...

43567 sekrit plans.doc

44211 pizza-costs.xls

...

And, actually, Hal takes the list from stdin, with a less-than sign. Blogger whines and eats my posts when I use those -- it thinks I'm opening an unclosed HTML tag. What a pain.)

The quotes are there because without them the code tries to do this:

mv attachment.43567 sekrit plans.doc

which gets the mysterious message back

mv: target `plans.doc' is not a directory

$

Uh-oh.

When this happens, I usually don't know what the message means. Figuring it out eats time. Plus, with my luck, some files have been moved but others haven't. Recovering from that eats even more time.

Here's what I type instead:

• First step: I write code that says what I'd like to do.

$ cat id-to-filename.txt | while read id file; do echo "mv attachment.$id $file"; done

...

mv attachment.43567 sekrit plans.doc

mv attachment.44211 pizza-costs.xls

...

Often, when I do this, I scan the output, notice something's going to go wrong, and fix it.

"Oh. Oops. I need quotes. I'm an idiot."

Note that no files were moved; my code's only echoing commands.

• Next step: I recall my command-line, with an up-arrow, and add fixes. I keep doing that until the commands I see are the ones I actually want.

$ cat id-to-filename.txt | while read id file; do echo "mv attachment.$id '$file' "; done

...

mv attachment.43567 'sekrit plans.doc'

mv attachment.44211 'pizza-costs.xls'

...

Look okay? Yep.

• Last step: I recall the previous command, one final time, and pipe it to a subshell, which executes the commands my code writes.

$ cat id-to-filename.txt | while read id file; do echo "mv attachment.$id '$file' "; done | bash

$

When I'm nervous about what I'm doing, I even try out the first line by itself, like this:

$ cat id-to-filename.txt | while read id file; do echo "mv attachment.$id '$file' "; done | head -1 | bash

$

I check the result, and if I've done the right thing I go ahead and run the rest.

$ cat id-to-filename.txt | while read id file; do echo "mv attachment.$id '$file' "; done | sed 1d | bash

$

"Never write code on the command line when you can write code that writes code on the command line," I always say.

The "help" Command, And Other Aids

In his latest Command-Line Kung Fu post, Hal Pomeranz talks about places to get help on Unix systems and their kin. (Technically, that's "their latest post," but his co-conspirators write about Microsoft stuff, which I don't care about.)

Hal concentrates on man(1), info(1), and apropos(1), and the --help flag. Good places to start, but there are other things worth mentioning.

So I will.

locate(1) is quite handy. I often find myself hunting for commands that don't have man entries of any kind, and are installed someplace bizarre. Once I find them, /path/to/command --help often tells me enough. If not, but they're in some special directory, there's sometimes a README or examples that do the trick.

Another frequent stop is the web. If command --help doesn't tell me what I want to know, the web's more likely to have a man page than my machine is. I'll now usually go there first.

If it's not an executable? How about type?

$ type ls

ls is aliased to `ls --color=auto'

$ type cdjob

cdjob is a function

cdjob ()

{

local d;

: ${1:?"usage $FUNCNAME %N"};

d=$(jobs $1 | perl -lane 'print "cd $1" if m/.*\(wd: (.*)\).*/');

test "$d" && eval $d

}

And what's type?

$ type type

type is a shell builtin

For information about type, do we have to pour through the zillion-page, bash man page? On-line?

Nope. Watch:

$ man type

No manual entry for type

$ type type

type is a shell builtin

$ help type

type: type [-afptP] name [name ...]

Display information about command type.

For each NAME, indicate how it would be interpreted if used as a

command name.

Options:

-a display all locations containing an executable named NAME;

includes aliases, builtins, and functions, if and only if

the `-p' option is not also used

-f suppress shell function lookup

-P force a PATH search for each NAME, even if it is an alias,

builtin, or function, and returns the name of the disk file

that would be executed

-p returns either the name of the disk file that would be executed,

or nothing if `type -t NAME' would not return `file'.

-t output a single word which is one of `alias', `keyword',

`function', `builtin', `file' or `', if NAME is an alias, shell

reserved word, shell function, shell builtin, disk file, or not

found, respectively

Arguments:

NAME Command name to be interpreted.

Exit Status:

Returns success if all of the NAMEs are found; fails if any are not found.

typeset: typeset [-aAfFilrtux] [-p] name[=value] ...

Set variable values and attributes.

Obsolete. See `help declare'.

Yes, there's really a help command. It gives help about shell builtins.

If I don't even have the command? (If, for example, it's part of someone else's script I've pulled down from somewhere?)

Here's what I get out of bash when I invoke als(1) on my Ubuntu box.

$ als

The program 'als' is currently not installed. You can install it by typing:

sudo apt-get install atool

als: command not found

Not help with the command, okay, but help getting it so I can then get help with it.

What would you pay? But wait. There's more.

If I guess at a command but mis-type it?

$ las

No command 'las' found, did you mean:

Command 'als' from package 'atool' (universe)

Command 'ls' from package 'coreutils' (main)

Command 'lfs' from package 'lustre-utils' (universe)

Command 'lms' from package 'lms' (universe)

Command 'les' from package 'atm-tools' (universe)

Command 'last' from package 'sysvinit-utils' (main)

Command 'laps' from package 'epix1' (universe)

Command 'lvs' from package 'lvm2' (main)

Command 'cas' from package 'amule-adunanza-utils' (universe)

Command 'cas' from package 'amule-utils' (universe)

Command 'as' from package 'binutils' (main)

Command 'ras' from package 'ras' (universe)

Command 'kas' from package 'openafs-kpasswd' (universe)

Command 'lat' from package 'lat' (universe)

las: command not found

I think that's nice. And I can use apt-cache show to tell me what each package is.

Checking Scripts for Syntax Errors

If I'm maintaining a lot of shell scripts in a directory, I usually want to syntax-check them before I check them in.

The file(1) command will mark most of them as shell scripts. The rest are, typically, libraries of shell functions that I name with .sh suffixes.

All shell scripts that file can find:

$ file * | awk -F: '/shell/{print $1}'

plus the libraries

$ file * | awk -F: '/shell/{print $1}' ; echo *.sh

now syntax check them

$ for i in $(file * | awk -F: '/shell/{print $1}' ; echo *.sh); do bash -n $i || echo $i fails; done

Just with command-line recall and editing.

Hello, World Again

I'd like to try saying "We sometimes take the shell too much for granted," another way.

Advice from masters is often good advice.

Here's my favorite chunk of the greatest of all programming texts, Kernighan and Ritchie's The C Programming Language (Prentice-Hall, 1978).

1.1 Getting Started

The only way to learn a new programming language is by writing programs in it. The first program to write is the same for all languages:

Print the words

hello, world

This is the basic hurdle; to leap over it you have to be able to create the program text somewhere, compile it successfully, load it, run it, and find out where your output went. With these mechanical details mastered, everything else is comparatively easy.

In C, the program to print "hello, world" is

#include

main()

{

printf("hello, world\n");

}

Just how to run this program depends on the system you are using. As a specific example, on the UNIX operating system you must create the program in a file whose name ends in ".c", such as hello.c, then compile it with the command

cc hello.c

If you haven't botched anything, such as omitting a character or misspelling something, the compilation will proceed silently, and make an executable file called a.out. Running that by the command

a.out

will produce

hello, world

as its output. On other systems, the rules will be different; check with a local expert.

Exercise 1-1. Run this program on your system. Experiment with leaving out parts of the program, to see what error messages you get.

Fine advice. Let's do exercise 1-1, but in the shell.

Run the analogous program? Okay.

$ echo hello, world

hello, world

Leave out parts? Let's leave out a part of the string.

$ echo hell, world

hell, world

Or part of the command.

$ eco hello, world

bash: eco: command not found

How about whitespace? It's okay to leave it out of the string,

$ echo hello,world

hello,world

but you need some between a command and its arguments.

$ echohello, world

bash: echohello,: command not found

My point: Programing in the shell is quick and easy. You just type. There's no editing, no special naming, no compiling, no a.out file, no loading and running, no need to consult a local expert.

If you type something incomprehensible, the shell gives you an error message and lets you try again, right away.

The Shell Enters a Beauty Contest

I'd never tout the shell as the be-all and end-all of programming languages, but it gets less attention and respect than it deserves.

For example, folks will remark, casually, that shell syntax is ugly. Who would design a language that doesn't even let you put spaces around the '=' in an assignment?

$ x=3

$ y = 3

-bash: y: command not found

$ z= 5

-bash: 5: command not found

Eeew. Real programs are in C. Or Perl. Or Python. Or Haskell. Or ...

Yep, the shell syntax has some design flaws all right. But let's run another beauty contest.

First, contestant #1:

#include <unistd.h>
#include <stdlib.h>

int main(void)
{
int     fd[2], nbytes;
pid_t   pid;

pipe(fd);

if ((pid = fork()) == 0) {
  dup2(fd[0], 0);
  close(fd[1]);
  execlp("/bin/grep", "/bin/grep", "^z", NULL);
} else {
  dup2(fd[1], 1);
  close(fd[0]);
  execlp("/bin/ls", "/bin/ls", "-1", "/bin", NULL);
  wait(NULL);
  exit(0);
}

return(0);
}

Next, contestant #2:

ls /bin | grep ^z

And contestant #1 doesn't even have normal error checking, which would make it much longer, uglier, and hard-to-follow.

Programmers get so used to the shell that they focus on its flaws, but take its virtues for granted.

Don't it always seem to go that you don't know what you've got till it's gone? -- Joni Mitchell

What tastes of paradise does the shell offer besides pipes? I/O redirection. Ease of process creation. Multi-process programming. Parallelism. Command-line editing. For that matter, the entire idea of a CLI, a "command-line interface."

Once I start listing things, it's hard to stop.

All this in a language you can use in scripts, or just by doing nothing harder than typing at a prompt.

Variables Without Values

Often, you only want to do something if a variable is unset.

I see code to handle such conditions that looks like this.

if [ "A$foo" = "A" ]

then

take-some-action

fi

It's either old code or code by old programmers.

The test is how you used to have to ask whether a variable was empty. Here's a newer idiom.

[ "$foo" ] || take-some-action

The test operator, [ ], comes in many flavors. For example

[ -d $X ] asks "Does $X name a directory?"

In its simplest form, though,

[ $X ]

asks "Is $X empty?" The test returns true if $X has something in it, false if it doesn't. The new code does the same thing as the old, but it's shorter and, arguably, easier to read.

But why not this?

[ $foo ] || take-some-action

Ah. Because if foo='1 2 3', then test complains that you've given it too many arguments.

[: 2: unary operator expected

One more trick: what if you're running with "set -u", which complains whenever it stumbles on an unset variable, with complaints like this

line 3: foo: unbound variable

Write the test like this:

["${foo-}" ] || take some action

If $foo is unset, ${foo-} has a null value. "Null" is a value; "unset" really means the variable was never set. So, with "${foo-}" the shell won't complain about an unset variable, but the test will still fail.

This is still shorter than the example we started with, but it's only more readable once you can read the idiom ${foo-} without stumbling.

On the other hand, the first example will also choke if $foo is unset, so it would also have to be modified like this:

if [ "A${foo-}" = "A" ]

then

take-some-action

fi

More Include Guards

I've already written about how to make include guards for "shell libraries" (files full of shell functions or variables to be sourced).

This is the basic form of the statement, which requires tailoring for each library:

if [ ${_gripe_version:-0} -gt 0 ]

then

return 0

else

_gripe_version=1

fi

Here's a more generic statement that you can put at the top of a file to achieve the same goal:

[ "${_libs/${BASH_SOURCE[0]}}" = "${_libs=}" ] ||

return 0 && _libs+=" ${BASH_SOURCE[0]}"

A dramatic reading of this off-putting code is left as an exercise to the reader.

It has the added attraction that you can, at any point, find out which libraries you've already sourced with echo $_libs .

It has the added detraction that you'll have to cut-and-paste it. There's no way you'll ever keep it in your head and type it correctly.

As a good test, first try this infinite recursion without include guards. (You'll have to ^C out quickly, or you'll get stuck in a source-a-thon.)

$ echo 'source foo.sh' > foo.sh

$ chmod +x foo.sh

$ ./foo.sh # don't wait long to ^C

Next, edit foo.sh to add an include guard at the top and re-run it. This time, it will return immediately, without help.

Simplifying Loopy Code

The determined Real Programmer can write FORTRAN programs in any language.

-- Ed Post, Real Programmers Don't Use PASCAL.

I just read through a friend's shell script. He doesn't program in the shell much, but he's a superb C programmer, so his script has loops that look like this:

file[0]=foo

file[1]=bar

file[2]=mumble

suffix[0]=.c

suffix[1]=.h

suffix[2]=.txt

nfiles=${#file[@]}

nsuffixes=${#suffix[@]}

i=0while [ $i -lt $nfiles ]

do

j=0

while [ $j -lt $nsuffixes ]

do

process ${file[$i]}${suffix[$j]}

(( j = j + 1 ))

done

(( i = i + 1 ))

done

Yep. That'll work. But this will, too.

for filename in {foo,bar,mumble}.{c,h,txt}

do

process $filename

done

Bash sees filenames as strings, and most shell commands accept space-separated lists of filenames. The shell handles anything that expands to a list of filenames, like globs or brace expansions, with real ease.

Use the Shell, Luke.

But *How* Random Is It?

Folks use /dev/urandom and $RANDOM to generate uniformly-distributed random numbers. Are they random? Yes.

Let's test. Here's how.

Surprise! The easiest way to start is to ask a more general question: Suppose you have a couple of sets of numbers. Are they from the same distribution?

For example, if you have a couple of batches of 10,000, 8-digit numbers, from the two different distributions, are they really spread out from 0 to 9999 the same way, or do they have clumps in different places?

There are ways to attack this, even if you don't know (or care) what the original distribution was. Here's a step-by-step walkthrough:

• Sort them together, smallest to biggest, coloring the first set red and the second, green.

• Put your finger on the middle of a line--zero on the number line--and begin reading off colors. If the number's red, move your finger left. If it's green, move it right.

• See how far away from the origin you wander.

Half the numbers are red, half green, so you'll end up back where you started.

How far away might you get along the way? Depends on the distribution of the reds and greens. If all the reds are smaller than all the greens, you'll go left to ten thousand, then turn around and come right back. If they're all bigger, then you'll get ten thousand away to the right before you snap back like a yo-yo. And except for these cases, you won't go as far before you return.

If the numbers are from the same distribution, then whether they're red or green is a coin-toss. The distance I expect to get from the the origin goes up as the square-root of the size of my collections.

(That's on average -- any single pair of batches could end up almost anywhere. "... the 'one chance in a million' will undoubtedly occur, with no less and no more than its appropriate frequency, however surprised we may be ...." -- R. A. Fisher)

There are lots of ways to get this result:

1. from the standard deviation of a binomial with p=0.5
2. from a two-sample Kolmogorov-Smirnov statistic with equal sample sizes
3. from looking at it as Brownian motion, using the root-mean-square (RMS) argument attributed to Einstein, in Feynman, volume 1, chapter 6

All roads lead to Rome.

Note: nothing I've said, so far, depends on the numbers being random--this just tests whether the red and green numbers come from the same distribution. In what follows, though, I'm going to ask whether batches spit out by random-number generators are uniformly-distributed.

Let's write code. And, since all code roads lead to Rome, too, I'll do it in the shell.

Start with two, random-number-generators, R1 and R2 that generate some fixed-size batch of random numbers.

• Check that each one spits out the same sized batch.

$ R1 | wc -l ; R2 | wc -l

• Mark each output with a second field, saying which way each number will move my finger

$ R1 | awk '$2=1'; R2 | awk '$2=-1'

• Sort the two together, on the first column

$ sort -n <(R1 | awk '$2=1') <(R2 | awk '$2=-1')

• Run through the output, keeping track, at each step, of how far I've gotten away from the origin

$ sort -n <(R1 | awk '$2=1') <(R2 | awk '$2=-1') | awk 'pos+=$2; d = ( pos <>

Notice how I'm just recalling the last command and editing it. All this is on the command line, where I can watch the effect of each step.

• Print just the the biggest distance I get from the origin, for the whole trip

$ sort -n <(R1 | awk '$2=1') <(R2 | awk '$2=-1') | awk 'pos+=$2; d = ( pos > 0 ) ? -pos : pos; print d' | sort -n | tail -1

Easy enough. I'll try it first with a script that uses the Halgorithm:

#!/bin/bash

head -10000 /dev/urandom | tr -dc 0-9 | perl -pe 's/(.{8})/\1\n/g' | head -${1:-10000}

Whatever argument I give it on the command line tells it how many eight-digit integers to generate. [Default: 10,000]

Two runs should produce different batches, but the same distribution. I bring back the earlier command and do half a dozen runs with 100 numbers from each batch.

$ for i in {1..6}; do sort -n <(R1 100 | awk '$2=1') <(R1 100 | awk '$2=-1') | awk 'pos+=$2; d = ( pos > 0 ) ? -pos : pos; print d' | sort -n | tail -1 ; done

13

20

6

7

10

10

The average? 10.6 .

(Careful! I'm comparing the batch produced by one run of the generator with the run produced by a different batch. It tells me what to expect for different batches from the same distribution.)

More runs, a hundred instead of a dozen, just gives a more accurate average: 12.2

If it varies with the square of the size of the batches, batches of 10,000 should give numbers nearer to 120.

$ for i in {1..6}; do sort -n <(R1 | awk '">=1') <(R1 | awk '">=-1') | awk 'pos+=">; d = ( pos > 0 ) ? -pos : pos; print d' | sort -n | tail -1 ; done

90

97

71

91

105

127

Good. The average value, over 100 paired runs, is about 125.

This, finally, lets me compare Hal's method with the shell-only method from an earlier post, which uses $RANDOM? Does $RANDOM have a different distribution from /dev/urandom?

Nope. The average distance is, again, about 125. If they're non-uniform, they're non-uniform in the same way.

But maybe neither is random. What if I compare them with a batch of uniformly-distributed, true random integers, downloaded from the web?

About 135. A little higher, but not high enough to set off a panic alarm. $RANDOM and /dev/urandom both give pseudo-random-numbers that are, roughly, uniformly distributed.

Another Random Post

Hal Pomeranz suggests this one-liner

head /dev/urandom | tr -dc 0-9 | sed -r 's/(.{8})/\1\n/g'

for generating big batches of random numbers. It's a winner: reasonable performance and easy-to-type. Timing information follows:

#!/bin/bash

echo == Shell arithmetic

(( R = 2**15-1, T = 10**8-1, C = T/R ))

readonly R T C

time for i in {0..10000}

do

printf "%8.8u\n" $(( RANDOM*C + ( RANDOM%C ) ))

done > /dev/null

echo; echo == Pipeline

time head -10000 /dev/urandom | tr -dc 0-9 | sed -r 's/(.{8})/\1\n/g' | head -10000 > /dev/null

Here's the numbers:

== Shell arithmetic

real 0m0.262s

user 0m0.256s

sys 0m0.004s

== Pipeline

real 0m0.421s

user 0m0.028s

sys 0m0.392s

Okay, the pipe's a little slower, but it's the same order of magnitude, and way easier to type.

Another Challenge From Hal & Ed: Random Numbers In the Shell

Hal Pomeranz and Ed Skoudis have a weekly blog, Command Line Kung Fu, where they set and solve interesting problems in both the Unix/Linux shell and Windows's CLI, COMMAND.COM.

This week's was how to generate random 8-digit integers.

Obligatory pedantic sidebar, which you can skip:

"Random" can mean a lot of things. If I flip a coin, and announce either "00000000" or "00000001", that's an 8-digit, random number. Ho hum. What I'm looking for here is integers uniformly distributed in the interval 0000000..99999999. I'll write this as U(0,10^8-1).

The problem is trickier than you might think. For example, the shell's random-number generator, $RANDOM, is U(0,2^15-1). Not big enough.

How about, say, summing calls to $RANDOM until the number is big enough?

Nope. Adding a bunch of uniformly-distributed numbers gives a random number, all right. But it isn't uniformly distributed anymore. It's a clumped-up, bell curve.

Hal explores several routes, culminating with a good one-liner:

$ head /dev/urandom | tr -dc 0-9 | cut -c1-8

But is there a way with the shell's own built-ins?

Yep. The answer's below. What's more, because this way doesn't call outside utilities or fork subshells, it should, in theory, be faster. And it is.

How much faster?

On my machine, the one-liner above generates 10,000 random numbers in just under 40 seconds. The code below does the same 10,000 in about a quarter of a second.

I've written it out as a script, with a dramatic reading in the comments, but if I were using it in something else, I'd ditch the big comments and put the code in-line.

#!/bin/bash
## Generate a uniformly distributed,

## 8-digit, random number: U(0,99999999)

## First, the logic

# (1) Get a uniformly-distributed random number,
# N = $RANDOM, up to R = 2^15-1 = 32767.
# That's U(0,R)

# (2) Stretch out the interval covered,
# up to nearly T = 10^8-1
# by multiplying by C = K/R.
# (We'll figure out K in a minute)
# This turns 0,1, 2, 3, ... into 0, C*1, C*2, ... K

# (3) Now add a random shift S = U(0,C-1)
# to turn these into 0, 0+1, 0+2, ... 0+C-1,
# C*1+0, C*1+1, ..., K+0, K+1, ... K+C-1.
# We can get S from another random number M = $RANDOM % C
# (% is the 'mod' operator)

# What's K? We want K+C-1 = T = 10^8-1, so we solve:
# K+C-1 = K+(K/R)-1 = 10^8-1; K[ (R+1)/R ] = 10^8;
# K = (10^8)*R/(R+1)

# For big R, that's so close to T
# that I'll just use K=T, C=T/R
# Our U(0,10^8-1) number is N*C + M

## Next, the code

# calculate the constants
(( R = 2**15-1, T = 10**8-1, C = T/R ))
readonly R T C

# do the calculation, and print the result out
# with 8, full digits.
printf "%8.8u\n" $(( RANDOM*C + ( RANDOM%C ) ))

Nothing up my sleeve ... Presto! Not bad, for a shell.


Update: Hal helpfully points out several things.

• I misspelled his name.

Oof. Sorry. Fixed. Thanks.

• There may be even faster solutions.

if the task were to generate 10K 8-digit
random numbers, I'd just suck 80K digits out of /dev/urandom and
chop them up into 8-digit chunks. That would be considerably
faster than running my command line 10K times in a row.

Maybe so .... Is there a way to do that in the shell? It's thought-provoking and an interesting challenge.

You couldn't store the 80K digits in the code, but you could keep from having to store them in a file, and the attendant I/O slowdown, by just providing them as output from a pipe.

(I'm told that in Windows, pipes are implemented with intermediate files. Not so in Unix and its offspring--the system really does hand data directly from one process to another.)

So, is there an easy way, in a shell script, to pull 8 digits at a time out of standard in?

• Execution efficiency isn't why you use the shell.

If the task is to generate a single 8-digit number, I claim my solution
is better from a typing perspective. :-)

Just so. Hal's exactly right.