Demonstration of a cache to speed up the performance of a computationally expensive function

calculation_cache.c

/*
README

Simple cache program in C.
The goal here was to create a cache for the 'do_thing' function.
Theoretically do_thing would take a lot of computation and the
use of a cache would speed it up. So if a user puts in the same
value twice e.g. do_thing(2.0), do_thing(2.0) the second call
will extract the already calculated value from the cache instead
of calculating it again.


Notes:

Tradeoff: data locality vs. O(log(n)) binary search tree 

The add_to_cache function is O(1), but the get_cached_result
function is O(n) because it's iterating over the entire cache.
To make this better, we could implement an ordered cache and use
a binary search tree (O(log(n))). However in this example we use 
a static array which should keep the data clumped together in 
memory, so we have the benefit of not having cache-misses.
These days CPU's are fast enough that it might be faster to have
them all close in memory rather than dealing with a BST that
could have them spread out in memory.

*/


#include <stdio.h>

// Our original (expensive) function
float do_thing(float value){
  printf("Doing thing with %f \n", value);
  return value + 3.1415;
}

// defining cache
typedef struct {
  float value;
  float result;
} CacheEntry;

#define cacheSize 100
CacheEntry cache[cacheSize];
int cache_indx = 0;

// cache functions
void add_to_cache(float value, float result){
  if (cache_indx == cacheSize) return;

  cache[cache_indx].value = value;
  cache[cache_indx].result = result;

  cache_indx++;
}

int get_cached_result(float value, float* result_memory){
  // returns 0 for no and 1 for yes.
  for (int i=0; i<cache_indx; i++){
    if (cache[i].value == value){
      *result_memory = cache[i].result;
      return 1;
    }
  }
  return 0;
}

// new function that makes use of the cache
float do_thing_efficiently(float value){
  float result;
  if (get_cached_result(value, &result) == 1){
    printf("found in cache! \n");
    
  }
  else {
    result = do_thing(value);
    add_to_cache(value, result);
  }
  return result;
}


// demonstrating the new algorithm
int main(){
  printf("%f\n", do_thing_efficiently(4.54));
  printf("%f\n", do_thing_efficiently(4.55));
  printf("%f\n", do_thing_efficiently(4.54));

  return 0;
}


/*
=========== OUTPUT =============
Doing thing with 4.540000 
7.681500
Doing thing with 4.550000
7.691500
found in cache!
7.681500
*/