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

Fix Issue 11047: use binary search instead of linear search to locate a pc-offset in the static call table.

R=asiva@google.com

Committed: https://code.google.com/p/dart/source/detail?r=23614

[srdjan, 2013-06-03 22:46:23]

This reduces the time of issue 11047 program from 9 seconds to .5 seconds (Mac
OS X).

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

LGTM with a possible suggestion to avoid having
a RawObject* parameter to a function.

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7821: intptr_t Code::BinarySearchInSCallTable(RawObject*
key) const {
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.

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7829: RawObject* key_in_table = table.At(real_index);
This can be
RawSmi* key_in_table = Smi::RawCast(table.At(real_index);

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7845: const intptr_t i =
BinarySearchInSCallTable(raw_code_offset);
This would be just:

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

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7862: const intptr_t i =
BinarySearchInSCallTable(raw_code_offset);
Ditto here.

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

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7821: intptr_t Code::BinarySearchInSCallTable(RawObject*
key) const {
On 2013/06/03 23:35:35, siva wrote:
> 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.

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());

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7845: const intptr_t i =
BinarySearchInSCallTable(raw_code_offset);
On 2013/06/03 23:35:35, siva wrote:
> This would be just:
> 
> const intptr_t i = BinarySearchInSCallTable(pc - EntryPoint());

And this would be:

const intptr_t i = BinarySearchInSCallTable(pc);

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

dbc:

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7787: // Check that the table is sorted by pc offsets.
Maybe I missed something, but where do we sort this table?

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

Thanks!

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7787: // Check that the table is sorted by pc offsets.
On 2013/06/04 08:36:49, Florian Schneider wrote:
> Maybe I missed something, but where do we sort this table?

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.

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7821: intptr_t Code::BinarySearchInSCallTable(RawObject*
key) const {
On 2013/06/03 23:38:25, siva wrote:
> On 2013/06/03 23:35:35, siva wrote:
> > 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.
> 
> 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());

Done.

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7821: intptr_t Code::BinarySearchInSCallTable(RawObject*
key) const {
On 2013/06/03 23:35:35, siva wrote:
> 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.

Using other suggestion (passing pc).

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7829: RawObject* key_in_table = table.At(real_index);
On 2013/06/03 23:35:35, siva wrote:
> This can be
> RawSmi* key_in_table = Smi::RawCast(table.At(real_index);

Using other suggestion (passing pc).

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7845: const intptr_t i =
BinarySearchInSCallTable(raw_code_offset);
On 2013/06/03 23:38:25, siva wrote:
> On 2013/06/03 23:35:35, siva wrote:
> > This would be just:
> > 
> > const intptr_t i = BinarySearchInSCallTable(pc - EntryPoint());
> 
> And this would be:
> 
> const intptr_t i = BinarySearchInSCallTable(pc);

Done.

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7845: const intptr_t i =
BinarySearchInSCallTable(raw_code_offset);
On 2013/06/03 23:35:35, siva wrote:
> This would be just:
> 
> const intptr_t i = BinarySearchInSCallTable(pc - EntryPoint());

Using other suggestion (passing pc).

https://codereview.chromium.org/16295022/diff/3001/runtime/vm/object.cc#newco...
runtime/vm/object.cc:7862: const intptr_t i =
BinarySearchInSCallTable(raw_code_offset);
On 2013/06/03 23:35:35, siva wrote:
> Ditto here.

Ditto

[srdjan, 2013-06-04 20:16:34]

Committed patchset #3 manually as r23614 (presubmit successful).