You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pulsar.apache.org by "lhotari (via GitHub)" <gi...@apache.org> on 2023/09/01 08:54:15 UTC

[GitHub] [pulsar] lhotari opened a new pull request, #21107: [fix][common] Fix bug in hash bucket algorithm implementation with Long pair keys

lhotari opened a new pull request, #21107:
URL: https://github.com/apache/pulsar/pull/21107

   Fixes #21106
   
   ### Motivation
   
   - Fix a bug in ConcurrentLongLongPairHashMap, ConcurrentLongPairSet and ConcurrentOpenHashMap where the hash bucket's storage index was incorrectly calculated.
     - the impact of the bug has been that the implementations have been rather unoptimal because of of frequent collisions in storing the item to the underlying array. Essentially the hash bucket algorithm hasn't been properly used.
   
   ### Modifications
   
   - rename `bucket` to `bucketIndex` to indicate that it's the bucket index in the storage array that needs to be calculated.
   - calculate bucketIndex by multiplying the hash bucket by the item size (4 or 2).
   
   ### Documentation
   
   <!-- DO NOT REMOVE THIS SECTION. CHECK THE PROPER BOX ONLY. -->
   
   - [ ] `doc` <!-- Your PR contains doc changes. -->
   - [ ] `doc-required` <!-- Your PR changes impact docs and you will update later -->
   - [x] `doc-not-needed` <!-- Your PR changes do not impact docs -->
   - [ ] `doc-complete` <!-- Docs have been already added -->


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] thetumbled commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1312980829


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   We have ensured that the index returned by method `signSafeMod` is a multiple of `ITEM_SIZE`, why do we need to multiply by 4 again? I don't get it.



##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongHashMap.java:
##########
@@ -632,8 +632,14 @@ static final long hash(long key) {
         return hash;
     }
 
-    static final int signSafeMod(long n, int max) {
-        return (int) n & (max - 1);
+    static final int signSafeMod(long dividend, int divisor) {
+        int mod = (int) (dividend % divisor);
+
+        if (mod < 0) {
+            mod += divisor;
+        }

Review Comment:
   As `max-1 > 0`, we won't get a negative result with `(int) n & (max - 1)` even if `n` is negative. This is unnecessary.
   



##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongHashMap.java:
##########
@@ -632,8 +632,14 @@ static final long hash(long key) {
         return hash;
     }
 
-    static final int signSafeMod(long n, int max) {
-        return (int) n & (max - 1);
+    static final int signSafeMod(long dividend, int divisor) {
+        int mod = (int) (dividend % divisor);

Review Comment:
   Using `&` is faster than the `%`, which is a trick to speed up.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] codelipenghui commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "codelipenghui (via GitHub)" <gi...@apache.org>.
codelipenghui commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1315899927


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   The modern Java compilers are smart enough to recognize when multiplication is equivalent to a bit shift and can optimize the multiplication operation to use a bit shift instead. It's better to focus on writing clear, readable code.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] thetumbled commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1312980829


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   `* 4` is equivalent to `<< 2`, moving this logic out of `signSafeMod` method seems meaningless?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] thetumbled commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1313675137


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   Change method name `signSafeMod` to `hash` may be better, right? 
   And i wonder whether the compiler will do such optimizations, could you verify this? thanks.
   IMO, these util class adopt some kind of ideas from common util class like `HashMap`, which use `&` to avoid `%` too.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] codelipenghui commented on pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "codelipenghui (via GitHub)" <gi...@apache.org>.
codelipenghui commented on PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#issuecomment-1706710445

   I also left a [comment](https://github.com/apache/pulsar/pull/21110#issuecomment-1706707456) on another related PR. Maybe we should consider to replace the customized map with ConcurrentHashMap.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] lhotari commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1313198384


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   The problem with the old code is that it is cryptic. In the original code, `signSafeMod` function's name is misleading. In the cases where the item takes 2 or 4 elements, there's a bitwise shift to left to multiply by 2 (`<< 1`) or 4 (`<< 2`). I doubt that using bitwise operations to optimize the speed of execution is worthwhile in Java code. It should be left to the compiler to do such optimizations.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] lhotari commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1313198384


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   The problem with the old code is that it is cryptic. In the original code, `signSafeMod` function's name is misleading. In the cases where the item takes 2 or 4 elements, there's a bitwise shift to left to multiply by 2 (`<< 1`) or 4 (`<< 2`), directly in the `signSafeMod` function. It's bad from maintainability perspective to have functions with names that don't match the implementation. I doubt that using bitwise operations to optimize the speed of execution is worthwhile in Java code. It should be left to the compiler to do such optimizations.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] lhotari commented on pull request #21107: [fix][misc] Fix bug in hash bucket algorithm implementation with Long pair keys in Pulsar collections

Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#issuecomment-1702449320

   The `signSafeMod` bug must have impacted also all other collection classes where the invalid implementation was used.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections [pulsar]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#issuecomment-1749877147

   The pr had no activity for 30 days, mark with Stale label.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] thetumbled commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1312980829


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   `* 4` is equivalent to `<< 2`, moving this logic out of `signSafeMod` method seems meaningless?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] codelipenghui commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "codelipenghui (via GitHub)" <gi...@apache.org>.
codelipenghui commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1315906178


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentOpenHashSet.java:
##########
@@ -598,8 +598,14 @@ static final <K> long hash(K key) {
         return hash;
     }
 
-    static final int signSafeMod(long n, int max) {
-        return (int) n & (max - 1);
+    static final int signSafeMod(long dividend, int divisor) {
+        int mod = (int) (dividend % divisor);
+
+        if (mod < 0) {
+            mod += divisor;
+        }
+
+        return mod;

Review Comment:
   Can we move to a Utility Class for computing the sign safe mod?
   We have a similar [Unitity Class](https://github.com/apache/pulsar/blob/c675a3dd6b4a3a6009d2a10c38ee79d8219b1920/pulsar-client/src/main/java/org/apache/pulsar/client/util/MathUtils.java#L24) in pulsar-client, not pulsar-client-api.
   Is it better to move it to pulsar-common to reduce the duplicated code?



##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentOpenHashSet.java:
##########
@@ -598,8 +598,14 @@ static final <K> long hash(K key) {
         return hash;
     }
 
-    static final int signSafeMod(long n, int max) {
-        return (int) n & (max - 1);
+    static final int signSafeMod(long dividend, int divisor) {
+        int mod = (int) (dividend % divisor);
+
+        if (mod < 0) {
+            mod += divisor;
+        }
+
+        return mod;

Review Comment:
   @lhotari And, could you please provide more context about 
   
   
   > the impact of the bug has been that the implementations have been rather unoptimal because of of frequent collisions in storing the item to the underlying array. Essentially the hash bucket algorithm hasn't been properly used.
   
   
   The HashMap in JDK is also used the same way to calculate the table index. Why `%` is better than `&` in this case to avoid the frequent collisions?
   
   Here is the code snippet in JDK 17:
   
   ```java
           if ((p = tab[i = (n - 1) & hash]) == null)
               tab[i] = newNode(hash, key, value, null);
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] thetumbled commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1312980829


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   We have ensured that the index returned by method `signSafeMod` is a multiple of `ITEM_SIZE`, why do we need to multiply by 4 again? I don't get it.
   `* 4` is equivalent to `<< 2`, moving this logic out of `signSafeMod` method seems meaningless?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [pulsar] thetumbled commented on a diff in pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections

Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #21107:
URL: https://github.com/apache/pulsar/pull/21107#discussion_r1312980829


##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   `* 4` is equivalent to `<< 2`, moving this logic out of `signSafeMod` method seems meaningless?
   be a code optimization, instead of bugfix.



##########
pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentLongLongPairHashMap.java:
##########
@@ -322,15 +324,15 @@ private static final class Section extends StampedLock {
         LongPair get(long key1, long key2, int keyHash) {
             long stamp = tryOptimisticRead();
             boolean acquiredLock = false;
-            int bucket = signSafeMod(keyHash, capacity);
+            int bucketIndex = signSafeMod(keyHash, capacity) * ITEM_SIZE;

Review Comment:
   `* 4` is equivalent to `<< 2`, moving this logic out of `signSafeMod` method seems meaningless?
   Be a code optimization, instead of bugfix.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections [pulsar]

Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari closed pull request #21107: [fix][misc] Fix bugs in hash bucket algorithm implementation in Pulsar collections
URL: https://github.com/apache/pulsar/pull/21107


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org