Bug 108868 - DFG should have a precise view of jump targets
Summary: DFG should have a precise view of jump targets
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on:
Blocks: 108414
  Show dependency treegraph
 
Reported: 2013-02-04 15:17 PST by Filip Pizlo
Modified: 2013-02-05 14:16 PST (History)
10 users (show)

See Also:


Attachments
the patch (18.56 KB, patch)
2013-02-04 15:24 PST, Filip Pizlo
oliver: review+
Details | Formatted Diff | Diff
patch for landing (17.01 KB, patch)
2013-02-04 19:30 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2013-02-04 15:17:09 PST
This will reduce the pressure on the CFG simplifier.
Comment 1 Filip Pizlo 2013-02-04 15:24:28 PST
Created attachment 186476 [details]
the patch
Comment 2 Oliver Hunt 2013-02-04 15:27:28 PST
Comment on attachment 186476 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=186476&action=review

Looks fine, my only concern is whether std::sort is guaranteed to not be a stupid quick sort

> Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp:116
> +    std::sort(out.begin(), out.end());

How well does std::sort work on mostly ordered data?
Comment 3 Filip Pizlo 2013-02-04 15:30:42 PST
(In reply to comment #2)
> (From update of attachment 186476 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=186476&action=review
> 
> Looks fine, my only concern is whether std::sort is guaranteed to not be a stupid quick sort
> 
> > Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp:116
> > +    std::sort(out.begin(), out.end());
> 
> How well does std::sort work on mostly ordered data?

I don't think I have a guarantee there.  My recollection is that they don't do the rookie use-first-element-as-pivot mistake but I haven't read the code.  But the performance numbers are looking consistently good...

As well, even if std::sort were to deteriorate to O(n^2), it's O(n^2) over basic blocks and not instructions.  The downside of _not_ running the precise jump target calculator is that we deteriorate to O(n^2) over instructions in the CFG simplifier - so much much worse.

It would be great to try to optimize this code more, though, if we see it showing up as a hot spot.
Comment 4 Filip Pizlo 2013-02-04 15:31:06 PST
Oops, I'll have to do a pretty big rebase apparently.
Comment 5 Filip Pizlo 2013-02-04 19:30:09 PST
Created attachment 186526 [details]
patch for landing
Comment 6 Filip Pizlo 2013-02-05 14:16:23 PST
Landed in http://trac.webkit.org/changeset/141931