Improve CodeRegionTable build time by 30x

Switch from linear search for code region to binary search.
Add a SampleVisitor for iterating over SampleBuffer.
Move stack walking class out of header into source file.

Processing 6.5 million stack frames went from 28 seconds to 741 millis.

R=asiva@google.com

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

[Cutch, 2014-02-11 21:53:13]

PTAL

[siva, 2014-02-12 00:58:52]

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc
File runtime/vm/profiler.cc (right):

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:210: return a || b || c || d;
There is no short circuiting of calls to contains this way, why not just do:

return other->contains(start_) ||
       other->contains(end_ - 1) ||
       contains(other->start()) ||
       contains(other->end() - 1);

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:363: intptr_t GetElapsed() {
const {

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:378: intptr_t start_;
DISALLOW stuff..... or make this a ValueObject. Probably it should be a
ValueObject.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:423: intptr_t FindUpperBound(uintptr_t pc) {
we usually use uword for address types.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:458: }
Would it make sense to combine FindUpperBound and FindLowerBound into a single:
intptr_t FindRegion(uword pc,
                    bool (*comparator)(uword pc, uword region_pc));
and pass in approriate comparators for the upper and lower cases.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:465: // We may have overshot by 1. Check previous entry.
Not sure how this happens?

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:802: }
Why not move this to the header file itself, seems very small.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:947: uword* CallerPC(uword* fp) {
const {

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:952: uword* CallerFP(uword* fp) {
const {

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:957: bool ValidFramePointer(uword* fp) {
const {

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.h
File runtime/vm/profiler.h (right):

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.h#ne...
runtime/vm/profiler.h:44: 
We usually have only one blank line before 'private:'

[Cutch, 2014-02-13 23:13:18]

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc
File runtime/vm/profiler.cc (right):

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:210: return a || b || c || d;
On 2014/02/12 00:58:52, siva wrote:
> There is no short circuiting of calls to contains this way, why not just do:
> 
> return other->contains(start_) ||
>        other->contains(end_ - 1) ||
>        contains(other->start()) ||
>        contains(other->end() - 1);

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:363: intptr_t GetElapsed() {
On 2014/02/12 00:58:52, siva wrote:
> const {

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:378: intptr_t start_;
On 2014/02/12 00:58:52, siva wrote:
> DISALLOW stuff..... or make this a ValueObject. Probably it should be a
> ValueObject.

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:423: intptr_t FindUpperBound(uintptr_t pc) {
On 2014/02/12 00:58:52, siva wrote:
> we usually use uword for address types.

Done here and elsewhere.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:458: }
On 2014/02/12 00:58:52, siva wrote:
> Would it make sense to combine FindUpperBound and FindLowerBound into a
single:
> intptr_t FindRegion(uword pc,
>                     bool (*comparator)(uword pc, uword region_pc));
> and pass in approriate comparators for the upper and lower cases.

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:465: // We may have overshot by 1. Check previous entry.
On 2014/02/12 00:58:52, siva wrote:
> Not sure how this happens?

It doesn't anymore.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:802: }
On 2014/02/12 00:58:52, siva wrote:
> Why not move this to the header file itself, seems very small.

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:947: uword* CallerPC(uword* fp) {
On 2014/02/12 00:58:52, siva wrote:
> const {

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:952: uword* CallerFP(uword* fp) {
On 2014/02/12 00:58:52, siva wrote:
> const {

Done.

https://codereview.chromium.org/151143003/diff/80001/runtime/vm/profiler.cc#n...
runtime/vm/profiler.cc:957: bool ValidFramePointer(uword* fp) {
On 2014/02/12 00:58:52, siva wrote:
> const {

Done.

[siva, 2014-02-19 18:09:54]

lgtm

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/isolate.cc
File runtime/vm/isolate.cc (right):

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/isolate.cc#n...
runtime/vm/isolate.cc:484: if (stack_lower == static_cast<uword>(~0)) {
should this be
if (stack_lower == kUwordMax) {
  ....
}

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/isolate.cc#n...
runtime/vm/isolate.cc:487: if (stack_lower == static_cast<uword>(~0)) {
Ditto...

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/profiler.cc
File runtime/vm/profiler.cc (right):

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/profiler.cc#...
runtime/vm/profiler.cc:379: };
Can this be just another timer, i.e:

the code below:
      ScopeStopwatch sw("CodeTableBuild");

could be:
  TimerScope timer(FLAG_profiler_stats, &ProfilerStats::codetable_build_timer);

Similar to how compiler_stats is done.

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/profiler.h
File runtime/vm/profiler.h (right):

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/profiler.h#n...
runtime/vm/profiler.h:44: 
extra blank line?

[Cutch, 2014-02-19 18:20:31]

I may follow this up with a second CL which adds a timer to the global timer
pool.

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/isolate.cc
File runtime/vm/isolate.cc (right):

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/isolate.cc#n...
runtime/vm/isolate.cc:484: if (stack_lower == static_cast<uword>(~0)) {
On 2014/02/19 18:09:54, siva wrote:
> should this be
> if (stack_lower == kUwordMax) {
>   ....
> }

Done.

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/isolate.cc#n...
runtime/vm/isolate.cc:487: if (stack_lower == static_cast<uword>(~0)) {
On 2014/02/19 18:09:54, siva wrote:
> Ditto...

Done.

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/profiler.h
File runtime/vm/profiler.h (right):

https://codereview.chromium.org/151143003/diff/130001/runtime/vm/profiler.h#n...
runtime/vm/profiler.h:44: 
On 2014/02/19 18:09:54, siva wrote:
> extra blank line?

Done.

[Cutch, 2014-02-19 19:15:23]

Committed patchset #5 manually as r32809 (presubmit successful).

[Bill Hesse, 2014-02-20 16:08:03]

On 2014/02/19 19:15:23, Cutch wrote:
> Committed patchset #5 manually as r32809 (presubmit successful).

I'm suspicious that this CL broke the ARM and MIPS vm tests.

[Bill Hesse, 2014-02-20 16:13:18]

On 2014/02/20 16:08:03, Bill Hesse wrote:
> On 2014/02/19 19:15:23, Cutch wrote:
> > Committed patchset #5 manually as r32809 (presubmit successful).
> 
> I'm suspicious that this CL broke the ARM and MIPS vm tests.

Oops - nevermind.  It looks like a docgen problem.