0

I needed a max function, to find the highest value in an array (of 350 int values), and being a friend of recursion, I tried a recursive approach:

max () {
    len=$#
    a=$1
    b=$2
    case $len in
        0)
            echo NaN
            ;;
        1)
            echo $1
            ;;
        2)
            (( a > b )) && echo $a || echo $b
            ;;
        *)
            shift; shift
            max $(max $a $b) $(max $@)
            ;;
    esac
}

It's scandalously slow. 2.6 s for 350 values.

Yes, the canonical unix way would be

time (echo ${yvals[@]} | tr " " "\n" | sort -n | tail -n 1 )

which takes 0,005s, and a while loop

max () {
    anz=$#
    max=$1
    while ((anz > 0))
    do
        b=$2
        (( b > max )) && max=$b
        shift
        anz=$#
    done
    echo $max
}

isn't far away with 0,010s -- well, it's twice as slow, but for such low values, the error margin might be higher, than the measured value. I'm not so much interested in the fastest performance, as long as the value count isn't too high. However, I was curious, whether gnu-parallel could bring an improvement, and for a long time, I'm waiting for an opportunity to learn more about parallel, but I prefer learning with real world examples, and rarely have examples, which might benefit from parallelizing.

So my naive approach was, to try the recursive version with

time parallel max ::: ${yvals[@]} 

and added some experimental options for parallel, like -j+0, which resulted in 350 values, each compared with nothing else, therefore being a maximum on its own. :)

Beside consulting the manpage, I watched 2 of the 4 YT-Videos from Ole Tange, the author of gnu-parallel, to find an example, close enough to my use case, to adopt it with small modifications, but didn't find any.

So I had the idea of asking at SE, but distracted from other things, I had disturbed my 6 shell windows history, so I started writing my question, and wanted to document the command, I tried, but now I wrote:

time parallel -X max ::: ${yvals[@]} 
6933
1689
23676
31553

and surprisingly, it kind of worked. Yes, 4 cores, so 4 results, easy to spot which is the maximum. And I could write a max function, which takes the maximum of these maximums.

time max $(parallel -X max ::: ${yvals[@]}) 
31553

real    0m0,501s (Only a 5th of the time, used without parallel).

So half a second is in the acceptable range for working interactively in the shell, but of course this is only by luck the right number of records, to make this experience. Is the shell known for poor performance in recursion? That's not my main question.

The main question is, whether there is a canonical way with parallel, to perform the function on the result again, which is a typical way of solving problems in functional programming, known as a fold. I guess map/reduce is in principle the same thing.

Since most of the time, data I'm working on is small, I lack the opportunity and suffering, to learn parallel in and out.

4
  • 1
    "Is the shell known for poor performance"? Yes. – Fox Feb 20 at 19:39
  • Well, the question was about recursion in the shell, which you omitted. To make fun of the shell? The while-loop is significantly faster, and shell code, too. – user unknown Feb 20 at 19:49
  • "Is the shell known for poor performance in recursion?" -- depends also on the shell. On my system, Bash takes about 3.5 s for running that with 350 numbers, while ksh takes 0.03 s. There was some other question here at some point about Bash being slow with passing a large number of parameters, but tail-call optimization (or lack of it) might also come into play. Anyway, taking a maximum of a list doesn't strike me as something that inherently requires recursion, other than for splitting it for parallel processing, so I wonder, if that's not your point here, is it just a distraction? – ilkkachu Feb 20 at 20:14
  • @ilkkachu: Well, recursion has become my default way of problem solving, since I learned a bit functional programming. Taking this way was very slow which reminded me, that I wanted to try gnu-parallel for a long time, but rarely had a case, where I thought, it could be helpful, so I gave it a try. Being stuck, I wrote a question here, and while writing, I found the main part of the solution by accident. The remark about the slow bash is only a sidenote.Maybe the case/esac part is exceptionally slow and somebody knows much more than I do? – user unknown Feb 21 at 5:00
2

Your max function runs in O(n^2) for the first 500 values in Bash. This is most likely due to you calling max with the remaining values. So these values will have to be copied.

mmax() {
    max $(seq $1)
}

seq 10000 | env_parallel --joblog bash.log mmax
(echo '#Bash';echo '#JobRuntime in seconds';field 10,4 < bash.log |sort -n) |
  head -n 1000 | plotpipe

enter image description here

For the first 1000 values the picture is a bit more muddy:

enter image description here

For ksh the first 500 values are not very clear:

enter image description here

But for 1000 values it also looks like O(n^2):

enter image description here

ksh crashes at 1237:

enter image description here

(plotpipe and field from: https://gitlab.com/ole.tange/tangetools).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.