7
\$\begingroup\$

I had a test task for internship where the main part was in implementing fixed size caches with different displacement policies (LRU/LFU/FIFO). I did that task, but was refused afterwards. Now I am wondering how my solution might be improved?

Requirements for an implementation are:

  • Cache must be thread-safe
  • Operations Put and Get have to be implemented (for storing and getting values by key respectively)

LRU Cache implementation:

#include <cstddef>
#include <list>
#include <mutex>
#include <stdexcept>
#include <unordered_map>
#include <utility>
#include <limits>

template <typename Key, typename Value>
class lru_cache {
 public:
  using value_type = typename std::pair<Key, Value>;
  using value_it = typename std::list<value_type>::iterator;
  using operation_guard = typename std::lock_guard<std::mutex>;

  lru_cache(size_t max_size) : max_cache_size{max_size} {
    if (max_size == 0) {
      max_cache_size = std::numeric_limits<size_t>::max();
    }
  }

  void Put(const Key& key, const Value& value) {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      if (cache_items_map.size() + 1 > max_cache_size) {
        // remove the last element from cache
        auto last = cache_items_list.crbegin();

        cache_items_map.erase(last->first);
        cache_items_list.pop_back();
      }

      cache_items_list.push_front(std::make_pair(key, value));
      cache_items_map[key] = cache_items_list.begin();
    }
    else {
      it->second->second = value;
      cache_items_list.splice(cache_items_list.cbegin(), cache_items_list,
                              it->second);
    }
  }

  const Value& Get(const Key& key) const {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      throw std::range_error("No such key in the cache");
    }
    else {
      cache_items_list.splice(cache_items_list.begin(), cache_items_list,
                              it->second);

      return it->second->second;
    }
  }

  bool Exists(const Key& key) const noexcept {
    operation_guard og{safe_op};

    return cache_items_map.find(key) != cache_items_map.end();
  }

  size_t Size() const noexcept {
    operation_guard og{safe_op};

    return cache_items_map.size();
  }

 private:
  mutable std::list<value_type> cache_items_list;
  std::unordered_map<Key, value_it> cache_items_map;
  size_t max_cache_size;
  mutable std::mutex safe_op;
};

LFU Cache implementation:

#include <algorithm>
#include <list>
#include <atomic>
#include <mutex>
#include <tuple>
#include <unordered_map>

template <typename Key, typename Value>
class lfu_cache {
 public:
  using freq_type = unsigned;
  using value_type = typename std::tuple<Key, Value, freq_type>;
  using value_it = typename std::list<value_type>::iterator;
  using operation_guard = typename std::lock_guard<std::mutex>;

  enum VTFields { key_f = 0, value_f = 1, frequency_f = 2 };

  lfu_cache(size_t max_size) : max_cache_size{max_size} {
    if (max_size == 0) {
      max_cache_size = std::numeric_limits<size_t>::max();
    }
  }

  void Put(const Key& key, const Value& value) {
    constexpr unsigned INIT_FREQ = 1;
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      if (cache_items_map.size() + 1 > max_cache_size) {
        // look for the element with the smallest frequency value
        auto least_fr =
            std::min_element(cache_items_list.cbegin(), cache_items_list.cend(),
                             [](const value_type& a, const value_type& b) {
                               return std::get<frequency_f>(a) <
                                      std::get<frequency_f>(b);
                             });

        cache_items_map.erase(std::get<key_f>(*least_fr));
        cache_items_list.erase(least_fr);
      }

      cache_items_list.emplace_front(std::make_tuple(key, value, INIT_FREQ));
      cache_items_map[key] = cache_items_list.begin();
    }
    else {
      // increase frequency of the existing value "key" and assigne new value
      std::get<value_f>(*it->second) = value;
      ++(std::get<frequency_f>(*it->second));
    }
  }

  const Value& Get(const Key& key) const {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      throw std::range_error("No such key in the cache");
    }
    else {
      // increment the frequency of the "key"-element
      ++(std::get<frequency_f>(*it->second));

      return std::get<value_f>(*it->second);
    }
  }

  bool Exists(const Key& key) const noexcept {
    operation_guard og{safe_op};

    return cache_items_map.find(key) != cache_items_map.end();
  }

  size_t Size() const noexcept {
    operation_guard og{safe_op};

    return cache_items_map.size();
  }

 private:
  mutable std::list<value_type> cache_items_list;
  std::unordered_map<Key, value_it> cache_items_map;
  size_t max_cache_size;
  mutable std::mutex safe_op;
};

FIFO Cache implementation:

#include <deque>
#include <iterator>
#include <mutex>
#include <unordered_map>
#include <utility>

template <typename Key, typename Value>
class fifo_cache {
 public:
  using value_type = typename std::pair<Key, Value>;
  using value_it = typename std::deque<value_type>::iterator;
  using operation_guard = typename std::lock_guard<std::mutex>;

  fifo_cache(size_t max_size) : max_cache_size{max_size} {
    if (max_size == 0) {
      max_cache_size = std::numeric_limits<size_t>::max();
    }
  }

  void Put(const Key& key, const Value& value) {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      if (cache_items_map.size() + 1 > max_cache_size) {
        // remove the last element from cache
        auto last = cache_items_deque.rbegin();

        cache_items_map.erase(last->first);
        cache_items_deque.pop_back();
      }

      cache_items_deque.push_front(std::make_pair(key, value));
      cache_items_map[key] = cache_items_deque.begin();
    }
    else {
      // just update value
      it->second->second = value;
    }
  }

  const Value& Get(const Key& key) const {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      throw std::range_error("No such key in the cache");
    }

    return it->second->second;
  }

  bool Exists(const Key& key) const noexcept {
    operation_guard og{safe_op};

    return cache_items_map.find(key) != cache_items_map.end();
  }

  size_t Size() const noexcept {
    operation_guard og{safe_op};

    return cache_items_map.size();
  }

 private:
  std::deque<value_type> cache_items_deque;
  std::unordered_map<Key, value_it> cache_items_map;
  size_t max_cache_size;
  mutable std::mutex safe_op;
};

EDIT: For those who are interesed in the result of refactoring link to the repo

\$\endgroup\$
1
  • \$\begingroup\$ This is a very well written program in modern C++ .. I am surprised they did not like this.. \$\endgroup\$
    – Guru
    Jun 19 '19 at 4:56
7
\$\begingroup\$

It looks like you put together a nice package given this was an internship application. You've used templates, stl, etc. and some of the newer features of C++, so in my opinion you showed a lot of promise. Perhaps there were other factors beyond your control that affected the candidate selection.

That said, to address your specific questions, here are some tips that jumped out:

1. No concrete interface defined

You were given a specification of a Get/Put interface, so it would have been nice to see an abstract base class implementation that your caches inherited from that enforced the implementation of the Get/Put methods. This provides two big advantages:

  • Future developers who want to extend your design with new cache algorithms have a 'contract' in the form of a base class they must follow which provides greater cohesion with the rest of your system.
  • Programmers wishing to use your new cache classes in their systems can maintain pointers to the base class which allows them to remain ignorant of the implementation details for each cache type. This encapsulation is very handy as your programs grow large.

2. Duplicate code

If you look at your three cache implementations, you'll notice a lot of areas that are repeated. Apart from the Get/Put methods, your thread-safety operation guards and all of your member variables could easily be pushed to a common base class. This also provides two handy features:

  • Removing the thread-safety mechanism from the 'cache-algorithm' (LRU/FIFO, LFU) decouples the two distinct problems into two separate domains. This allows the thread safety implementation to be overhauled/replaced as needed in the future without touching the core algorithm code. NOT doing this isn't a show-stopper, because your locking logic was quite small, but showing an injectable thread-locking mechanism might have scored some additional 'points' in the evaluation of your code.

  • Once you start pushing the cache_items_map, max_cache_size, safe_op members into a common base class, you'll start to notice that your 'cache-algorithm' bits of code (i.e. the actual logic for the LRU/LFU/FIFO cache lookup and rollover) is actually independent of how the data is stored in the base class. You may find that you can refactor the algorithm logic out of the class entirely into its own separate class. This would be an example of the Strategy Design Pattern

3. Test code

It's been awhile since I had to do a technical interview that involved active coding, but it's good practice to create test code for any new software you write to validate your logic. I've not actually tried to compile/run your sample code above, but are you sure it works? Sure enough to send it up on a Mars rover, put it into a medical device, monitor a nuclear facility, or perform high-frequency trades on the stock market? Providing test code provides (you guessed it) two big advantages:

  • Dogfooding: Test code requires you to use your shiny new classes as an application developer rather than an software architect. One of the best ways to streamline your software is to spend some time using it. You'll find the areas that are awkward to type, hard to instantiate, hard to delete, etc.
  • Verification: It's hard to evaluate an algorithm without running it through its paces. Does creating an instance of lfu_cache and trying to populate std::numeric_limits::max() number of ints work well? How about 256byte sized structs, or 32MB pictures? Does your rollover work properly? Does the LFU really purge the least frequently used item? etc. etc. Providing verification code details exactly how your logic performs, and provides the surety to both you (and your interviewers) that your classes will work as advertised.

Good luck with your job search. If you're writing code like pre-employment, I think you'll do just fine.

\$\endgroup\$
2
  • \$\begingroup\$ James, thank you for your feedback. According to your points: 1. I missed out on an inheritance benefits. 2. Should I throw away locks inside cache? what if several threads tries to read from caches that use policy that might change priority of stored object? \$\endgroup\$
    – vpetrigo
    May 17 '16 at 14:02
  • \$\begingroup\$ sorry for misunderstaing point 2. I read the whole your advice once again and all things seem clear to me. \$\endgroup\$
    – vpetrigo
    May 17 '16 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.