Telling the GoogleBot to not index your site doesn't necessarily remove your site from Google. They can and often do still show your site but they replace your description a generic statement that they can't show it because you have decided not to include your site in their index. It is crazy but true.
Word-Aligned Bloom Filters
51–60 of 82 posts
Re: Word-Aligned Bloom Filters
#52Oh, that's elegant. If I math right, setting 5 bits in a 64-bit word extends the effective length of the hash function by approximately (5-1) * log_2(64) = (5-1) * 6 = 24 bits. In a simple bloom filter of storage size m bits, the hash functions have length log_2(m). All else being equal, the number of hash functions used -- hence the number of memory reads per lookup -- gets reduced by a factor of log_2(m) / [24 + lo…
Each word in this design is a little bloom filter. It has number of bits (m)=64; number of hashes (k)=5; and going for 1% false positive rate, which per formula (with n being number of items in the filter) in [1] is:
fpr = (1 - e ^ -(k * n)/m ) ^ k
There is exactly 1 hash function (to compute the 64 bit key). 5 bits are pseudo-randomly selected (giving us k=5) and written to an array element indexed off of the 64 bit key itself.
So sizing this [naively] is a matter of taking your n (say 4 million items) and dividing by 4 and getting a 1 million array of words.
What is not discussed in detail is block selection. Given the segmented nature of the array based data structure, distributing exactly 4 items per word is impossible for an on-line filter (as that requires perfect hashing). So, the actual 'load' capacity of this filter is, in array form, a fraction of 4 x array-len. Precisely, given an array of size S words, with capacity of Sx4, well before we reach Sx4, our keys will resolve to array elements, the little micro filters, that already have 4 registrations. Inserting the full allocated capacity (Sx4) will certainly result in a significant number of words having n greater than 4, which reduces the false positive rate. At 5 items we have fpr at 3.5%, and at 6 fpr is 7.3%. Equally, some array elements (words) will have less than 4 elements, getting exceptional fprs. For example, at 2 entries, fpr is 0.0063%! If we load the full capacity, we can no longer make statements about "1%" false positive rates, as OP does, it should be noted.
So, you either have to keep track of elements assigned to words (3 bits / word to count 0..4), or you compute a probable value to minimize overloaded array elements, keeping max writes to a word to 4 items. My guess would be ~70%ish utilization range of allocated memory. In this case, we get our desired 1% (max) but get bonuses of fortunate keys that land in underloaded words and get super high assurances at the cost of eating a bit of space inefficiency. /g
So this is the classic ball into bins question [2]. For hashes, the surprising but powerful 2 choice approach gets us high 90%s load factors. I'd recommend that. Yes, we'll x2 hashing and cache-line costs, but loading factor will be in high 90s range. Here OP should examine two candidate words, and pick the one with least items. [On look ups, we have 2 filters (words), one of which asserts it doesn't have it, and another that is 99% sure it does. Or both disclaim having it.]
[1]: https://en.wikipedia.org/wiki/Bloom_filter#Probability_of_fa...
[2]: https://en.wikipedia.org/wiki/Balls_into_bins_problem
p.s. to OP: you could also return the fpr if you keep track of items per word so the call site has insight into the assurances. That would be useful for a probabilistic data structure.
Re: Word-Aligned Bloom Filters
#53At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!
This article has a pretty good explanation, IMO: https://freecontent.manning.com/all-about-bloom-filters/
Re: Word-Aligned Bloom Filters
#54Earlier quoted context omitted.
yep, great fan of his work here. thanks for sharing that podcast. that kind of optimization requires you to know your machine architecture quite well. SIMD optimizations aren't new. but it's always amazing to see these performance increases on a single machine! our CPUs and GPUs are quite amazing. we have decided, as a field, that we can get enough virtual CPUs, GPUs, or RAM on-demand. and that we shouldn't concern o…
Simd convinced me to take college courses in algorithms and to learn higher maths. Things like image decoding rely heavily on doing transformations, and you just have to know the math behind it to an exact point to be able to effectively turn scalar math to vector effectively. Ontop of this you have to identify what can and cannot be vectorized and how it can be integrated. Working in simd isn't too hard In itself on…
Thanks: Any books / blogs you'd recommend?
Re: Word-Aligned Bloom Filters
#55Earlier quoted context omitted.
Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter. As with anything, there are tradeoffs and your requirements can change…
> As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it. We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to th…
> We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are.
Nothing says a bloom filter has to be the only data structure you use. It's a performance optimization; even if 1% of the time you have to consult a more expensive data structure to confirm your result, it can still save you a lot of computation in the long run.
> Finding just one hash collision in a wide hash is computationally stupidly hard.
But bloom filters don't use wide hashes; the domain of the hash function is the number of bits in the filter.
> Domains cost quite a lot of money so that is still pretty unrealistic.
In the case of malware, the cost of buying domains isn't that relevant, because you can compromise existing domains using automated attacks.
Re: Word-Aligned Bloom Filters
#56I find these optimizations fascinating. Anyone familiar with Lemire likely knows about this, but I listened to a podcast episode[1] with him a few days ago and learned about `simdjson`, the tool he authored that parses JSON at 25x the speed of the standard C++ library.[2][3] It's worth looking at if you're into this sort of thing. 1. https://corecursive.com/frontiers-of-performance-with-daniel... 2. https://www.youtu…
For some reason, writing a less-that-completey-naive JSON parser for C++ seems to be a right of passage for all C++ developers who eventually go on to great things.
Re: Word-Aligned Bloom Filters
#57Earlier quoted context omitted.
yep, great fan of his work here. thanks for sharing that podcast. that kind of optimization requires you to know your machine architecture quite well. SIMD optimizations aren't new. but it's always amazing to see these performance increases on a single machine! our CPUs and GPUs are quite amazing. we have decided, as a field, that we can get enough virtual CPUs, GPUs, or RAM on-demand. and that we shouldn't concern o…
Simd convinced me to take college courses in algorithms and to learn higher maths. Things like image decoding rely heavily on doing transformations, and you just have to know the math behind it to an exact point to be able to effectively turn scalar math to vector effectively. Ontop of this you have to identify what can and cannot be vectorized and how it can be integrated. Working in simd isn't too hard In itself on…
After listening to the JSON episode, I've been spending the last few days coding up a SIMD implementation of LZ77 substring matching, for use in DEFLATE.
I used Zig, which has first-class SIMD support. As in, no need to go down to the assembly or use intrinsics, or even use a library. I just got it working and haven't had time to profile it, however (I'm new to profiling code).
Re: Word-Aligned Bloom Filters
#58This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase. Let's take an extreme case: You have 250 million paying customers you want to cache access to. Yeah, that's way more than you probably have, but the point is that you can keep 250 million integers in memory no problem what so ever. It fits in a gigabyte. There are raspberry pis with eight times that amou…
A Bloom filter with 1% FPR would fit in 285 MB and need 7 accesses per key.
Re: Word-Aligned Bloom Filters
#59I'm really suspicious about whether this would really work out in most workloads. On modern architectures, it's the random memory reference that kills performance. Predictive pre-fetching in the pipeline has a impossible time figuring out what to get ready in the caches with random lookups; it's not like a linear sweep. This style of bloom-filter needs to be quite large, and it pulls only one cache-line in per key lo…
> I'm really suspicious about whether this would really work out in most workloads. What kinds of workloads are those? Workloads where the Bloom filter itself fits in cache? > On modern architectures, it's the random memory reference that kills performance Yeah, the whole point of the article is that moving from a traditional Bloom filter to a block Bloom filter is to improve from N random accesses per query/update t…
If you had many lookups to do, then an approach with a coroutine that issues a prefetch instruction then yields to other lookups while the data is fetched in memory might be effective.
Similar to this: http://www.vldb.org/pvldb/vol11/p1702-jonathan.pdf
Re: Word-Aligned Bloom Filters
#60At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!
I always think of them as "bouncer filter."
Think of them as asking a bouncer if they have seen a suspect enter a club. They don't know folks by name, but can answer a series questions about the people that entered.
Then, the "hashes" are effectively your new questions. Did someone with green hair enter? Did someone limping enter? Wearing a hat? Etc
To that end, it is clear that you won't get a definitive yes to entry. You may get a sufficient no, though.