Search code examples
c++recursionmemoization

Applying memoization makes golom sequence slower

I am trying to wrap my head around memoization using c++, and I am trying to do an example with the "golom sequence"

int main(int argc, char* argv[])
{
    std::unordered_map<int, int> hashTable;

    
    int value = 7;
    
    auto start = std::chrono::high_resolution_clock::now(); 
    std::cout << golomS(4, hashTable) << std::endl;
    auto stop = std::chrono::high_resolution_clock::now();
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::cout << golom(4) << std::endl;;
    auto stop1 = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(stop1 - start1);

    std::cout << "Time taken by function 1: "
           << duration.count() << " microseconds" << std::endl;

    
    std::cout << "Time taken by function 2: "
          << duration1.count() << " microseconds" << std::endl;
    
    return 0;
}

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1 + golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int> golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

As an output I get this:

4

4

Time taken by function 1: 687 microseconds //This is Golom S

Time taken by function 2: 242 microseconds //This is Golom

Shouldn't GolomS be faster with memoization? I tried wrapping my head around the debugger, but im not sure where the effective "slowness" is coming from.

My question is: How can I change the method I made golomS, to be faster than golom. Thank you. -Adam

Solution

  • On top of the other answers, I would like to add that this could really benefit from proper benchmarking.

    In order to get reliable results you want to run the tests multiple times, and take steps to ensure that memory caches and other system-level shenanigans aren't interfering with the results.

    Thankfully, there are libraries out there that can handle most of these complexities for us. For example, here's a better benchmark of your code using google's Benchmark library:

    N.B. the fixes proposed by the other answers have been integrated.

    #include <chrono>

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1 + golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int>& golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}


static void TestGolomb(benchmark::State& state) {
  for (auto _ : state) {
    benchmark::DoNotOptimize(golom(state.range(0)));
  }
}
BENCHMARK(TestGolomb)->DenseRange(1, 17, 2);

static void TestGolombS(benchmark::State& state) {
  for (auto _ : state) {
    // Make sure we always start from a fresh map
    std::unordered_map<int, int> golomb;

    // Ignore construction and destruction of the map
    auto start = std::chrono::high_resolution_clock::now();
    benchmark::DoNotOptimize(golomS(state.range(0), golomb));
    auto end = std::chrono::high_resolution_clock::now();

    auto elapsed_seconds =
      std::chrono::duration_cast<std::chrono::duration<double>>(
        end - start);

    state.SetIterationTime(elapsed_seconds.count());
  }
}
BENCHMARK(TestGolombS)->DenseRange(1, 17, 2);

    Which gives us the following profile suggesting that the breakeven point is around 14-15:

    Results

    see on quick-bench