You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kvrocks.apache.org by tw...@apache.org on 2023/03/28 05:49:02 UTC
[incubator-kvrocks] branch unstable updated: Rewrite popcount and bitpos in redis bitmap (#1359)
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 a2b033f9 Rewrite popcount and bitpos in redis bitmap (#1359)
a2b033f9 is described below
commit a2b033f9ca82472116de0c2b3958f0013ad8ca4d
Author: Twice <tw...@gmail.com>
AuthorDate: Tue Mar 28 13:48:56 2023 +0800
Rewrite popcount and bitpos in redis bitmap (#1359)
---
src/common/encoding.cc | 88 +++----------------
src/common/encoding.h | 10 +++
src/common/type_util.h | 25 ++++++
src/types/redis_bitmap_string.cc | 183 ++++++++++++---------------------------
src/types/redis_bitmap_string.h | 4 +-
5 files changed, 103 insertions(+), 207 deletions(-)
diff --git a/src/common/encoding.cc b/src/common/encoding.cc
index b069d6d3..20b30c9c 100644
--- a/src/common/encoding.cc
+++ b/src/common/encoding.cc
@@ -24,96 +24,29 @@
#include <limits.h>
#include <stdint.h>
#include <string.h>
-#include <sys/types.h> /* This will likely define BYTE_ORDER */
#include <unistd.h>
#include <string>
#include <utility>
-/* Byte ordering detection */
-
-#ifndef BYTE_ORDER
-#if (BSD >= 199103)
-#include <machine/endian.h>
-#else
-#if defined(linux) || defined(__linux__)
-#include <endian.h>
-#else
-#define LITTLE_ENDIAN 1234 /* least-significant byte first (vax, pc) */
-#define BIG_ENDIAN 4321 /* most-significant byte first (IBM, net) */
-#define PDP_ENDIAN 3412 /* LSB first in word, MSW first in long (pdp)*/
-
-#if defined(__i386__) || defined(__x86_64__) || defined(__amd64__) || defined(vax) || defined(ns32000) || \
- defined(sun386) || defined(MIPSEL) || defined(_MIPSEL) || defined(BIT_ZERO_ON_RIGHT) || defined(__alpha__) || \
- defined(__alpha)
-#define BYTE_ORDER LITTLE_ENDIAN
-#endif
-
-#if defined(__i386__) || defined(__x86_64__) || defined(__amd64__) || defined(vax) || defined(ns32000) || \
- defined(sun386) || defined(MIPSEL) || defined(_MIPSEL) || defined(BIT_ZERO_ON_RIGHT) || defined(__alpha__) || \
- defined(__alpha)
-#define BYTE_ORDER LITTLE_ENDIAN
-#endif
-
-#if defined(sel) || defined(pyr) || defined(mc68000) || defined(sparc) || defined(is68k) || defined(tahoe) || \
- defined(ibm032) || defined(ibm370) || defined(MIPSEB) || defined(_MIPSEB) || defined(_IBMR2) || defined(DGUX) || \
- defined(apollo) || defined(__convex__) || defined(_CRAY) || defined(__hppa) || defined(__hp9000) || \
- defined(__hp9000s300) || defined(__hp9000s700) || defined(BIT_ZERO_ON_LEFT) || defined(m68k) || defined(__sparc)
-#define BYTE_ORDER BIG_ENDIAN
-#endif
-#endif /* linux */
-#endif /* BSD */
-#endif /* BYTE_ORDER */
-
-/* Sometimes after including an OS-specific header that defines the
- * endianess we end with __BYTE_ORDER but not with BYTE_ORDER that is what
- * the Redis code uses. In this case let's define everything without the
- * underscores. */
-#ifndef BYTE_ORDER
-#ifdef __BYTE_ORDER
-#if defined(__LITTLE_ENDIAN) && defined(__BIG_ENDIAN)
-#ifndef LITTLE_ENDIAN
-#define LITTLE_ENDIAN __LITTLE_ENDIAN
-#endif
-#ifndef BIG_ENDIAN
-#define BIG_ENDIAN __BIG_ENDIAN
-#endif
-#if (__BYTE_ORDER == __LITTLE_ENDIAN)
-#define BYTE_ORDER LITTLE_ENDIAN
-#else
-#define BYTE_ORDER BIG_ENDIAN
-#endif
-#endif
-#endif
-#endif
-
-#if !defined(BYTE_ORDER) || (BYTE_ORDER != BIG_ENDIAN && BYTE_ORDER != LITTLE_ENDIAN)
-/* you must determine what the correct bit order is for
- * your compiler - the next line is an intentional error
- * which will force your compiles to bomb until you fix
- * the above macros.
- */
-#error "Undefined or invalid BYTE_ORDER"
-#endif
-
void EncodeFixed8(char *buf, uint8_t value) { buf[0] = static_cast<char>(value & 0xff); }
void EncodeFixed16(char *buf, uint16_t value) {
- if constexpr (BYTE_ORDER == LITTLE_ENDIAN) {
+ if constexpr (IsLittleEndian()) {
value = __builtin_bswap16(value);
}
__builtin_memcpy(buf, &value, sizeof(value));
}
void EncodeFixed32(char *buf, uint32_t value) {
- if constexpr (BYTE_ORDER == LITTLE_ENDIAN) {
+ if constexpr (IsLittleEndian()) {
value = __builtin_bswap32(value);
}
__builtin_memcpy(buf, &value, sizeof(value));
}
void EncodeFixed64(char *buf, uint64_t value) {
- if constexpr (BYTE_ORDER == LITTLE_ENDIAN) {
+ if constexpr (IsLittleEndian()) {
value = __builtin_bswap64(value);
}
__builtin_memcpy(buf, &value, sizeof(value));
@@ -148,16 +81,15 @@ void PutDouble(std::string *dst, double value) {
__builtin_memcpy(&u64, &value, sizeof(value));
- auto ptr = &u64;
- if ((*ptr >> 63) == 1) {
+ if ((u64 >> 63) == 1) {
// signed bit would be zero
- *ptr ^= 0xffffffffffffffff;
+ u64 ^= 0xffffffffffffffff;
} else {
// signed bit would be one
- *ptr |= 0x8000000000000000;
+ u64 |= 0x8000000000000000;
}
- PutFixed64(dst, *ptr);
+ PutFixed64(dst, u64);
}
bool GetFixed8(rocksdb::Slice *input, uint8_t *value) {
@@ -210,7 +142,7 @@ uint16_t DecodeFixed16(const char *ptr) {
__builtin_memcpy(&value, ptr, sizeof(value));
- return BYTE_ORDER == LITTLE_ENDIAN ? __builtin_bswap16(value) : value;
+ return IsLittleEndian() ? __builtin_bswap16(value) : value;
}
uint32_t DecodeFixed32(const char *ptr) {
@@ -218,7 +150,7 @@ uint32_t DecodeFixed32(const char *ptr) {
__builtin_memcpy(&value, ptr, sizeof(value));
- return BYTE_ORDER == LITTLE_ENDIAN ? __builtin_bswap32(value) : value;
+ return IsLittleEndian() ? __builtin_bswap32(value) : value;
}
uint64_t DecodeFixed64(const char *ptr) {
@@ -226,7 +158,7 @@ uint64_t DecodeFixed64(const char *ptr) {
__builtin_memcpy(&value, ptr, sizeof(value));
- return BYTE_ORDER == LITTLE_ENDIAN ? __builtin_bswap64(value) : value;
+ return IsLittleEndian() ? __builtin_bswap64(value) : value;
}
double DecodeDouble(const char *ptr) {
diff --git a/src/common/encoding.h b/src/common/encoding.h
index 3b45fd2b..27fe82eb 100644
--- a/src/common/encoding.h
+++ b/src/common/encoding.h
@@ -25,6 +25,15 @@
#include <string>
+enum class Endian {
+ LITTLE = __ORDER_LITTLE_ENDIAN__,
+ BIG = __ORDER_BIG_ENDIAN__,
+ NATIVE = __BYTE_ORDER__,
+};
+
+constexpr bool IsLittleEndian() { return Endian::NATIVE == Endian::LITTLE; }
+constexpr bool IsBigEndian() { return Endian::NATIVE == Endian::BIG; }
+
bool GetFixed8(rocksdb::Slice *input, uint8_t *value);
bool GetFixed16(rocksdb::Slice *input, uint16_t *value);
bool GetFixed32(rocksdb::Slice *input, uint32_t *value);
@@ -44,6 +53,7 @@ uint16_t DecodeFixed16(const char *ptr);
uint32_t DecodeFixed32(const char *ptr);
uint64_t DecodeFixed64(const char *ptr);
double DecodeDouble(const char *ptr);
+
char *EncodeVarint32(char *dst, uint32_t v);
void PutVarint32(std::string *dst, uint32_t v);
bool GetVarint32(rocksdb::Slice *input, uint32_t *value);
diff --git a/src/common/type_util.h b/src/common/type_util.h
new file mode 100644
index 00000000..8e90b721
--- /dev/null
+++ b/src/common/type_util.h
@@ -0,0 +1,25 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#pragma once
+
+// dependent false for static_assert with constexpr if, see CWG2518/P2593R1
+template <typename T>
+constexpr bool AlwaysFalse = false;
diff --git a/src/types/redis_bitmap_string.cc b/src/types/redis_bitmap_string.cc
index de3a2fac..d0f0f877 100644
--- a/src/types/redis_bitmap_string.cc
+++ b/src/types/redis_bitmap_string.cc
@@ -22,13 +22,14 @@
#include <glog/logging.h>
+#include <cstdint>
+
#include "redis_string.h"
#include "storage/redis_metadata.h"
+#include "type_util.h"
namespace Redis {
-extern const uint8_t kNum2Bits[256];
-
rocksdb::Status BitmapString::GetBit(const std::string &raw_value, uint32_t offset, bool *bit) {
auto string_value = raw_value.substr(Metadata::GetOffsetAfterExpire(raw_value[0]));
uint32_t byte_index = offset >> 3;
@@ -84,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((unsigned char *)(&string_value[0] + start), bytes);
+ *cnt = redisPopcount(reinterpret_cast<const uint8_t *>(string_value.data()) + start, bytes);
}
return rocksdb::Status::OK();
}
@@ -104,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((unsigned char *)(&string_value[0] + start), bytes, bit);
+ *pos = redisBitpos(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
@@ -125,59 +126,34 @@ rocksdb::Status BitmapString::BitPos(const std::string &raw_value, bool bit, int
/* Count number of bits set in the binary array pointed by 's' and long
* 'count' bytes. The implementation of this function is required to
* work with a input string length up to 512 MB.
- *
- * This is a function from the redis project.
- * This function started out as:
- * https://github.com/antirez/redis/blob/94f2e7f/src/bitops.c#L40
* */
-size_t BitmapString::redisPopcount(unsigned char *p, int64_t count) {
+size_t BitmapString::redisPopcount(const uint8_t *p, int64_t count) {
size_t bits = 0;
- /* Count initial bytes not aligned to 32 bit. */
- while (reinterpret_cast<uint64_t>(p) & 3 && count) {
- bits += kNum2Bits[*p++];
- count--;
+ for (; count >= 8; p += 8, count -= 8) {
+ bits += __builtin_popcountll(*reinterpret_cast<const uint64_t *>(p));
}
- /* Count bits 28 bytes at a time */
- auto p4 = reinterpret_cast<uint32_t *>(p);
- while (count >= 28) {
- uint32_t aux1 = *p4++;
- uint32_t aux2 = *p4++;
- uint32_t aux3 = *p4++;
- uint32_t aux4 = *p4++;
- uint32_t aux5 = *p4++;
- uint32_t aux6 = *p4++;
- uint32_t aux7 = *p4++;
- count -= 28;
-
- aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
- aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
- aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
- aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
- aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
- aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
- aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
- aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
- aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
- aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
- aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
- aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
- aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
- aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
- bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) + ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
- ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) + ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
- ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) + ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
- ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F)) *
- 0x01010101) >>
- 24;
+ if (count > 0) {
+ uint64_t v = 0;
+ __builtin_memcpy(&v, p, count);
+ bits += __builtin_popcountll(v);
}
- /* Count the remaining bytes. */
- p = (unsigned char *)p4;
- while (count--) bits += kNum2Bits[*p++];
+
return bits;
}
+template <typename T = void>
+inline int clzllWithEndian(uint64_t x) {
+ if constexpr (IsLittleEndian()) {
+ return __builtin_clzll(__builtin_bswap64(x));
+ } else if constexpr (IsBigEndian()) {
+ return __builtin_clzll(x);
+ } else {
+ static_assert(AlwaysFalse<T>);
+ }
+}
+
/* Return the position of the first bit set to one (if 'bit' is 1) or
* zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes.
*
@@ -185,94 +161,47 @@ size_t BitmapString::redisPopcount(unsigned char *p, int64_t count) {
* no zero bit is found, it returns count*8 assuming the string is zero
* 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.
- *
- * This is a function from the redis project.
- * This function started out as:
- * https://github.com/antirez/redis/blob/94f2e7f/src/bitops.c#L101
* */
-int64_t BitmapString::redisBitpos(unsigned char *c, int64_t count, int bit) {
- uint64_t *l = nullptr;
- uint64_t skipval = 0, word = 0, one = 0;
- int64_t pos = 0; /* Position of bit, to return to the caller. */
- uint64_t j = 0;
- int found = 0;
-
- /* Process whole words first, seeking for first word that is not
- * all ones or all zeros respectively if we are lookig for zeros
- * or ones. This is much faster with large strings having contiguous
- * blocks of 1 or 0 bits compared to the vanilla bit per bit processing.
- *
- * Note that if we start from an address that is not aligned
- * to sizeof(unsigned long) we consume it byte by byte until it is
- * aligned. */
-
- /* Skip initial bits not aligned to sizeof(unsigned long) byte by byte. */
- skipval = bit ? 0 : UCHAR_MAX;
- found = 0;
- while (reinterpret_cast<uint64_t>(c) & (sizeof(*l) - 1) && count) {
- if (*c != skipval) {
- found = 1;
- break;
+int64_t BitmapString::redisBitpos(const uint8_t *c, int64_t count, bool bit) {
+ int64_t res = 0;
+
+ if (bit) {
+ int64_t ct = count;
+
+ for (; count >= 8; c += 8, count -= 8) {
+ uint64_t x = *reinterpret_cast<const uint64_t *>(c);
+ if (x != 0) {
+ return res + clzllWithEndian(x);
+ }
+ res += 64;
}
- c++;
- count--;
- pos += 8;
- }
- /* Skip bits with full word step. */
- l = reinterpret_cast<uint64_t *>(c);
- if (!found) {
- skipval = bit ? 0 : UINT64_MAX;
- while (count >= static_cast<int>(sizeof(*l))) {
- if (*l != skipval) break;
- l++;
- count -= sizeof(*l);
- pos += sizeof(*l) * 8;
+ if (count > 0) {
+ uint64_t v = 0;
+ __builtin_memcpy(&v, c, count);
+ res += v == 0 ? count * 8 : clzllWithEndian(v);
}
- }
- /* Load bytes into "word" considering the first byte as the most significant
- * (we basically consider it as written in big endian, since we consider the
- * string as a set of bits from left to right, with the first bit at position
- * zero.
- *
- * Note that the loading is designed to work even when the bytes left
- * (count) are less than a full word. We pad it with zero on the right. */
- c = reinterpret_cast<unsigned char *>(l);
- for (j = 0; j < sizeof(*l); j++) {
- word <<= 8;
- if (count) {
- word |= *c;
- c++;
- count--;
+ if (res == ct * 8) {
+ return -1;
+ }
+ } else {
+ for (; count >= 8; c += 8, count -= 8) {
+ uint64_t x = *reinterpret_cast<const uint64_t *>(c);
+ if (x != (uint64_t)-1) {
+ return res + clzllWithEndian(~x);
+ }
+ res += 64;
}
- }
-
- /* Special case:
- * If bits in the string are all zero and we are looking for one,
- * return -1 to signal that there is not a single "1" in the whole
- * string. This can't happen when we are looking for "0" as we assume
- * that the right of the string is zero padded. */
- if (bit == 1 && word == 0) return -1;
-
- /* Last word left, scan bit by bit. The first thing we need is to
- * have a single "1" set in the most significant position in an
- * unsigned long. We don't know the size of the long so we use a
- * simple trick. */
- one = UINT64_MAX; /* All bits set to 1.*/
- one >>= 1; /* All bits set to 1 but the MSB. */
- one = ~one; /* All bits set to 0 but the MSB. */
- while (one) {
- if (((one & word) != 0) == bit) return pos;
- pos++;
- one >>= 1;
+ if (count > 0) {
+ uint64_t v = -1;
+ __builtin_memcpy(&v, c, count);
+ res += v == (uint64_t)-1 ? count * 8 : clzllWithEndian(~v);
+ }
}
- /* If we reached this point, there is a bug in the algorithm, since
- * the case of no match is handled as a special case before. */
- LOG(ERROR) << "End of redisBitpos() reached.";
- return 0; /* Just to avoid warnings. */
+ return res;
}
} // namespace Redis
diff --git a/src/types/redis_bitmap_string.h b/src/types/redis_bitmap_string.h
index 74cb35a4..cca3fcc7 100644
--- a/src/types/redis_bitmap_string.h
+++ b/src/types/redis_bitmap_string.h
@@ -38,8 +38,8 @@ class BitmapString : public Database {
int64_t *pos);
private:
- static size_t redisPopcount(unsigned char *p, int64_t count);
- static int64_t redisBitpos(unsigned char *c, int64_t count, int bit);
+ static size_t redisPopcount(const uint8_t *p, int64_t count);
+ static int64_t redisBitpos(const uint8_t *c, int64_t count, bool bit);
};
} // namespace Redis