Summary: | DFG should have a precise view of jump targets | ||||||||
---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Filip Pizlo <fpizlo> | ||||||
Component: | JavaScriptCore | Assignee: | Filip Pizlo <fpizlo> | ||||||
Status: | RESOLVED FIXED | ||||||||
Severity: | Normal | CC: | barraclough, ggaren, gyuyoung.kim, mark.lam, mhahnenberg, msaboff, oliver, rakuco, sam, webkit.review.bot | ||||||
Priority: | P2 | ||||||||
Version: | 528+ (Nightly build) | ||||||||
Hardware: | All | ||||||||
OS: | All | ||||||||
Bug Depends on: | |||||||||
Bug Blocks: | 108414 | ||||||||
Attachments: |
|
Description
Filip Pizlo
2013-02-04 15:17:09 PST
Created attachment 186476 [details]
the patch
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? (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. Oops, I'll have to do a pretty big rebase apparently. Created attachment 186526 [details]
patch for landing
Landed in http://trac.webkit.org/changeset/141931 |