You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by jo...@apache.org on 2020/01/28 00:48:32 UTC
[impala] branch master updated: Remove dead code: FifoMultimap
This is an automated email from the ASF dual-hosted git repository.
joemcdonnell pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git
The following commit(s) were added to refs/heads/master by this push:
new 4fa6b52 Remove dead code: FifoMultimap
4fa6b52 is described below
commit 4fa6b5260d9e28dee63a87de3bea1434706a9d05
Author: Joe McDonnell <jo...@cloudera.com>
AuthorDate: Mon Jan 27 10:52:20 2020 -0800
Remove dead code: FifoMultimap
The FifoMultimap (be/src/util/lru-cache.h, etc) was used in an older
version of the file handle cache. It is now unused, so this removes
it.
Testing:
- Ran a clean compile
Change-Id: I2f5008e2cb05d093f7dc03f889f9846a95b1e9a7
Reviewed-on: http://gerrit.cloudera.org:8080/15109
Reviewed-by: Tim Armstrong <ta...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
be/src/util/CMakeLists.txt | 2 -
be/src/util/lru-cache-test.cc | 153 -----------------------------------------
be/src/util/lru-cache.h | 141 -------------------------------------
be/src/util/lru-cache.inline.h | 89 ------------------------
4 files changed, 385 deletions(-)
diff --git a/be/src/util/CMakeLists.txt b/be/src/util/CMakeLists.txt
index 20018e4..1f28ffe 100644
--- a/be/src/util/CMakeLists.txt
+++ b/be/src/util/CMakeLists.txt
@@ -119,7 +119,6 @@ add_library(UtilTests STATIC
hdfs-util-test.cc
hdr-histogram-test.cc
logging-support-test.cc
- lru-cache-test.cc
metrics-test.cc
min-max-filter-test.cc
openssl-util-test.cc
@@ -183,7 +182,6 @@ ADD_UNIFIED_BE_LSAN_TEST(hdr-histogram-test HdrHistogramTest.*)
# to use a unified executable
ADD_BE_LSAN_TEST(internal-queue-test)
ADD_UNIFIED_BE_LSAN_TEST(logging-support-test "LoggingSupport.*")
-ADD_UNIFIED_BE_LSAN_TEST(lru-cache-test "FifoMultimap.*")
ADD_UNIFIED_BE_LSAN_TEST(metrics-test "MetricsTest.*")
ADD_UNIFIED_BE_LSAN_TEST(min-max-filter-test "MinMaxFilterTest.*")
ADD_UNIFIED_BE_LSAN_TEST(openssl-util-test "OpenSSLUtilTest.*")
diff --git a/be/src/util/lru-cache-test.cc b/be/src/util/lru-cache-test.cc
deleted file mode 100644
index 96a9b28..0000000
--- a/be/src/util/lru-cache-test.cc
+++ /dev/null
@@ -1,153 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#include "lru-cache.h"
-
-#include <boost/thread.hpp>
-#include <glog/logging.h>
-
-#include "common/logging.h"
-#include "testutil/gtest-util.h"
-#include "util/test-info.h"
-
-#include "common/names.h"
-
-using boost::thread;
-using boost::thread_group;
-
-using namespace impala;
-
-TEST(FifoMultimap, Basic) {
- FifoMultimap<int, int> c(3);
- int result;
- ASSERT_EQ(3, c.capacity());
- c.Put(0, 1);
- c.Put(0, 2);
- ASSERT_EQ(2, c.size());
- ASSERT_FALSE(c.Pop(99, &result));
- c.Pop(0, &result);
- c.Pop(0, &result);
- ASSERT_FALSE(c.Pop(0, &result));
-}
-
-TEST(FifoMultimap, Invalid) {
- FifoMultimap<int, int> c(0);
- int result;
- ASSERT_EQ(0, c.capacity());
- c.Put(0, 1);
- ASSERT_EQ(0, c.size());
- ASSERT_FALSE(c.Pop(99, &result));
-}
-
-TEST(FifoMultimap, Evict) {
- FifoMultimap<int, int> c(3);
- int result;
- c.Put(0, 1);
- c.Put(1, 2);
- c.Put(2, 3);
- ASSERT_EQ(3, c.size());
- c.Put(3, 4);
- ASSERT_EQ(3, c.size());
- ASSERT_FALSE(c.Pop(0, &result));
- ASSERT_TRUE(c.Pop(1, &result));
- ASSERT_EQ(2, result);
- ASSERT_FALSE(c.Pop(1, &result));
- ASSERT_EQ(2, c.size());
-}
-
-TEST(FifoMultimap, Large) {
- FifoMultimap<int, int> c(1000);
- int result;
- for (int i = 0; i < 1000; ++i) {
- c.Put(i, i);
- }
- ASSERT_EQ(1000, c.size());
- for (int i = 0; i < 2000; ++i) {
- int key = rand();
- c.Pop(key % 1000, &result);
- ASSERT_EQ(999, c.size());
- c.Put(key % 1000, i);
- ASSERT_EQ(1000, c.size());
- }
-}
-
-static int del_sum = 0;
-void TestDeleter(int* v) { del_sum += *v; }
-
-TEST(FifoMultimap, Deleter) {
- FifoMultimap<int, int> c(10, TestDeleter);
- for (int i = 1; i <= 1000; ++i) {
- c.Put(i, i);
- }
- int n = 1000 - c.capacity();
- // All values from 1 to n have been evicted, so the sum of all values must match del_sum
- ASSERT_EQ((n * (n + 1)) / 2, del_sum);
-}
-
-static int del_count = 0;
-void TestCountDeleter(int* v) { ++del_count; }
-
-void ParallelPut(const int start, const int end, FifoMultimap<int, int>* shelf) {
- int val;
- for (int i = start; i < end; ++i) {
- if (i % 3 == 0) {
- if (shelf->Pop(i, &val)) {
- shelf->Put(i, i);
- }
- }
- shelf->Put(i, i);
- }
-}
-
-TEST(FifoMultimap, ParallelEviction) {
- del_sum = 0;
- FifoMultimap<int, int> c(10, TestCountDeleter);
-
- thread_group group;
- size_t count = 100000;
- size_t thread_count = 10;
- size_t part = count / thread_count;
- for (int i = 0; i < thread_count; ++i) {
- group.add_thread(new thread(ParallelPut, 0, part, &c));
- }
- group.join_all();
- ASSERT_EQ(10, c.size());
- ASSERT_EQ(count - c.capacity(), del_count);
-}
-
-TEST(FifoMultimap, PopShouldPopMostRecent) {
- FifoMultimap<int, int> c(3);
- int result;
- c.Put(1, 1);
- c.Put(1, 2);
- c.Put(1, 3);
- ASSERT_TRUE(c.Pop(1, &result));
- ASSERT_EQ(3, result);
- c.Put(1, 3);
- c.Put(1, 4);
- ASSERT_EQ(3, c.size());
- ASSERT_TRUE(c.Pop(1, &result));
- ASSERT_EQ(4, result);
- ASSERT_EQ(2, c.size());
- ASSERT_TRUE(c.Pop(1, &result));
- ASSERT_EQ(3, result);
- ASSERT_EQ(1, c.size());
- ASSERT_TRUE(c.Pop(1, &result));
- ASSERT_EQ(2, result);
- ASSERT_EQ(0, c.size());
-}
-
diff --git a/be/src/util/lru-cache.h b/be/src/util/lru-cache.h
deleted file mode 100644
index bca3284..0000000
--- a/be/src/util/lru-cache.h
+++ /dev/null
@@ -1,141 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#ifndef IMPALA_UTIL_LRU_CACHE_H_
-#define IMPALA_UTIL_LRU_CACHE_H_
-
-#include <boost/optional.hpp>
-#include <boost/thread.hpp>
-#include <boost/thread/mutex.hpp>
-#include <boost/unordered_map.hpp>
-#include <list>
-#include <map>
-#include <stack>
-
-#include "gutil/macros.h"
-#include "util/spinlock.h"
-
-namespace impala {
-
-/// Implementation of a FifoMultimap.
-///
-/// The FifoMultimap is a cache-like data structure that keeps `capacity` number of
-/// key-value pairs organized and accessible by key allowing multiple values per key. If
-/// capacity is reached, key-value pairs are evicted in the least recently added order.
-///
-/// When accessing the values that have identical keys (via Pop(k)), values are typically
-/// returned in LIFO order of this key. However, this property can only be guaranteed when
-/// compiled with C++11 enabled. The motivation for accessing values in this particular
-/// order is to avoid keeping all values of a particular key hot, even though only a
-/// subset of the values is actually used.
-///
-/// On destruction of this class all resources are freed using the optional deleter
-/// function.
-///
-/// This class is thread-safe and some methods may block under contention. This class
-/// cannot be copied or assigned.
-///
-/// Example of a cache with capacity 3:
-///
-/// * First `<K1, V1>` is added to the cache, then `<K2, V2>`, `<K2, V3>`.
-///
-/// Eviction case: If a new key value pair is added `<K1, V1>` will be evicted as it
-/// is the oldest entry. (FIFO)
-///
-/// Element access: If `K2` is accessed, `V3` will be returned first. (LIFO)
-///
-/// This class is thread-safe and protects its members using a spin lock.
-template<typename Key, typename Value>
-class FifoMultimap {
- public:
- typedef std::pair<Key, Value> ValueType;
-
- /// Deleter function type used to allow cleanup of resources held by Value when it is
- /// evicted. This method should only be used if it is not possible to embed the
- /// cleanup logic in the Value class itself.
- typedef void (*DeleterFn)(Value*);
-
- /// Instantiates the collection with an upper bound of `capacity` key-value pairs stored
- /// in the FifoMultimap and a `deleter` function pointer that can be used to free resources
- /// when a value is evicted from the FifoMultimap.
- FifoMultimap(size_t capacity, const DeleterFn& deleter = &FifoMultimap::DummyDeleter)
- : capacity_(capacity), deleter_(deleter), size_(0) {}
-
- /// Walk the list of elements and call the deleter function for each element.
- ~FifoMultimap();
-
- /// Add a key-value pair to the collection. Uniqueness of keys is not enforced. If the
- /// capacity is exceeded the oldest element will be evicted.
- void Put(const Key& k, const Value& v);
-
- /// Accesses an element of the collection by key and returns the value. In the process
- /// the key-value pair is removed from the collection. If the element is not found,
- /// returns boost::none.
- ///
- /// Typically, this will return the last element that was added under key `k` in case of
- /// duplicate keys.
- bool Pop(const Key& k, Value* out);
-
- /// Returns the total number of entries in the collection.
- size_t size(){
- boost::lock_guard<SpinLock> g(lock_);
- return cache_.size();
- }
-
- /// Returns the capacity of the cache
- size_t capacity() const { return capacity_; }
-
- private:
- DISALLOW_COPY_AND_ASSIGN(FifoMultimap);
-
- /// Total capacity, cannot be changed at run-time.
- const size_t capacity_;
-
- const DeleterFn deleter_;
-
- /// Protects access to cache_ and lru_list_.
- SpinLock lock_;
-
- typedef std::list<ValueType> ListType;
-
- /// The least recently added item is stored at the beginning of the list. The length of
- /// the list is limited to `capacity` number of elements. New elements are always
- /// appended to the end of the list.
- ListType lru_list_;
-
- typedef std::multimap<Key, typename ListType::iterator> MapType;
-
- /// Underlying associative container, that maps a key to an entry in the recently used
- /// list. The iterator on the list is only invalidated if the key-value pair is removed.
- MapType cache_;
-
- /// Number of elements stored in the cache.
- size_t size_;
-
- /// Evicts the least recently added element from the cache. First, the element is
- /// removed from both internal collections and as a last step the `deleter_` function is
- /// called to free potentially acquired resources.
- void EvictValue();
-
- static void DummyDeleter(Value* v) {}
-};
-
-}
-
-#include "lru-cache.inline.h"
-
-#endif // IMPALA_UTIL_LRU_CACHE_H_
diff --git a/be/src/util/lru-cache.inline.h b/be/src/util/lru-cache.inline.h
deleted file mode 100644
index 0271e6a..0000000
--- a/be/src/util/lru-cache.inline.h
+++ /dev/null
@@ -1,89 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#ifndef IMPALA_UTIL_LRU_CACHE_INLINE_H_
-#define IMPALA_UTIL_LRU_CACHE_INLINE_H_
-
-namespace impala {
-
-template <typename Key, typename Value>
-FifoMultimap<Key, Value>::~FifoMultimap() {
- for (typename ListType::iterator b = lru_list_.begin(),
- e = lru_list_.end(); b != e; ++b) {
- deleter_(&(b->second));
- }
-}
-
-template <typename Key, typename Value>
-void FifoMultimap<Key, Value>::Put(const Key& k, const Value& v) {
- boost::lock_guard<SpinLock> g(lock_);
- if (capacity_ <= 0) return;
- if (size_ >= capacity_) EvictValue();
- const ValueType& kv_pair = std::make_pair(k, v);
- const typename MapType::value_type& val =
- std::make_pair(k, lru_list_.insert(lru_list_.end(), kv_pair));
- // Find an insert hint to use with the insert operation
- typename MapType::iterator it = cache_.lower_bound(k);
- if (it == cache_.end() || it->first != k) {
- cache_.insert(val);
- } else {
- // If the insert hint is sufficiently good, the element will be inserted before in the
- // sequence of elements having the same key
- cache_.insert(it, val);
- }
- ++size_;
-}
-
-template <typename Key, typename Value>
-bool FifoMultimap<Key, Value>::Pop(const Key& k, Value* out) {
- boost::lock_guard<SpinLock> g(lock_);
- // Find the first value under key k.
- typename MapType::iterator it = cache_.lower_bound(k);
- if (it == cache_.end() || it->first != k) return false;
- typename ListType::iterator lit = it->second;
- *out = lit->second;
- lru_list_.erase(lit);
- cache_.erase(it);
- --size_;
- return true;
-}
-
-template <typename Key, typename Value>
-void FifoMultimap<Key, Value>::EvictValue() {
- DCHECK(!lru_list_.empty());
- typename ListType::iterator to_evict = lru_list_.begin();
- // Find all elements under this key, until C++11 the order of the elements is not
- // guaranteed.
- std::pair<typename MapType::iterator, typename MapType::iterator> range =
- cache_.equal_range(to_evict->first);
- // Search until the value is found in the range of the same key.
- while (range.first != range.second) {
- if (range.first->second == to_evict) {
- cache_.erase(range.first);
- break;
- }
- ++range.first;
- }
- DCHECK(range.first != range.second); // LCOV_EXCL_LINE
- deleter_(&(to_evict->second));
- lru_list_.erase(to_evict);
- --size_;
-}
-
-}
-
-#endif // IMPALA_UTIL_LRU_CACHE_INLINE_H_