Joe McDonnell has uploaded this change for review. ( http://gerrit.cloudera.org:8080/16597
Change subject: IMPALA-10127: Fix performance for enforcement of lirs_tombstone_multiple ...................................................................... IMPALA-10127: Fix performance for enforcement of lirs_tombstone_multiple When enforcing lirs_tombstone_multiple for the LIRS cache, currently it needs to walk backwards through the recency list to find the oldest tombstone entry to remove it. This traversal can involve passing a large number of non-tombstone entries. In pathological cases, it is O(N) where N is the number of entries in the cache. This modifies the LIRS implementation to use a combined unprotected and tombstone list. The first half of the list is unprotected entries. The second half is tombstone entries. The tombstone portion of the list allows the enforcement for the lirs_tombstone_multiple to be O(1) when finding the oldest tombstone entry. The unprotected half of the list operates as it did before, except that the combined list requires maintaining a pointer to the front of the unprotected list (i.e. the boundary between the unprotected portion and the tombstone portion). Using a combined list means that evicting an unprotected entry to become a tombstone entry is only updating a pointer. This is a common operation, so it keeps the overhead of the tombstone list low. Performance: For all existing performance test cases in cache-bench, lookups/sec are within 2% of the current implementation of LIRS. This adds a new pathalogical case to cache-bench where the cache hit rate is 0.2%. This causes extensive use of the lirs_tombstone_multiple. This case sees a 2000x improvement, going from 1.3K lookups/sec to 2.96M lookups/sec. Testing: - lirs-cache-test passes (debug and release) - This also adds the DATA_CACHE_EVICTION_POLICY environment variable to run-all-tests.sh to allow easy testing with LIRS. - Ran a core job with 500MB cache using LIRS Change-Id: I25b697f57c7daacccf8791a5a7b31878a6f7f1d2 --- M be/src/util/cache/cache-bench.cc M be/src/util/cache/lirs-cache.cc M bin/run-all-tests.sh 3 files changed, 169 insertions(+), 64 deletions(-) git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/97/16597/1 -- To view, visit http://gerrit.cloudera.org:8080/16597 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: Impala-ASF Gerrit-Branch: master Gerrit-MessageType: newchange Gerrit-Change-Id: I25b697f57c7daacccf8791a5a7b31878a6f7f1d2 Gerrit-Change-Number: 16597 Gerrit-PatchSet: 1 Gerrit-Owner: Joe McDonnell <joemcdonn...@cloudera.com>
