Reorder switch clauses using newly-introduced execution counters in

Reorder switch clauses using newly-introduced execution counters in
unoptimized clause bodies.

R=danno@chromium.org
BUG=

[indutny, 2013-06-02 08:21:15]

Probable improvements and things to done:

* Improve resetting counters by dictionary of references to type feedback cells
* Handle counter overflow (isn't actually needed if below will be done)
* Remove counters from unoptimized code once function is marked as
unoptimizable.

@danno: Sorry I don't know anyone else in the team, please forward it to anyone
else if that isn't what you're responsible for.

[indutny, 2013-06-02 09:12:48]

On 2013/06/02 08:21:15, indutny wrote:
> Probable improvements and things to done:
> 
> * Improve resetting counters by dictionary of references to type feedback
cells
> * Handle counter overflow (isn't actually needed if below will be done)
> * Remove counters from unoptimized code once function is marked as
> unoptimizable.
> 
> @danno: Sorry I don't know anyone else in the team, please forward it to
anyone
> else if that isn't what you're responsible for.

Added handling for counter overflow.

[indutny, 2013-06-02 09:21:37]

On 2013/06/02 09:12:48, indutny wrote:
> On 2013/06/02 08:21:15, indutny wrote:
> > Probable improvements and things to done:
> > 
> > * Improve resetting counters by dictionary of references to type feedback
> cells
> > * Handle counter overflow (isn't actually needed if below will be done)
> > * Remove counters from unoptimized code once function is marked as
> > unoptimizable.
> > 
> > @danno: Sorry I don't know anyone else in the team, please forward it to
> anyone
> > else if that isn't what you're responsible for.
> 
> Added handling for counter overflow.

Also, I think current soft deoptimization insertion will work only for cases
where the most of the clauses ain't used... I need to figure out something
clever to make it deoptimize on clause popularity change.

[indutny, 2013-06-02 20:57:26]

On 2013/06/02 09:21:37, indutny wrote:
> On 2013/06/02 09:12:48, indutny wrote:
> > On 2013/06/02 08:21:15, indutny wrote:
> > > Probable improvements and things to done:
> > > 
> > > * Improve resetting counters by dictionary of references to type feedback
> > cells
> > > * Handle counter overflow (isn't actually needed if below will be done)
> > > * Remove counters from unoptimized code once function is marked as
> > > unoptimizable.
> > > 
> > > @danno: Sorry I don't know anyone else in the team, please forward it to
> > anyone
> > > else if that isn't what you're responsible for.
> > 
> > Added handling for counter overflow.
> 
> Also, I think current soft deoptimization insertion will work only for cases
> where the most of the clauses ain't used... I need to figure out something
> clever to make it deoptimize on clause popularity change.

Danno, I'm introducing here a deoptimizing counter instruction to support
reordering of switch clauses after distribution changes. Basically it counts
number of hits in top clauses and substracts number of hits from bottom clauses,
and when this number becomes negative - its starting soft deoptimization and
recompiles switch function using newly gained distribution data.

The problem right now is that ARM and MIPS doesn't seem to be working with this
DeoptCounterAdd instruction, somehow they're observing incorrect initial value
of cell... I'm still trying to figure it out, but wanted to share with you
things that I already have to receive comments early.

[indutny, 2013-06-03 06:51:49]

On 2013/06/02 20:57:26, indutny wrote:
> On 2013/06/02 09:21:37, indutny wrote:
> > On 2013/06/02 09:12:48, indutny wrote:
> > > On 2013/06/02 08:21:15, indutny wrote:
> > > > Probable improvements and things to done:
> > > > 
> > > > * Improve resetting counters by dictionary of references to type
feedback
> > > cells
> > > > * Handle counter overflow (isn't actually needed if below will be done)
> > > > * Remove counters from unoptimized code once function is marked as
> > > > unoptimizable.
> > > > 
> > > > @danno: Sorry I don't know anyone else in the team, please forward it to
> > > anyone
> > > > else if that isn't what you're responsible for.
> > > 
> > > Added handling for counter overflow.
> > 
> > Also, I think current soft deoptimization insertion will work only for cases
> > where the most of the clauses ain't used... I need to figure out something
> > clever to make it deoptimize on clause popularity change.
> 
> Danno, I'm introducing here a deoptimizing counter instruction to support
> reordering of switch clauses after distribution changes. Basically it counts
> number of hits in top clauses and substracts number of hits from bottom
clauses,
> and when this number becomes negative - its starting soft deoptimization and
> recompiles switch function using newly gained distribution data.
> 
> The problem right now is that ARM and MIPS doesn't seem to be working with
this
> DeoptCounterAdd instruction, somehow they're observing incorrect initial value
> of cell... I'm still trying to figure it out, but wanted to share with you
> things that I already have to receive comments early.

Oh, and here is an example demonstrating performance improvements of this patch:
https://gist.github.com/indutny/add4bfa2a915eab3b108 .

[Sven Panne, 2013-06-03 07:30:44]

A few drive-by comments: I don't really like this approach, it is a really heavy
change for a tiny, localized improvement. Our switch-handling should really need
some attention, but I would really prefer a radically different approach, like
choosing between if-then-else cascades, binary search trees and some kind of
hashing scheme. Fiddling around with deopts is a dead end IMHO.

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen-gvn.cc
File src/hydrogen-gvn.cc (right):

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen-gvn.cc#newco...
src/hydrogen-gvn.cc:408: instr->IsDeoptCounter() || instr->IsDeoptCounterAdd())
{
This is a no-go: We're doing something wrong if we have to change GVN for a
localized performance improvement.

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen.cc#newcode4949
src/hydrogen.cc:4949: void
HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
We shouldn't grow this monster even more, making it basically non-understandable
and unmaintainable (>200 lines).

https://codereview.chromium.org/16128004/diff/15001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/16128004/diff/15001/src/objects.h#newcode4496
src/objects.h:4496: DECL_ACCESSORS(deopt_counter_cells, FixedArray)
Do we really have space left without going over our size threshold here?

[indutny, 2013-06-03 07:50:53]

Just FYI to consider, benchmarks seems to be running a little bit faster after
applying this patch.

Before:

Richards: 15995
DeltaBlue: 17270
Crypto: 17093
RayTrace: 17763
EarleyBoyer: 20444
RegExp: 2822
Splay: 5866
NavierStokes: 20310
----
Score (version 7): 12448

After:

Richards: 15992
DeltaBlue: 18354
Crypto: 17104
RayTrace: 17763
EarleyBoyer: 20204
RegExp: 2953
Splay: 5805
NavierStokes: 19846
----
Score (version 7): 12544

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen-gvn.cc
File src/hydrogen-gvn.cc (right):

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen-gvn.cc#newco...
src/hydrogen-gvn.cc:408: instr->IsDeoptCounter() || instr->IsDeoptCounterAdd())
{
On 2013/06/03 07:30:44, Sven Panne wrote:
> This is a no-go: We're doing something wrong if we have to change GVN for a
> localized performance improvement.

Well, its just DeoptCounterAdd that behaves like SoftDeoptimize in some cases.

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/16128004/diff/15001/src/hydrogen.cc#newcode4949
src/hydrogen.cc:4949: void
HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
On 2013/06/03 07:30:44, Sven Panne wrote:
> We shouldn't grow this monster even more, making it basically
non-understandable
> and unmaintainable (>200 lines).

Surely it can be split in multiple parts.

https://codereview.chromium.org/16128004/diff/15001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/16128004/diff/15001/src/objects.h#newcode4496
src/objects.h:4496: DECL_ACCESSORS(deopt_counter_cells, FixedArray)
On 2013/06/03 07:30:44, Sven Panne wrote:
> Do we really have space left without going over our size threshold here?

Well... no assertion happens for me, so it seems like yes?

[Sven Panne, 2013-06-03 09:22:02]

https://codereview.chromium.org/16128004/diff/15001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/16128004/diff/15001/src/objects.h#newcode4496
src/objects.h:4496: DECL_ACCESSORS(deopt_counter_cells, FixedArray)
On 2013/06/03 07:50:53, indutny wrote:
> On 2013/06/03 07:30:44, Sven Panne wrote:
> > Do we really have space left without going over our size threshold here?
> 
> Well... no assertion happens for me, so it seems like yes?

I was not concerned about correctness, I was concerned about wasting memory
because of alignment constraints.

[Jakob Kummerow, 2013-06-03 10:04:15]

More DBC:

I think it's fundamentally wrong to trigger soft deopts based on hit counts in
case-switches. Recompilation can be very expensive. I'm not strictly against
collecting more information in full-codegen and using that to generate better
optimized code; but considering how quickly functions are optimized, whatever
counts we have collected until then are probably not statistically significant
enough to be a reliable estimate of future hotness.

The benchmark results you've provided don't provide sufficient motivation to do
this. DeltaBlue is known to be flaky; run it again a few times both with and
without your patch and you'll see that the improvement is not consistent. RegExp
doesn't even contain a "switch" statement, so that's got to be a flake too.
Which means in summary I can't see any visible improvement.

[danno, 2013-06-03 10:47:59]

Now the non-DBC :-)

I don't think using deoptimization and type feedback is the right way forward
with switch/case constructs at this point. There is much lower-hanging fruit
that shouldn't require any (or at least minimal) platform-specific,  low-level
compiler changes, that apply to many more cases, and that should achieve similar
performance results to what your patch does.

There are handful of "standard" compiler techniques to optimize switch
statements, e.g. using a binary search of the case labels, hash codes for string
case labels and jump tables for large mostly contiguous case label sets. These
standard techniques should be applied before reaching for the type feedback
hammer. Biased case label checks before starting a binary label search could be
used someday to squeeze a little extra performance out, but I think it's clumsy
overkill to do that work now without the "standard" set of optimizations as a
basis, and even more so if you rely on a new custom deoptimization mechanism to
do so.

That being said, I'd welcome patches that implemented any of the standard
techniques that I've mentioned above. :-)

https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions...
src/hydrogen-instructions.h:107: V(DeoptCounter)                              \
In addition to my general feedback to your approach, here's some feedback about
the implementation: We are generally trying to reduce the number of hydrogen
instructions, not increase them. If you want to manipulate data counters form
Hydrogen code and then trigger a deoptimization, then you should use
HLoad/HStore/HAdd instructions followed by a "normal" deopt or a call to a
runtime function that does the necessary bookkeeping and then does a lazy
deopt... both approaches don't require any new platform-specific code.

[indutny, 2013-06-03 10:56:11]

Thank you for reviewing, sad that it won't get in, but that's ok. I'll look into
proposed optimization techniques and will share results with you (if I'll have
any).

https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions...
src/hydrogen-instructions.h:107: V(DeoptCounter)                              \
On 2013/06/03 10:48:00, danno wrote:
> In addition to my general feedback to your approach, here's some feedback
about
> the implementation: We are generally trying to reduce the number of hydrogen
> instructions, not increase them. If you want to manipulate data counters form
> Hydrogen code and then trigger a deoptimization, then you should use
> HLoad/HStore/HAdd instructions followed by a "normal" deopt or a call to a
> runtime function that does the necessary bookkeeping and then does a lazy
> deopt... both approaches don't require any new platform-specific code. 

Hm... you're right, but even this case I would need to patch lithium to store
this cells in Code object.

[indutny, 2013-06-03 19:37:18]

On 2013/06/03 10:56:11, indutny wrote:
> Thank you for reviewing, sad that it won't get in, but that's ok. I'll look
into
> proposed optimization techniques and will share results with you (if I'll have
> any).
> 
>
https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions.h
> File src/hydrogen-instructions.h (right):
> 
>
https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions...
> src/hydrogen-instructions.h:107: V(DeoptCounter)                             
\
> On 2013/06/03 10:48:00, danno wrote:
> > In addition to my general feedback to your approach, here's some feedback
> about
> > the implementation: We are generally trying to reduce the number of hydrogen
> > instructions, not increase them. If you want to manipulate data counters
form
> > Hydrogen code and then trigger a deoptimization, then you should use
> > HLoad/HStore/HAdd instructions followed by a "normal" deopt or a call to a
> > runtime function that does the necessary bookkeeping and then does a lazy
> > deopt... both approaches don't require any new platform-specific code. 
> 
> Hm... you're right, but even this case I would need to patch lithium to store
> this cells in Code object.

Just pushed small update to code that I'd like you to consider merging
regardless of this CL approval (let me know if I need to open separate CL for
it): https://codereview.chromium.org/16128004/diff2/22001:26001/src/objects.cc

Basically, right now all code type feedback cells are reset on GC to fight
useless heap references and memory leaks (right?), and doing so with smis isn't
really important and breaks my code :)

[indutny, 2013-06-03 20:04:04]

On 2013/06/03 19:37:18, indutny wrote:
> On 2013/06/03 10:56:11, indutny wrote:
> > Thank you for reviewing, sad that it won't get in, but that's ok. I'll look
> into
> > proposed optimization techniques and will share results with you (if I'll
have
> > any).
> > 
> >
>
https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions.h
> > File src/hydrogen-instructions.h (right):
> > 
> >
>
https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions...
> > src/hydrogen-instructions.h:107: V(DeoptCounter)                            

> \
> > On 2013/06/03 10:48:00, danno wrote:
> > > In addition to my general feedback to your approach, here's some feedback
> > about
> > > the implementation: We are generally trying to reduce the number of
hydrogen
> > > instructions, not increase them. If you want to manipulate data counters
> form
> > > Hydrogen code and then trigger a deoptimization, then you should use
> > > HLoad/HStore/HAdd instructions followed by a "normal" deopt or a call to a
> > > runtime function that does the necessary bookkeeping and then does a lazy
> > > deopt... both approaches don't require any new platform-specific code. 
> > 
> > Hm... you're right, but even this case I would need to patch lithium to
store
> > this cells in Code object.
> 
> Just pushed small update to code that I'd like you to consider merging
> regardless of this CL approval (let me know if I need to open separate CL for
> it): https://codereview.chromium.org/16128004/diff2/22001:26001/src/objects.cc
> 
> Basically, right now all code type feedback cells are reset on GC to fight
> useless heap references and memory leaks (right?), and doing so with smis
isn't
> really important and breaks my code :)

And another note, octane benchmark results over 10 runs seems to be mostly equal
for this CL and bleeding edge. So, while not introducing any performance
improvement in benchmark, it, at least, doesn't make things worse.

[indutny, 2013-06-03 21:13:50]

On 2013/06/03 20:04:04, indutny wrote:
> On 2013/06/03 19:37:18, indutny wrote:
> > On 2013/06/03 10:56:11, indutny wrote:
> > > Thank you for reviewing, sad that it won't get in, but that's ok. I'll
look
> > into
> > > proposed optimization techniques and will share results with you (if I'll
> have
> > > any).
> > > 
> > >
> >
>
https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions.h
> > > File src/hydrogen-instructions.h (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/16128004/diff/22001/src/hydrogen-instructions...
> > > src/hydrogen-instructions.h:107: V(DeoptCounter)                          
 
> 
> > \
> > > On 2013/06/03 10:48:00, danno wrote:
> > > > In addition to my general feedback to your approach, here's some
feedback
> > > about
> > > > the implementation: We are generally trying to reduce the number of
> hydrogen
> > > > instructions, not increase them. If you want to manipulate data counters
> > form
> > > > Hydrogen code and then trigger a deoptimization, then you should use
> > > > HLoad/HStore/HAdd instructions followed by a "normal" deopt or a call to
a
> > > > runtime function that does the necessary bookkeeping and then does a
lazy
> > > > deopt... both approaches don't require any new platform-specific code. 
> > > 
> > > Hm... you're right, but even this case I would need to patch lithium to
> store
> > > this cells in Code object.
> > 
> > Just pushed small update to code that I'd like you to consider merging
> > regardless of this CL approval (let me know if I need to open separate CL
for
> > it):
https://codereview.chromium.org/16128004/diff2/22001:26001/src/objects.cc
> > 
> > Basically, right now all code type feedback cells are reset on GC to fight
> > useless heap references and memory leaks (right?), and doing so with smis
> isn't
> > really important and breaks my code :)
> 
> And another note, octane benchmark results over 10 runs seems to be mostly
equal
> for this CL and bleeding edge. So, while not introducing any performance
> improvement in benchmark, it, at least, doesn't make things worse.

Attaching here the code that I'm aiming to optimize
https://gist.github.com/indutny/6073202c100f4df2599a , after applying this patch
it's performance improves by 10%. And the difference could be bigger if it'll
spend less time concatenating strings and doing other stuff.