Improve the performance of bit set searches with a compiler intrinsic.

runtime/platform/utils.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef PLATFORM_UTILS_H_
 #define PLATFORM_UTILS_H_
 
 #include "platform/assert.h"
 #include "platform/globals.h"
 
@@ skipping 61 matching lines @@
   }
 
   template<typename T>
   static inline T* RoundUp(T* x, int n) {
     return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uword>(x), n));
   }
 
   static uint32_t RoundUpToPowerOfTwo(uint32_t x);
   static int CountOneBits(uint32_t x);
 
+  static int CountTrailingZeros(uint32_t x);
+  static int CountTrailingZeros(uint64_t x);

[siva, 2012/07/24 01:07:43]

I am wondering if it makes sense to just have one version of
this 
static int CountTrailingZeros(uword x);
and in the implementation use
#if defined(ARCH_IS_64_BIT)
#elif defined(ARCH_IS_32_BIT)
#else
#error ...
#endif

[cshapiro, 2012/07/24 02:43:50]

Originally, I wrote this method as a template like so

template<typename T>
int CountTrailingZeros(T x) {
  if (sizeof(x) == 4) // 32-bit intrinsic
  else if (sizeof(x) == 8) // 64 bit intrinsic
  else // assert
}

This looked a bit ugly and seemed like overkill so I just punted on it and
settled on separate versions for 32-bit and 64-bit because the other two bit
operations on lines 79 and 80 were specified for 32-bit words and not a uword.

However, this might just be shortsightedness and maybe all of these functions
should be defined for uword only.  Let me know what you think and I will happily
fix this and do a cleanup for the other 2 definitions as well.

+
   // Computes a hash value for the given string.
   static uint32_t StringHash(const char* data, int length);
 
   // Computes a hash value for the given word.
   static uint32_t WordHash(word key);
 
   // Check whether an N-bit two's-complement representation can hold value.
   template<typename T>
   static inline bool IsInt(int N, T value) {
     ASSERT((0 < N) &&
@@ skipping 71 matching lines @@
                                 intptr_t length) {
     return offset >= 0 &&
            count >= 0 &&
            length >= 0 &&
            count <= (length - offset);
   }
 };
 
 }  // namespace dart
 
+#if defined(TARGET_OS_LINUX)
+#include "platform/utils_linux.h"
+#elif defined(TARGET_OS_MACOS)
+#include "platform/utils_macos.h"
+#elif defined(TARGET_OS_WINDOWS)
+#include "platform/utils_win.h"
+#else
+#error Unknown target os.
+#endif
+
 #endif  // PLATFORM_UTILS_H_