Bug 1415454 - Replace log2 lookup table with FloorLog2. r?njn draft
authorMike Hommey <mh+mozilla@glandium.org>
Wed, 08 Nov 2017 16:20:40 +0900
changeset 694762 6489add16ef2e96677ba96be3b8db4e508463b6f
parent 694761 5365daf0cd10d62669057867636b6213c06d266e
child 694768 3db7b72f306429326c289bd4a6c96ff79da23c3f
push id88233
push userbmo:mh+mozilla@glandium.org
push dateWed, 08 Nov 2017 07:30:11 +0000
reviewersnjn
bugs1415454
milestone58.0a1
Bug 1415454 - Replace log2 lookup table with FloorLog2. r?njn FloorLog2 expands to, essentially, a compiler builtin/intrinsic, that, in turn, expands to a single machine instruction on tier 1 and other platforms. On platforms where that's not the case, we can expect the compiler to generate fast code anyways. So overall, this is all better than manually using a log2 lookup table. Also replace a manual power-of-two check with mozilla::IsPowerOfTwo, which does the same test.
memory/build/mozjemalloc.cpp
--- a/memory/build/mozjemalloc.cpp
+++ b/memory/build/mozjemalloc.cpp
@@ -2338,43 +2338,18 @@ arena_run_reg_dalloc(arena_run_t* run, a
   static_assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3 >=
                   kNumQuantumClasses,
                 "size_invs doesn't have enough values");
 
   // Avoid doing division with a variable divisor if possible.  Using
   // actual division here can reduce allocator throughput by over 20%!
   diff =
     (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->mRunFirstRegionOffset);
-  if ((size & (size - 1)) == 0) {
-    // log2_table allows fast division of a power of two in the
-    // [1..128] range.
-    //
-    // (x / divisor) becomes (x >> log2_table[divisor - 1]).
-    // clang-format off
-    static const unsigned char log2_table[] = {
-      0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
-    };
-    // clang-format on
-
-    if (size <= 128) {
-      regind = (diff >> log2_table[size - 1]);
-    } else if (size <= 32768) {
-      regind = diff >> (8 + log2_table[(size >> 8) - 1]);
-    } else {
-      // The run size is too large for us to use the lookup
-      // table.  Use real division.
-      regind = diff / size;
-    }
+  if (mozilla::IsPowerOfTwo(size)) {
+    regind = diff >> FloorLog2(size);
   } else if (size <= ((sizeof(size_invs) / sizeof(unsigned)) * kQuantum) + 2) {
     regind = size_invs[(size / kQuantum) - 3] * diff;
     regind >>= SIZE_INV_SHIFT;
   } else {
     // size_invs isn't large enough to handle this size class, so
     // calculate regind using actual division.  This only happens
     // if the user increases small_max via the 'S' runtime
     // configuration option.