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

runtime/vm/bit_set.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 VM_BIT_SET_H_
 #define VM_BIT_SET_H_
 
 #include "platform/utils.h"
 #include "vm/globals.h"
 
@@ skipping 40 matching lines @@
         return (w << kBitsPerWordLog2) + Utils::CountTrailingZeros(data_[w]);
       }
     }
     return -1;
   }
 
   intptr_t Last() const {
     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_));
   }
 
   intptr_t Size() const {
     return N;
   }
 
  private:
   static const int kLengthInWords = 1 + ((N - 1) / kBitsPerWord);
   uword data_[kLengthInWords];
 };
 
 }  // namespace dart
 
 #endif  // VM_BIT_SET_H_