Self-Memoizing Functions Can Be Orders of Magnitude Faster

Whenever you have a function that needs better performance, you may be able to have it memoize its results (or keep its previous results in a cache). This works for functions that are deterministic (always return the same result for the arguments passed).

For this demonstration, I have a function that indicates whether a number is prime or not. A prime number is a number greater than 1 that has no positive divisors other than 1 and itself. You can find-out more about prime number at Wikipedia here: https://en.wikipedia.org/wiki/Prime_number

My isPrime function is based on the code found here: http://studymaths.co.uk/topics/checkIfPrime.php

The method of verifying prime numbers I've implemented is called trial division which consists of testing whether a number is a multiple of any integer between 2 and its square root.

Here's my code:

Math Helper Constructor Function

The above code is memoizing its results whenever the memoize argument is true (truthy). The cache object is where the results are being cached. The cache object is made available to the isPrime function through a closure created by the JavaScript runtime.

The first piece of logic contained in the isPrime function is to check to see if it should use memoized results. If so, it checks the cache object for the number argument passed and if found it returns the result it contains.

Calculate Primes

Main

The code on lines 1-30, a constructor function named MathHelper is defined. Constructor functions are instantiated with the new keyword. The constructor takes one argument named memoize to indicate whether the isPrime function should memoize (or cache) its results.

The code on lines 33-59 determines all of the prime numbers between the values defined in the startNum and endNum arguments inclusive. The third argument, isPrime, is the function this code uses to identify prime numbers.

The code on lines 61-65 simply output results.

The code on lines 67-80 instantiate the Math Helper, initialize the startNum and endNum arguments and perform two rounds of prime number calculations while outputting the results.

With the memoize argument set to false, the results output to the console were as follows:

Results with Memoization Disabled

So, it found 1,270,607 prime numbers between 0 and 20,000,000. The first iteration took 22,578 ms (nearly 23 seconds). The second iteration took 21,784 ms (nearly 22 seconds). As you can see, both iterations took nearly the same amount of time to complete.

With the memoize argument set to true, the results output to the console were as follows:

Results with Memoization Enabled

It still found 1,270,607 prime numbers between 0 and 20,000,000. The first iteration took 21,265 ms (a little more than 21 seconds). The second iteration took 253 ms (about a quarter of a second). The second iteration was 83 times faster than the first iteration. The second iteration benefitted from the memoizing that took place during the first iteration.

Whenever you need to improve the performance of a function that produces deterministic results, designing it to memoize its results can improve performance by several orders of magnitude.