Inline assembly routines for paq8

[Shelwien]

http://shelwien.googlepages.com/paq8p_asm_v0.rar

A few days ago I discovered that apparently IntelC supports
GNU inline asm syntax even under windows, including the
parameter specification syntax.
And basically that allows to write much more practical
assembly implementations - as the code can be properly
inlined and doesn't require any inefficient thunks.

Well, of course, gcc also supports its out asm syntax .

So I invented my own syntax for inline asm (intel with
some extensions) and had written a preprocessor to
translate it into gcc's AT&T syntax, and this is the result.
(.src files contain the "original" versions).

Like this, its no more necessary to use an external
assembler, and also some redundant stack operations
are removed, and functions can be inlined.

Now it'd be really nice if somebody could test this
and say whether it really helps (and how much),
and whether its possible to compile faster builds from this source.

Also I used a random version, but the same approach
should be applicable to other versions, like paq8px etc.

[Rugxulo]

http://shelwien.googlepages.com/paq8p_asm_v0.rar

A few days ago I discovered that apparently IntelC supports
GNU inline asm syntax even under windows, including the
parameter specification syntax.

However, I heard that Apple's GCC only supports AT&T, oddly enough.

So I invented my own syntax for inline asm (intel with
some extensions) and had written a preprocessor to
translate it into gcc's AT&T syntax, and this is the result.
(.src files contain the "original" versions).

Like this, its no more necessary to use an external
assembler, and also some redundant stack operations
are removed, and functions can be inlined.

Well, I already translated it to WASM (OpenWatcom) and GAS (GCC) so it didn't need NASM / YASM. But GAS doesn't support OBJ, hence OpenWatcom most likely still needs NASM or WASM (although its linker supports other formats like COFF, but its assembler won't output that, only third-party JWasm does).

Now it'd be really nice if somebody could test this
and say whether it really helps (and how much),
and whether its possible to compile faster builds from this source.

Compile faster builds? I guess you mean LovePimple's magic touch here.

Also I used a random version, but the same approach
should be applicable to other versions, like paq8px etc.

To be perfectly honest, I'm such a dumb dumb, that I find GNU inline syntax abysmal and confusing. And AT&T ... GAS has supported Intel style since BinUtils 2.10 or so (almost ten years), so why anybody still prefers "%%eax $#(blah)" is beyond me. But that's not a criticism directed at you ....

Anyways, nice job, I'll take a closer look.

[toffer]

If IntelC mirrors GCC's invocation (with these config suff), there's

"-masm=intel"

and for switching between Intel/AT&T there's

asm(
".intel_syntax noprefix"
... code ...
".att_syntax"
: input/output/clobber
)

[Shelwien]

IntelC documentation explicitly says that it doesn't support directives
(including these) and some other things (eg. symbols and labels) yet,
so there's no other way around.
But there're workarounds, and with my preprocessor I'm now able to
write asm inlines properly connected to surrounding code.

[Shelwien]

Guess I'd post some samples for lazy people:

Source:

__declspec(align(16))
int mask[] = { 0x10001,0x10001,0x10001,0x10001 };

void train(short *t, short *w, int n, int err) {
<asm>
  input a t=t
  input d w=w
  input c n=n
  input rm err=err
  input m mask=mask[0]
  clobber xmm0,xmm1

  add ecx, 7            ; n/8 rounding up
  and ecx, -8
  jz 1f
  sub eax, 16
  sub edx, 16
  movd xmm0,err
  pshuflw xmm0,xmm0,0
  punpcklqdq xmm0,xmm0
2:                  ; each iteration adjusts 8 weights
  movdqa xmm3, [eax+ecx*2] 	; t[i]
  movdqa xmm2, [edx+ecx*2] 	; w[i]
  paddsw xmm3, xmm3     ; t[i]*2
  pmulhw xmm3, xmm0     ; t[i]*err*2 >> 16
  paddsw xmm3, mask	; (t[i]*err*2 >> 16)+1
  psraw xmm3, 1         ; (t[i]*err*2 >> 16)+1 >> 1
  paddsw xmm2, xmm3     ; w[i] + xmm3
  movdqa [edx+ecx*2], xmm2
  sub ecx, 8
  ja  2b
1:
</asm>
}

Preprocessed output:

__declspec(align(16))
int mask[] = { 0x10001,0x10001,0x10001,0x10001 };

void train(short *t, short *w, int n, int err) {
  ASM ("\
  add $7,%%ecx; \
  and $-8,%%ecx; \
  jz 1f; \
  sub $16,%%eax; \
  sub $16,%%edx; \
  movd %3,%%xmm0; \
  pshuflw $0,%%xmm0,%%xmm0; \
  punpcklqdq %%xmm0,%%xmm0; \
2:   movdqa (%%eax,%%ecx,2),%%xmm3; \
  movdqa (%%edx,%%ecx,2),%%xmm2; \
  paddsw %%xmm3,%%xmm3; \
  pmulhw %%xmm0,%%xmm3; \
  paddsw %4,%%xmm3; \
  psraw $1,%%xmm3; \
  paddsw %%xmm3,%%xmm2; \
  movdqa %%xmm2,(%%edx,%%ecx,2); \
  sub $8,%%ecx; \
  ja 2b; \
1:   " :  : "a"(t),"d"(w),"c"(n),"rm"(err),"m"(mask[0]) : "xmm0","xmm1"
  );

}

Basically the main problem is related to these input/output
specifications... GNU syntax requires _counting_ them.
And such instruction syntax is not any convenient anyway too.
But with a preprocessor its ok now
If its like that, I may even start to use assembly inlines again

[Skymmer]

Ok, lets see what is the beast that Inline assembly. Here are a couple of tests for PAQ8p.

            | enwik6  |   bsp    |  wav   |  bmp   |   exe   |   jpeg  |
-------------------------------------------------------------|---------|
paq8p       | 102.540 | 126.474  | 44.781 | 40.020 | 133.986 | 135.455 |
paq8p_sse2  | 108.558 | 134.450  |  crash | 42.388 | 144.558 | 146.720 |
paq8p_s0    | 208.481 | 255.383  | 71.339 | 64.356 | 258.113 | 194.290 |
paq8p_s1    | 100.428 | 123.823  | 60.269 | 40.361 | 132.410 | 173.413 |
paq8p_s2    |  99.982 | 123.273  | 56.446 | 39.780 | 131.830 | 169.482 |
-----------------------------------------------------------------------'

This test brings a lot of issues.
1.) In all cases sse2 compile is slower than plain one.
2.) sse2 compile causes immediate crash on WAV files. I don't know if it have been noticed previously or not.
3.) Plain compile is somehow fastest for WAV and JPEG files.
4.) For WAV and EXE different compiles produce different output files. In details (size\CRC):

EXE
paq8p          266 630     4639BDF9
paq8p_sse2     266 632     6A27A85C
paq8p_s0       266 630     4639BDF9
paq8p_s1       266 630     4639BDF9
paq8p_s2       266 632     6A27A85C

WAV
paq8p          1 312 740     63849E41
paq8p_sse2            32     5A340C5B
paq8p_s0       1 312 741     4CFA32CD
paq8p_s1       1 312 745     A391564F
paq8p_s2       1 312 738     15C357B5

5.) s2 compiles are always crash at the end of compression although creating normal compressed files.

[Simon Berger]

Let's try to forget the differences in wav compression thats really not fixable and shouldn't be fixed by compilations.
It seems there has to be a bigger rewrite of the wav model.

[Rugxulo]

Anyways, nice job, I'll take a closer look.

Well, it seems that BinUtils 2.17 and newer don't like it yet 2.16.1 is okay. I don't know why. Gah, I hate compiler (/ libary / source) errors (/ bugs / quirks) on such stupid things.

[Shelwien]

1. _s0 is ia32/NOASM/IntelC 11.1 build, _s1=SSE1, _s2=SSE2 (using
corresponding inline asm routines).

2. paq8p_sse2 is an "original" gcc/mingw build from paq8p archive.

3. Skymmer, thanks for testing, at least it confirms my results
(also I only checked with texts and it didn't crash that much).
But actually by comparing I meant
a) compiling same paq8 with the same compiler and settings, but
using C++ / inline asm / external asm and comparing the speed.
b) comparing the speed of best known paq8p build to paq8p_s2,

4. Considering crashes. Actually this asm code is weird enough -
for example, SSE2 train() can modify up to 30 bytes of unrelated
data before the start of w[] table - supposedly for alignment.
To me that seems the main reason for crashes.

5. This asm code doesn't look really optimal anyway, and I might
be able to fix the alignment issue and further improve the speed,
but please give me a more relevant version first
(paq8px_v61 or what? I don't really track these).

6. "Well, it seems that BinUtils 2.17 and newer don't like it yet 2.16.1 is okay".
I didn't check version details, but my gcc/mingw seemed to understand these
inline asm routines, though I had to specify -march=pentium4 for that.

[Shelwien]

Here're similar paq8px_v61 compiles:
http://shelwien.googlepages.com/paq8px61_sh1.rar

Also I patched the Array allocator a little, so SSE2 version
doesn't crash on me anymore. Has to be further checked though.

[Skymmer]

Thanks! Some speed ranks for TestBed.tar file.

paq8px                     1128.939
paq8px_speed_optimised     1086.921
paq8px_sse2_amd            1110.871
paq8px_sse2_intel          1121.536
paq8px61_s00               1975.021
paq8px61_s02               2023.013
paq8px61_s11               1116.945
paq8px61_s22               1104.431

Would be interesting to see compiles from LovePimple based on provided inline assembly

[Rugxulo]

6. "Well, it seems that BinUtils 2.17 and newer don't like it yet 2.16.1 is okay".
I didn't check version details, but my gcc/mingw seemed to understand these
inline asm routines, though I had to specify -march=pentium4 for that.

Very odd that GCC 3.4.4 + BinUtils 2.16.1 works, but newer now requires -march=pentium4 (or similar) to work. I blindly guess because someone thought inline assembly should be moderated by GCC itself (even though passed to GAS). I'm not sure I prefer this new method, honestly, esp. since the error message is not exactly helpful.

P.S. Does Intel's compiler have its own built-in assembler?

P.P.S. What exactly is in the OPT11/ subdir? Looks like leftovers.

[Shelwien]

> P.S. Does Intel's compiler have its own built-in assembler?

Yes. Even two, apparently (GNU and MS).
But asm parameter specification is only supported with gnu syntax .

> P.P.S. What exactly is in the OPT11/ subdir? Looks like leftovers.

That's statistics for "profile-guided optimization".
(There's a feature in modern compilers which allows to build a special "instrumented"
executable first, then run some tests, and then use gathered statistics
in subsequent compiles, which is usually quite helpful).
So these files are required to compile the same executables as I posted.

[LovePimple]

I tested these under GCC by compiling the included paq8p source with march=pentium3 for sse and march=pentium4 for sse2. The compiler did not report any errors, but the P3 executable fails during compression testing. I don't have the hardware to test the P4 compile.

Here are the all the files from my test...

http://www.sendspace.com/file/qa32ug

[Rugxulo]

I tested these under GCC by compiling the included paq8p source with march=pentium3 for sse and march=pentium4 for sse2. The compiler did not report any errors, but the P3 executable fails during compression testing. I don't have the hardware to test the P4 compile.

Blame Shelwien for only including the P4/SSE2 inline asm routines. "Every computer supports it", yeah right.

[LovePimple]

Does my P4 compile function correctly?

[M4ST3R]

Does my P4 compile function correctly?

yes, it looks ok

[LovePimple]

Thanks M4ST3R!

[M4ST3R]

I wrote inline asm routines in MS syntax. Compile with /DINLINE_INTELC_MMX or /DINTEL_INTELC_SSE2. It can be compiled by MSVC or ICL.

paq8px_v61: Source, regular mmx, regular sse2, inlined mmx, inlined sse2 compiles included
The speed gain is 0.5%

I'm new to inlined asm then I'm not completely sure of what I did. Don't blame me if it crashes on your computer. But don't be too much afraid, I ran these builds on my own PC and it didn't crash

[Skymmer]

Here is a little bit revisited test table for PAQ8p. Now with LovePimple's compilations included, total time rankings and highlighting

                  | enwik6  |  bmp   |   bsp   |   exe   |  jpeg   |  wav   |   total  |
-------------------------------------------------------------------|--------|----------|
paq8p             | 102.753 | 39.455 | 126.502 | 133.731 | 127.224 | 44.592 | 574.257  |
paq8p_sse2        | 108.678 | 42.329 | 134.702 | 144.098 | 138.248 | crash  | -------- |
paq8p_s0          | 208.585 | 64.193 | 255.564 | 257.523 | 187.927 | 71.192 | 1044.984 |
paq8p_s1          | 100.496 | 40.095 | 123.919 | 132.171 | 165.465 | 60.108 | 622.254  |
paq8p_s2          |  99.982 | 39.780 | 123.273 | 131.830 | 162.280 | 56.446 | 613.591  |
paq8p_p3_fun_sse  | 113.269 | 44.396 | 141.063 | 152.457 | 139.257 | 50.955 | 641.397  |
paq8p_p4_fun_sse2 | 113.539 | 43.571 | 141.158 | 152.608 | 144.157 | 51.882 | 646.915  |
---------------------------------------------------------------------------------------'

Strange thing here is that paq8p_p4_fun_sse2 is slower than paq8p_p3_fun_sse

Shelwien, LP, thanks for provided stuff
Who's next in test-queue ?

[LovePimple]

I didn't use any optimization for those compiles. Try these...

http://www.sendspace.com/file/gzz22c

[Skymmer]

I'll gladly test it, more exactly speaking already started, but I suppose its not exactly what Shelwien wanted to see. The idea was to compile PAQ8p with GCC with both usual assembly and inline version provided and perform comparison between them. So, LovePimple, can you provide compiles maded with usual assembly, if its not hurt of course? Preferably compiled with the same optimisation level as last ones so we can perform a fair comparison.

[Skymmer]

Here is the updated results-table. Now with latest optimised compiles from LP based on inline asm and new column called total w/o wav which have been introduced due the fact that two compiles are crashing on WAV data.

                   | enwik6  |  bmp   |   bsp   |   exe   |  jpeg   |  wav   |   total  | total w/o wav |
-------------------|---------|--------|---------|---------|---------|--------|----------|---------------|
paq8p              | 102.753 | 39.455 | 126.502 | 133.731 | 127.224 | 44.592 | 574.257  | 529.665       |
paq8p_sse2         | 108.678 | 42.329 | 134.702 | 144.098 | 138.248 | crash  | -------- | 568.055       |
paq8p_s0           | 208.585 | 64.193 | 255.564 | 257.523 | 187.927 | 71.192 | 1044.984 | 973.792       |
paq8p_s1           | 100.496 | 40.095 | 123.919 | 132.171 | 165.465 | 60.108 | 622.254  | 562.146       |
paq8p_s2           |  99.982 | 39.780 | 123.273 | 131.830 | 162.280 | 56.446 | 613.591  | 557.145       |
paq8p_p3_fun_sse   | 113.269 | 44.396 | 141.063 | 152.457 | 139.257 | 50.955 | 641.397  | 590.442       |
paq8p_p4_fun_sse2  | 113.539 | 43.571 | 141.158 | 152.608 | 144.157 | 51.882 | 646.915  | 595.033       |
paq8p_fun_sse      |  97.771 | 39.135 | 118.978 | 126.664 | 133.323 | 46.652 | 562.523  | 515.871       |
paq8p_fun_sse_alt  |  96.657 | 38.043 | 118.266 | 126.028 | 129.782 | 45.831 | 554.697  | 508.866       |
paq8p_fun_sse2     |  97.331 | 37.966 | 118.769 | 126.131 | 133.904 | crash  | -------- | 514.101       |
paq8p_fun_sse2_alt |  96.997 | 37.707 | 118.751 | 126.236 | 132.915 | 46.694 | 559.300  | 512.606       |
--------------------------------------------------------------------------------------------------------'

Once again a couple of issues:
1.) paq8p_fun_sse2 crashes on WAV data as same as paq8p_sse2
2.) Plain compile is still unbeatable on JPEG and WAV data.

[LovePimple]

I'll gladly test it, more exactly speaking already started, but I suppose its not exactly what Shelwien wanted to see. The idea was to compile PAQ8p with GCC with both usual assembly and inline version provided and perform comparison between them. So, LovePimple, can you provide compiles maded with usual assembly, if its not hurt of course? Preferably compiled with the same optimisation level as last ones so we can perform a fair comparison.

OK, here's a copy of PAQ8P compiled exactly as requested...

http://www.sendspace.com/file/xzqstd

[Skymmer]

OK, here's a copy of PAQ8P compiled exactly as requested...

Thank you man! Now we can perform additional comparison so here is the updated table where first four compiles are using usual assembly and all others are maded with Inline ASM by Shelwien.

                      | enwik6  |  bmp   |   bsp   |   exe   |  jpeg   |  wav   |   total  | total w/o wav |
----------------------|---------|--------|---------|---------|---------|--------|----------|---------------|
OR_paq8p              | 102.753 | 39.455 | 126.502 | 133.731 | 127.224 | 44.592 | 574.257  | 529.665       |
OR_paq8p_sse2         | 108.678 | 42.329 | 134.702 | 144.098 | 138.248 | crash  | -------- | 568.055       |
LP_paq8p_sse2         |  98.390 | 39.770 | 120.013 | 127.583 | 136.133 | 47.028 | 568.917  | 521.889       |
LP_paq8p_sse2_alt     |  97.646 | 39.393 | 119.515 | 127.092 | 133.941 | 46.776 | 564.363  | 517.587       |
                      |         |        |         |         |         |        |          |               |
SH_paq8p_s0           | 208.585 | 64.193 | 255.564 | 257.523 | 187.927 | 71.192 | 1044.984 | 973.792       |
SH_paq8p_s1           | 100.496 | 40.095 | 123.919 | 132.171 | 165.465 | 60.108 | 622.254  | 562.146       |
SH_paq8p_s2           |  99.982 | 39.780 | 123.273 | 131.830 | 162.280 | 56.446 | 613.591  | 557.145       |
LP_paq8p_p3_fun_sse   | 113.269 | 44.396 | 141.063 | 152.457 | 139.257 | 50.955 | 641.397  | 590.442       |
LP_paq8p_p4_fun_sse2  | 113.539 | 43.571 | 141.158 | 152.608 | 144.157 | 51.882 | 646.915  | 595.033       |
LP_paq8p_fun_sse      |  97.771 | 39.135 | 118.978 | 126.664 | 133.323 | 46.652 | 562.523  | 515.871       |
LP_paq8p_fun_sse_alt  |  96.657 | 38.043 | 118.266 | 126.028 | 129.782 | 45.831 | 554.697  | 508.866       |
LP_paq8p_fun_sse2     |  97.331 | 37.966 | 118.769 | 126.131 | 133.904 | crash  | -------- | 514.101       |
LP_paq8p_fun_sse2_alt |  96.997 | 37.707 | 118.751 | 126.236 | 132.915 | 46.694 | 559.300  | 512.606       |
-----------------------------------------------------------------------------------------------------------'

Well, I suppose results are talking for themself. Inline ASM prooved itself to be faster than usual one. Thanks, Eugene