A suggestion of code improvement for BloomFilter.

longlong354 commented 3 months ago

API(s)

com.google.common.hash.BloomFilter::optimalNumOfBits(long n, double p)
&
com.google.common.hash.BloomFilter::optimalNumOfHashFunctions(long n, long m)

How do you want it to be improved?

1. use static caculated value of log(2) and squared log(2) :

        private static final double LOG_TWO = Math.log(2);
    private static final double SQUARED_LOG_TWO = Math.pow(LOG_TWO,2);

2. calculate optimalNumOfBits by static values:

    static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / SQUARED_LOG_TWO);
    }

3. caculate optimalNumOfHashFunction by false positive rate(p) directly and using LOG_TWO :

        static int optimalNumOfHashFunctions(double p){
        return  Math.max(1, (int) Math.round( - Math.log(p) / LOG_TWO));
    }

Why do we need it to be improved?

Slightly reduce the method's execution time.
Refine the calculation of the optimalNumOfHashFunctions method to be more concise and efficient. The current code may lead people to mistakenly believe that the result is related to the number of samples(n) and the number of bits（m）, when in fact it is only related to the false positive rate(p).

Example

as the given codes in  “How do you want it to be improved”

Current Behavior

as the source codes in “How do you want it to be improved”

Desired Behavior

as the given codes in com.google.common.hash.BloomFilter::optimalNumOfBits(long n, double p) & com.google.common.hash.BloomFilter::optimalNumOfHashFunctions(long n, long m)

Concrete Use Cases

as "How do you want it to be improved"

Checklist

[X] I agree to follow the code of conduct.
[X] I have read and understood the contribution guidelines.
[X] I have read and understood Guava's philosophy, and I strongly believe that this proposal aligns with it.

eamonnmcmanus commented 3 months ago

This appears to have been a deliberate change back in 2012. Maybe @kluever remembers the rationale.

longlong354 commented 3 months ago

Thanks for reply. My fault didn't express the main point clearly enough. The main recommendation is using

optimalNumOfHashFunctions(double p)

instead of

optimalNumOfHashFunctions(long n, long m)

Ayush-Thakur-geek commented 2 months ago

Hey, @longlong354

So, you just want the usage of (double p) and not (long m, long n) as argument for bloomfilter.

eamonnmcmanus commented 2 months ago

The situation now is roughly that we start from $n$, the expected number of entries, and $p$, the desired false positive probability, and we derive $m$, the optimal number of bits, as

$$ m = \lfloor {-n\ \ln\ p } / { (\ln\ 2)^2} \rfloor $$

Then we further derive $k$, the optimal number of hash functions, as

$$ k = (m / n)\ \ln\ 2 \approx {-n\ \ln\ p } / { \ln\ 2} $$

rounded to an integer. You are proposing instead

$$ k = { -\ln\ p } / { \ln\ 2 } $$

removing the factor of $n$. That's a different number. Are you saying that it's more accurate? Could you explain why?

longlong354 commented 2 months ago

The derivation of the formula

k = (m / n) ln 2 ≈ -n ln p / ln 2

is inaccurate; it should be

k = (m / n) ln 2 ≈ - ln p / ln 2

Please kindly note that the bolded 'n' in the numerator cancels out with the 'n' in m( m = ⌊ − n ln ⁡ p / ( ln ⁡ 2 ) 2 ⌋ )"

ps: refering to https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions also can be verified in https://krisives.github.io/bloom-calculator/ that n does not affect k

longlong354 commented 2 months ago

Hey, @longlong354

So, you just want the usage of (double p) and not (long m, long n) as argument for bloomfilter.

yep~

Romain-E commented 1 month ago

Hi, I would like to take on this issue. I propose optimizing the optimalNumOfBits and optimalNumOfHashFunctions methods as follows:

Pre-calculate constant values for log(2) and log(2)^2 to avoid recalculating these in each method call, which will slightly improve performance.
Refine the calculation of optimalNumOfBits to ensure a false positive rate of 0 is handled by setting it to Double.MIN_VALUE, and use the pre-calculated values for efficiency.
Simplify optimalNumOfHashFunctions to calculate the number of hash functions directly from the false positive rate p, as this is the only factor affecting the result, rather than the number of elements n and bits m. These changes will clarify the logic and improve performance.

Please let me know if I can proceed with these modifications!

eamonnmcmanus commented 1 month ago

Sorry, I lost track of this issue.

@longlong354 is right that the algebra in my earlier comment was incorrect, and it does seem as if rewriting the code as suggested would make sense.

I still don't know why the code was rewritten in 2012 to remove the pre-calculation of $\ln\ 2$ and $\ln^2\ 2$. I expect that the JIT compiler is able to inline these constants, but we could reasonably do it explicitly and save it the work.

I think we would accept a PR on the lines of the original comment. If @longlong354 wants to send that PR I think that would make the most sense, and otherwise @Romain-E. The only non-obvious thing I see is how to adjust the corresponding tests in BloomFilterTest. I think the second test method is no longer relevant but I'm not sure about the first.

Romain-E commented 1 month ago

I concur that the second test (testOptimalNumOfHashFunctionsRounding) no longer applies with the new approach and should probably be removed. The first test (testOptimalHashes) could be adjusted to work with the updated method by testing for different values of p rather than n and m. Alternatively, we could add a method that derives p from n and m and maintain the test in a slightly modified form.

Let me know if this direction works for you, and I’d be happy to proceed with the PR.

longlong354 commented 1 month ago

Thank u all for the discussion. Pls proceed @Romain-E, thanks in advance.

Romain-E commented 1 week ago

Hi ! I hope this message finds you well! I wanted to check in regarding PR #7346. I would be grateful if you could take a look whenever time allows, as I am eager to understand any feedback you might have to improve this optimization further.

Thanks again for your time and consideration, and please let me know if there's anything specific I should adjust.

Best regards

longlong354 commented 1 week ago

Hi ! I hope this message finds you well! I wanted to check in regarding PR #7346. I would be grateful if you could take a look whenever time allows, as I am eager to understand any feedback you might have to improve this optimization further.

Thanks again for your time and consideration, and please let me know if there's anything specific I should adjust.

Best regards

Looks perfect. Benefited a great deal from the changes on max(). Almost fogot static import feature in Java, thanks a lot~

Romain-E commented 4 days ago

Hello ! Do I need to change anything after this commit ? Or is it good ? I've never worked on this project before.

google / guava