javascript

2021/12/21

Program performance: cleaner !== better

Here's how (and why) my Fibonacci sequence function runs, at minimum, 160% faster than the cleaner proposed solution.

Author: Tristan Brewster

A rare image of a SoyDev's personal machine.

Yesterday, while working on my latest project, Hydro, I wrote a function that involved some very, very elementary math. While the implementation itself is by no means monumental, it rekindled a deep appreciation of mine for mathematics.

With this reignited passion of mine, I decided to depart from my normal routine and embark on a small journey of minor mathematical algorithmic implementations in JavaScript.

After a few minutes of searching, I came upon 30 seconds of code, a site that lists a variety of common operations, algorithms, and so on—all in JavaScript.

I proposed a challenge to myself: alongisde implementing my own solution, I decided to also make my solution faster.

Here's what I learned in doing do.


Exploring numbers

About a year ago, I posted about a modified Caesar cipher I created. Instead of the traditional incremental alphabetical shift (1, 2, 3, ...), I utilized the Fibonacci sequence to shift the letters.

Therefore, abcde would become bcefj.

Anyways...

Naturally, scanning through 30 seconds of code, the Fibonacci sequence function caught my eye.

Although I successfully implemented faster solutions to a variety of their other problems, this particular problem had such an incredible result that I figured it best to write about.

Cleaner does not (always) mean better

With modern systems covering the globe, performance isn't always a top-priority for a majority of sole programmers. In fact, I myself would often prefer cleaner, clearer code than more performant code. Sometimes, the benefit of easy-to-understand code is better than a 100th of a millisecond performance improvement.

This begs the question, though: why is cleaner, shorter code often less performant? The answer may seem obvious: functions that are shorter often utilize "functional sugar," which do more under-the-hood than they appear.

Since this article is JavaScript-oriented, let's use the Array.prototype.reduce() method as an example.

Consider the following:

The reduce method being used to sum all numbers in an array

Look at that: this function is clean as hell. Anyone reading this code should have absolutely no trouble understanding what it does. The problem is, the reduce method is slow in comparison to a custom implementation.

Consider the longer, faster alternative:

A custom method being used to sum all numbers in an array

Before some of you armchair politicians repremand me, the second function is only slightly, but technically, faster.

This is precisely the point, however. Custom, more "bare metal" solutions that utilize the smallest number of standard library functions are, in general, faster. This fact just makes sense. Utilizing standard lib functions (I know "standard lib" isn't necessarily appropriate for JavaScript, but you know what I mean) are similar to making a drug deal through a middle man.

It looks like this:

Money -> Middle man -> Primary dealer

And, of course, the middle man takes a slice of the profit, making your deal less efficient for you (in general).

In programs, this philosophy also applies, albeit differently:

Operation -> Standard lib function -> Bare metal implementation

As you can guess, the standard lib function takes a "slice" of the time it would take for a custom implementation.

The trade-offs

So why do middle men and standard lib functions exist? To make your life easier.

Much in the same way that a middle man makes access to your drugs easier (in general), the standard lib functions make common operations easier, often at the (largely inconsequential) cost of run time.

Anyways... enough of the philosophic drug deal talk, let's get into the meat of the article.

The Fibonacci function

For those unfortunate souls who are unaware of the Fibonacci sequence, it looks like this:

1 1 2 3 5 8 13 21 ...

That is, the next number in the sequence is the sum of the two previous numbers. Therefore, the next value is 34.

The sequence has large applications, both in nature and mathematics, and is generally revered for its elegancy.

Even still, the programmatic implementation is elegant as well.


Let's take a look at the solution proposed by 30 seconds of code:

The Fibonacci function from 30 seconds of code

Not bad! It's clean, small, and it works. The problem: it utilizes a lot of standard lib functions: Array, reduce, and concat.

For most uses, the performance dip here isn't a huge deal.

Except, it is. And this solution has one major flaw: it hangs really bad for large values of n.

What if you want to get all Fibonacci numbers from 1 to 2,000,000?

This solution simply isn't suited for it.

Now, let's take a look at my solution:

My Fibonacci function

It's longer, more messy, and looks "much closer to the metal," so to speak. So what's the benefit?

With an n value of 200, it runs 161% faster.

Measuring performance

JavaScript has a built-in function called performance.now(). Utilizing this, I was able to measure the performance of my solution in comparison to the proposed solution.

To be fair, and to reduce as many "flukes" as possible, I didn't just test the performance of a single function call. Instead, I ran each function 100 times, pushed the performance value to an array, and then calculated the average run time for each function.

For an n value of 200 and an iteration count of 100, these were the results (in milliseconds):

  • Their function: 0.29387796971946956
  • My function: 0.03741856999695301

A percentage difference of 154%.

Not too bad! Their function still runs pretty fast. 0.2 milliseconds is largely inconsequential.

The problem is that their function is exponentially slower for greater values of n.

This is crazy.

Consider the following stats for n = 2000

  • Their function: 20.185438539981842
  • My function: 0.06339812997728586

Let's try for n = 5000:

  • Their function: 105.38415335990489
  • My function: 0.12280924994498492

What about for n = 10,000:

  • Their function: 406.9436482297257
  • My function: 0.21343793995678426

And finally, for n = 2,000,000:

  • My function: 51.06757746014744
  • Their function: I don't actually know. I let it run for a good 45 minutes, and it would not output the result. The simulator program I used actually crashed for n = 5,000,000 (crashed with their function, mind you.)

Interestingly enough, if I throw a log in the for loop, I found that, with n = 2,000,000, their function spent 45 minutes only on the first iteration. That is insane.


The point

There's no inherent "point" to this article. Instead, it provides some food for thought. In general, I think there are lots of programmers out there who think that these "standard lib" functions are perfect in implementation, and can't possibly give them any problems down the line.

Forget the performance issue with this, there could potentially be major bugs introduced by using some of these standard lib functions incorrectly. Specifically, in a manner they aren't supposed to be used for.

The next time you need to work with an array of over a million items, reconsider the functions you use.

Thanks for reading.


If you'd like to test the performance yourself, view this GitHub Gist.

End of Line.

Infinium

Building and maintaining the future of open-source.

Contact us
Copyright © 2021 Infinium LLC. All rights reserved.

This website is open-source.

Made with in Salt Lake City.