Fix Issue 11047: use binary search instead of linear search to locate a pc-offset in the static cal…

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 23566)
+++ runtime/vm/object.cc	(working copy)
@@ -7783,6 +7783,14 @@
 
 void Code::set_static_calls_target_table(const Array& value) const {
   StorePointer(&raw_ptr()->static_calls_target_table_, value.raw());
+#if defined(DEBUG)
+  // Check that the table is sorted by pc offsets.

[Florian Schneider, 2013/06/04 08:36:49]

Maybe I missed something, but where do we sort this table?

[srdjan, 2013/06/04 15:45:27]

Added comment
  // FlowGraphCompiler::AddStaticCallTarget adds pc-offsets to the table while
  // emitting assembly. This guarantees that every succeeding pc-offset is
  // larger than the previously added one.

+  for (intptr_t i = kSCallTableEntryLength;
+      i < value.Length();
+      i += kSCallTableEntryLength) {
+    ASSERT(value.At(i - kSCallTableEntryLength) < value.At(i));
+  }
+#endif  // DEBUG
 }
 
 
@@ -7810,19 +7818,39 @@
 }
 
 
+intptr_t Code::BinarySearchInSCallTable(RawObject* key) const {

[siva, 2013/06/03 23:35:35]

Can we change the signature of this function to
intptr_t Code::BinarySearchInSCallTable(intptr_t code_offset);

and move the
RawSmi* raw_code_offset = Smi::New(code_offset);
into this function.

[siva, 2013/06/03 23:38:25]

An even better option might be to pass the pc itself
i.e:
intptr_t Code::BinarySearchInSCallTable(uword pc);

RawSmi* raw_code_offset = Smi::New(pc - EntryPoint());

[srdjan, 2013/06/04 15:45:27]

Done.

[srdjan, 2013/06/04 15:45:27]

Using other suggestion (passing pc).

+  NoGCScope no_gc;
+  const Array& table = Array::Handle(raw_ptr()->static_calls_target_table_);
+  intptr_t imin = 0;
+  intptr_t imax = table.Length() / kSCallTableEntryLength;
+  while (imax >= imin) {
+    const intptr_t imid = ((imax - imin) / 2) + imin;
+    const intptr_t real_index = imid * kSCallTableEntryLength;
+    RawObject* key_in_table = table.At(real_index);

[siva, 2013/06/03 23:35:35]

This can be
RawSmi* key_in_table = Smi::RawCast(table.At(real_index);

[srdjan, 2013/06/04 15:45:27]

Using other suggestion (passing pc).

+    if (key_in_table < key) {
+      imin = imid + 1;
+    } else if (key_in_table > key) {
+      imax = imid - 1;
+    } else {
+      return real_index;
+    }
+  }
+  return -1;
+}
+
+
 RawFunction* Code::GetStaticCallTargetFunctionAt(uword pc) const {
   RawObject* raw_code_offset =
       reinterpret_cast<RawObject*>(Smi::New(pc - EntryPoint()));
+  const intptr_t i = BinarySearchInSCallTable(raw_code_offset);

[siva, 2013/06/03 23:35:35]

This would be just:

const intptr_t i = BinarySearchInSCallTable(pc - EntryPoint());

[siva, 2013/06/03 23:38:25]

And this would be:

const intptr_t i = BinarySearchInSCallTable(pc);

[srdjan, 2013/06/04 15:45:27]

Done.

[srdjan, 2013/06/04 15:45:27]

Using other suggestion (passing pc).

+  if (i < 0) {
+    return Function::null();
+  }
   const Array& array =
       Array::Handle(raw_ptr()->static_calls_target_table_);
-  for (intptr_t i = 0; i < array.Length(); i += kSCallTableEntryLength) {
-    if (array.At(i) == raw_code_offset) {
-      Function& function = Function::Handle();
-      function ^= array.At(i + kSCallTableFunctionEntry);
-      return function.raw();
-    }
-  }
-  return Function::null();
+  Function& function = Function::Handle();
+  function ^= array.At(i + kSCallTableFunctionEntry);
+  return function.raw();
 }
 
 
@@ -7831,15 +7859,11 @@
       reinterpret_cast<RawObject*>(Smi::New(pc - EntryPoint()));
   const Array& array =
       Array::Handle(raw_ptr()->static_calls_target_table_);
-  for (intptr_t i = 0; i < array.Length(); i += kSCallTableEntryLength) {
-    if (array.At(i) == raw_code_offset) {
-      ASSERT(code.IsNull() ||
-             (code.function() == array.At(i + kSCallTableFunctionEntry)));
-      array.SetAt(i + kSCallTableCodeEntry, code);
-      return;
-    }
-  }
-  UNREACHABLE();
+  const intptr_t i = BinarySearchInSCallTable(raw_code_offset);

[siva, 2013/06/03 23:35:35]

Ditto here.

[srdjan, 2013/06/04 15:45:27]

Ditto

+  ASSERT(i >= 0);
+  ASSERT(code.IsNull() ||
+         (code.function() == array.At(i + kSCallTableFunctionEntry)));
+  array.SetAt(i + kSCallTableCodeEntry, code);
 }