MTF: There can be only one!

[Bulat Ziganshin]

Eugene Shelwien further optimized his vectorizable constant-speed MTF implementation. Now, according to my tests it delivers constant speed of 114 MiB/s with AVX2 and 93 MiB/s with SSE2. The best-so-far implementation from BSC runs at 70 MiB/s on enwik9 and only 20 MiB/s on random data. All these measurements were taken on my Haswell i7-4770, with single thread running at 3.9 GHz.

usage example:
encoding: mtf_gc70_SSE2.exe c infile outfile
decoding: mtf_gc70_SSE2.exe d infile outfile

Older MTF-related threads:
http://encode.su/threads/509-MTF-and...and-Codec-APIs
http://encode.su/threads/546-Move-to...Implementation

Meanwhile, i work on GPU implementation. I invite to this thread everyone who want to compete with us!

[Bulat Ziganshin]

I've replaced archive in the first post with new, 5-10% faster version. Please redownload.

First direct comparison of BSC and Shelwien algorithms as compiled by GCC 4.9 -O3, on plain enwik9:

x64 AVX2:
bsc     :   71.6 MiB/s,  13324.488 ms
shelwien:  114   MiB/s,   8337.480 ms  (60% faster)


x64 SSE2:
bsc     :   68.7 MiB/s,  13878.604 ms
shelwien:   93.0 MiB/s,  10255.390 ms  (35% faster)