Skip to content

Commit 1e5ef1f

Browse files
srhsrh
committed
Revamp LRU cache
Has the effect of fixing the bug in the LRU cache where (a) it doesn't actually cache non-empty keys (b) the empty key's entry gets pointed at the most recent non-empty value
1 parent 5d6f196 commit 1e5ef1f

File tree

3 files changed

+85
-154
lines changed

3 files changed

+85
-154
lines changed

‎src/containers/lru_cache.hpp‎

Lines changed: 49 additions & 91 deletions
Original file line numberDiff line numberDiff line change
@@ -1,111 +1,69 @@
11
#ifndef CONTAINERS_LRU_CACHE_HPP_
22
#define CONTAINERS_LRU_CACHE_HPP_
33

4-
#include <map>
4+
#include <unordered_map>
55
#include <list>
66

77
#include "errors.hpp"
88

9-
template <typename K, typename V>
9+
template <class K, class V>
1010
class lru_cache_t {
1111
public:
12-
typedef K key_type;
13-
typedef V value_type;
14-
typedef V &reference;
15-
typedef const V &const_reference;
16-
17-
typedef std::pair<K, V> entry_pair_t;
18-
typedef std::list<entry_pair_t> cache_list_t;
19-
typedef std::map<K, typename cache_list_t::iterator> cache_map_t;
20-
21-
typedef typename cache_list_t::iterator iterator;
22-
typedef typename cache_list_t::const_iterator const_iterator;
23-
typedef typename cache_list_t::reverse_iterator reverse_iterator;
24-
typedef typename cache_list_t::const_reverse_iterator const_reverse_iterator;
25-
26-
private:
27-
// Cache entries, ordered by access time (so cache_list_.begin() points to the
28-
// most recently accessed entry).
29-
cache_list_t cache_list_;
30-
// Map from key values to position in cache list.
31-
cache_map_t cache_map_;
32-
size_t _max;
33-
public:
34-
explicit lru_cache_t(size_t max) : cache_list_(), cache_map_(), _max(max) {}
35-
36-
// These iterators can be invalidated if someone uses `[]` or `find`; specifically
37-
// it can be the case (particularly with the end positions) that the object you're
38-
// looking at can be recycled by the LRU cache as you insert new entries.
39-
iterator begin() { return cache_list_.begin(); }
40-
const_iterator begin() const { return cache_list_.cbegin(); }
41-
const_iterator cbegin() const { return cache_list_.cbegin(); }
42-
iterator end() { return cache_list_.end(); }
43-
const_iterator end() const { return cache_list_.cend(); }
44-
const_iterator cend() const { return cache_list_.cend(); }
45-
46-
reverse_iterator rbegin() { return cache_list_.rbegin(); }
47-
const_reverse_iterator rbegin() const { return cache_list_.crbegin(); }
48-
const_reverse_iterator crbegin() const { return cache_list_.crbegin(); }
49-
reverse_iterator rend() { return cache_list_.rend(); }
50-
const_reverse_iterator rend() const { return cache_list_.crend(); }
51-
const_reverse_iterator crend() const { return cache_list_.crend(); }
52-
53-
size_t size() const { return cache_list_.size(); }
54-
size_t max_size() const { return _max; }
55-
bool empty() const { return cache_list_.empty(); }
56-
57-
V &operator[](const K &key) {
58-
auto search = cache_map_.find(key);
59-
if (search != cache_map_.end()) {
60-
bump(search);
61-
return search->second->second;
62-
} else {
63-
return insert(K(key));
64-
}
12+
explicit lru_cache_t(size_t max_size) : list_(), map_(), max_size_(max_size) {
13+
guarantee(max_size > 0);
6514
}
66-
V &operator[](K &&key) {
67-
auto search = cache_map_.find(key);
68-
if (search != cache_map_.end()) {
69-
bump(search);
70-
return search->second->second;
15+
16+
size_t max_size() const { return max_size_; }
17+
size_t size() const { return map_.size(); }
18+
19+
// Looks up a key, sets *out to point at its value, and marks the entry 'most
20+
// recently used'. Returns false if the key is not found.
21+
bool lookup(const K &key, V **out) {
22+
auto it = map_.find(key);
23+
if (it != map_.end()) {
24+
list_iterator list_iter = it->second;
25+
list_.splice(list_.end(), list_, list_iter);
26+
*out = &list_iter->second;
27+
return true;
7128
} else {
72-
return insert(std::move(key));
29+
*out = nullptr;
30+
return false;
7331
}
7432
}
75-
iterator find(const K &key) {
76-
auto search = cache_map_.find(key);
77-
if (search != cache_map_.end()) {
78-
bump(search);
79-
return search->second;
33+
34+
// Returns true if an insertion was performed. (Does nothing, doesn't even update
35+
// LRU, if no insertion was performed.)
36+
bool insert(K key, V value) {
37+
auto it = map_.find(key);
38+
if (it != map_.end()) {
39+
return false;
8040
} else {
81-
return cache_list_.end();
41+
if (map_.size() == max_size_) {
42+
list_iterator evictee = list_.begin();
43+
DEBUG_VAR size_t count = map_.erase(evictee->first);
44+
rassert(count == 1);
45+
list_.pop_front();
46+
}
47+
48+
list_.push_back(std::make_pair(key, std::move(value)));
49+
list_iterator list_iter = list_.end();
50+
--list_iter;
51+
DEBUG_VAR auto res = map_.emplace(std::move(key), list_iter);
52+
rassert(res.second);
53+
return true;
8254
}
8355
}
56+
8457
private:
85-
V &insert(const K &key) {
86-
cache_list_.push_front(std::make_pair(key, V()));
87-
cache_map_[key] = cache_list_.begin();
88-
if (cache_list_.size() > _max) {
89-
cache_map_.erase(cache_list_.back().first);
90-
cache_list_.pop_back();
91-
}
92-
return cache_list_.begin()->second;
93-
}
94-
V &insert(K &&key) {
95-
cache_list_.push_front(std::make_pair(std::move(key), V()));
96-
cache_map_[key] = cache_list_.begin();
97-
if (cache_list_.size() > _max) {
98-
cache_map_.erase(cache_list_.back().first);
99-
cache_list_.pop_back();
100-
}
101-
return cache_list_.begin()->second;
102-
}
103-
void bump(const typename cache_map_t::iterator &it) {
104-
entry_pair_t pair = *(it->second);
105-
cache_list_.erase(it->second);
106-
cache_list_.push_front(std::move(pair));
107-
it->second = cache_list_.begin();
108-
}
58+
using list_iterator = typename std::list<std::pair<K, V>>::iterator;
59+
60+
// Elements are pushed onto the back and popped (when evicted) off the front.
61+
std::list<std::pair<K, V>> list_;
62+
std::unordered_map<K, list_iterator> map_;
63+
64+
size_t max_size_;
65+
66+
DISABLE_COPYING(lru_cache_t);
10967
};
11068

11169
#endif // CONTAINERS_LRU_CACHE_HPP_

‎src/rdb_protocol/terms/string.cc‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -65,8 +65,8 @@ class match_term_t : public op_term_t {
6565
std::string re = args->arg(env, 1)->as_str().to_std();
6666
std::shared_ptr<re2::RE2> regexp;
6767
regex_cache_t &cache = env->env->regex_cache();
68-
auto search = cache.regexes.find(re);
69-
if (search == cache.regexes.end()) {
68+
std::shared_ptr<re2::RE2> *found;
69+
if (!cache.regexes.lookup(re, &found)) {
7070
regexp.reset(new re2::RE2(re, re2::RE2::Quiet));
7171
if (!regexp->ok()) {
7272
rfail(base_exc_t::LOGIC,
@@ -75,9 +75,9 @@ class match_term_t : public op_term_t {
7575
regexp->error_arg().c_str(),
7676
regexp->error().c_str());
7777
}
78-
cache.regexes[re] = regexp;
78+
cache.regexes.insert(re, regexp);
7979
} else {
80-
regexp = search->second;
80+
regexp = *found;
8181
}
8282
r_sanity_check(static_cast<bool>(regexp));
8383
// We add 1 to account for $0.

‎src/unittest/lru_cache_test.cc‎

Lines changed: 32 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -4,65 +4,38 @@
44

55
namespace unittest {
66

7-
TEST(LRUCacheTest, Simple) {
8-
lru_cache_t<int, int> cache(10);
9-
cache[4] = 5;
10-
cache[8] = 10;
11-
cache[0] = 12;
12-
EXPECT_EQ(10, cache.max_size()) << "cache max size is not correct";
13-
EXPECT_EQ(3, cache.size()) << "cache current size is not correct";
14-
EXPECT_EQ(10, cache[8]) << "cache [] is not correct";
15-
cache[4] = 18;
16-
EXPECT_EQ(cache[4], 18) << "cache update is wrong";
17-
18-
auto it = cache.begin();
19-
EXPECT_EQ(4, it->first);
20-
EXPECT_EQ(18, it->second);
21-
++it;
22-
EXPECT_EQ(8, it->first);
23-
EXPECT_EQ(10, it->second);
24-
++it;
25-
EXPECT_EQ(0, it->first);
26-
EXPECT_EQ(12, it->second);
27-
++it;
28-
EXPECT_EQ(cache.end(), it) << "Wrong number of iterations?";
29-
}
30-
31-
TEST(LRUCacheTest, Eviction) {
32-
lru_cache_t<int, int> cache(10);
33-
for (int i = 0; i < 20; i++) cache[i] = i;
34-
EXPECT_EQ(10, cache.size());
35-
EXPECT_EQ(19, cache.begin()->first);
36-
EXPECT_EQ(10, cache.rbegin()->first);
37-
cache[4] = 42;
38-
cache[14] = 88;
39-
cache[8] = 18;
40-
EXPECT_EQ(10, cache.size());
41-
42-
auto it = cache.begin();
43-
EXPECT_EQ(8, it->first);
44-
EXPECT_EQ(18, it->second);
45-
++it;
46-
EXPECT_EQ(14, it->first);
47-
EXPECT_EQ(88, it->second);
48-
++it;
49-
EXPECT_EQ(4, it->first);
50-
EXPECT_EQ(42, it->second);
51-
++it;
52-
EXPECT_EQ(19, it->first);
53-
EXPECT_EQ(19, it->second);
54-
EXPECT_EQ(12, cache.rbegin()->first);
55-
}
56-
57-
TEST(LRUCacheTest, Find) {
58-
lru_cache_t<int, int> cache(10);
59-
for (int i = 0; i < 20; i++) cache[i] = i;
60-
EXPECT_EQ(19, cache.begin()->first);
61-
EXPECT_EQ(cache.end(), cache.find(3));
62-
EXPECT_EQ(19, cache.begin()->first);
63-
EXPECT_EQ(13, cache.find(13)->first);
64-
EXPECT_EQ(13, cache.begin()->first);
65-
EXPECT_EQ(10, cache.rbegin()->first);
7+
TEST(LRUCacheTest, Basic) {
8+
lru_cache_t<std::string, std::string> cache(4);
9+
EXPECT_TRUE(cache.insert("4", "5"));
10+
EXPECT_TRUE(cache.insert("8", "10"));
11+
EXPECT_TRUE(cache.insert("0", "12"));
12+
EXPECT_EQ(3, cache.size());
13+
EXPECT_EQ(4, cache.max_size());
14+
std::string *p;
15+
bool res = cache.lookup("8", &p);
16+
ASSERT_TRUE(res);
17+
EXPECT_EQ("10", *p);
18+
// Usage ordering is now 4 0 8.
19+
EXPECT_EQ(false, cache.insert("4", "9"));
20+
EXPECT_TRUE(cache.insert("7", "77"));
21+
// Usage ordering is now 4 0 8 7
22+
EXPECT_EQ(4, cache.size());
23+
EXPECT_TRUE(cache.insert("6", ""));
24+
EXPECT_EQ(4, cache.size());
25+
// Usage ordering is now 0 8 7 6. The key "4" was evicted.
26+
res = cache.lookup("4", &p);
27+
EXPECT_FALSE(res);
28+
res = cache.lookup("0", &p);
29+
ASSERT_TRUE(res);
30+
EXPECT_EQ("12", *p);
31+
// Usage ordering is now 8 7 6 0.
32+
EXPECT_TRUE(cache.insert("9", "99"));
33+
// Usage ordering is now 7 6 0 9.
34+
EXPECT_EQ(4, cache.size());
35+
res = cache.lookup("8", &p);
36+
EXPECT_FALSE(res);
37+
res = cache.lookup("4", &p);
38+
EXPECT_FALSE(res);
6639
}
6740

6841
} // namespace unittest

0 commit comments

Comments
 (0)