King of the Checkers is too expensive

Once upon a time you had a great idea and created an amazing platform checkers4all.com - an online portal for all checkers lovers. Now this is a popular place for people around the world so there are 1M Unique Users daily.

For some time you had requests to create a dedicated trophy for a person with the most winned games - King of the Checkers. Now it's time to implement it fast!

The Code

So you prepared a simple javascript code to find the player with most winned games:

function findMaxSlow(arr) {
  return arr.sort((a, b) => b - a)[0];
}

Your team mate prepared another version:

function findMaxFast(arr) {
    if (arr.length === 0) return null; //Protection against empty array
    let max = -Infinity; // Use instead of `arr[0]`
    for (const num of arr) {
        if (num > max) {
            max = num;
        }
    }
    return max;
}

Implementation

Before you implement it on the websitelet’s test its efficiency. Let’s make a few assumptions:

• As mentioned there is 1M Unique Users per day
• Let’s assume each of them is reloading a main page 15 times per day - this gives us about 500M page views per month
• You don’t use any cache for showing King of the Checkers as you want them to be a real time (and you want to do it easy and fast)

Let’s use AWS Lambda to check how long each version of code will need to find a max for 1M users.

Lambda based on “sort”

export async function handler(event) {
   const numbers = Array.from({ length: 1_000_000 }, () => Math.floor(Math.random() * 1000000));
   function findMaxSlow(arr) {
       return arr.sort((a, b) => b - a)[0];  // Sortowanie całej tablicy, by znaleźć max
   }
   const maxValue = findMaxSlow(numbers);
   return {
       statusCode: 200,
       body: JSON.stringify({
           max: maxValue
       }),
   };
}

Lambda based on “for”

export async function handler(event) {
   const numbers = Array.from({ length: 1_000_000 }, () => Math.floor(Math.random() * 1000000));
   function findMaxFast(arr) {
       if (arr.length === 0) return null; //Zabezpieczenie na wypadek pustej tablicy
       let max = -Infinity; // Zamiast `arr[0]`, używamy bezpiecznej wartości
       for (const num of arr) {
           if (num > max) {
               max = num;
           }
       }
       return max;
   }
   const maxValue = findMaxFast(numbers);
   return {
       statusCode: 200,
       body: JSON.stringify({
           max: maxValue
       }),
   };
}

Tests and Costs

Tests shows that average time of execution of code based on sort is 4 times higher!

Using AWS Calculator let’s check the cost of 500M Monthly Lambda executions with assumptions:

• Architecture is based on ARM.
• Memory is 128MB
• Storage is 512MB

Price of Lambda based on on “sort”