\nToday’s Little Program isn’t even a program.\nIt’s just a function.\n<\/p>\n
\nThe problem statement is as follows:\nGiven a nonempty JavaScript array of numbers,\nfind the index of the smallest value.\n(If the smallest value appears more than once,\nthen any such index is acceptable.)\n<\/p>\n
\nOne solution is simply to do the operation manually,\nsimulating how you would perform the operation with\npaper and pencil:\nYou start by saying that the first element is the winner,\nand then you go through the rest of the elements.\nIf the next element is smaller than the one you have,\nyou declare that element the new provisional winner.\n<\/p>\n
\nfunction indexOfSmallest(a) {\n var lowest = 0;\n for (var i = 1; i < a.length; i++) {\n if (a[i] < a[lowest]) lowest = i;\n }\n return lowest;\n}\n<\/pre>\n\nAnother solution is to use the reduce<\/code> intrinsic\nto run the loop, so you merely have to provide\nthe business logic of the\ninitial guess\nand the if<\/code> statement.\n<\/p>\n\nfunction indexOfSmallest(a) {\n return a.reduce(function(lowest, next, index) {\n return next < a[lowest] : index ? lowest; },\n 0);\n}\n<\/pre>\n\nA third solution is to use JavaScript intrinsics to\nfind the smallest element and then convert\nthe element to its index.\n<\/p>\n
\nfunction indexOfSmallest(a) {\n return a.indexOf(Math.min.apply(Math, a));\n}\n<\/pre>\n\nWhich one is fastest?\n<\/p>\n
\nOkay, well, first, before you decide which one is fastest,\nyou need to make sure they are all correct.\nOne thing you discover is that the min\/indexOf<\/code>\ntechnique fails once the array gets really, really large,\nor at least it does in Internet Explorer and Firefox.\n(In my case, Internet Explorer and Firefox gave up at around\n250,000 and 500,000 elements, respectively.)\nThat’s because you start hitting engine limits on the number\nof parameters you can pass to a single function.\nInvoking apply<\/code> on an array of 250,000 elements\nis the equivalent of calling min<\/code> with 250,000\nfunction parameters.\n<\/p>\n\nSo we’ll limit ourselves to arrays of length at most 250,000.\n<\/p>\n
\nBefore I share the results, I want you to guess which\nalgorithm you think will be the fastest\nand which will be the slowest.\n<\/p>\n
\nStill waiting.\n<\/p>\n
\nI expected the manual version to come in last place,\nbecause, after all, it’s doing everything manually.\nI expected the reduce version to be slightly faster,\nbecause it offloads some of the work into an intrinsic\n(though the function call overhead may have negated\nany of that improvement).\nI expected the min\/indexOf version to be fastest\nbecause nearly all the work is being done in intrinsics,\nand the cost of making two passes over the data\nwould be made up by the improved performance of the intrinsics.\n<\/p>\n
\nHere are the timings of the three versions with arrays of\ndifferent size, running on random data.\nI’ve normalized run times so that the results are independent\nof CPU speed.\n<\/p>\n
\n\n Relative running time per array element<\/b><\/font>\n<\/caption>\n\nElements<\/th>\n manual<\/th>\n reduce<\/th>\n min\/indexOf<\/th>\n<\/tr>\n \nInternet Explorer 9<\/th>\n<\/tr>\n \n100,000<\/td>\n 1.000<\/td>\n 2.155<\/td>\n 2.739<\/td>\n<\/tr>\n \n200,000<\/td>\n 1.014<\/td>\n 2.324<\/td>\n 3.099<\/td>\n<\/tr>\n \n250,000<\/td>\n 1.023<\/td>\n 2.200<\/td>\n 2.330<\/td>\n<\/tr>\n \nInternet Explorer 10<\/th>\n<\/tr>\n \n100,000<\/td>\n 1.000<\/td>\n 4.057<\/td>\n 4.302<\/td>\n<\/tr>\n \n200,000<\/td>\n 1.028<\/td>\n 4.057<\/td>\n 4.642<\/td>\n<\/tr>\n \n250,000<\/td>\n 1.019<\/td>\n 4.091<\/td>\n 4.068<\/td>\n<\/tr>\n<\/table>\n\nAre you surprised?\nI sure was!\n<\/p>\n
\nNot only did I have it completely backwards,\nbut the margin of victory for the manual version was way\nbeyond what I imagined.\n<\/p>\n
\n(This shows that the only way to know\nyour program’s performance characteristics for sure\nis to sit down and measure it<\/i>.)\n<\/p>\n
\nWhat I think is going on is that the JavaScript optimizer\ncan do a really good job of optimizing the manual code\nsince it is very simple.\nThere are no function calls, the loop body is just one line,\nit’s all right out there in the open.\nThe versions that use intrinsics end up hiding some of the\ninformation from the optimizer.\n(After all, the optimizer cannot predict ahead of time whether\nsomebody has overridden the default implementation of\nArray.prototype.reduce<\/code> or\nMath.prototype.min<\/code>,\nso it cannot blindly inline the calls.)\nThe result is that the manual version can run over twice\nas fast on IE9 and over four times as fast on IE10.\n<\/p>\n\nI got it wrong because I thought of JavaScript too much like\nan interpreted language.\nIn a purely interpreted language,\nthe overhead of the interpreter is roughly proportional\nto the number of things you ask it to do,\nas opposed to how hard it was to do any of those things.\nIt’s like a fixed service fee imposed on every transaction,\nregardless of whether the transaction was for $100 or 50 cents.\nYou therefore try to make one big purchase (call a complex intrinsic)\ninstead of a lot of small ones (read an array element,\ncompare two values, increment a variable, copy one variable to another).\n<\/p>\n
\nBonus chatter<\/b>:\nI ran the test on Firefox, too,\nbecause I happened to have it handy.\n<\/p>\n