Why does this dynamic programming optimization actually make code slower?

This is from Leetcode problem: Concatenated Words. Below is a working solution. I added what I thought to be an optimization (see code comment), but it actually slows down the code. If I remove the wrapping if statement, it runs faster.

To me, the optimization helps avoid having to:

1. call an expensive O(n) substring()
2. check inside wordsSet
3. making an unnecessary function call to checkConcatenation

Surely if (!badStartIndices.has(end + 1)) isn't more expensive than all the above, right? Maybe it has something to do with Javascript JIT compilation? V8? Thoughts?

Use this to test: Test Case.

var findAllConcatenatedWordsInADict = function (words) {    console.time();    // 1) put all words in a set    const wordsSet = new Set(words);    let badStartIndices;      // 2) iterate words, recursively check if it's a valid word    const concatenatedWords = [];    function checkConcatenation(word, startIdx = 0, matches = 0) {      if (badStartIndices.has(startIdx)) {        return false;      }        if (startIdx === word.length && matches >= 2) {        concatenatedWords.push(word);        return true;      }        for (let end = startIdx; end < word.length; end++) {        // I ADDED THE IF STATEMENT AS AN OPTIMIZATION. BUT CODE RUNS FASTER WITHOUT IT.        // NOTE: Code is correct with & without if statement.        if (!badStartIndices.has(end + 1)) {           const curWord = word.substring(startIdx, end + 1);          if (wordsSet.has(curWord)) {            if (checkConcatenation(word, end + 1, matches + 1)) {              return true;            }          }        }      }        badStartIndices.add(startIdx);      return false;    }      for (const word of words) {      // reset memo at beginning of each word      badStartIndices = new Set();      checkConcatenation(word);    }      console.timeEnd();    return concatenatedWords;  };  

https://stackoverflow.com/questions/67443445/why-does-this-dynamic-programming-optimization-actually-make-code-slower May 08, 2021 at 10:05AM