609121 - nanojit: handle small immediates specially in CseFilter

Status: RESOLVED FIXED

(Core Graveyard :: Nanojit, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: patch (against TM 56615:2098bd53381e)

More than half of all int immediates used in TraceMonkey code are in the range 0..16.  This patch modifies CseFilter to not hash such immediates but just put them directly in an array of size 17.  It also changes the prefix of the NLKind values from "LIns" to "NL".

It's a small win for TM on SunSpider with just the tracejit (with the methodjit and profiling on not much gets trace in SunSpider any more), so it seems worth doing.

---------------------------------------------------------------
| millions of instructions executed                           |
| total                        | on-trace (may overestimate)  |
---------------------------------------------------------------
|    77.651    77.589 (1.001x) |    22.612    22.613 (------) | 3d-cube
|    39.294    39.292 (------) |    22.697    22.697 (------) | 3d-morph
|   167.387   167.128 (1.002x) |    15.699    15.703 (------) | 3d-raytrace
|   130.527   130.522 (------) |    538033    538072 (------) | access-binary-
|    85.137    85.119 (------) |    75.983    75.983 (------) | access-fannkuc
|    27.636    27.635 (------) |    15.194    15.194 (------) | access-nbody
|    34.513    34.513 (------) |    23.344    23.344 (------) | access-nsieve
|     7.010     7.009 (------) |     2.858     2.858 (------) | bitops-3bit-bi
|    34.367    34.366 (------) |    30.097    30.097 (------) | bitops-bits-in
|    14.072    14.072 (------) |    10.215    10.215 (------) | bitops-bitwise
|    36.823    36.822 (------) |    31.634    31.634 (------) | bitops-nsieve-
|   149.070   149.070 (------) |         0         0 (------) | controlflow-re
|    64.895    64.824 (1.001x) |    27.033    27.035 (------) | crypto-aes
|    33.184    33.012 (1.005x) |     4.379     4.379 (------) | crypto-md5
|    19.163    19.132 (1.002x) |     6.316     6.317 (------) | crypto-sha1
|    99.536    99.534 (------) |    11.670    11.670 (------) | date-format-to
|    69.422    69.374 (1.001x) |     9.548     9.550 (------) | date-format-xp
|    42.244    42.243 (------) |    28.679    28.679 (------) | math-cordic
|    22.382    22.381 (------) |     6.158     6.158 (------) | math-partial-s
|    21.469    21.459 (------) |    13.188    13.188 (------) | math-spectral-
|    49.359    49.358 (------) |    34.579    34.579 (------) | regexp-dna
|    29.161    29.159 (------) |     9.067     9.067 (------) | string-base64
|    84.494    84.490 (------) |    23.533    23.533 (------) | string-fasta
|   143.171   143.169 (------) |    12.273    12.273 (------) | string-tagclou
|   128.437   128.436 (------) |     7.663     7.664 (------) | string-unpack-
|    43.204    43.201 (------) |     8.220     8.221 (------) | string-validat
-------
|  1653.623  1652.922 (------) |   453.206   453.220 (------) | all

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: patch, v2 (against TM 56615:2098bd53381e)

Oh, and something that's been bugging me for a while:  LirBuffer::_bytesAllocated is always zero, so LirBuffer::bytesCount() is wrong.  Both of those members are dead so this patch removes them.

Comment 2

[Rick Reitmaier]

Comment on attachment 487712 [details] [diff] [review]
patch, v2 (against TM 56615:2098bd53381e)

The prior table size was 128, the new size is 64 + 17, just curious  if you had some data which prompted the shrinkage.

BTW byteCount is used by TR via CodegenLIR, but if its wrong lets remove it unless the fix is trivial.

Comment 3

[Nicholas Nethercote [inactive]]

(In reply to comment #2)
> 
> The prior table size was 128, the new size is 64 + 17, just curious  if you had
> some data which prompted the shrinkage.

IIRC Cachegrind told me that reducing to 64 was a tiny bit better.

> BTW byteCount is used by TR via CodegenLIR, but if its wrong lets remove it
> unless the fix is trivial.

It's only used for profiling dumps, AFAICT.

Comment 4

[Edwin Smith]

Comment on attachment 487712 [details] [diff] [review]
patch, v2 (against TM 56615:2098bd53381e)

I need to delegate the review since I'm travelling this week.  The only part I'm curious about is what the range of small constants is used by TR.

Comment 5

[William Maddox]

Attachment: Study of integer constant values in TR

I instrumented nanojit in TR and collected some data on integer constants presented to CSE when running the performance test suite.  I omitted the microbenchmarks in the hope that the results might be more representative of real applications.

The results show that integer constant values cluster in the [0,15] range. It may be reasonable to consider expanding the range of "direct-mapped" values, but the cost of clearing the tables at labels would have to be considered. We might revisit the choice of small integer if we implemented a constant-time invalidation scheme.

Comment 6

[William Maddox]

Comment on attachment 487712 [details] [diff] [review]
patch, v2 (against TM 56615:2098bd53381e)

Looks good.  R+

Comment 7

[Nicholas Nethercote [inactive]]

(In reply to comment #5)
> We might revisit the choice of small integer if we implemented a constant-time
> invalidation scheme.

Any thoughts on what a constant-time invalidation scheme would look like?

Comment 8

[William Maddox]

(In reply to comment #7)

> Any thoughts on what a constant-time invalidation scheme would look like?

The standard way would be with a timestamp that gets incremented to invalidate the table.  Each entry is tagged with the timestamp at which it was created, and which is checked on access.  This is beneficial for tables that are cleared frequently, but sparsely populated and accessed between clears.  See the
following patch for a version of the nanojit HashMap that uses this scheme:

https://bugzilla.mozilla.org/attachment.cgi?id=465838&action=diff

Comment 9

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/projects/nanojit-central/rev/04d7771f3f85
http://hg.mozilla.org/tracemonkey/rev/993c90c046ff

Comment 10

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/993c90c046ff