[incubator-kvrocks] branch unstable updated: Use more efficient popcount in Redis::Bitmap (#1363)

[tw...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

twice pushed a commit to branch unstable
in repository https://gitbox.apache.org/repos/asf/incubator-kvrocks.git


The following commit(s) were added to refs/heads/unstable by this push:
     new f36842c4 Use more efficient popcount in Redis::Bitmap (#1363)
f36842c4 is described below

commit f36842c49ff7619c5bb3fbc927d62a0df9bc7b16
Author: Twice <tw...@gmail.com>
AuthorDate: Sun Apr 2 20:22:40 2023 +0800

    Use more efficient popcount in Redis::Bitmap (#1363)
---
 src/types/redis_bitmap.cc        | 16 +++-------------
 src/types/redis_bitmap_string.cc |  8 ++++----
 src/types/redis_bitmap_string.h  |  5 ++---
 3 files changed, 9 insertions(+), 20 deletions(-)

diff --git a/src/types/redis_bitmap.cc b/src/types/redis_bitmap.cc
index bf5fbf11..21060129 100644
--- a/src/types/redis_bitmap.cc
+++ b/src/types/redis_bitmap.cc
@@ -38,15 +38,6 @@ const char kErrBitmapStringOutOfRange[] =
     "The size of the bitmap string exceeds the "
     "configuration item max-bitmap-to-string-mb";
 
-extern const uint8_t kNum2Bits[256] = {
-    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2,
-    3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
-    3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
-    6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
-    3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
-    5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
-    6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
-
 rocksdb::Status Bitmap::GetMetadata(const Slice &ns_key, BitmapMetadata *metadata, std::string *raw_value) {
   std::string old_metadata;
   metadata->Encode(&old_metadata);
@@ -263,10 +254,9 @@ rocksdb::Status Bitmap::BitCount(const Slice &user_key, int64_t start, int64_t s
     if (s.IsNotFound()) continue;
     size_t j = 0;
     if (i == start_index) j = u_start % kBitmapSegmentBytes;
-    for (; j < value.size(); j++) {
-      if (i == stop_index && j > (u_stop % kBitmapSegmentBytes)) break;
-      *cnt += kNum2Bits[static_cast<uint8_t>(value[j])];
-    }
+    auto k = static_cast<int64_t>(value.size());
+    if (i == stop_index) k = u_stop % kBitmapSegmentBytes + 1;
+    *cnt += BitmapString::RawPopcount(reinterpret_cast<const uint8_t *>(value.data()) + j, k);
   }
   return rocksdb::Status::OK();
 }
diff --git a/src/types/redis_bitmap_string.cc b/src/types/redis_bitmap_string.cc
index d0f0f877..fc656f40 100644
--- a/src/types/redis_bitmap_string.cc
+++ b/src/types/redis_bitmap_string.cc
@@ -85,7 +85,7 @@ rocksdb::Status BitmapString::BitCount(const std::string &raw_value, int64_t sta
    * zero can be returned is: start > stop. */
   if (start <= stop) {
     int64_t bytes = stop - start + 1;
-    *cnt = redisPopcount(reinterpret_cast<const uint8_t *>(string_value.data()) + start, bytes);
+    *cnt = RawPopcount(reinterpret_cast<const uint8_t *>(string_value.data()) + start, bytes);
   }
   return rocksdb::Status::OK();
 }
@@ -105,7 +105,7 @@ rocksdb::Status BitmapString::BitPos(const std::string &raw_value, bool bit, int
     *pos = -1;
   } else {
     int64_t bytes = stop - start + 1;
-    *pos = redisBitpos(reinterpret_cast<const uint8_t *>(string_value.data()) + start, bytes, bit);
+    *pos = RawBitpos(reinterpret_cast<const uint8_t *>(string_value.data()) + start, bytes, bit);
 
     /* If we are looking for clear bits, and the user specified an exact
      * range with start-end, we can't consider the right of the range as
@@ -127,7 +127,7 @@ rocksdb::Status BitmapString::BitPos(const std::string &raw_value, bool bit, int
  * 'count' bytes. The implementation of this function is required to
  * work with a input string length up to 512 MB.
  * */
-size_t BitmapString::redisPopcount(const uint8_t *p, int64_t count) {
+size_t BitmapString::RawPopcount(const uint8_t *p, int64_t count) {
   size_t bits = 0;
 
   for (; count >= 8; p += 8, count -= 8) {
@@ -162,7 +162,7 @@ inline int clzllWithEndian(uint64_t x) {
  * padded on the right. However if 'bit' is 1 it is possible that there is
  * not a single set bit in the bitmap. In this special case -1 is returned.
  * */
-int64_t BitmapString::redisBitpos(const uint8_t *c, int64_t count, bool bit) {
+int64_t BitmapString::RawBitpos(const uint8_t *c, int64_t count, bool bit) {
   int64_t res = 0;
 
   if (bit) {
diff --git a/src/types/redis_bitmap_string.h b/src/types/redis_bitmap_string.h
index cca3fcc7..bf6d7fda 100644
--- a/src/types/redis_bitmap_string.h
+++ b/src/types/redis_bitmap_string.h
@@ -37,9 +37,8 @@ class BitmapString : public Database {
   static rocksdb::Status BitPos(const std::string &raw_value, bool bit, int64_t start, int64_t stop, bool stop_given,
                                 int64_t *pos);
 
- private:
-  static size_t redisPopcount(const uint8_t *p, int64_t count);
-  static int64_t redisBitpos(const uint8_t *c, int64_t count, bool bit);
+  static size_t RawPopcount(const uint8_t *p, int64_t count);
+  static int64_t RawBitpos(const uint8_t *c, int64_t count, bool bit);
 };
 
 }  // namespace Redis