Page MenuHomePhabricator

allow cuckoocache to function as a map
ClosedPublic

Authored by deadalnix on Dec 3 2019, 05:49.

Details

Summary

For the new value-tracking script cache, we can keep using the cuckoo
cache system but now using it as a map.

Test Plan

make check

Diff Detail

Repository
rABC Bitcoin ABC
Branch
cuckoomap
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 8385
Build 14788: Default Diff Build & Tests
Build 14787: arc lint + arc unit

Event Timeline

src/test/cuckoocache_tests.cpp
48

Amusingly, if we just use u=0 for the last hash, all the tests pass fine. In the cuckoocache_hit_rate_ok test, this causes the normalized hit rate to drop from 0.989480 to 0.989442, compared to the sigcache's 0.989503. That is basically insignificant though, since changing the test seed makes much larger fluctuations.

(In contrast if I zero out the last *two* hashes then it causes tests to fail.)

In other words, we can probably drop to having the cache look at 7 hashes instead of 8. This increases the speed of a read miss by 14%, and the speed of a low-load insertion should see a similar boost since the initial search will be faster.

deadalnix requested changes to this revision.Dec 3 2019, 17:41

You probably want to investigate why the build failed.

src/cuckoocache.h
434

I think this comment adds more to the confusion than anything else.

522

That comment in itself is a strong tel there is some factoring that needs to takes place.

src/test/cuckoocache_tests.cpp
31

Don't copy bad style. Fix it instead.

61

If this is a KV element, then you really want to pass a key and a value to this instead of filling the value with random garbage.

62

You can then remove the setter. In general, when you end up with both setters (OO style) and getters (functional style) in the same object, you are doing something wrong.

If generating variant is still desired, you can have functions such as withValue(...) that generate and return a modified copy.

65

I would advice against the use of memcpy. Why not have an std::array<uint8_t, 28> and a uint32_t as member for the element?

70

Maybe it is a good idea to actually use a function such as matchKey(const ExampleMapElement &rhs) rather than use operator== because this is clearly not an equality test.

464

Use {} as an empty statement instead.

Also, I don't think this is a bit strange and I'm not sure what it is testing. This is potentially looping forever and not really testing that the value we get are working properly, because they are set randomly to begin with, see comments on ExampleMapElement.

This revision now requires changes to proceed.Dec 3 2019, 17:41
deadalnix edited reviewers, added: markblundeberg; removed: deadalnix.

Address comments, except making the constructor of the test map element explicit, as it makes the test way more complex and the upside is not very clear.

I see, my strategy was to avoid the kind of refactoring done in D4641 and D4643 and this one, and have a lighter touch to avoid too much code ownership. But, this works too.

src/cuckoocache.h
426 ↗(On Diff #14716)

typo 'witht he'

519 ↗(On Diff #14716)

out of curiosity why not keep inline on these methods?

src/test/cuckoocache_tests.cpp
481 ↗(On Diff #14716)

not needed for this test

508 ↗(On Diff #14716)

typo 'int he'

This revision now requires changes to proceed.Dec 10 2019, 05:25
src/cuckoocache.h
519 ↗(On Diff #14716)

Because it is completely pointless in a template.

green with some comments

src/cuckoocache.h
512 ↗(On Diff #14724)

just noticed this, seems to be missed from previous diff

src/test/cuckoocache_tests.cpp
107 ↗(On Diff #14724)

note that (since not re-seeded) this does 400000 calls.

501 ↗(On Diff #14724)

It's interesting that this manages to have 100000 successive inserts. Without any erases, the epoch system does allow the table to get pretty full. I tried setting this to 2 million iterations and it only fails 7 times.

This revision is now accepted and ready to land.Dec 10 2019, 21:00
src/test/cuckoocache_tests.cpp
501 ↗(On Diff #14724)

With each element having 8 positions, it's not that incredible.