why is this bash code so slow in comparison to corresponding cpp code?

Viewed 175

I am new to OS as it was introduced to us very recently. we have bash code to run as our lap experiments. my last task was to code a program to print whether a number is prime or not. i coded it first in cpp because i am comfortable in cpp. and then coded same in bash after lot of googling. but my bash code is very slower than the cpp code.

I wrote a cpp code to check whether a number is prime or not. cpp code :

#include <iostream>
using namespace std;

bool isprime(int a) {
    if (a == 2 || a == 3)
        return true;
    if (a % 2 == 0)
        return false;
    if (a % 3 == 0)
        return false;
    for (int i = 1; (6 * i - 1) * (6 * i - i) <= a; ++i) {
        if (a % (6 * i - 1) == 0)
            return false;
        if (a % (6 * i + 1) == 0)
            return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    cout << ((isprime(n)) ? "Prime" : "Not Prime") << endl;
    return 0;
}

I wrote the same code in bash (linux):

read num
f=1
if test $num -eq 2
  then f=1
elif test $num -eq 3
  then f=1
elif  test `expr $num % 2` -eq 0
  then f=0
elif test `expr $num % 3` -eq 0
  then f=0
else
  for (( i=1; $((`expr i\*6-1`))**2 <= num; i++))
  do
    t=`expr $i \* 6 - 1`
    if test `expr $num % $t` -eq 0
    then
      f=0
    fi
    t=`expr $i \* 6 + 1`
    if test `expr $num % $t` -eq 0
    then
      f=0
    fi
  done
fi

if test $f -eq 1
then
  echo 'Prime'
else
  echo 'Not-Prime'
fi

but cpp code is very fast and bash code is very slow here is terminal input and output

a@a:~/Cp$ cat > input
1000000007
^?^C
a@a:~/Cp$ time ./a.out < input
Prime

real    0m0.003s
user    0m0.003s
sys 0m0.000s
a@a:~/Cp$ time ./prog.sh <input
^C
real    0m8.258s
user    0m5.906s
sys 0m2.794s
a@a:~/Cp$ # I interrupted the execution.

I have no idea why is this happening?

3 Answers

The C++ as other compiled languages have for sure a better performance with respect to interpreted languages like bash, sh, python.

This because when you use a compiled program, only a process is launched, while when you run an interpreted program it instatiates a great number of subprocesses also for basic operation.

So is trivial that c++ program is faster than the bash one.

There's not much to the code other than tests and math, but you are spending a lot of time on those individual bash-level commands.

We can eliminate the overhead of the bash-level command/process calls by pushing all of the code down into a single awk call.

Here's a verbose copy of your bash code running in awk:

$ cat isprime
#!/usr/bin/bash
input=${1}                                                 # user's input number;
                                                           # OP will probably want to add some logic to validate the input as numeric

awk -v num="${input}" '                                    # pass input number to awk in 'num' variable
BEGIN { f=1 }                                              # init our flag
      {        if (  num      == 2 ) { f=1 }
          else if (  num      == 3 ) { f=1 }
          else if ( (num % 2) == 0 ) { f=0 }
          else if ( (num % 3) == 0 ) { f=0 }
          else for ( i=1 ; (i*6-1)**2 <= num ; i++ ) {
                   t=(i*6-1)
                   if ( (num % t) == 0 ) { f=0 ; break }   # for non-prime numbers we can abort the for loop to save some cycles
                   t=(i*6+1)
                   if ( (num % t) == 0 ) { f=0 ; break }   # for non-prime numbers we can abort the for loop to save some cycles
               }
      }
END { msg="Prime"
      if ( f == 0 ) { msg="Not-Prime" }
      print msg                                            # print our finding to stdout
    }
' <<< ""                                                   # awk needs a 'file' to work on so we'll feed it an empty here-string

Timing this script for the sample number '1000000007` gives us:

$ time ./isprime 1000000007
Prime

real    0m0.262s
user    0m0.061s
sys     0m0.170s

NOTE: Repeated runs of the above test showed real run times ranging from 0m0.082s to 0m0.262s; the wide range of numbers is due to me running the above under cygwin in a Windows7 VM; I would expect more consistent run times (towards the lower end?) in a linux environment; ymmv ...

And a non-prime test:

$ time ./isprime 1000000006
Not-Prime

real    0m0.125s
user    0m0.015s
sys     0m0.045s

Not as fast as the C++ program but definitely a good bit faster than processing all those individual bash-level test/process calls.

There are a few awkisms that could be added to shave some additional time off the run but for the sake of this answer I wanted to make it as easy as possible to compare the code with the OPs C++/shell code snippets.


The usefulness of this awk solution will be based on the size of the input (number).

Testing the above against some 20-24 digit primes shows this awk solution immediately bails on the %2==0 or %3==0 tests. This comes down to numerical limits in a basic awk implementation.

From my man pages for awk:

-M
--bignum
    Force arbitrary precision arithmetic on numbers. This option has no effect if gawk is  not  compiled  to
    use the GNU MPFR and GMP libraries.  (In such a case, gawk issues a warning.)

Adding the -M flag to the above awk solution does allow the script to work on a 21-digit prime, but it's not fast ...

awk -M -v num="${input}" ' ...

# and then:

$ time ./isprime 998887766553300224411
... as I type this it's going on 8 minutess of 100% cpu utilization (total of a single core)
... aborted after 13 minutes

While I have no doubt this awk solution would eventually complete, the basic fact is it's going to take a looooong time to count from 1 to a 21-digit number by increments of 1 (i++) (this will be true for any implementation whether it be bash, awk, C++, etc).

For really large numbers I'd be looking at other (much more complex) algorithms for verifying a number is a prime.

This is a much faster bash version

read num
f=1
if test $num -eq 2 -o $num -eq 3
  then f=1
elif  (( num % 2 == 0 || num % 3 == 0 ))
  then f=0
else
  for (( i=1; ; i++)); do
    t=$((i * 6 - 1))
    (( t * t > num )) && break
    (( num % t == 0 || num % (i * 6 + 1) == 0 )) && { f=0; break; }
  done
fi

if test $f -eq 1; then
  echo 'Prime'
else
  echo 'Not-Prime'
fi

All calls to expr have been removed.

time bash test.sh <<< 1000000007
Prime

real    0m0.128s
user    0m0.000s
sys     0m0.094s
Related