NEON for table lookups?

NEON for table lookups?

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1656543002
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot

[msarett, 2016-01-30 20:40:12]

Description was changed from

==========
NEON for table lookups?

BUG=skia:
==========

to

==========
NEON for table lookups?

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot
==========

[msarett, 2016-01-30 20:43:17]

msarett@google.com changed reviewers:
+ mtklein@google.com

[msarett, 2016-01-30 20:43:18]

Thought you might find this interesting (though it's probably a dead end).

I didn't have high hopes to begin with, but the weird behavior/performance of
VTBX seems to have made this idea even more awful than I originally thought.

BTW, you might as well ignore everything except for SkSwizzler.cpp

[msarett, 2016-01-30 21:03:37]

Second patch is better, but still too slow.  Out of curiosity, I think I'll
write a bench to see how close it's getting.

[msarett, 2016-02-01 15:01:18]

No hope for this.  Way slower than the scalar code.

[msarett, 2016-02-01 15:01:29]

Description was changed from

==========
NEON for table lookups?

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot
==========

to

==========
NEON for table lookups?

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot
==========

[mtklein, 2016-02-01 15:08:50]

On 2016/02/01 15:01:18, msarett wrote:
> No hope for this.  Way slower than the scalar code.

Apple's Accelerate framework has a function vtablelookup (no relation to
vtables) that looks pretty similar to what we want here:

$ clang -framework Accelerate demo.c

#include <Accelerate/Accelerate.h>
int main(void) {
    uint32_t table[256];
    for (int i = 0; i < 256; i++) {
        table[i] = i*i;
    }
    vSInt32 ix = { 2,3,4,7 };
    vUInt32 vals = vtablelookup(ix, table);
    printf("%d %d %d %d\n", vals[0], vals[1], vals[2], vals[3]);  // 4, 9, 16,
49
    return 0;
}

The SSE vtablelookup disassembly doesn't look like anything special.  This makes
me think it must be somehow clever on ARM, or what would be the point?  (I guess
it's of old enough vintage that it might have been implemented cleverly on
PPC...)

[msarett, 2016-02-01 15:19:59]

Any way to look at the disassembly on ARM?

[mtklein, 2016-02-01 15:32:15]

On 2016/02/01 15:19:59, msarett wrote:
> Any way to look at the disassembly on ARM?

I first just called vtablelookup in an infinite loop, then attached Instruments
and looked at the disassembly there.
We can try this if we get an iThing set up correctly.

An alternative is to hunt down the right .dylib then call otool -tv ...

E.g. for x86:
  otool -tv
/System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libvMisc.dylib
| less

Sometimes otool -tv doesn't behave and then I switch over to objdump (brew
install binutils, then gobjdump -d ...)

(I've noticed Apple has started shipping 3-format fat binaries on x86: i386,
x86-64, and x86-64h, where the h presumably means "Haswell".  Neat.)

[mtklein, 2016-02-01 15:44:00]

On 2016/02/01 15:32:15, mtklein wrote:
> On 2016/02/01 15:19:59, msarett wrote:
> > Any way to look at the disassembly on ARM?
> 
> I first just called vtablelookup in an infinite loop, then attached
Instruments
> and looked at the disassembly there.
> We can try this if we get an iThing set up correctly.
> 
> An alternative is to hunt down the right .dylib then call otool -tv ...
> 
> E.g. for x86:
>   otool -tv
>
/System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libvMisc.dylib
> | less
> 
> Sometimes otool -tv doesn't behave and then I switch over to objdump (brew
> install binutils, then gobjdump -d ...)
> 
> (I've noticed Apple has started shipping 3-format fat binaries on x86: i386,
> x86-64, and x86-64h, where the h presumably means "Haswell".  Neat.)

Duh... the iOS .dylib ships on the device, not in the SDK... we should see if we
can get the Instruments approach to work.

[mtklein, 2016-02-01 16:30:37]

https://codereview.chromium.org/1656543002/diff/20001/src/codec/SkSwizzler.cpp
File src/codec/SkSwizzler.cpp (right):

https://codereview.chromium.org/1656543002/diff/20001/src/codec/SkSwizzler.cp...
src/codec/SkSwizzler.cpp:247: t0 = vld4q_u8((const uint8_t*) (table +  0)); //
rgba
Where's our weak link?  I don't suppose things get any better if we do 16 rounds
of 16 pixels at a time, staying in d-registers?

Does this loop unroll completely?  If not, does it make a difference speed-wise
if we do that manually?

[msarett, 2016-02-01 16:42:11]

On 2016/02/01 16:30:37, mtklein wrote:
> https://codereview.chromium.org/1656543002/diff/20001/src/codec/SkSwizzler.cpp
> File src/codec/SkSwizzler.cpp (right):
> 
>
https://codereview.chromium.org/1656543002/diff/20001/src/codec/SkSwizzler.cp...
> src/codec/SkSwizzler.cpp:247: t0 = vld4q_u8((const uint8_t*) (table +  0)); //
> rgba
> Where's our weak link?

Looking that disassmbly (which I'll chat you), I don't have too many complaints.
We do 6 moves where we should do 2 vswaps.

And I think there are two avoidable moves right before the vst4.

I'm also seeing this which is confusing:
934:	6e0740f5 	.inst	0x6e0740f5 ; undefined

> I don't suppose things get any better if we do 16 rounds
> of 16 pixels at a time, staying in d-registers?
> 

Haven't tried this.

> Does this loop unroll completely?  If not, does it make a difference
speed-wise
> if we do that manually?

The loop doesn't unroll at all.


I can see trying your suggestions:
(1) Stay in the d registers.
(2) Unroll the loop.

But FYI, I've just uploaded a bench.  Right now on Nexus 6P times the scalar
code
at 1.06 us and the vector code at 8.14 us.

[msarett, 2016-02-02 00:03:46]

The latest Patch Set uses inline assembly and works just well enough to
benchmark.

There is no performance gain.  I think it's time for me to stop wasting time on
this :).

[mtklein, 2016-02-02 00:37:13]

On 2016/02/02 00:03:46, msarett wrote:
> The latest Patch Set uses inline assembly and works just well enough to
> benchmark.
> 
> There is no performance gain.  I think it's time for me to stop wasting time
on
> this :).

SGTM.  Just think how happily we'd land a CL that turned a giant mess of inline
assembly into
   SkPMColor c = table[index];

Best to focus on the positive aspects of this:
  - learning there's no more vswp
  - learning inline asm (and that it's miserable)