Avoiding Unnecessary External Commands
Every line of code in a shell script takes time to execute. This section shows two examples in which avoiding unnecessary external commands results in a significant performance improvement.
In this section:
Finding the Ordinal Rank of a Character (More Quickly)
Reducing Use of the eval Builtin
Finding the Ordinal Rank of a Character (More Quickly)
The Monte Carlo method sample code, found in “An Extreme Example: The Monte Carlo (Bourne) Method for Pi,” shows a number of ways to calculate the ordinal value of a byte. The version written using a pure shell approach is painfully slow, in large part because of the loops required.
The best way to optimize performance is to find an external utility written in a compiled language that can perform the same task more easily. Thus, the solution to that performance problem was to use perl or awk to do the heavy lifting. Although they are not compiled languages, both perl and awk have compiled routines (ord and index, respectively) to find the index of a character within a string.
However, when using outside utilities is not possible, you can still reduce the complexity by executing outside tools less frequently. For example, once you have an initialized array containing all of the characters from 1–255 (skipping null), you can reduce the number of iterations by removing more than one character at a time until the character disappears, then going back by one batch of characters and working your way forward again, one character at a time.
The following code runs more than twice as fast (on average) as the purely linear search:
function ord2() |
{ |
local CH="$1" |
local STRING="" |
local OCCOPY=$ORDSTRING |
local COUNT=0; |
# Delete ten characters at a time. When this loop |
# completes, the decade containing the character |
# will be stored in LAST. |
CONT=1 |
BASE=0 |
LAST="$OCCOPY" |
while [ $CONT = 1 ] ; do |
LAST=`echo "$OCCOPY" | sed 's/^\(..........\)/\1/'` |
OCCOPY=`echo "$OCCOPY" | sed 's/^..........//'` |
CONT=`echo "$OCCOPY" | grep -c "$CH"` |
BASE=`expr $BASE + 10` |
done |
BASE=`expr $BASE - 10` |
# Search for the character in LAST. |
CONT=1; |
while [ $CONT = 1 ]; do |
# Copy the string so we know if we've stopped finding |
# non-matching characters. |
OCTEMP="$LAST" |
# echo "CH WAS $CH" |
# echo "ORDSTRING: $ORDSTRING" |
# If it's a close bracket, quote it; we don't want to |
# break the regexp. |
if [ "x$CH" = "x]" ] ; then |
CH='\]' |
fi |
# Delete a character if possible. |
LAST=$(echo "$LAST" | sed "s/^[^$CH]//"); |
# On error, we're done. |
if [ $? != 0 ] ; then CONT=0 ; fi |
# If the string didn't change, we're done. |
if [ "x$OCTEMP" = "x$LAST" ] ; then CONT=0 ; fi |
# Increment the counter so we know where we are. |
COUNT=$((COUNT + 1)) # or COUNT=$(expr $COUNT '+' 1) |
# echo "COUNT: $COUNT" |
done |
COUNT=$(($COUNT + 1 + $BASE)) # or COUNT=$(expr $COUNT '+' 1) |
# If we ran out of characters, it's a null (character 0). |
if [ "x$OCTEMP" = "x" ] ; then COUNT=0; fi |
# echo "ORD IS $COUNT"; |
# Return the ord of the character in question.... |
echo $COUNT |
# exit 0 |
} |
As you tune, you should be cognizant of the average case time. In the case of a linear search, assuming all possible character values are equally likely, the average time is half of the number of items in the list, or about 127 comparisons. Searching in units of 10, the average is about 1/10 of that plus half of 10, or about 17.69 comparisons, with a worst case of 34 comparisons. The optimal value is 16, with an average of 15.9375 comparisons, and a worst case of 30 comparisons.
Of course, you could write the code as a binary search. Because splitting a string is not easy to do quickly, a binary search works best with strings of known length in which you can cache a series of strings containing some number of periods. If you are searching a string of arbitrary length, this technique would probably be much, much slower than a linear search (unless you use bash-specific substring expansion, as described in “Truncating Strings”).
Caching the split strings increases initialization time slightly but reduces execution time by about a factor of 2 compared to the “skip 16” version. Whether that tradeoff is appropriate depends largely on how many times you need to perform this operation. If the answer is once, then the extra initialization time will likely erase any performance gain from using the binary search. If the answer is more than once, the binary search is preferable.
Listing 8-1 contains the binary search version.
Listing 8-1 A binary search version of the Bourne shell ord function
# Initialize the split strings. This code should be added to ord_init. |
SPLIT=128 |
while [ $SPLIT -ge 1 ] ; do |
COUNT=$SPLIT |
STRING="" |
while [ $COUNT -gt 0 ] ; do |
STRING="$STRING""." |
COUNT=$((COUNT - 1)) |
done |
eval "SPLIT_$SPLIT=\"$STRING\""; |
SPLIT=$((SPLIT / 2)) |
done |
function split_str() |
{ |
STR="$1" |
NUM="$2" |
SPLIT="$(eval "echo \"\$SPLIT_$NUM\"")" |
LEFT="$(echo "$STR" | sed "s/^\\($SPLIT\\).*$/\\1/")" |
RIGHT="$(echo "$STR" | sed "s/^$SPLIT//")" |
} |
function ord3() |
{ |
local CH="$1" |
OCCOPY="$ORDSTRING" |
FIRST=1; |
LAST=257 |
ord3_sub "$CH" "$ORDSTRING" $FIRST $LAST |
} |
function ord3_sub() |
{ |
local CH="$1" |
OCCOPY="$2" |
FIRST=$3 |
LAST=$4 |
# echo "FIRST: $FIRST, LAST: $LAST" |
if [ $FIRST -ne $(($LAST - 1)) ] ; then |
SPLITWIDTH=$((($LAST - $FIRST) / 2)) |
split_str "$OCCOPY" $SPLITWIDTH |
if [ $(echo "$LEFT" | grep -c "$CH") -eq 1 ] ; then |
# echo "left" |
ord3_sub "$CH" "$LEFT" $FIRST $(( $FIRST + $SPLITWIDTH )) |
else |
# echo "right" |
ord3_sub "$CH" "$RIGHT" $(( $FIRST + $SPLITWIDTH )) $LAST |
fi |
else |
echo $(( $FIRST + 1 )) |
fi |
} |
As expected, this performs significantly better, decreasing execution time by about ten percent in this case. The improved performance, however, is almost precisely offset by the extra initialization costs to enable you to split the list. That is why you should never assume that a theoretically optimal algorithm will perform better than a theoretically less optimal algorithm. In shell scripting, the performance impact of constant cost differences can easily outweigh improvements in algorithmic complexity.
Reducing Use of the eval Builtin
The eval builtin is a very powerful tool. However, it adds considerable overhead when you use it.
If you are executing the eval builtin repeatedly in a loop and do not need to use the results for intermediate calculations, it is significantly faster to store each expression as a series of semicolon-separated commands, then execute them all in a single pass at the end.
For example, the following code shifts the entries in a pseudo-array by one row:
function test1() |
{ |
X=1; XA=0 |
while [ $X -lt 5 ] ; do |
Y=1; |
while [ $Y -lt 5 ] ; do |
eval "FOO_$X""_$Y=FOO_$XA""_$Y" |
Y=`expr $Y + 1` |
done |
X=`expr $X + 1` |
XA=`expr $XA + 1` |
done |
} |
You can speed up this function by about 20% by concatenating the assignment statements into a single string and running eval only once, as show in the following example:
function test3() |
{ |
X=1; XA=0 |
LIST="" |
while [ $X -lt 5 ] ; do |
Y=1; |
while [ $Y -lt 5 ] ; do |
LIST="$LIST$SEMI""FOO_$X""_$Y=\$FOO_$XA""_$Y" |
SEMI=";" |
Y=`expr $Y + 1` |
done |
X=`expr $X + 1` |
XA=`expr $XA + 1` |
done |
# echo $LIST |
eval $LIST |
} |
An even more dramatic performance improvement comes when you can precache these commands into a variable. If you need to repeatedly execute a fairly well-defined series of statements in this way (but don’t want to waste hundreds of lines of space in your code), you can create the list of commands once, then use it repeatedly.
By caching the list of commands, the second and subsequent executions improve by about a factor of 200, which puts its performance at or near the speed of a function call with all of the assignment statements written out.
Another useful technique is to precache a dummy version of the commands, with placeholder text instead of certain values. For example, in the above code you could cache a series of statements in the form ROW_X_COL_1=ROW_Y_COL_1;, repeating for each column value. Then, when you needed to copy one row to another, you could do this:
eval `echo $ROWCOPY | sed "s/X/$DEST_ROW/g" | sed "s/Y/$SRC_ROW/g"` |
If you don’t have separate variables for source and destination rows, you might write something like the following:
eval `echo $ROWCOPY | sed "s/X/$ROW/g" | sed "s/Y/$(expr $ROW + 1)/g"` |
By writing the code in this way, you have replaced several lines of iterator code and dozens of eval instructions with a single eval instruction and two executions of sed. The resulting performance improvement is dramatic.
Last updated: 2008-04-08
  |
||
|
|
|
|
| ||
Get information on Apple products.
Visit the Apple Store online or at retail locations. 1-800-MY-APPLE Copyright © 2007 Apple Inc. All rights reserved. | Terms of use | Privacy Notice |