TechFindings

  head = [];
  tail = [1,2,3,4];

  permute(head,tail);

  permute( [1] , [2,3,4] )
  permute( [2] , [1,3,4] )
  permute( [3] , [1,2,4] )
  permute( [4] , [1,2,3] )

// These functions are part of a "test-class" starting like:
function testorder1() {
    var cnt = 0;

// Functional test
    this.test = function(p) {
        if ( false !== p.reduce(function(acc,val) {
            if ( false === acc || val < acc ) return false;
            return val;
        }, -1)) cnt++;
    };

// Iterative test (much faster)
    this.test = function(p) {
        var i;
        for ( i=1 ; i<p.length ; i++ ) {
            if ( p[i] < p[i-1] ) return;
        }
        cnt++;
    };

'use strict';

// UTILITIES

function arrayToNum(p, s, e) {
    var r = 0;
    var m = 1;
    var i;
    for ( i=e-1 ; s<=i ; i-- ) {
        r += m * p[i];
        m *= 10;
    }
    return r;
}

function arrayWithZeros(n) {
    var i;
    var a = new Array(n);
    for ( i=0 ; i<a.length ; i++ ) a[i] = 0;
    return a;
}


// PERMUTATION ENGINES

function permutations0(n, callback) {
}

// IMMUTABLE (SLOWEST)

function permutations1(n, callback) {
    var i;
    var numbers = [];
    for ( i=1 ; i<=n ; i++ ) numbers.push(i);
    permute1([],numbers,callback);
}

function permute1(head, tail, callback) {
    if ( 0 === tail.length ) {
        callback(head);
        return;
    }

    tail.forEach(function(t, i, a) {
        permute1( [t].concat(head),
                  a.slice(0,i).concat(a.slice(i+1)),
                  callback);

    });
}

// MUTATES ITS OWN DATA, BUT NOT ITS ARGUMENTS

function permutations2(n, callback) {
    var i;
    var numbers = [];
    for ( i=1 ; i<=n ; i++ ) numbers.push(i);
    permute2([],numbers,callback);
}

function permute2(head, tail, callback) {
    if ( 0 === tail.length ) {
        callback(head);
        return;
    }
    var h2 = [tail[0]].concat(head);
    var t2 = tail.slice(1);
    var i  = 0;
    var tmp;
    
    while (true) {
        permute2(h2, t2, callback);
        if ( i === t2.length ) return;
        tmp   = h2[0];
        h2[0] = t2[i];
        t2[i] = tmp;
        i++;
    }
}

// MUTATES ALL DATA (INTERNALLY) (FASTEST)

function permutations3(n, callback) {
    var i;
    var head  = arrayWithZeros(n);
    var tails = new Array(n+1);

    for ( i=1 ; i<=n ; i++ ) {
        tails[i] = arrayWithZeros(i);
    }

    for ( i=1 ; i<=n ; i++ ) {
        tails[n][i-1] = i;
    }

    function permute3(x) {
        var j;
        var tail_this;
        var tail_next;
        var tmp;
        if ( 0 === x ) {
            callback(head);
            return;
        }
        tail_this = tails[x];
        tail_next = tails[x-1];

        for ( j=1 ; j<x ; j++ ) {
            tail_next[j-1] = tail_this[j];
        }

        j=0;
        while ( true ) {
            head[x-1] = tail_this[j];
            permute3(x-1);
             
            j++;
            if ( j === x ) return;

            tmp            = head[x-1];
            head[x-1]      = tail_next[j-1];
            tail_next[j-1] = tmp;
        }
    }

    permute3(n);
}

// TEST FUNCTIONS

function testprint() {
    this.test = function(p) {
        console.log(JSON.stringify(p));
    };

    this.done = function() {
        return 'Done';
    };
}

// CHECKS IF PERMUTATION IS ORDERED - FUNCTIONAL (SLOWEST)

function testorder1() {
    var cnt = 0;

    this.test = function(p) {
        if ( false !== p.reduce(function(acc,val) {
            if ( false === acc || val < acc ) return false;
            return val;
        }, -1)) cnt++;
    };

    this.done = function() {
        return cnt;
    };
}

// CHECKS IF PERMUTATION IS ORDERED - IMPERATIVE (FASTEST)

function testorder2() {
    var cnt = 0;

    this.test = function(p) {
        var i;
        for ( i=1 ; i<p.length ; i++ ) {
            if ( p[i] < p[i-1] ) return;
        }
        cnt++;
    };

    this.done = function() {
        return cnt;
    };
}

// TEST FUNCTION FOR PROJECT EULER 32

function testeuler() {
    var sums = {};

    this.test = function(p) {
        var w1, w2, w;
        var m1, m2, mx;
        w =  Math.floor(p.length/2);
        w1 = 1;
        w2 = p.length - w - w1;
    
        while ( w1 <= w2 ) {
            m1 = arrayToNum(p,     0, w1      );
            m2 = arrayToNum(p,    w1, w1+w2   );
            mx = arrayToNum(p, w1+w2, p.length);
        
            if ( m1 < m2 && m1 * m2 === mx ) {
                sums['' + mx] = true;
            }
        
            w1++;
            w2--;
        }
    };

    this.done = function() {
        var i;
        var r = 0;
        for ( i in sums ) {
            r += +i;
        }
        return r;
    };
}

// MAIN PROGRAM BELOW

function processData(input, parg, targ) {
    var r;

    var test = null;
    var perm = null;

    switch ( parg ) {
    case '0':
        perm = permutations0;
        break;
    case '1':
        perm = permutations1;
        break;
    case '2':
        perm = permutations2;
        break;
    case '3':
        perm = permutations3;
        break;
    }

    switch ( targ ) {
    case 'E':
        test = new testeuler;
        break;
    case 'O1':
        test = new testorder1;
        break;
    case 'O2':
        test = new testorder2;
        break;
    case 'P':
        test = new testprint();
        break;
    }


    r = perm(+input, test.test);
    console.log(test.done());
} 

function main() {
    var input = '';
    var parg = '1';
    var targ = 'E';
    var i;

    for ( i=2 ; i<process.argv.length ; i++ ) {
        switch ( process.argv[i] ) {
        case '0':
        case '1':
        case '2':
        case '3':
            parg = process.argv[i];
            break;
        case 'E':
        case 'O1':
        case 'O2':
        case 'P':
            targ = process.argv[i];
            break;
        }
    }
    

    process.stdin.resume();
    process.stdin.setEncoding('ascii');
    process.stdin.on('data', function (s) {
        input += s;
    });

    process.stdin.on('end', function () {
       processData(input, parg, targ);
    });
}

main();

### Project Euler Test: 3 different permutation generators ###
$ echo 9 | time node projecteuler32.js 3 E
45228
8.95user ...
b$ echo 9 | time node projecteuler32.js 2 E
45228
25.03user ...
$ echo 9 | time node projecteuler32.js 1 E
45228
70.34user ...

### Simple check-order test, two different versions. Fastest permutations.
b$ echo 9 | time node projecteuler32.js 3 O1
1
23.71user ...
$ echo 9 | time node projecteuler32.js 3 O2
1
4.72user ...

function goodBadUgly_1(list) {
  var i, c;
  var ret = {
    good : [],
    bad  : [],
    ugly : []
  }
  for ( i=0 ; i<list.length ; i++ ) {
    c = list[i];
    if ( !validateItem(c) )
      ret.bad.push(c);
    else if ( uglyItem(c) )
      ret.ugly.push(c);
    else
      ret.good.push(c);
  }
  return ret;
}

function goodBadUgly_2(list) {
  return {
    good : list.filter(function(c) {
                         return validateItem(c) && !uglyItem(c);
                      }),
    bad  : list.filter(function(c) {
                         return !validateItem(c);
                      }),
    ugly : list.filter(function(c) {
                         return  validateItem(c) && uglyItem(c);
                      })
  };
}

const isPalindromeStd = (str) => {
  let a=0;
  let b=str.length-1;
  while ( a<b ) {
    if ( str[a] !== str[b] ) return false;
    a++; b--;
  }
  return true;
};

const reverseStr = (str) => {
  return Array.from(str).reverse().join('');
};

const isPalindromeRev = (str) =>  {
  return str === reverseStr(str); 
};

1. John 2017/07/15 at 19:14

   You may want to re-run your tests. My results were completely different. I ran these tests on a MacBook Air 1.6 GHz Intel Core i5, using Node 6.11, and Node 7.8 (no difference between the two). I threw in a console timer to test the actual execution time (otherwise we’d be including the loading of node itself), and they all ran in under 10ms. So performance wise they are equal. You can see the screenshots here:

   http://imgur.com/a/ALOd5

   You seem to not have taken into account Node V8’s JIT optimizations. Namely loop unrolling, which works the same whether the loop is imperative or functional. See the following youtube link for more info from one of the V8 engineers where he explains that the majority of javascript benchmarking is useless, because of the JIT optimizer. In essence, once the optimizer kicks in, we’re actually testing nothing.

   https://www.youtube.com/watch?v=65-RbBwZQdU

   Lastly, your functional variant is not pure since it modifies state (var cnt) outside it’s scope (I saw you mentioned it, just clarifying). Therefore using the Array.reduce method is needlessly verbose when you really want to bail out if the array is not sorted. There is no need to create a new array like reduce does. Performance is the same, as you can see in the images. It’s just ugly looking for no reason at all.

   EDIT: See below for an improved version using every() instead of reduce().

   If you feel my test methods were off, let me know how you'd like them to be executed.
2. zo0ok 2017/07/16 at 19:24

   John, appreciate your time and effort! I should have been more clear about how to run the tests 😳

   Try:
   $ echo 9 | time node 1 E

   (then you can replace 1 with 2 or 3, and E with O1 or O2)

   9 means that 9! permutations are tested.
   You can use a lower number obviously. The reason for the strange input format is that this was originally a HackerRank exercise using stdin rather than arguments.

   I doubt they all run in 10ms this way. I much appreciate if you run your tests again and let me know what you find.
3. zo0ok 2017/07/16 at 20:31

   Interesting video about (micro)optimization. However, I don’t think I fell into those traps (I was quite aware of all of them). In my case I input data (as a side effect) and make calculations based on it. All permutations are unique so they cant easily be optimized away. In the end I print the result (a side effect) which can never optimized away.

   It is very unlikely even for the simple check-if-array-is-ordered scenario that they JIT-compiler understands that I generate all permutations exactly one, and that exactly one permutation is the ordered one.
4. John 2017/07/16 at 23:36

   Here are the new results. I rewrote the FP function to be more expressive and faster. I also left out your Project Euler function because that’s not really testing functional programming, but rather whether mutations are faster than immutable objects (no one disagrees with that). As far as I know, FP does not forbid side effects or mutations, just asks that one contains them if they are needed.

   So really, for the tests to be fair, they should be FP vs imperative using similar data structures. These are the results I got for your sorting function variants:

   input 8: (results in seconds)

   Immutable permutations:
   –FP Variant 0.131s
   –Imperative 0.134s

   Mutates its own data, but not its args:
   –FP Variant 0.052s
   –Imperative 0.057s

   Mutates all data (internally)
   –FP Variant 0.048s
   –Imperative 0.022s

   input 9: (results in seconds)

   Immutable permutations:
   –FP Variant 0.943s
   –Imperative 0.844s

   Mutates its own data, but not its args:
   –FP Variant 0.337s
   –Imperative 0.308s

   Mutates all data (internally)
   –FP Variant 0.159s
   –Imperative 0.039s

   So as you can see, using the FP paradigm with an input of 8, the differences are negligible at no more than ~25ms.

   Using an input of 9, the differences are greater, but still negligible at no more than ~120ms. Whereas you were getting difference of ~300-500ms.

   So to say that FP is slow is incorrect according to my results. If the algorithm calls for side effects or mutations, then their use must be contained. For the other 99.99% of the app that is not performance critical, FP + immutability should run more than fast enough.

   If I made a mistake somewhere, again, let me know as I’m still learning about FP. Here’s the FP testOrder version I used that ran 100ms faster.

   this.test = p => {
           if (
               p.every((el, idx, arr) => {
                   if (idx === 0) return true;
                   return el < arr[idx - 1];
               }) !== false
           ) {
               cnt += 1;
           }
       };
   
5. zo0ok 2017/07/17 at 11:27

   Hi John!

   I do appreciate the feedback!

   First I want to say the the mystery deepens. My original 0.11s for my Imperative version, I failed to reproduce that number. It turns out (roughly) that the imperative code runs with different performance on different node versions:
   Node 5: 0.11s
   Node 6: 0.21s
   Node 8: 0.40s
   With Node 8 the “imperative advantage” is essentially gone. But not thanks to the functional approach being faster but becuase the imperative being slower. I find this strange.

   I do appreciate your contribution with every() rather than reduce(). That makes FP algorithmically equivalent with the imperative code and it is faster than the functional alternatives.

   Now, to my eye the every()-implementation is the most hard-to-read of them all. I find the usage of idx+arr breaking the cleanliness of an FP approach. This is one thing that I think is problematic with FP: it makes it hard to produce clean solutions with the right computational complexity. reduce() is more readable and clean, but obviously non optimal. every() does the right thing, but it is not clean anymore.

   You write that “FP does not forbid side effects or mutations, just asks that one contains them if they are needed”. I appreciate your pragmatic approach. I think my argument is that FP is quite hard (to do right) and when there is a dogmatic preference for “pure functions” or “use map(), reduce() for everything” the result is not good.
6. zo0ok 2017/07/17 at 11:37

   John, another thing…

   “the differences are negligible”

   For many purposes this may be true. And I am not asking for stupid microoptimization: I just prefer simple efficient code to less efficient code.

   Even thought the differences are small (in ms for a benchmark) when you have code that turns out to be performance critical (or just too slow) then “small differences everywhere” can actually make a real difference.

   If you have a loop calling a function, and the function is executed tens of thousands of times per second… and that function in turn operates on an array in non optimal way, it can start making a real difference.

   I do like
   1) Simple code
   2) The right efficient algorithm
   Often I find FP fails to deliver any of these. And as a bonus, you get more overhead with FP as well.
7. John 2017/07/17 at 18:05

   There’s a lot to cover, so bear with me till the end.

   I tested this in node 6.11, and 7.8 and I got very similar results in both. The differences you’re seeing in the node versions are most likely due to the V8 optimization engine. In the video I posted in my first comment, one of Google’s V8 engineers mentioned that Angular claimed their implementation was faster than a previous iteration, when in reality, the V8 engine had a bug that had been corrected. It’s also very likely the case with the imperative test being slower in node 8. It appears the loop is not being unrolled, and possibly bailing optimization, leading to the imperative test being slower.

   Also, I’m not being pragmatic about using mutations. It’s part of FP thinking. Those who claim mutations must never exist don’t truly understand FP. Here is an article and a university course lecture to back me up regarding the use of mutation in FP.

   What FP is “against” is uncontrolled mutation and side effects (I put “against” in quotes because totally eliminating side effects is impossible).

   https://dzone.com/articles/functional-programming-is-not-what-you-probably-th

   Notice he says “uncontrolled”. That’s the main distinction. Every side effect and mutation must be contained and controlled.

   Mutation is not uniformly evil. We’ve seen that we cannot create cyclic data (graphs) without it, for example. Many programs also require that you use mutation to maintain information.

   http://web.cs.wpi.edu/~cs2102/common/kathi-notes/mutation-part2.html

   As far as every being harder to read, I disagree. Especially if you write the tests in a true FP style, with one operation per function.

   this.test = p => {
           if (isSorted(p) !== false) {
               count += 1;
           }
       };
   
   const isSorted = p =>
       p.every((element, index, array) => {
           if (index === 0) return true;
           return element < array[index – 1];
       });
   
   or
   
   const isSorted = p =>
       p.every((element, index, array) =>
           (index === 0 ? true : element < array[index - 1]));
   

   While there is more to read, it is much clearer in intent vs a basic loop, or even your reduce variation. Another benefit of FP is knowing what each function does at first glance. Looking at the test function I can tell that if the array is sorted, we increase count by 1. The sorted function simply tells me to check that every element is sorted correctly, and if it's not, to return false and bail out.

   Your reduce version, while functional (and less verbose?), is also needlessly mentally complex.

   - First, you have to read the end of the function call to find it's starting point.
   - then check if acc === false, if not
   - check if the current value < acc and return false, if not
   - return the current value and use it as the acc.
   - then repeat for each element until you have a single, final value.

   When debugging one must keep all this state in a mental construct, which means more work than needs to be done. Especially since your function can return either false or a numerical value.

   Whereas the every version only does as much work as necessary (true to FP paradigm). IOW:

   - go through every element (el),
   - check if the index === 0 and return true. If not,
   - check if the element is less than the previous element in the array (array[index - 1), if it's not
   - return false and bail out (which is why it's faster).

   Much easier to reason about, less steps, more declarative, and with no state to keep track of. Hence no deciphering of intent, or extra mental load.

   And the overhead is minimal according to my tests. Which is why I decided to comment after running your tests. The main performance difference is in mutable state, not FP style code. And as my tests show, for performance critical ops, we can drop back to mutation. If it still needs even more micro-optimizations, then drop back to imperative. But the use cases for those are going to be minimal and contained. Which is the main benefit of the FP paradigm. Controlled mutations and side effects.
8. zo0ok 2017/07/17 at 22:30

   Thanks for your comments John!

   I cleaned up the code the way I think you meant it to be 🙂 Otherwise please let me know! It is not my intention to make you look bad by editing your comments!

   I usually just use
   <pre>
   </pre>
   …good old HTML that happens to work.

   I am not sure if you really mean?

       element < array[index-1]
   

   Should it be the other way around? (well, it matters little)

   Anyway, I am much confused about this slowdown with newer versions of Node. I will look more into it and try to make something more clear. It may of course be so that all my benchmarks from the beginning was nonsense (the way the video implied), but I really doubt it.

   I will make use of your functional code and I will think about.

   I also much appreciate the link about mutable state and FP – I have not read it yet!
9. zo0ok 2017/07/18 at 00:09

   John, I wrote a more simple test program.

   $ node ./benchmark.js 7

   'use strict';
   
   function simpleReduce(array, func, initval) {
        var i;
        var v = initval;
        for ( i=0 ; i<array.length ; i++ ) {
            v = func(v, array[i]);
        }
        return v;
   }
   
   // UTILITIES
   
   function arrayWithZeros(n) {
       var i;
       var a = new Array(n);
       for ( i=0 ; i<a.length ; i++ ) a[i] = 0;
       return a;
   }
   
   
   // PERMUTATIONS
   
   function Counter(n) {
       this.max = n;
       this.digits = arrayWithZeros(n);
   
       this.next = function() {
           var i=0;
   
           while ( i<this.max ) {
               this.digits[i]++;
               if ( this.max !== this.digits[i] ) return true;
               this.digits[i] = 0;
               i++;
           }
           return false;
       }
   }
   
   
   // TEST FUNCTIONS
   
   function testorderPrint(p) {
       console.log('    ' + p);
       return true;
   }
   
   function testorderReduce(p) {
       return p.reduce(function(acc,val) {
           if ( false === acc || val <= acc ) return false;
           return val;
       }, -1);
   }
   
   function testorderEvery(p) { 
       return p.every((el, idx, arr) => {
           if (idx === 0) return true;
           return el > arr[idx - 1];
       });
   }
   function testorderSimpleReduce(p) {
       return simpleReduce(p,function(acc,val) {
           if ( false === acc || val <= acc ) return false;
           return val;
       });
   }
   
   function testorderImperative(p) {
       var i;
       for ( i=1 ; i<p.length ; i++ ) {
           if ( p[i] <= p[i-1] ) return false;
       }
       return true;
   }
   
   var tests = {
   //  'Print'         : testorderPrint,
       'Imperative'    : testorderImperative,
       'SimpleReduce'  : testorderSimpleReduce,
       'Every'         : testorderEvery,
       'Reduce'        : testorderReduce
   };
   
   function testrun(testsize, testfunc) {
       var c = new Counter(testsize);
       var r = 0;
   
       do {
           if ( false !== testfunc(c.digits) ) r++;
       } while ( c.next() );
       return r;
   }
   
   function testruns(testsize) {
       var t;
       var t0, t1;
       var r;
       for ( t in tests ) {
           t0 = Date.now();
           r = testrun(testsize, tests[t]);
           t1 = Date.now();
           console.log('  ' + (t1-t0) + ' ms : ' + t + ' (r=' + r + ')');
       }
   }
   
   function main() {
       var testsize = 0;
   
       switch ( process.argv.length ) {
       case 0:
       case 1:
       case 2:
           break; // very unlikely
       case 3:
           testsize = +(process.argv[2]);
           break;
       default:
           console.log('Only one argument allowed');
           return;
       }
   
       console.log('** Warming up (5) **');
       testruns(5);
   
       if ( 0 < testsize && testsize < 16 ) {
           console.log('** Actual Run (size=' + testsize + ') **');
           testruns(testsize);
   
           console.log('** Actual Run (size=' + testsize + ') **');
           testruns(testsize);
       }
   }
   
   main();
   

   Apart from simplifying it I also wanted to isolate the testorder-function more, so now the permutation function is trivial and cheaper.
10. John 2017/07/18 at 01:29

    Yeah, you corrected it properly. I used the code tag, not the pre. That’s prob why it came out weird. I really do appreciate you taking the time to test this out with me. Like I said, I’m just getting into FP and running these tests is really helping me. Hope it’s the same for you. 😀

    Now, I did find a bug in the Counter function that for some reason is slowing down the FP code. I added a console.time to the function as shown in the code block below, and here’s the output I got. I used a size of 8 because the bug caused 9 perms to crash on my machine.

    ** Actual Run (size=8) **
    counter: 1882.894ms
    1884 ms : Every (r=1)

    counter: 511.657ms
    512 ms : Imperative (r=1)

    counter: 2295.055ms
    2295 ms : SimpleReduce (r=1)

    counter: 4444.126ms
    4445 ms : Reduce (r=1)

    As you can see, if you discount the time spent in the counter function, the execution times are consistent with my previous findings. I can’t trace the root of the bug though. It looks like it shouldn’t make a difference, so it’s probably a V8 optimization issue, more than a FP issue. Let me know if you get the same results.

    function Counter(n) {
        console.time('counter');
        this.max = n;
        this.digits = arrayWithZeros(n);
    
        this.next = function () {
            let i = 0;
    
            while (i < this.max) {
                this.digits[i]++;
                if (this.max !== this.digits[i]) return true;
                this.digits[i] = 0;
                i++;
            }
            console.timeEnd('counter');
            return false;
        };
    }
    
11. John 2017/07/18 at 08:57

    Ok, I’m back. lol. After extensive testing, it’s not a bug after all, but rather that your new algorithm is now iterating over many more arrays than before, and I foolishly assumed you just refactored the original. For a size of 6, there are 46,656. For 7 there are 823,543 different arrays. For 8, a total of 16,777,216.

    I must say, this is a pretty clever algorithm that eventually broke the native every method. So I asked around and I came to understand that we weren’t inherently testing FP, instead we were testing Javascript’s functional algorithm. So I modified lodash’s version to decrement vs increment the loop, which gained me an extra 80ms and it produces results which are much, much better. The updated code is at the end. Here are my new results:

    ** Actual Run (size=6; 46,656 arrays) **
    3 ms : Imperative (r=1)
    4 ms : Every Lodash (r=1)
    22 ms : Native Every (r=1)

    ** Actual Run (size=7; 823,543 arrays) **
    41 ms : Imperative (r=1)
    79 ms : Every Lodash (r=1)
    122 ms : Native Every (r=1)

    ** Actual Run (size=8; 16,777,216 arrays) **
    835 ms : Imperative (r=1)
    1530 ms : Every Lodash (r=1)
    2485 ms : Native Every (r=1)

    So as you can see, the differences are still negligible up until 823,543 iterations of an array with 7 items. Even at 16,777,216 iterations it’s still less than a 1 second difference. The native Every method however falls for reasons unbeknownst to me.

    My takeaway is that the native Javascript methods may not be adequate performance-wise. Actually, they most definitely aren’t. But that doesn’t mean FP is inherently slow since it boils down to the algorithm used. And as you can see below, we maintain pure functions and still don’t lose the clarity of intent or the reusability of our functions.

    Lodash Every refactored:

    const every = (array, predicate) => {
        let index = array == null ? 0 : array.length;
    
        while (--index > 0) {
            if (!predicate(array[index], index, array)) {
                return false;
            }
        }
        return true;
    };
    

    testOrderEvery callback:

        const testorderEveryLodash = testArr =>
            every(testArr, (el, idx, arr) => el > arr[idx - 1]);
    
12. zo0ok 2017/07/18 at 10:05

    So, I ignore your thoughts about timing inside the counter function, right?

    I did some tests the other day replacing the test-order-function with a native C++ function. That was slower. It seems the transition between JavaScript-JIT and Native is not for free. I think that is why rewriting reduce(), every() in JavaScript beats standard library!

    When it comes to “negligable”… in real code you wouldn’t do the same testorder on millions of arrays over and over again. But when real code gets slow (and it does) some time is spent on value adding things, and some time is spent on overhead (using map() instead of for() ).

    If you run code when your user clicks a button in the GUI: is 5ms negligable? 25ms? 100ms?
    If you run code for every HTTP request, 5ms overhead significantly limits the number of requests per second you can handle.

    I am not saying 16M element array is reasonable. But you may have 5-10MB of data in memory and you may need to scan through it several times to update your GUI or produce an HTTP response.

    When it comes to your optimized every(): The good thing is that you could eliminate the expensive branch if index=0 (it gets expensive since it happens in every call). But FP is about clarity and being generic first. Now you have reinvented every() and created an everyTheFirst(). That is neither clear nor generic 🙂 I think already using arr[idx – 1] is… well not as clear as just using one “el” at a time.

    The clear thing would perhaps have been to invent an everyPair() function, which would allow something like:

    const testorderX = testArr =>
        everyPair(testArr, (e0, e1) =< e0 < e1);
    

    But if there is often a need for a specialised replacement of map(), reduce(), every() then the benefit of clarity and being generic is a bit lost.

    The imperative code is:
    a) arguably as simple as any functional code
    b) fastest

    I dont mind FP in general, but it is important to see its value and its limitations.

    Look here: There is a "Functional Style (recommended)" and an "Imperative Style".
    It just does not make sense.
    https://www.rosettacode.org/wiki/Luhn_test_of_credit_card_numbers#Scala
13. John 2017/07/18 at 18:22

    I’ll address each of your points. But first, to clarify, we are no longer talking about whether FP is problematically slow, but entering the realm of subjective coding preferences.

    1.
    Even under your examples of GUI interaction or data management, I’d still say it’s negligible in our multi-core world. FP is thread safe. So spreading out your operations over multiple cores would be trivial. Besides, Erlang is a FP language and powers cellphone switches because it guarantees uptime to up to 9 nines. That’s 99.9999999% of uptime (or roughly 30ms of downtime per year). And I don’t see many other heavier uses of ops than cellphone switches. So I already knew that FP works at scale. I was more interested of its use for webapps and UI, which this test helped me settle on.

    For parallelism, I’ll refer you back to my previous comment’s link, but this time in reference to parallel computing at Google

    A friend of mine is on the Google Chrome team. These are his comments on the role of functional programming (versus mutation-based programming) at Google.

    What should be type of a search method be? Assume we want (roughly) the same results each time we search on the same terms.

    String -> results

    What’s the type of a typical command in a system for searching for flights (for example)?

    flight-constraints -> void

    Both of these operations search massive amounts of data. We therefore want to distribute the computation into smaller chucks that different machines can run in parallel. Which of these two type contracts is easier to parallelize?

    Relying on state complicates handling many real-world problems:
    Functional code is easy to parallelize; mutation-based code is not.

    The average PC stays up roughly 2 months without crashing. If you build your infrastructure on thousands of cheap machines, you’ll have one failing every few minutes. You must be able to move computations to new machines when a machine goes down.

    Testing is much harder with shared state or lots of local state.

    How do you schedule updates to highly-shared data structures when machines might die mid-computation? Functions have to return effects (ie, operations to perform on data). Now, highly-parallel algorithms such as map-reduce can work with the results.

    http://web.cs.wpi.edu/~cs2102/common/kathi-notes/mutation-part2.html

    2.
    You claim I reinvented every into an everyFirst function. That’s completely wrong. I’ve decoupled my every function and made it reusable, which is one of the major benefits of FP. Check this out. (I also removed the extra element because, at least to you, it was harder to read.)

    **Checks if every element is 2x the previous

    const testDouble= testArr =>
    every(testArr, (_, idx, arr) => arr[idx] === arr[idx – 1] * 2);

    **Checks if every element is sorted in decrementing order

    const testDouble= testArr =>
    every(testArr, (_, idx, arr) => arr[idx] >= arr[idx – 1] );

    I could literally make any test that takes advantage of my every function to compare each element in an array. You’d have to rewrite your imperative code for all possible use cases. And repetition is a code smell. To make an everyPair function defeats the purpose of FP and reusable code, just for the sake of using a few less letters.

    You also say using el <= arr[idx -1] is “not as clear as just using one “el” at a time.” Yet, your imperative code shows this:

    p[i] <= p[i – 1]

    It’s literally the same exaction notation (except I used 4 more letters?). But that’s just personal preference at this point. Nothing about either is inherently more difficult to read.

    3.
    I don’t know scala, but that looks extremely overly and needlessly complex. And that code isn’t vetted. So some random on the internet wrote it, meaning that it can’t be used as the bible of what FP code should look like. Instead, look at this imperative vs FP code. Tell me which is more readable. Yet, the poster claims some of his students still found the original easier to understand. It’s just a matter of “learning to think in FP”. And we all know that programmers don’t like learning new ways of doing things. 😆

    https://softwareengineering.stackexchange.com/a/158721/6605

    4.
    Most importantly, I’d say that FP is hard to do right. Not because it’s inherently hard, but because most people claiming to be FP’ers are not really coding in the paradigm. And that is probably because the first paradigm most of us learn is imperative. I must reiterate:

    Using functional methods is not the definition of Functional Programming

    And that’s where I see a lot of people go wrong. To claim that is akin to claiming to use OOP simply because one uses objects. OOP without inheritance is like FP without modular, reusable functions. Non-existent.

    So really, the FP I wrote is:
    1. Just as readable as the imperative version
    2. More modular, leading to reusable code, hence less places for bugs
    3. Just as fast except for micro-optimizations

    I’m sorry, but according to my test results, FP sucking because it’s slow is not a reality.

    I do thank you for setting up this test because I learned a lot trying to make them equal. Your last test was especially convincing and proved to me that FP in Javascript is not performant, not because of FP, but because of ECMA’s algorithms. Should I need something more performant, refactoring the methods won’t be an issue.

    In the end it comes down to preference in style. What you find readable, I find verbose, and vice-versa. What you find easier to debug, I may not. And that’s ok. But objectively speaking, FP is on par with imperative.
14. zo0ok 2017/07/18 at 23:11

    John, you are very reasonable and mostly correct 🙂

    We very much agree about:

    
    Using functional methods is not the definition of Functional Programming.
    And that’s where I see a lot of people go wrong. To claim that is akin to
    claiming to use OOP simply because one uses objects. OOP without inheritance
    is like FP without modular, reusable functions. Non-existent.”
    

    My problem is I work with (relatively junior) programmers in JavaScript exclusively (and JavaScript is not multithreaded anywhere ever).
    I see code like this (really):

      a.forEach(function(v0,i0,a0) {
        b.forEach(function(v1,i1,a1) {
          if ( i0 == i1 ) {
            ...
          }
        })
      })
    

    …and programmers dont want to replace it with a single for-loop becuase for-loops are bad and FP is great and lamda functions are cool.

    (to me) A functional approach would be to write a NAMED PURE function of the true loop body (…).
    If the loop itself happens to be a while-loop, a for-loop or something else: use the simplest solution. Not two nested forEach.

    And I just hear: its better, its testable, its fast enough…

    I always pick the most simple algorithm and implementation.
    In the orginal code there was a “pure nothing mutable” vs a “all mutable” implementation.
    I much prefer the pure functional code because it is so much easier. If it is not fast enough I can optimize it later.

    I am fine with FP. Really.
    But “FP-hype” is making real programmers write a lot of horrible code “in the name of FP”.
    I just want to call out this madness.

    My little series of FP-sucks is about making people think and consider (and understand) what they really do. And admittedly I found nothing on Google when I searched for FP sucks so I decided to fill that spot.

    I think it is highly confusing to make a new “every” function that omits the first element.
    I think (just like you) it is great to make and reuse an “everyExceptTheFirst” function (or an everyPair function). But I am sceptical to the widespread use of the index and array parameters becuase that was not how they were meant to be used.

    Well, I am a little behind, still looking forward to reading your article about mutable data!
15. John 2017/07/19 at 00:59

    First, anyone who’s using a nested forEach loop should be shot on site 👿 That’s the worst piece of evil to bestow on other’s eyes. FP is about small, modular decoupled code. Emphasis on small. Your approach is actually more functional than theirs I’d say. I doubt there’s anything decoupled from their implementation.

    I honestly thank you for challenging me to think this thoroughly. You say there’s no FP sucks articles out there, and I’d counter there’s very little ‘this is what FP actually is’. I agree that nearly all of it is hype, with little substance. This gitbook cleared things up for me and mostly stayed away from math and hype. I’d suggest anyone that’s lost on FP concepts to read it.

    https://drboolean.gitbooks.io/mostly-adequate-guide

    If anyone is interested in seeing a better example of FP composition, I wrote some code in the comments of your other article over here:

    http://techfindings.one/archives/2652/comment-page-1#comment-24308

    As for rewriting the every, there’s no need. As we saw in the test, iterating through 47K arrays was more than fast enough. Anyone getting more than 47k requests per second has problems that we all wish we had. And at that point, you can rewrite it, use a library, or spawn web workers/child processes in node and go ‘multi-threaded’. Yes, I know javascript is essentially single threaded. But you can spawn multiple processes and use more threads. Otherwise node would not have a foothold in the corporate world.

    I’d love to write an article about mutable data! But I’m still too green with FP to even consider writing one word of objective truth. My comments here were mostly about playing devil’s advocate, and in return I actually ended up learning even more about FP.
16. zo0ok 2017/07/19 at 20:52

    Thank you John! I will read your links, hopefully tomorrow!
    And I will write a little introduction to this post: obviously the idea is not to prove that FP always sucks because it is slow.
17. Functional Programming is Slow – revisited | TechFindings - pingback on 2020/11/07 at 19:34

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Copyright © 2023 TechFindings | Powered by zBench and WordPress