suggestions for speedups

[MPdaedalus]

Hi, loving using your Cuckoo filter always loved the concept behind cuckoo hashing but never ended up using it until now.

There are some ways to make it faster however.

1: Support primitives such as int, long so there is no autoboxing overhead and garbage generation,
this would probably necessitate a class for each type like the trove collections do.
eg, IntCuckooFilter, LongCuckooFilter etc.

2: use atomicArray and compare and swap instead of locks for concurrency, locking always has a big overhead. see> https://github.com/Valloric/guava/tree/lock-free-bloom

3: Use xxHash instead of MurMur it is twice as fast with the same or better quality hashes and made the normal guava bloom filter access go from 440ns for the MURMUR128_MITZ_64 to 93ns for xxHash
see> google/guava#2748 (comment)

thanks for building such as great filter!

[MGunlogson]

Thanks for the feedback! I have a local build I've been working on that decreases the size of the filters ~30% at a trivial performance cost. Unfortunately it has introduced a bug I'm having trouble tracking down that is affecting the statistical properties of the filter (false positive rate) so I can't commit yet. I have a personal todo list for optimizations and I could always use some help from other contributors.

Supporting primitive types should be weighed against the decreased flexibility and code burden of added logic paths. In my local build I've replaced the Guava Funnel implementation with a static call to avoid some allocation. As mentioned in the thread for lock-free Bloom you linked, this could be done fairly easily by an individual for isolated cases but trades a lot of general API friendliness.

I looked into using atomics but a few nuances of the Cuckoo filter make this impractical as far as my limited knowledge of atomics goes. There are two issues using atomics I ran into, the first is more severe. The number one problem using Atomics or CAS in Cuckoo filters is that writes to the filter are not aligned to word boundaries. The filter backing Bitset is actually a long array underneath. The fingerprints overlap longs fairly arbitrarily unless your fingerprint size is a partial multiple of 64. In practice this means you sometimes need to write multiple longs atomically at the same time. This might be possible using optimistic writes but it sounded like a really tough problem :) . The other related issue is that you have two buckets plus a victim slot, and all three need to be locked or written atomically at the same time to prevent inconsistent state being read for different threads. I'm not saying its not possible to do lockless access, but it's beyond my knowledge.

I did a few things to try to minimize the cost of locking. First, the locking is done by an interface that's swapped out with NOPs when running single threaded. JIT should be smart enough to remove the locks completely when run this way. The other thing I did was segment based locking, based on what I saw in the OpenJDK for ConcurrentHashMap. If you pick a high enough expected concurrency for your threads, the lock contention and therefore locking cost should be low.

I don't see any downsides to adding support for xxHash. I will add this to my todo list unless you want to take a crack at it :). The current code relies on Guava's hashing primitives but I'm suspicious that the filter is slower because of this.

I'm adding a TODO.txt to the project so that other potential contributors can see what I'm working on

[MPdaedalus]

I might have a crack at adding a xxhash implementation in the next week or two if I can find the time.

I think adding primitives will give a noticeable speed up when doing millions of reads per sec on the filter. You could avoid the extra logic paths by simply having a separate branch or copy of the main CookooFilter class for each primitive with the generics stripped out.

I haven't tested Vallorics lock-free bloom filter against your CuckooFilter but it should be interesting to see how they stack up.

[MGunlogson]

I have a simple JMH setup for my own testing against Guava's Bloom. I will post it this week so you don't need to write performance tests. Realistically, if xxhash is faster for Guava it will be faster here too. I'm starting to agree with you about primitives after seeing the use cases for these filters. Feel free to submit a patch for xxhash any time

Thanks!

[MPdaedalus]

visualVM is telling me two thirds of mightcontain() time is from FilterTable.checkTag and one third from the hashing. I noticed you are declaring a Boolean variable inside a loop which usually harms performance, here is a version without the variable>

boolean checkTag(long bucketIndex, int posInBucket, long tag) {
long tagStartIdx = getTagOffset(bucketIndex, posInBucket);
for (long i = 0; i < bitsPerTag; i++) {
if (memBlock.get(i + tagStartIdx) != ((tag & (1L << i)) != 0))
return false;
}
return true;
}

Other things that might speed up the method include deincrementing on the loop rather than incrementing (so long as things still work as intended) as doing >=0 uses a faster machine code than comparing against a non zero number, worth a shot.

I know bitsPerTag is final but ass it is a class variable rather than a local method variable it may entail another instruction to get the reference, the VM is probably smart enough to not perform the lookup on every loop iteration but you could assign it to a local final int and see if it makes any difference.

eg.
final int bitysPerTag = bitsPerTag;
for (long i = 0; i < bitysPerTag; i++) {

maybe you could test these ideas against your JMH setup to see if they make any difference when mightContain() is called millions of times per second.

I can do roughly 3 million mightContain() calls per core on my machine, as each Integer or Long object is 16 bytes that's 48MB of garbage per second per core not including any object creation overhead, the use of objects also makes hashing more complicated compared to hashing primitives which is a piece of cake.

i'll try to get started on xxHash this week

[MPdaedalus]

done xxHash and added FilterTable.checkTag improvements, check my Pull request for more info

[MGunlogson]

Excellent! My thanks. I might be busy tomorrow for good Friday but I will merge this ASAP

…

On Apr 13, 2017 10:10 PM, "MPdaedalus" ***@***.***> wrote: done xxHash and added FilterTable.checkTag improvements, check my Pull request for more info — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AG_BnKQQHp63hoUpG_O2_HrmoJwndnBFks5rvuOsgaJpZM4M4LLd> .

[MPdaedalus]

I have reworked the CucKoo filter to remove Generics, because of the large scale changes I have created a separate branch called "primitive filter". The garbage creation was very bad, in the original version i had 16 garbage collections with about 5 objects and 100 bytes of garbage per call, with xxHash (still with generics) I then had 8 collections and with the latest version that does not create any garbage for mightContain() I had no collections, this was with 32 million mightContain calls. This saved about 10-15 seconds of GC pause time alone. This was with a Young generation size of 4.6GB.

SerializableSaltedHasher.java and IndexTagCalc.java has been removed and the hashing and bucket index and tag is generated inside the mightContain and put/delete methods and the actual hashing algorithm is only a few lines for a "long" and has been moved to Utils.java . There is also the added benefit that all references to Guava has been removed so the CuckooFilter can be used standalone without requiring the Guava libraries. I had to make some changes to do this such as replacing guava sanity checks on the builders with throwable IllegalArgumentExceptions and removing some annotations and using java math libraries and copying some Guava math methods.

I also played about with findTag() to see if I could get some more speedups but my tests were hit and miss, I thought only checking all positions in the first bucket before checking the alternative second bucket would save a cache miss on most occasions but you would need to test it further with JMH to see if it makes a consistent difference see>MPdaedalus@3ebd9fb

Overall in my tests the 32 Million MightContain calls has gone from 11-12 seconds with your original version to 3-4 seconds with my primitive version with xxHash. This does not include the GC pause savings mentioned above.

I think I have gone as far as I can with it as far as speed ups go, I don't have any more time to work on it anymore. Feel free to msg me if you have any bugs and let me know how much of an improvement there is on your JMH harness.

[MGunlogson]

Excellent! I will merge back to master as soon as possible this week and test out my local changes merged with yours. Thank you for the effort, that is a very impressive speedup! I will get you bench data against Guava once it's merged, it should be quite a bit faster than Guava Bloom now

…

On Apr 16, 2017 7:15 PM, "MPdaedalus" ***@***.***> wrote: I have reworked the CucKoo filter to remove Generics, because of the large scale changes I have created a separate branch called "primitive filter". The garbage creation was very bad, in the original version i had 16 garbage collections with about 5 objects and 100 bytes of garbage per call, with xxHash (still with generics) I then had 8 collections and with the latest version that does not create any garbage for mightContain() I had no collections, this was with 32 million mightContain calls. This saved about 10-15 seconds of GC pause time alone. This was with a Young generation size of 4.6GB. SerializableSaltedHasher.java and IndexTagCalc.java has been removed and the hashing and bucket index and tag is generated inside the mightContain and put/delete methods and the actual hashing algorithm is only a few lines for a "long" and has been moved to Utils.java . There is also the added benefit that all references to Guava has been removed so the CuckooFilter can be used standalone without requiring the Guava libraries. I had to make some changes to do this such as replacing guava sanity checks on the builders with throwable IllegalArgumentExceptions and removing some annotations and using java math libraries and copying some Guava math methods. I also played about with findTag() to see if I could get some more speedups but my tests were hit and miss, I thought only checking all positions in the first bucket before checking the alternative second bucket would save a cache miss on most occasions but you would need to test it further with JMH to see if it makes a consistent difference see> ***@***.*** <MPdaedalus@3ebd9fb> Overall in my tests the 32 Million MightContain calls has gone from 11-12 seconds with you'r original version to 3-4 seconds with my primitive version with xxHash. This does not include the GC pause savings mentioned above. I think I have gone as far as I can with it as far as speed ups go, I don't have any more time to work on it anymore. Feel free to msg me if you have any bugs and let me know how much of an improvement there is on your JMH harness. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AG_BnPd5Cra1kIOw25X5KrOCP5Vdkh0Rks5rwq8OgaJpZM4M4LLd> .

[MGunlogson]

Just letting you know I haven't forgotten. I've been very busy at work this week, hopefully I will have time this weekend. The contribution is very much appreciated but I haven't been a good programmer and allowed my local version to diverge a lot from master. Your revisions are also substantial so reconciling them will take me some time. I promise to get a 2.0 version out with our merged changes by May 5, otherwise I will give you control of the project. Thanks, mark

…

On Apr 16, 2017 9:30 PM, "Mark Gunlogson" ***@***.***> wrote: Excellent! I will merge back to master as soon as possible this week and test out my local changes merged with yours. Thank you for the effort, that is a very impressive speedup! I will get you bench data against Guava once it's merged, it should be quite a bit faster than Guava Bloom now On Apr 16, 2017 7:15 PM, "MPdaedalus" ***@***.***> wrote: > I have reworked the CucKoo filter to remove Generics, because of the > large scale changes I have created a separate branch called "primitive > filter". The garbage creation was very bad, in the original version i had > 16 garbage collections with about 5 objects and 100 bytes of garbage per > call, with xxHash (still with generics) I then had 8 collections and with > the latest version that does not create any garbage for mightContain() I > had no collections, this was with 32 million mightContain calls. This saved > about 10-15 seconds of GC pause time alone. This was with a Young > generation size of 4.6GB. > > SerializableSaltedHasher.java and IndexTagCalc.java has been removed and > the hashing and bucket index and tag is generated inside the mightContain > and put/delete methods and the actual hashing algorithm is only a few lines > for a "long" and has been moved to Utils.java . There is also the added > benefit that all references to Guava has been removed so the CuckooFilter > can be used standalone without requiring the Guava libraries. I had to make > some changes to do this such as replacing guava sanity checks on the > builders with throwable IllegalArgumentExceptions and removing some > annotations and using java math libraries and copying some Guava math > methods. > > I also played about with findTag() to see if I could get some more > speedups but my tests were hit and miss, I thought only checking all > positions in the first bucket before checking the alternative second bucket > would save a cache miss on most occasions but you would need to test it > further with JMH to see if it makes a consistent difference see> > ***@***.*** > <MPdaedalus@3ebd9fb> > > Overall in my tests the 32 Million MightContain calls has gone from 11-12 > seconds with you'r original version to 3-4 seconds with my primitive > version with xxHash. This does not include the GC pause savings mentioned > above. > > I think I have gone as far as I can with it as far as speed ups go, I > don't have any more time to work on it anymore. Feel free to msg me if you > have any bugs and let me know how much of an improvement there is on your > JMH harness. > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#2 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AG_BnPd5Cra1kIOw25X5KrOCP5Vdkh0Rks5rwq8OgaJpZM4M4LLd> > . >

[MPdaedalus]

Don't worry about it, take you'r time, I am using my version already for my own projects so you don't need to rush to merge changes. I guess you could put a link to my versions on the main project page in the mean time for users that don't want to wait for the speedup.

[MGunlogson]

@MPdaedalus If you would like ownership of this repo, I'll gladly transfer it to you.

Java still doesn't have a good Cuckoo filter implementation but mine has known bugs and misses many optimization opportunities using primitives. There's also more modern, faster hash algos now. And even off-heap storage options in Java 17+

[MPdaedalus]

thanks for the offer but I also don't have any time for this at the moment either so I must respectfully decline, I will contact you in the future if anything changes.