This is an automated email from the ASF dual-hosted git repository. bneradt pushed a commit to branch lru-cache in repository https://gitbox.apache.org/repos/asf/trafficserver-libswoc.git
commit 3fbf08c268d9c52fa00da1171a0678ea72d00580 Author: Alan M. Carroll <[email protected]> AuthorDate: Thu Oct 7 20:57:55 2021 -0500 LRU Cache - ready for testing. --- code/include/swoc/IntrusiveDList.h | 4 +- example/CMakeLists.txt | 3 +- example/ex_lru_cache.cc | 76 +++++++++++++++++++++++++++++++++++--- 3 files changed, 75 insertions(+), 8 deletions(-) diff --git a/code/include/swoc/IntrusiveDList.h b/code/include/swoc/IntrusiveDList.h index fa0bb10..a3070bb 100644 --- a/code/include/swoc/IntrusiveDList.h +++ b/code/include/swoc/IntrusiveDList.h @@ -649,7 +649,9 @@ IntrusiveDList<L>::take_head() -> value_type * { if (_head) { if (nullptr == (_head = L::next_ptr(_head))) { _tail = nullptr; // transition non-empty -> empty - } else { L::prev_ptr(_head) = nullptr; } + } else { + L::prev_ptr(_head) = nullptr; + } L::next_ptr(zret) = L::prev_ptr(zret) = nullptr; --_count; } diff --git a/example/CMakeLists.txt b/example/CMakeLists.txt index e1e0563..af57fc2 100644 --- a/example/CMakeLists.txt +++ b/example/CMakeLists.txt @@ -25,5 +25,6 @@ endif() add_executable(ex_lru_cache ex_lru_cache.cc) target_link_libraries(ex_lru_cache PUBLIC libswoc) if (CMAKE_COMPILER_IS_GNUCXX) - target_compile_options(ex_lru_cache PRIVATE -Wall -Wextra -Werror) + target_compile_options(ex_lru_cache PRIVATE -Wall -Wextra -Werror -ggdb3) + target_link_options(ex_lru_cache PRIVATE -lpthread) endif() diff --git a/example/ex_lru_cache.cc b/example/ex_lru_cache.cc index 777a150..10a205e 100644 --- a/example/ex_lru_cache.cc +++ b/example/ex_lru_cache.cc @@ -9,6 +9,7 @@ #include <unistd.h> #include <chrono> #include <utility> +#include <thread> #include "swoc/TextView.h" #include "swoc/swoc_ip.h" @@ -37,8 +38,10 @@ public: LRU() = default; self_type & insert(K const& key, V && value); + self_type & erase(K const& key); V retrieve(K const& key) const; + size_t count() const { return _table.count(); } protected: struct Item { @@ -53,17 +56,22 @@ protected: Links _list; Links _map; + + Item(self_type && that) : _key(that._key), _value(std::move(that._value)) {} + Item(K const& key, V && value) : _key(key), _value(std::move(value)) {} + + self_type & operator = (self_type && that) { _key = that._key; _value = std::move(that._value); return *this; } }; struct Linkage { - static Item * next_ptr(Item * item) { return item->_list._next; } - static Item * prev_ptr(Item * item) { return item->_list._prev; } + static Item * & next_ptr(Item * item) { return item->_list._next; } + static Item * & prev_ptr(Item * item) { return item->_list._prev; } }; using List = swoc::IntrusiveDList<Linkage>; struct Hashing { - static Item * next_ptr(Item * item) { return item->_map._next; } - static Item * prev_ptr(Item * item) { return item->_map._prev; } + static Item * & next_ptr(Item * item) { return item->_map._next; } + static Item * & prev_ptr(Item * item) { return item->_map._prev; } static inline const std::hash<K> Hasher; static K const& key_of(Item * item) { return item->_key; } static decltype(Hasher(std::declval<K>())) hash_of(K const& key) { return Hasher(key); } @@ -87,11 +95,17 @@ template <typename K, typename V> auto LRU<K, V>::insert(K const &key, V &&value if (spot != _table.end()) { spot->_value = std::move(value); } else { - auto *item = _arena.make<Item>(key, std::move(value)); + Item * item = _free.take_head(); + if (item != nullptr) { + new (item) Item(key, std::move(value)); + } else { + item = _arena.make<Item>(key, std::move(value)); + } _table.insert(item); _list.append(item); - if (_list.size() > _max) { + if (_list.count() > _max) { target = _list.take_head(); + _table.erase(target); } } } @@ -126,6 +140,14 @@ template <typename K, typename V> auto LRU<K, V>::retrieve(K const &key) const - // -------------------------------------------------- int main(int, char *[]) { + static constexpr size_t N_THREAD = 12; ///< Number of threads. + static constexpr size_t N_ITER = 100000; + + std::array<std::thread, N_THREAD> threads; + std::mutex gate_m; + std::condition_variable gate_cv; + std::atomic<int> count = -1; + struct Data { time_point _expire; int _code = 0; @@ -133,5 +155,47 @@ int main(int, char *[]) { LRU<IPAddr, Data> lru; + auto worker = [&] () -> void { + unsigned dummy; + { + std::unique_lock _(gate_m); + gate_cv.wait(_, [&] () {return count >= 0; }); + } + swoc::IP4Addr addr((reinterpret_cast<uintptr_t>(&dummy) >> 16) & 0xFFFFFFFF); + for ( unsigned i = 0 ; i < N_ITER ; ++i ) { + lru.insert(addr, Data{time_point(), 1}); + addr = htonl(addr.host_order() + 1); + } + { + std::unique_lock _(gate_m); + ++count; + } + gate_cv.notify_all(); + }; + + for ( unsigned i = 0 ; i < N_THREAD; ++i ) { + threads[i] = std::thread(worker); + } + + auto t0 = std::chrono::system_clock::now(); + { + std::unique_lock _(gate_m); + count = 0; + gate_cv.notify_all(); + } + + { + std::unique_lock _(gate_m); + gate_cv.wait(_, [&] () { return count == N_THREAD; }); + } + auto tf = std::chrono::system_clock::now(); + auto delta = tf - t0; + + std::cout << "Done in " << delta.count() << " with " << lru.count() << std::endl; + std::cout << "ns per operation " << (delta.count() / (N_THREAD * N_ITER)) << std::endl; + for ( unsigned i = 0 ; i < N_THREAD ; ++i ) { + threads[i].join(); + } + return 0; }
