opencurve / curve

Curve is a sandbox project hosted by the CNCF Foundation. It's cloud-native, high-performance, and easy to operate. Curve is an open-source distributed storage system for block and shared file storage.
https://opencurve.io
Apache License 2.0
2.33k stars 522 forks source link

[Feat]: Optimize LRU cache promotion #2946

Closed zztaki closed 10 months ago

zztaki commented 11 months ago

Is your feature request related to a problem? (你需要的功能是否与某个问题有关?) In src/common/lru_cache.h, LRUCache's method MoveToFront will do copying the requested elem, erasing the elem from list, pushing duplica to the list's head, and even updating the hashtable. This will waste time.

Describe the solution you'd like (描述你期望的解决方法) list.splice is OK instead of the above steps.

Describe alternatives you've considered (描述你想到的折衷方案)

Additional context/screenshots (更多上下文/截图) I've done some performance testing with epoch = 1000000.

    auto cache = std::make_shared<LRUCache<int, int>>(5, nullptr);
    for(int i = 0; i < 5; i++){
        cache->Put(i, i);
    }
    clock_t start,end;

    start = clock();
    for(int i = 0; i < EPOCH; i++){
        int v;
        for(int k = 0; k < 5; k++){
            cache->Get(k, &v);
            assert(k == v);
        }
    }
    end = clock();
    std::cout << "Get with duplicate: " << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

    start = clock();
    for(int i = 0; i < EPOCH; i++){
        int v;
        for(int k = 0; k < 5; k++){
            cache->GetWithSplice(k, &v);
            assert(k == v);
        }
    }
    end = clock();
    std::cout << "Get without duplicate: " << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

Result is

Get with duplicate: 2.17597
Get without duplicate: 1.42666
zztaki commented 11 months ago

If you think this makes sense, I'm glad to do PRs to optimize LRUCache, TimedLRUCache and SglLRUCache without affecting the semantics. :)

Ziy1-Tan commented 10 months ago

If you think this makes sense, I'm glad to do PRs to optimize LRUCache, TimedLRUCache and SglLRUCache without affecting the semantics. :)

Good catch, just do it! Maybe you could use google/benchmark to evaluate impremovement.:)

zztaki commented 10 months ago

If you think this makes sense, I'm glad to do PRs to optimize LRUCache, TimedLRUCache and SglLRUCache without affecting the semantics. :)

Good catch, just do it! Maybe you could use google/benchmark to evaluate impremovement.:)

Nice tool! I will try it and submit a PR soon~