SIMD implementation of Convolver for Lanczos filter etc.

SIMD implementation of Convolver for Lanczos filter etc.

replace current convolver function (horizontal/vertical) with SSE2 intrinsic version. Performance is not tuned to the optimal carefully in this patch. but it still should beat C version easily.


BUG=62820
TEST=unittest. and image_operation_bench.

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=77527

[evannier, 2011-02-14 23:45:13]

Jie, I took a quick look and did not look deeply at the intrinsics. Most of the
problems are around what we had talked about over chat, so it should come as no
surprise ;-)

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:10: #ifdef ARCH_CPU_X86_FAMILY
I believe Chrome coding style recommends:
#if defined(XXX)

See also below, on why I think the ARCH_CPU_X86 might be the wrong define to
use.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:229: template<bool has_alpha>
has_alpha is not used anywhere, suggesting there is a bug here.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:230: void ConvolveHorizontally_SSE2(const unsigned char*
src_data,
Maybe move that closer to the the other Horizontally for easier comparison (or
not).

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:231: const ConvolutionFilter1D& filter,
here and elsewhere, indentation looks odd. And various lint errors.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:234: int width = filter.num_values();
Maybe name this num_values for better symmetry with the non SIMD version.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:238: for (int i = 0; i < width; i += 1) {  // One pixel
per iteration.
same comment about the naming.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:243: const unsigned char* start =
src_data+(filter_offset<<2);
what is wrong with the way it was written in the other code:
 const unsigned char* row_to_filter = &src_data[filter_offset * 4];

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:243: const unsigned char* start =
src_data+(filter_offset<<2);
Since this is going to be used as a __m128i, I would do, const __m128i* start =
reinterpret_cast<const ...>(etc);
This avoids the casts below, and makes the start += 16, a start +=1, which might
be clearer ... To the compiler.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:247: __m128i coeff =
_mm_loadl_epi64((__m128i*)filter_values);
Maybe add a comment explaining that you have ensured that this address is 64 bit
aligned (well, I assume you did).

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:249: __m128i coeff16 = _mm_shufflelo_epi16(coeff,
_MM_SHUFFLE(1, 1, 0, 0));
I have not looked at the resulting assembly, but I have been fairly disappointed
in GCC code generation when it comes to the use of intrisics, and it looks like
it might be possible that GCC might have to perform register spill over to the
stack. Check what it does, and maybe consider doing the other coeff16 shuffle
and unpack right there (it is the same number of registers, but it might help
GCC, or not).

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:257: __m128i mul_hi = _mm_mulhi_epi16(src16, coeff16);
Because of the many stalls these operations might generate, I would interleave
both parts in one single pass. Not sure if this would require more registers. 
If you have already considered that and timed it, please comment on your choice.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:288: // Note: filter_values must be pad to
align_up(filter_offset, 8);
padded

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:296: // TODO(jiesun): line buffer must be pad to
align_up(filter_offset, 16);
padded

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:318: accum = _mm_packus_epi16(accum, zero);
I am missing something.
the first packs_epi32 will move everything in 16 bit values, sign saturated:
// [16] 0, 0, 0, 0, a', r', g', b' 
The second, will take the 16 bit values, and apply the same thing, except this
is unsigned.
So, if we have a negative value, say a' is 0xFFFF, the resulting a'' will be
0xFF, right ?
(using [8] 0 0 ... 0 a'' r'' g'' b'')
Then, instead of having '0', we end up getting 0xFF.

As a test, make sure that your convolver handles well negative values as
coefficients (to generate a negative value), and very large values for > 0xFF
values.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:332: #ifdef ARCH_CPU_X86_FAMILY
Since this code is SSE2, I would use the preprocessor SSE2:
#if defined __SSE2___
Not sure if this is portable across all platforms, but it will work on GCC.
That implies that the code would need to be compiled with -msse2 to be included,
which is not acceptable for compatibility with non sse2 processors, since you do
not want GCC to generate SSE instructions when it has no right to.
So, what I had been thinking was to split off this file into multiple files,
compiled for various targets. This way you are guaranteed that the compiler will
not complain for x86 targets that do not compile with -msse2 (actually I am not
sure whether this is something that all versions of Chrome already do, since our
platform can always assume that x86 => sse2 or sse3 for that matter).

I do not know if this a good example, but Skia handles this type of issues in
this fashion:

- Create a function getter:
typedef (*Foo)(myinputs);
Foo* getFunction() {
  Foo* p = platformFunction();
  if (p) {
    return p;
  }
  return GenericFoo;
}

Then, for each platform, you have:
PlatformFunction_x86() {
  if (has_sse2) {  // check the right registers.
     return Foo_SSE2;
  }
  return NULL;
}
The two files containing the functions above being compiled without -msse2

Then, another file:
Foo_SSE2.cc
Foo_SSE2() {
   // put the SSE2 code here
}

this one compiled with SSE2.

Again, this might be moot if Chrome assumes that all platforms it runs on have
SSE2, but I thought I mentioned it.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:652: bool use_sse2) {
This does not seem right to be part of the API, given that SSE2 is not a
relevant feature from the outside.
The problem I understand is that the padding you need to apply is going to be
dependent on whether this is going to be set. Suggesting creating a Convolver
Engine virtual class which can have a type SSE2, and then knows how to deal with
padding and realignment of coefficients.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.cc
File skia/ext/image_operations.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.c...
skia/ext/image_operations.cc:320: output->PaddingForSIMD(8);
At the API layer, this seems wrong to be visible from the outside.
For example one could conceive that an optimization (that I discussed in my
comments) that the layer below would be responsible for detecting cycles in the
values, at which point, when you push the values in 'AddFilter' you have no
guarantee that any value was actually added.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
File skia/ext/image_operations_bench.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
skia/ext/image_operations_bench.cc:240: for (int x = 0; x < source_.width()*4;
x++) {
I am not much of a fan of the hard coded '4', but I have tons of code doing this
in Chrome (which I correct when I find it, and need to modify it).

[jiesun, 2011-02-15 00:19:22]

thanks for review! I am going to address all the concerns.
also I am going to split the cpuid/sse2 support detection in a seperate patch.
http://codereview.chromium.org/6526005/

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:229: template<bool has_alpha>
actually, it is always vertical after horizontal pass. therefore horizontal
never worry about alpha. but I think you are right on this.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:247: __m128i coeff =
_mm_loadl_epi64((__m128i*)filter_values);
I think there is no alignment requirement for _mm_loadl_epi64. I did not align
filter values for each filter. just pad at the end of all filters to make sure
the 64 bit load always access valid addresses.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:318: accum = _mm_packus_epi16(accum, zero);
according to http://msdn.microsoft.com/en-us/library/07ad1wx4(v=vs.80).aspx
it will pack 16 bits to 8 bits with unsigned saturation.
that's what i want exactly. ?

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:332: #ifdef ARCH_CPU_X86_FAMILY
thanks, I was trying to do that function pointer magic before, but there are
some issues with gcc function pointer with templated function... I am thinking
to use virtual function and create different convolver class on different
platform.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:652: bool use_sse2) {
also to test by comparing two version, I had to override the default decision at
some level...

[fbarchard, 2011-02-15 23:16:45]

intrinsics are problematic in general, for 32 bit builds.
compile and disassemble to see if the code looks anything like you were hoping.
I recommend inline, or yasm.  (we have yasm in chromium now... see libjpeg-turbo
and ffmpeg for how to use it)

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:695: //if (0) {
remove if you're done with this

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.cc
File skia/ext/image_operations.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.c...
skia/ext/image_operations.cc:320: output->PaddingForSIMD(8);
should be 16?

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.c...
skia/ext/image_operations.cc:477: int num_ids = cpu_info[0];
is this necessary?  i thought everyone that supports cpuid at all, support
function 1?

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
File skia/ext/image_operations_bench.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
skia/ext/image_operations_bench.cc:240: for (int x = 0; x < source_.width()*4;
x++) {
The width()*4 should also have a space.
Maybe you should fill source.rowBytes() instead?

[jiesun, 2011-02-17 20:17:58]

I am going to defer any optimization to next patches. but suggestion on
optimization are welcome.

here is the unittest output on my Z600.

[ RUN      ] Convolver.SIMDVerification
[12230:12230:867392632946:INFO:convolver_unittest.cc(294)] from:1920x1080
to:1920x1080 w/o alpha
[12230:12230:867392632993:INFO:convolver_unittest.cc(297)] c:79107 sse:50372
[12230:12230:867392633004:INFO:convolver_unittest.cc(298)] ratio:1.57046
[12230:12230:867392824922:INFO:convolver_unittest.cc(294)] from:1920x1080
to:1920x1080 with alpha
[12230:12230:867392824969:INFO:convolver_unittest.cc(297)] c:97122 sse:47955
[12230:12230:867392824979:INFO:convolver_unittest.cc(298)] ratio:2.02527
[12230:12230:867393102283:INFO:convolver_unittest.cc(294)] from:1920x1080
to:720x480 w/o alpha
[12230:12230:867393102331:INFO:convolver_unittest.cc(297)] c:21648 sse:13975
[12230:12230:867393102341:INFO:convolver_unittest.cc(298)] ratio:1.54905
[12230:12230:867393149749:INFO:convolver_unittest.cc(294)] from:1920x1080
to:720x480 with alpha
[12230:12230:867393149795:INFO:convolver_unittest.cc(297)] c:25992 sse:13533
[12230:12230:867393149805:INFO:convolver_unittest.cc(298)] ratio:1.92064
[12230:12230:867393416795:INFO:convolver_unittest.cc(294)] from:1920x1080
to:1377x523 w/o alpha
[12230:12230:867393416842:INFO:convolver_unittest.cc(297)] c:42112 sse:27358
[12230:12230:867393416853:INFO:convolver_unittest.cc(298)] ratio:1.53929
[12230:12230:867393511070:INFO:convolver_unittest.cc(294)] from:1920x1080
to:1377x523 with alpha
[12230:12230:867393511121:INFO:convolver_unittest.cc(297)] c:51437 sse:26538
[12230:12230:867393511137:INFO:convolver_unittest.cc(298)] ratio:1.93824
[12230:12230:867393652053:INFO:convolver_unittest.cc(294)] from:720x480
to:1920x1080 w/o alpha
[12230:12230:867393652100:INFO:convolver_unittest.cc(297)] c:56918 sse:35165
[12230:12230:867393652111:INFO:convolver_unittest.cc(298)] ratio:1.6186
[12230:12230:867393801850:INFO:convolver_unittest.cc(294)] from:720x480
to:1920x1080 with alpha
[12230:12230:867393801890:INFO:convolver_unittest.cc(297)] c:69302 sse:33166
[12230:12230:867393801901:INFO:convolver_unittest.cc(298)] ratio:2.08955
[12230:12230:867393903740:INFO:convolver_unittest.cc(294)] from:720x480
to:720x480 w/o alpha
[12230:12230:867393903780:INFO:convolver_unittest.cc(297)] c:13045 sse:8337
[12230:12230:867393903790:INFO:convolver_unittest.cc(298)] ratio:1.56471
[12230:12230:867393935328:INFO:convolver_unittest.cc(294)] from:720x480
to:720x480 with alpha
[12230:12230:867393935349:INFO:convolver_unittest.cc(297)] c:15900 sse:7841
[12230:12230:867393935357:INFO:convolver_unittest.cc(298)] ratio:2.0278
[12230:12230:867394017809:INFO:convolver_unittest.cc(294)] from:720x480
to:1377x523 w/o alpha
[12230:12230:867394017852:INFO:convolver_unittest.cc(297)] c:25930 sse:16858
[12230:12230:867394017862:INFO:convolver_unittest.cc(298)] ratio:1.53814
[12230:12230:867394083169:INFO:convolver_unittest.cc(294)] from:720x480
to:1377x523 with alpha
[12230:12230:867394083214:INFO:convolver_unittest.cc(297)] c:32155 sse:15966
[12230:12230:867394083225:INFO:convolver_unittest.cc(298)] ratio:2.01397
[12230:12230:867394261061:INFO:convolver_unittest.cc(294)] from:1377x523
to:1920x1080 w/o alpha
[12230:12230:867394261114:INFO:convolver_unittest.cc(297)] c:59164 sse:36175
[12230:12230:867394261141:INFO:convolver_unittest.cc(298)] ratio:1.63549
[12230:12230:867394414318:INFO:convolver_unittest.cc(294)] from:1377x523
to:1920x1080 with alpha
[12230:12230:867394414366:INFO:convolver_unittest.cc(297)] c:72256 sse:33667
[12230:12230:867394414376:INFO:convolver_unittest.cc(298)] ratio:2.1462
[12230:12230:867394550545:INFO:convolver_unittest.cc(294)] from:1377x523
to:720x480 w/o alpha
[12230:12230:867394550591:INFO:convolver_unittest.cc(297)] c:13636 sse:8731
[12230:12230:867394550610:INFO:convolver_unittest.cc(298)] ratio:1.56179
[12230:12230:867394583643:INFO:convolver_unittest.cc(294)] from:1377x523
to:720x480 with alpha
[12230:12230:867394583676:INFO:convolver_unittest.cc(297)] c:17021 sse:8251
[12230:12230:867394583685:INFO:convolver_unittest.cc(298)] ratio:2.0629
[12230:12230:867394702478:INFO:convolver_unittest.cc(294)] from:1377x523
to:1377x523 w/o alpha
[12230:12230:867394702522:INFO:convolver_unittest.cc(297)] c:27606 sse:17475
[12230:12230:867394702533:INFO:convolver_unittest.cc(298)] ratio:1.57974
[12230:12230:867394768450:INFO:convolver_unittest.cc(294)] from:1377x523
to:1377x523 with alpha
[12230:12230:867394768492:INFO:convolver_unittest.cc(297)] c:33464 sse:16321
[12230:12230:867394768502:INFO:convolver_unittest.cc(298)] ratio:2.05036
[12230:12230:867394869789:INFO:convolver_unittest.cc(294)] from:325x241
to:1920x1080 w/o alpha
[12230:12230:867394869836:INFO:convolver_unittest.cc(297)] c:47354 sse:29149
[12230:12230:867394869847:INFO:convolver_unittest.cc(298)] ratio:1.62455
[12230:12230:867395001132:INFO:convolver_unittest.cc(294)] from:325x241
to:1920x1080 with alpha
[12230:12230:867395001179:INFO:convolver_unittest.cc(297)] c:58073 sse:26577
[12230:12230:867395001190:INFO:convolver_unittest.cc(298)] ratio:2.18508
[12230:12230:867395072035:INFO:convolver_unittest.cc(294)] from:325x241
to:720x480 w/o alpha
[12230:12230:867395072080:INFO:convolver_unittest.cc(297)] c:9506 sse:6010
[12230:12230:867395072090:INFO:convolver_unittest.cc(298)] ratio:1.5817
[12230:12230:867395097533:INFO:convolver_unittest.cc(294)] from:325x241
to:720x480 with alpha
[12230:12230:867395097557:INFO:convolver_unittest.cc(297)] c:12079 sse:5619
[12230:12230:867395097566:INFO:convolver_unittest.cc(298)] ratio:2.14967
[12230:12230:867395144482:INFO:convolver_unittest.cc(294)] from:325x241
to:1377x523 w/o alpha
[12230:12230:867395144518:INFO:convolver_unittest.cc(297)] c:19257 sse:12293
[12230:12230:867395144527:INFO:convolver_unittest.cc(298)] ratio:1.5665
[12230:12230:867395195984:INFO:convolver_unittest.cc(294)] from:325x241
to:1377x523 with alpha
[12230:12230:867395196023:INFO:convolver_unittest.cc(297)] c:23864 sse:11412
[12230:12230:867395196033:INFO:convolver_unittest.cc(298)] ratio:2.09113

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:10: #ifdef ARCH_CPU_X86_FAMILY
On 2011/02/14 23:45:13, evannier wrote:
> I believe Chrome coding style recommends:
> #if defined(XXX)
> 
> See also below, on why I think the ARCH_CPU_X86 might be the wrong define to
> use.

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:229: template<bool has_alpha>
On 2011/02/14 23:45:13, evannier wrote:
> has_alpha is not used anywhere, suggesting there is a bug here.

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:230: void ConvolveHorizontally_SSE2(const unsigned char*
src_data,
I am grouping all SIMD function into a #ifdef. not sure which one is better.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:231: const ConvolutionFilter1D& filter,
On 2011/02/14 23:45:13, evannier wrote:
> here and elsewhere, indentation looks odd. And various lint errors.

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:234: int width = filter.num_values();
On 2011/02/14 23:45:13, evannier wrote:
> Maybe name this num_values for better symmetry with the non SIMD version.

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:238: for (int i = 0; i < width; i += 1) {  // One pixel
per iteration.
On 2011/02/14 23:45:13, evannier wrote:
> same comment about the naming.

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:243: const unsigned char* start =
src_data+(filter_offset<<2);
On 2011/02/14 23:45:13, evannier wrote:
> what is wrong with the way it was written in the other code:
>  const unsigned char* row_to_filter = &src_data[filter_offset * 4];

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:296: // TODO(jiesun): line buffer must be pad to
align_up(filter_offset, 16);
On 2011/02/14 23:45:13, evannier wrote:
> padded

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.cc
File skia/ext/image_operations.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.c...
skia/ext/image_operations.cc:320: output->PaddingForSIMD(8);
I agree this is ugly, but there is no "finalizefilters". padding only happened
at the end of all filters.  filter_values is also private. ...

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.c...
skia/ext/image_operations.cc:320: output->PaddingForSIMD(8);
16 byte = 8 coefficient because Fixed is short(2bytes)

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations.c...
skia/ext/image_operations.cc:477: int num_ids = cpu_info[0];
On 2011/02/15 23:16:45, fbarchard wrote:
> is this necessary?  i thought everyone that supports cpuid at all, support
> function 1?

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
File skia/ext/image_operations_bench.cc (right):

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
skia/ext/image_operations_bench.cc:240: for (int x = 0; x < source_.width()*4;
x++) {
On 2011/02/15 23:16:45, fbarchard wrote:
> The width()*4 should also have a space.
> Maybe you should fill source.rowBytes() instead?

Done.

http://codereview.chromium.org/6334070/diff/19002/skia/ext/image_operations_b...
skia/ext/image_operations_bench.cc:240: for (int x = 0; x < source_.width()*4;
x++) {
On 2011/02/14 23:45:13, evannier wrote:
> I am not much of a fan of the hard coded '4', but I have tons of code doing
this
> in Chrome (which I correct when I find it, and need to modify it).

Done.

[brettw, 2011-02-21 04:45:45]

Mostly I'd like a lot more comments. Most people (including me) don't know what
the SSE instructions are off the top of their head, and it's so low-level it can
be difficult to follow what the higher-level flow of the algorithm is doing. You
have a lot of low-level mathematical comments which are nice, and I'd like a
similar thing for high-level comments for each block of code.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:237: __m128i mask[4];
What's mask[0] for? Can you provide a comment for what this is for and note you
you don't need mask[0]?

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:248: const __m128i* row_to_filter =
Can you comment what this means?

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:252: __m128i coeff, coeff16;
For each of the "blocks" of SSE code you're written, can you provide comments
explaining in English what you're doing and what the contents of the different
variables will be at the end?

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:292: // remaining
Can you provide a better comment here?

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:450: int filter_length,
Check indentation

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.h
File skia/ext/convolver.h (right):

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.h#newcod...
skia/ext/convolver.h:102: inline void PaddingForSIMD(int align) {
I would have thought that you'd want to pad up to the next multiple of the
alignment. If you have 9 things in the filter, do you really just want to leave
it at that, or do you want to pad to 16?

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.h#newcod...
skia/ext/convolver.h:160: int source_byte_row_stride,
Style: be sure to align the args in these two functions to after the (

[jiesun, 2011-02-22 21:37:02]

Please have another look.
More comments are added in this patch for readabilities..
unfortunately the SIMD code is messy in general, just like those regular
expressions, kind of "write once". 
I am insisting to defer optimization because of that a lot of optimization
techniques actually degrade the readabilities, such as instruction reordering,
loop-unrolling, inline assembly instead of intrinsic, alignment tricks, register
reduction... ( I am not so certain that we want to pursue all of them. )
therefore it is better to have a version that's cleaner for review before
aggressive optimization.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:237: __m128i mask[4];
yes, mask[0] is not used.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:248: const __m128i* row_to_filter =
On 2011/02/21 04:45:45, brettw wrote:
> Can you comment what this means?

Done.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:252: __m128i coeff, coeff16;
On 2011/02/21 04:45:45, brettw wrote:
> For each of the "blocks" of SSE code you're written, can you provide comments
> explaining in English what you're doing and what the contents of the different
> variables will be at the end?

Done.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:292: // remaining
On 2011/02/21 04:45:45, brettw wrote:
> Can you provide a better comment here?

Done.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:450: int filter_length,
On 2011/02/21 04:45:45, brettw wrote:
> Check indentation

Done.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.h
File skia/ext/convolver.h (right):

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.h#newcod...
skia/ext/convolver.h:102: inline void PaddingForSIMD(int align) {
padding in SIMD serve two purpose:
1. make element align to element size boundary, such as 16 or 8.
2. prevent SIMD load and store instruction to access violation.
here I only try to solve problem (2). therefore only padding once after all
filters are added.
solving (1) need to padding for each filters ( not a big deal). but because of
current implementation use <vector> and it is tricky to align at the beginning.

http://codereview.chromium.org/6334070/diff/38008/skia/ext/convolver.h#newcod...
skia/ext/convolver.h:160: int source_byte_row_stride,
On 2011/02/21 04:45:45, brettw wrote:
> Style: be sure to align the args in these two functions to after the (

Done.

[brettw, 2011-02-25 06:43:02]

I get the SSE stuff much better now, thanks for the great comments.

I don't think the amount of code duplication between the two versions of the
Convolve2D functions is good. I really want to find a way to avoid this.

Some options: (1) If statements (might be a lot of branches but they should be
predicted almost perfectly so this is probably OK). (2) Parameterize the stuff
needed like number of rows to group and pass in the horizontal and vertical
convolusion functions as a struct of function pointers (3) Templates like the
has_alpha trick, although I'm worried this will make the code unreadable.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:257: // We will load and accumulate with four coefficients
per iterations.
Grammar nit: iteration (no "s"). Same below for when you duplicated this.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:377: for (int i = 0; i < num_values; ++i) {
It's weird this for loop is so different than the one in the function above. Can
you make them look the same (same variable name, probably out_x is better, and
use ++ instead of += 1).

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:429: int r = filter_length&3;
Please put a space around the &

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:445: ITERATION(src_data[0]+start, accum0);
Spaces around the +'s

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:496: for (int i = 0; i < width; i += 4) {
Can you give your loop variables better names than i and j here? Perhaps
consider the ones used in the "C" version of the algorithm.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:833: int last_filter_offset, last_filter_length;
Can you comment why you need these?

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:857: if (source_has_alpha)
These multi-line conditionals need {}

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.h
File skia/ext/convolver.h (right):

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.h#newcod...
skia/ext/convolver.h:108: // This has to be done after all |AddFilter| calls.
I get this now, thanks! I presume that in the future we could make sure the 0th
value in the filter is aligned on an 8-byte boundary and get some speed-up?

[jiesun, 2011-02-25 20:49:55]

thanks for review.
could you take a look the "patch 2" above, instead of use use_sse2 as parameter
, could I change it to template parameter. is that what you want?

[brettw, 2011-02-25 20:54:54]

Looking at it, I think I like the approach in patch 2 better than the template
approach. It seems like the extra branching overhead will be minimal and it will
save executable size.

[jiesun, 2011-03-01 00:14:34]

please have another look then.

use __SSE2__ to detect if -msse2 is specified during build.

[fbarchard, 2011-03-01 01:33:14]

The expression I use in chromium is

#if defined(__SSE2__) || defined(ARCH_CPU_X86_64) || _M_IX86_FP==2



On Mon, Feb 28, 2011 at 4:14 PM, <jiesun@chromium.org> wrote:

> please have another look then.
>
> use __SSE2__ to detect if -msse2 is specified during build.
>
>
>
>
> http://codereview.chromium.org/6334070/
>

[fbarchard, 2011-03-01 17:14:30]

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:11: #if defined(OS_WIN) || defined(__SSE2__)
I guess this is ok.  This is the expression I've tried lately:

#if defined(__x86_64__) || defined(_M_X64) || defined(__SSE2__) || _M_IX86_FP==2

which also works for /arch:AVX.
Another way to build your code is add attribute to your functions:
void ConvolveHorizontally_SSE2(
    const unsigned char* src_data,
    const ConvolutionFilter1D& filter,
    unsigned char* out_row)
    __attribute__ ((__target__ ("sse2")));

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:228: 
This strikes me as a lot of hard to maintain code, for a small win.  Its a small
win, mostly due to implementing it with intrinsics on 32 bit compilers.
I'd prefer see smaller amount of assembly, or move it to inline or yasm - if you
can achieve 5x or more, its interesting.

[brettw, 2011-03-03 17:56:19]

LGTM, just some style nits.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:736: // even runtime support SSE2 instructions, we had not
built with SSE2 support.
This comment doesn't really parse, can you reword (with capital letter at the
beginning, too).

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:777: filter_y.FilterForValue(num_output_rows-1,
&last_filter_offset,
Spaces around -

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:791: src[i] = &source_data[(next_x_row+i) *
source_byte_row_stride];
Spaces around +

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:795: next_x_row+=4;
Spaces around +=

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:798: // image area. therefore we use C version here.
Hacking into skia
I'd probably remove the sentence "Hacking into skia to add line paddings..."
since it doesn't really help here.

[jiesun, 2011-03-07 18:57:15]

Do I need a final LGTM.

Frank: are you insisting that ifdefs?

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:257: // We will load and accumulate with four coefficients
per iterations.
On 2011/02/25 06:43:02, brettw wrote:
> Grammar nit: iteration (no "s"). Same below for when you duplicated this.

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:377: for (int i = 0; i < num_values; ++i) {
On 2011/02/25 06:43:02, brettw wrote:
> It's weird this for loop is so different than the one in the function above.
Can
> you make them look the same (same variable name, probably out_x is better, and
> use ++ instead of += 1).

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:429: int r = filter_length&3;
On 2011/02/25 06:43:02, brettw wrote:
> Please put a space around the &

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:445: ITERATION(src_data[0]+start, accum0);
On 2011/02/25 06:43:02, brettw wrote:
> Spaces around the +'s

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:496: for (int i = 0; i < width; i += 4) {
On 2011/02/25 06:43:02, brettw wrote:
> Can you give your loop variables better names than i and j here? Perhaps
> consider the ones used in the "C" version of the algorithm.

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:833: int last_filter_offset, last_filter_length;
On 2011/02/25 06:43:02, brettw wrote:
> Can you comment why you need these?

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:857: if (source_has_alpha)
On 2011/02/25 06:43:02, brettw wrote:
> These multi-line conditionals need {}

Done.

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.h
File skia/ext/convolver.h (right):

http://codereview.chromium.org/6334070/diff/38015/skia/ext/convolver.h#newcod...
skia/ext/convolver.h:108: // This has to be done after all |AddFilter| calls.
correct. it is not done in this patch, because I am worried about vector
implementation on different platforms.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:228: 
the only speed up for this algorithm is parallelism, which we do 32 bits ( 4
elements in the same time) , therefore the maximum speedup of 4. certainly due
to Amdahl's law, you will achieve only partial speedup because some of them are
not able to make them parallel.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:736: // even runtime support SSE2 instructions, we had not
built with SSE2 support.
On 2011/03/03 17:56:19, brettw wrote:
> This comment doesn't really parse, can you reword (with capital letter at the
> beginning, too).

Done.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:777: filter_y.FilterForValue(num_output_rows-1,
&last_filter_offset,
On 2011/03/03 17:56:19, brettw wrote:
> Spaces around -

Done.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:791: src[i] = &source_data[(next_x_row+i) *
source_byte_row_stride];
On 2011/03/03 17:56:19, brettw wrote:
> Spaces around +

Done.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:795: next_x_row+=4;
On 2011/03/03 17:56:19, brettw wrote:
> Spaces around +=

Done.

http://codereview.chromium.org/6334070/diff/51005/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:798: // image area. therefore we use C version here.
Hacking into skia
On 2011/03/03 17:56:19, brettw wrote:
> I'd probably remove the sentence "Hacking into skia to add line paddings..."
> since it doesn't really help here. 

Done.

[fbarchard, 2011-03-07 20:38:10]

http://codereview.chromium.org/6334070/diff/59001/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/59001/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:12: #include <emmintrin.h>  // ARCH_CPU_X86_FAMILY was
defined in build/config.h
This header can't be used unless you enable SSE2.
Chrome official builds don't.  Which poses 2 problems:
1. how to make this avoid breaking the build
2. how to make this actually work using sse2, on Chrome.

[jiesun, 2011-03-07 20:55:24]

I had ifdef already change to conform other place in chromium projects. is this
okay ?

let's worry about gyp magic later.

http://codereview.chromium.org/6334070/diff/59001/skia/ext/convolver.cc
File skia/ext/convolver.cc (right):

http://codereview.chromium.org/6334070/diff/59001/skia/ext/convolver.cc#newco...
skia/ext/convolver.cc:12: #include <emmintrin.h>  // ARCH_CPU_X86_FAMILY was
defined in build/config.h
my understanding is that on windows this is always true.
and gcc will set __SSE2__ when -msse2 is specified on 32 bits and on 64 bits
linux, this is always true too.

[brettw, 2011-03-07 21:39:33]

On Mon, Mar 7, 2011 at 10:57 AM,  <jiesun@chromium.org> wrote:
> Do I need a final LGTM.

You don't need to wait from another pass from me.

Brett

[fbarchard, 2011-03-08 18:52:27]

LGTM
This code should at least build/run.  Likely the SSE2 will be disabled on
Chrome, since the SSE2 is not enabled.  So a followup should be done to look
into that... enabling SSE2 for this module, in the gyp, using inline or yasm.