BFS for Insert path

[dave-andersen]

We should think about bringing in the BFS-based insert from libcuckoo. It permits more parallel memory accesses & work on the insert path and might give us a nice speed boost.

Barring that, I wonder if it's helpful to try to check the first two buckets in a more explicitly parallel fashion. Might not be, but we can pretty quickly determine if they're full.

[jbapple-cloudera]

I have not had luck with prefetching speeding things up when the cycles between the prefetch and the use of the bits numbers in the low dozens.

[dave-andersen]

In the case of the packed table, there's a slightly complex decode step involved that involves more bit manipulation and a dereference into a lookup table. We can actually skip that in the common case (one of the two buckets has space): You don't have to decode the packed bits to get a one-sided error guess if the bucket is full. If all (un-packed) tags are non-zero, you know it's full, so you can avoid one latency worth of the bucket fetch & decode. Interleaving the bucket search in this way should provide for a reasonable speedup for table construction on the packed table.

[scut-lz]

Hi,does anyone knows that why the speed for inserting items intio the filter is so slow? Are there any other ideas to speed up the inserting and lookuping?Thx