[GitHub] [incubator-doris] gaodayue commented on a diff in pull request #9521: [improvement][performance] improve lru cache resize performance and memory usage

[GitBox <gi...@apache.org>]

gaodayue commented on code in PR #9521:
URL: https://github.com/apache/incubator-doris/pull/9521#discussion_r873618153


##########
be/src/olap/lru_cache.cpp:
##########
@@ -106,40 +103,38 @@ LRUHandle* HandleTable::remove(const CacheKey& key, uint32_t hash) {
     LRUHandle** ptr = _find_pointer(key, hash);
     LRUHandle* result = *ptr;
 
-    remove(result);
+    if (result != nullptr) {
+        *ptr = result->next_hash;
+        _elems--;
+    }
 
     return result;
 }
 
-void HandleTable::remove(const LRUHandle* h) {
-    if (h != nullptr) {
-        if (h->next_hash != nullptr) {
-            h->next_hash->prev_hash = h->prev_hash;
-        }
-        DCHECK(h->prev_hash != nullptr);
-        h->prev_hash->next_hash = h->next_hash;
-        --_elems;
+bool HandleTable::remove(const LRUHandle* h) {
+    LRUHandle** ptr = &(_list[h->hash & (_length - 1)]);
+    while (*ptr != nullptr && *ptr != h) {
+        ptr = &(*ptr)->next_hash;
     }
+
+    LRUHandle* result = *ptr;

Review Comment:
   This PR will not slow down `remove` because
   1. the expected length for the linked list is 1 given a good hash function, so we won't spend too much time traversing the list
   2. only pointer comparison is used for each iteration, no time-consuming key comparison
   
   As a result, CacheTest.SimpleBenchmark changed from 1576ms to 1570ms on 160000 iteration, and from 161392ms to 158165ms on 16000000 iteration.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org