Closed Bug 558327 Opened 10 years ago Closed 9 years ago

JIT support for in (has) operator

Categories

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect, P2)

defect

Tracking

(Not tracked)

RESOLVED FIXED
Q3 11 - Serrano

People

(Reporter: pnkfelix, Assigned: pnkfelix)

Details

(Whiteboard: PACMAN)

Attachments

(2 files, 2 obsolete files)

The has-variant of the in operator, "(n in x)", is "only" a bit slower than the composition (x[n] != undefined), assuming one adds the fixes proposed in patches with bug 555982.

There is no reason in principle that the in operator should not match or exceed the speed of the get operator[].  The reason that the get operator[] is currently winning is due to JIT optimization, but analagous optimizations could be applied to the in (has) operator.
Assignee: nobody → fklockii
OS: Mac OS X → All
Hardware: x86 → All
Target Milestone: --- → flash10.2
This benchmark compares (n in x) versus (x[n] != undefined).

It is a revised version of attachment 436004 [details].

The interesting thing about it is that it also compares typed versus untyped for the index n, and object versus array for the cache x.  So there's three dimensions it explores.

With tamarin-redux on Mac OS X Intel x86 (32-bit), here is some example output:

% ./tr/objdir-r4371/shell/avmshell cmp_in_and_lookup.abc 
obj (build: [0..1000000:1000000] lookup: [0..1000000:1000000] iters: 1 => fetches: 1000000) lookup_dur: 75ms lookup_typed_dur: 45ms in_dur: 6933ms in_typed_dur: 15469ms factor: 92.44 factor_typed: 343.75
arr (build: [0..1000000:1000000] lookup: [0..1000000:1000000] iters: 1 => fetches: 1000000) lookup_dur: 60ms lookup_typed_dur: 28ms in_dur: 1780ms in_typed_dur: 1802ms factor: 29.66 factor_typed: 64.35
preliminary.  passes acceptance tests.  but does not yet have specialized support for various vector variants, which there seems to be precedent for in jit-calls.h.  Stay tuned...
Whiteboard: PACMAN
Priority: -- → P2
Blocks: 555982
Component: Virtual Machine → JIT Compiler (NanoJIT)
(In reply to comment #2)
> preliminary.  passes acceptance tests.  but does not yet have specialized
> support for various vector variants, which there seems to be precedent for in
> jit-calls.h.  Stay tuned...

I hacked something together, but I now hypothesize that the reason for all the specialization for the Vector get/set methods in the JIT is so that we can specialize based on the type of the *values* being stored/retrieved, and this is irrelevant to the in operator.

So I suspect I can rebase the above patch and put it up for review; adding variants for Array/Bytevector/Vector.<T> is not likely to pay off at all.
get/set access to Vector, is specialized for both index types and value types.  For "in", agree, only index types are important.
No longer blocks: 555982
rebased, and revised to match convention urged in bug 460083.
Attachment #438733 - Attachment is obsolete: true
Attachment #452740 - Flags: review?(edwsmith)
Generalized microbenchmark to also address ByteArray and Vector based maps.

I arbitrarily chose to do the benchmarking on a 64-bit build (on my Mac OS X 2.8 laptop, 2.8 ghz Core  2 Duo)

Before JIT support:

bash-3.2$ ~/Dev/tamarin-redux/objdir-64/shell/avmshell cmp_in_and_lookup.abc -- all 100 100000
obj (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 507ms lookup_typed_dur: 331ms in_dur: 548ms in_typed_dur: 382ms factor: 1.08 factor_typed: 1.15
arr (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 381ms lookup_typed_dur: 237ms in_dur: 410ms in_typed_dur: 250ms factor: 1.07 factor_typed: 1.05
brr (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 428ms lookup_typed_dur: 257ms in_dur: 414ms in_typed_dur: 246ms factor: 0.96 factor_typed: 0.95
vec (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 420ms lookup_typed_dur: 264ms in_dur: 420ms in_typed_dur: 247ms factor: 1 factor_typed: 0.93
bash-3.2$ ~/Dev/tamarin-redux/objdir-64/shell/avmshell cmp_in_and_lookup.abc -- all 10000 1000
obj (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 495ms lookup_typed_dur: 321ms in_dur: 556ms in_typed_dur: 380ms factor: 1.12 factor_typed: 1.18
arr (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 384ms lookup_typed_dur: 238ms in_dur: 403ms in_typed_dur: 251ms factor: 1.04 factor_typed: 1.05
brr (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 397ms lookup_typed_dur: 291ms in_dur: 411ms in_typed_dur: 243ms factor: 1.03 factor_typed: 0.83
vec (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 414ms lookup_typed_dur: 266ms in_dur: 420ms in_typed_dur: 244ms factor: 1.01 factor_typed: 0.91


After JIT support:

bash-3.2$ ~/Dev/Bugz/tamarin-redux/objdir-64/shell/avmshell cmp_in_and_lookup.abc -- all 100 100000
obj (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 503ms lookup_typed_dur: 332ms in_dur: 565ms in_typed_dur: 268ms factor: 1.12 factor_typed: 0.8
arr (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 409ms lookup_typed_dur: 257ms in_dur: 422ms in_typed_dur: 147ms factor: 1.03 factor_typed: 0.57
brr (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 436ms lookup_typed_dur: 271ms in_dur: 415ms in_typed_dur: 138ms factor: 0.95 factor_typed: 0.5
vec (build: [0..100:100] lookup: [0..100:100] iters: 100000 => fetches: 10000000) lookup_dur: 467ms lookup_typed_dur: 281ms in_dur: 423ms in_typed_dur: 138ms factor: 0.9 factor_typed: 0.49
bash-3.2$ ~/Dev/Bugz/tamarin-redux/objdir-64/shell/avmshell cmp_in_and_lookup.abc -- all 10000 1000
obj (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 505ms lookup_typed_dur: 322ms in_dur: 553ms in_typed_dur: 264ms factor: 1.09 factor_typed: 0.81
arr (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 415ms lookup_typed_dur: 254ms in_dur: 421ms in_typed_dur: 146ms factor: 1.01 factor_typed: 0.57
brr (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 436ms lookup_typed_dur: 275ms in_dur: 413ms in_typed_dur: 136ms factor: 0.94 factor_typed: 0.49
vec (build: [0..10000:10000] lookup: [0..10000:10000] iters: 1000 => fetches: 10000000) lookup_dur: 455ms lookup_typed_dur: 282ms in_dur: 459ms in_typed_dur: 163ms factor: 1 factor_typed: 0.57

Basically, the untyped cases stayed roughly the same, while the in-operator for typed code got much faster, from roughly 240ms to 140ms.  (This is of course a micro-benchmark devised to highlight the difference, usual caveats, yadda yadda yadda.)

Once I have finished getting bug 571256 into shape, I should extend its set of benchmarks to include typed in-operator and fetch benchmarks.  But that need not be part of resolving this ticket; I just wanted to provide some data (above).
Attachment #438106 - Attachment is obsolete: true
(In reply to comment #6)
> I just wanted to provide some data (above).

p.s. I apologize for the ugliness of the presentation.  It would be a little less ugly if Bugzilla did not restrict to 80-character width, but I think the benefits of that restriction outweigh the costs.  In the future I will attempt to stick to presentations provided by runtests.py infrastructure; but in this case I just wanted to get this taken care of quickly.
Attachment #452740 - Flags: review?(edwsmith) → review+
Comment on attachment 452740 [details] [diff] [review]
add jit support support for in operator

(push me please)
(the buildbot failure was unrelated.)
Status: NEW → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Flags: flashplayer-bug-
You need to log in before you can comment on or make changes to this bug.