MDEV-19787 Speedup Table_map_iterator, via compiler intrinsics

Use __builtin_ctzll on GCC/Clang and _BitScanForward/_BitScanForward64 on
MSVC to speed up Table_map_iterator::next_bit(), up to 3 times in benchmarks

2 files changed, 50 insertions, 18 deletions

diff --git a/include/my_bit.h b/include/my_bit.h
index 7a408bd0535..ccdf5a069e1 100644
--- a/include/my_bit.h
+++ b/include/my_bit.h
@@ -130,6 +130,47 @@ static inline uchar last_byte_mask(uint bits)
   /* Return bitmask for the significant bits */
   return ((2U << used) - 1);
 }
+
+#ifdef _MSC_VER
+#include <intrin.h>
+#endif
+
+#define MY_FIND_FIRST_BIT_END sizeof(ulonglong)*8
+/*
+  Find the position of the first(least significant) bit set in
+  the argument. Returns 64 if the argument was 0.
+*/
+static inline uint my_find_first_bit(ulonglong n)
+{
+  if(!n)
+    return MY_FIND_FIRST_BIT_END;
+#if defined(__GNUC__)
+  return __builtin_ctzll(n);
+#elif defined(_MSC_VER)
+#if defined(_M_IX86)
+  unsigned long bit;
+  if( _BitScanForward(&bit, (uint)n))
+    return bit;
+  _BitScanForward(&bit, (uint)(n>>32));
+  return bit + 32;
+#else
+  unsigned long bit;
+  _BitScanForward64(&bit, n);
+  return bit;
+#endif
+#else
+  /* Generic case */
+  uint  shift= 0;
+  static const uchar last_bit[16] = { 32, 0, 1, 0,
+                                      2, 0, 1, 0,
+                                      3, 0, 1, 0,
+                                      2, 0, 1, 0};
+  uint bit;
+  while ((bit = last_bit[(n >> shift) & 0xF]) == 32)
+    shift+= 4;
+  return shift+bit;
+#endif
+}
 C_MODE_END
 
 #endif /* MY_BIT_INCLUDED */
diff --git a/sql/sql_bitmap.h b/sql/sql_bitmap.h
index 765e4ee2725..02dc8198c7c 100644
--- a/sql/sql_bitmap.h
+++ b/sql/sql_bitmap.h
@@ -27,29 +27,20 @@
 #include <my_bitmap.h>
 #include <my_bit.h>
 
-/* An iterator to quickly walk over bits in unlonglong bitmap. */
+
+/* An iterator to quickly walk over bits in ulonglong bitmap. */
 class Table_map_iterator
 {
   ulonglong bmp;
-  uint no;
 public:
-  Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
-  int next_bit()
+  Table_map_iterator(ulonglong t): bmp(t){}
+  uint next_bit()
   {
-    static const char last_bit[16] = { 32, 0, 1, 0,
-                                      2, 0, 1, 0,
-                                      3, 0, 1, 0,
-                                      2, 0, 1, 0 };
-    uint bit;
-    while ((bit= last_bit[bmp & 0xF]) == 32)
-    {
-      no += 4;
-      bmp= bmp >> 4;
-      if (!bmp)
-        return BITMAP_END;
-    }
-    bmp &= ~(1LL << bit);
-    return no + bit;
+    if (!bmp)
+      return BITMAP_END;
+    uint bit= my_find_first_bit(bmp);
+    bmp &= ~(1ULL << bit);
+    return bit;
   }
   int operator++(int) { return next_bit(); }
   enum { BITMAP_END= 64 };