Speed up freelist by using intrinsics to find last set bit.

runtime/vm/bit_set.h

Index: runtime/vm/bit_set.h
===================================================================
--- runtime/vm/bit_set.h	(revision 39895)
+++ runtime/vm/bit_set.h	(working copy)
@@ -58,13 +58,27 @@
     for (int w = kLengthInWords - 1; w >= 0; --w) {
       uword d = data_[w];
       if (d != 0) {
-        // TODO(koda): Define HighestBit(uword) or use uint64_t[] for data_.
-        return (w << kBitsPerWordLog2) + Utils::HighestBit(d);
+        return ((w + 1) << kBitsPerWordLog2) - Utils::CountLeadingZeros(d) - 1;
       }
     }
     return -1;
   }
 
+  intptr_t ClearLastAndFindPrevious(intptr_t current_last) {
+    ASSERT(Test(current_last));
+    ASSERT(Last() == current_last);
+    intptr_t w = current_last >> kBitsPerWordLog2;
+    uword mask = (static_cast<uword>(1) << (current_last & (kBitsPerWord - 1)));
+    data_[w] ^= mask;
+    do {
+      uword d = data_[w];
+      if (d != 0) {
+        return ((w + 1) << kBitsPerWordLog2) - Utils::CountLeadingZeros(d) - 1;
+      }
+    } while (--w >= 0);

[Ivan Posva, 2014/09/08 06:58:08]

I find this loop hard to read. In addition it visually bothers me that the
data_[w] value is read twice, once outside and once inside the loop.

[koda, 2014/09/09 20:51:41]

I aimed for consistency with existing code.

Uploaded a new version that separates the read from the write and moves the
return out of the loop; do you find it easier to read?

+    return -1;
+  }
+
   void Reset() {
     memset(data_, 0, sizeof(data_));
   }