PAQ9 preview

[Matt Mahoney]

Here is a preview of PAQ9
http://cs.fit.edu/~mmahoney/compression/paq9a.zip

It uses the same archive format and command line interface as lpq1 (based on lpaq1) with similar compression ratio, but a little slower. For highly redundant files (like fp.log), compression is faster. It lacks models for specific file types like exe, bmp, wav, jpeg, etc. I plan to add those later. I plan to have the file type detected automatically (or by command line options) and only turn on the models needed. This should improve speed over paq8, which has most of the models on at once.

paq9a has an LZP preprocessor. It codes a match using one bit and a literal using 9 bits, which are modeled separately. This speeds up compression of highly redundant files but also hurts compression because you have to include the mispredicted byte as context for modeling the literals. As a compromise, only matches of length 12 or more are coded and only longer contexts include the extra byte.

I also experimented with a different form of context mixing. Instead of mixing all the contexts at once (using a neural network), I used a chain of 2 input mixers (again a neural network). I am not sure if this compresses better, though.

Also, I reimplemented the APM (SSE) as a 2 input mixer with one input fixed. This saves memory and reduces the number of free parameters, which should help for small files or rapidly changing data.

paq9a -1 (19 MB)
824,845 a10.jpg.paq9a-1
1,255,208 acrord32.exe.paq9a-1
487,957 english.dic.paq9a-1
3,643,525 FlashMX.pdf.paq9a-1
395,669 fp.log.paq9a-1
1,654,770 mso97.dll.paq9a-1
754,253 ohs.doc.paq9a-1
757,053 rafale.bmp.paq9a-1
499,172 vcfiu.hlp.paq9a-1
470,607 world95.txt.paq9a-1
10,743,059 bytes

paq9a -9 (1585 MB)
823,883 a10.jpg.paq9a-9
1,235,497 acrord32.exe.paq9a-9
457,932 english.dic.paq9a-9
3,633,260 FlashMX.pdf.paq9a-9
392,231 fp.log.paq9a-9
1,610,168 mso97.dll.paq9a-9
727,424 ohs.doc.paq9a-9
739,561 rafale.bmp.paq9a-9
493,760 vcfiu.hlp.paq9a-9
431,508 world95.txt.paq9a-9
10,545,224 bytes

19,974,112 enwik8.paq9a-9 539 510 sec. (comp + decomp)
165,193,368 enwik9.paq9a-9 4200 sec.
(still testing decompression)

[Simon Berger]

Hey, nice to read . But I don?t get it. Will paq and lpaq be the same and only difference will be some small features and the special file modells? Compression now seems to be little over lpaq8 (on general files). Without beeing into context mixing my thoughts were, that lpaq uses many less modells (without counting the modells for special files). Thats the reason why it is faster but with less compression. Is the overall compression not finished yet?
Also you wrote LZP will be used. But it has no better compression and isn?t faster (only on files where LZP works well).
That were the things I only wondered about, reading your post

[LovePimple]

Thanks Matt!

Mirror: Download

[Nania Francesco]

Thanks Matt!

[toffer]

Hi!

It is very suprising to me, that your lzp coding scheme is exactly the same i'm working on to improve speed in my cm implementation. If you want to get things faster (i did some experiments) use the cm hashing table to store the lzp stuff. In orders 4 and 6 a hash bucket has 3 instead of 4 nibble models - there's no big hit in compression loss (cm only) but the 16 bytes offer space for lzp pointers and a small match length model (nonlinear quantization of lengths). To predict the next character i mix orders 6, 4, a special one (some "synthetic" stuff). Btw which lzp orders work best? I found order 4 and 5 or 6 to do well. Have you done any experiments in directly modeling the next predicted character by match length (as you do in lzp) - this is something on my todo list. Maybe i can avoid some work. I noticed that you can gain speed and compression in just combining the highest 3 or 4 order's predictions - lower orders seem to be "noisier".

And something else - happy new year!

[Stephan Busch]

Dear Matt,

I have tested your new PAQ9a and here are the results:

PAQ9a reached 38th place; compressed to 1.848.055.180 bytes in 22042 seconds;
LPAQ7e reached 46th place; compressed to 1.874.189.389 bytes in 16475 seconds.

I like the tendancy to faster PAQ variants; with filetype specialized filters it can outperform PAQ8 one day. The LZP is also good.

D:TESTSETS>paq9a a 3d.paq9a -8 3d.tar
3d.tar 239679488 -> 73949466
-> 73949477 in 964.16 sec
HashTable<16> 99.6100% full, 50.9763% utilized of 524288 KiB
LZP hash table 96.8708% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 136045762 literals, 103633726 matches (43.2385% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a 3d.paq9a -8 bmp.tar
Cannot overwrite archive 3d.paq9a

D:TESTSETS>paq9a a bmp.paq9a -8 bmp.tar
bmp.tar 623902208 -> 344260272
-> 344260284 in 4551.50 sec
HashTable<16> 99.6106% full, 59.0046% utilized of 524288 KiB
LZP hash table 100.0000% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 606104885 literals, 17797323 matches (2.8526% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a psx.paq9a -8 psx.tar
psx.tar 649017344 -> 284624019
-> 284624031 in 2850.43 sec
HashTable<16> 99.6098% full, 57.7057% utilized of 524288 KiB
LZP hash table 99.9933% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 378434752 literals, 270582592 matches (41.6911% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a bin.paq9a -8 bin.tar
bin.tar 97058304 -> 26086295
-> 26086307 in 413.94 sec
HashTable<16> 99.4529% full, 44.2300% utilized of 524288 KiB
LZP hash table 75.0790% full of 131072 KiB
LZP buffer 72.3141% full of 131072 KiB
LZP 61591868 literals, 35466436 matches (36.5414% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a dna.paq9a -8 dna.txt
dna.txt 73370264 -> 17192886
-> 17192898 in 371.34 sec
HashTable<16> 99.6090% full, 32.5051% utilized of 524288 KiB
LZP hash table 29.0954% full of 131072 KiB
LZP buffer 54.6651% full of 131072 KiB
LZP 60280595 literals, 13089669 matches (17.8406% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a drv.paq9a -8 driver.tar
driver.tar 347785216 -> 49897899
-> 49897914 in 840.58 sec
HashTable<16> 99.6088% full, 49.2641% utilized of 524288 KiB
LZP hash table 92.7042% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 116071640 literals, 231713576 matches (66.6255% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a enc.paq9a -8 enc.tar
enc.tar 350370304 -> 85092841
-> 85092853 in 1175.57 sec
HashTable<16> 99.6109% full, 52.5981% utilized of 524288 KiB
LZP hash table 97.3972% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 155114609 literals, 195255695 matches (55.7284% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a fnt.paq9a -8 fonts.tar
fonts.tar 15106560 -> 5911348
-> 5911362 in 77.54 sec
HashTable<16> 73.6286% full, 27.1049% utilized of 524288 KiB
LZP hash table 26.4846% full of 131072 KiB
LZP buffer 11.2553% full of 131072 KiB
LZP 10868044 literals, 4238516 matches (28.0575% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a freedb.paq9a -8 freedb.txt
freedb.txt 728757760 -> 94161780
-> 94161795 in 2335.89 sec
HashTable<16> 99.5277% full, 40.7194% utilized of 524288 KiB
LZP hash table 96.1098% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 312801226 literals, 415956534 matches (57.0775% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a gb.paq9a -8 gb.txt
gb.txt 160734208 -> 32842004
-> 32842015 in 770.54 sec
HashTable<16> 94.6364% full, 34.6240% utilized of 524288 KiB
LZP hash table 80.0652% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 118212523 literals, 42521685 matches (26.4547% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a mod2.paq9a -8 mod2.tar
mod2.tar 63442944 -> 36097513
-> 36097526 in 380.53 sec
HashTable<16> 99.6061% full, 46.6298% utilized of 524288 KiB
LZP hash table 78.1020% full of 131072 KiB
LZP buffer 47.2687% full of 131072 KiB
LZP 52107215 literals, 11335729 matches (17.8676% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a nokia.paq9a -8 nokia.tar
nokia.tar 28546560 -> 2109822
-> 2109836 in 37.23 sec
HashTable<16> 36.3129% full, 12.7470% utilized of 524288 KiB
LZP hash table 10.6137% full of 131072 KiB
LZP buffer 21.2688% full of 131072 KiB
LZP 5568090 literals, 22978470 matches (80.4947% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a o2.paq9a -8 o2.tar
o2.tar 306484224 -> 234730263
-> 234730274 in 2164.58 sec
HashTable<16> 99.6091% full, 59.8792% utilized of 524288 KiB
LZP hash table 99.9501% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 264656508 literals, 41827716 matches (13.6476% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a wav.paq9a -8 wav.tar
wav.tar 605648896 -> 479196804
-> 479196816 in 4557.05 sec
HashTable<16> 99.6096% full, 63.8175% utilized of 524288 KiB
LZP hash table 100.0000% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 602996740 literals, 2652156 matches (0.4379% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a sav.paq9a -8 sav2.tar
sav2.tar 151070720 -> 50532061
-> 50532074 in 551.07 sec
HashTable<16> 99.6100% full, 47.1710% utilized of 524288 KiB
LZP hash table 85.6420% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 73987941 literals, 77082779 matches (51.0243% matched)
Used 799221 KiB memory

D:TESTSETS>paq9a a src.paq9a -8 sources.tar
sources.tar 209364992 -> 31369702
-> 31369718 in 545.28 sec
HashTable<16> 99.5867% full, 43.0527% utilized of 524288 KiB
LZP hash table 80.1746% full of 131072 KiB
LZP buffer 100.0000% full of 131072 KiB
LZP 74930635 literals, 134434357 matches (64.2105% matched)
Used 799221 KiB memory

[Matt Mahoney]

But I don?t get it.

Of course the goal is better speed and better compression. I have not achieved that yet. The purpose of releasing the code was to start a discussion. The idea was to use LZP to speed up compression of highly redundant data and to model the higher order contexts. Unfortunately it hurts compression so I will need to fix that or abandon the approach. I compensated by adding more models, which is why it is slower than lpaq1. paq9a has some sparse models which improve compression of binary files, but text is a bit worse.

paq9 is probably a poor choice for a name right now, because it is not yet ready to be a successor to paq8. That is my eventual goal, however. I am not happy about the speed of paq8, which is my reason for experimenting with new architectures.

Another major change is using chains of 2 input mixers. (Eugene Shelwien mentioned this idea, going from low to high orders). This idea might be too messy for combining lots of contexts, but I want to avoid too many models to get better speed. Instead, I want to use the file type to select the best models. I designed the code to make it easy to mix different types of compression this way (right now, just compress or store).

I did try adding a bit history to the LZP hash table to provide more context for the match probability, but this did not work, at least not as well as using low order contexts.

[Matt Mahoney]

Btw which lzp orders work best?

The higher the better. I used order 12 as a tradeoff between speed and compression. If I only had to model the matches and not the literals, I found orders as low as 2 worked best. (I looked up context hashes of orders 6, 3, and 2). To model the match probability I used the match length, and for lower orders (up to about 10) I also used the offset (quantized on a log scale). Small offsets are usually more likely to be matched. Then I adjusted the probability using low order contexts. It seemed like there was a lot of overlap in the contexts I used for modeling matches and literals, but I didnt try to combine them.

The problem with modeling literals is that the distribution depends on what byte was predicted (since it is removed from the literal distribution). This means the predicted byte has to be added to the context, which increases the model size and hurts compression. This is mainly a problem for low orders where the predicted byte is more likely to vary in the same context.

[Stephan Busch]

I like both the idea and the goals of PAQ9 and I am sure it will become a PAQ8 successor. 2 years ago, PAQ7 was not as powerful as PAQAR, but in the end later variants were both much faster and compressed better.

Please, Matt, keep up the excellent work on PAQ9 and don't abandon it.


Yours,
Stephan

[encode]

2 Matt:
There are many things to try with LZP.

You may use a fixed order for LZP - order-8 and higher.
No need in match legths - predicted/not predicted only stuff.

 
if (tab[hash] == c) // predicted 
... 
else // nope 
... 
 
tab[hash] = c; // update

Overall, I will suggest to minimize LZP in PAQ - i.e. use LZP for highest orders only (instead of a match model).

A kind of PPMDet (PPMZ).

You may also use a special structure for chars - i.e. keep count of a byte and if it frequently seen, do not replace it with another.

In addition, a tricky model can be used with LZP - a special flag model (predicted/not predicted char) additionally to partial literal model update - regardless of an LZP you may update the main model.

And so on...

[giorgiotani]

Nice to see PAQ9, I hope it may grow up as a very good research thread like PAQ8 and LPAQ* are!

[schnaader]

The (de)compression speed asymmetry makes PAQ9 a good candidate for a merge with Precomp:

lprepaq -t+ 5 FlashMX.pdf: (No precompression)
4526946 -> 3631849, 55.47 s
lprepaq 5 FlashMX.pdf:
4526946 -> 2242369, 190.37 s

paq9a -3 FlashMX.pdf:
4526946 -> 3636325, 95.19 s
paq9a -3 FlashMX.pcf:
26936624 -> 2295579, 133.88 s

Note how lprepaq gets about 3,5 times slower because the temporary PCF file has almost 27 MB, while paq9a is just 1,5 times slower. Same for paq8o8(pre), although I'll soon release a faster version of paq8o8pre that handles PDF images as BMPs and gains much speed doing so.

[LovePimple]

Quick speed test...

Test machine: Intel PIII @750 MHz, 512 MB RAM with Windows 2000 Pro + SP4 operating system

Test file: enwik8

PAQ9A Settings: -5

enwik8 100000000 -> 20689913
-> 20689924 in 1849.11 sec
HashTable<16> 99.6114% full, 43.8024% utilized of 65536 KiB
LZP hash table 99.3974% full of 16384 KiB
LZP buffer 100.0000% full of 16384 KiB
LZP 76831446 literals, 23168554 matches (23.1686% matched)
Used 111093 KiB memory

The test was also timed with AcuTimer v1.2:

Elapsed Time: 00 00:30:50.969 (1850.969 Seconds)

Same test with LPQ1

enwik8 100000000 -> 19888389
-> 19888399 in 1169.14 sec

Elapsed Time: 00 00:19:29.662 (1169.662 Seconds)

and LPAQ8 (5)

100000000 -> 20614034 in 1280.671 sec. using 102 MB memory

Elapsed Time: 00 00:21:22.279 (1282.279 Seconds)

[Matt Mahoney]

2 Matt:
There are many things to try with LZP.

You may use a fixed order for LZP - order-8 and higher.
No need in match legths - predicted/not predicted only stuff.


if (tab[hash] == c) // predicted
...
else // nope
...

tab[hash] = c; // update

The problem with this approach is that the match length is useful for modeling the match probability. This allows very long matches to be compressed to almost nothing, like this (2 copies of Calgary corpus). You cant do this with fixed orders.

C:&#92;res>paq9a a x calgary&#92;* calgary&#92;*
calgary&#92;BIB 111261 -> 23588
calgary&#92;BOOK1 768771 -> 202716
calgary&#92;BOOK2 610856 -> 128383
calgary&#92;GEO 102400 -> 47632
calgary&#92;NEWS 377109 -> 93212
calgary&#92;OBJ1 21504 -> 8886
calgary&#92;OBJ2 246814 -> 57876
calgary&#92;PAPER1 53161 -> 11619
calgary&#92;PAPER2 82199 -> 17788
calgary&#92;PIC 513216 -> 43494
calgary&#92;PROGC 39611 -> 9495
calgary&#92;PROGL 71646 -> 11467
calgary&#92;PROGP 49379 -> 8311
calgary&#92;TRANS 93695 -> 12151
calgary&#92;BIB 111261 -> 41
calgary&#92;BOOK1 768771 -> 89
calgary&#92;BOOK2 610856 -> 75
calgary&#92;GEO 102400 -> 33
calgary&#92;NEWS 377109 -> 63
calgary&#92;OBJ1 21504 -> 19
calgary&#92;OBJ2 246814 -> 79
calgary&#92;PAPER1 53161 -> 19
calgary&#92;PAPER2 82199 -> 21
calgary&#92;PIC 513216 -> 199
calgary&#92;PROGC 39611 -> 18
calgary&#92;PROGL 71646 -> 25
calgary&#92;PROGP 49379 -> 21
calgary&#92;TRANS 93695 -> 36
-> 677711 in 18.03 sec

[Piotr Tarsa]

why not just use matchmodel from lpaq?

ie. get probability from matchmodel and when probability is higher than x (x may be fixed or variable) or we've matcher last y bits (y is a threshold) then disable all other models.

[Matt Mahoney]

The matchmodel doesn't give you the speedup. With LZP you only model 1 bit per byte instead of 8. Notice the percent matched and the speed difference:

C:
esmaxcomp>..paq9a a x1 flashmx.pdf
flashmx.pdf 4526946 -> 3631654
-> 3631670 in 36.13 sec
HashTable<16> 86.1691% full, 31.1660% utilized of 262144 KiB
LZP hash table 21.3184% full of 65536 KiB
LZP buffer 6.7457% full of 65536 KiB
LZP 4123617 literals, 403329 matches (8.9095% matched)
Used 406005 KiB memory

C:
esmaxcomp>..paq9a a x2 fp.log
fp.log 20617071 -> 391464
-> 391475 in 15.00 sec
HashTable<16> 4.3259% full, 1.4494% utilized of 262144 KiB
LZP hash table 2.4792% full of 65536 KiB
LZP buffer 30.7218% full of 65536 KiB
LZP 1363990 literals, 19253081 matches (93.3842% matched)
Used 406005 KiB memory

[Shelwien]

Compiled paq9a myself.
http://shelwien.googlepages.com/paq9a.exe
Seems to be 10% faster.

[LovePimple]

I tried to test your 10% faster version of PAQ9A on my Intel P3 @750 MHz machine. I wanted to compare compression time with the time from my previous test.

Fatal Error: This program was not built to run on the processor in your system.
The allowed processors are: Intel(R) Pentium(R) 4 and compatible Intel processor
s. Enables new optimizations in addition to Intel processor-specific optimizatio
ns.

I guess I wont be testing this one after all!

[Shelwien]

Well, here you go: http://shelwien.googlepages.com/paq9a_p3.exe
Still should be faster than gcc version, I think.

[LovePimple]

Thanks Shelwien! Will test it now and post results later.

[LovePimple]

Results below...

enwik8 100000000 -> 20689913
-> 20689924 in 1779.02 sec
HashTable<16> 99.6114% full, 43.8024% utilized of 65536 KiB
LZP hash table 99.3974% full of 16384 KiB
LZP buffer 100.0000% full of 16384 KiB
LZP 76831446 literals, 23168554 matches (23.1686% matched)
Used 111093 KiB memory

Elapsed Time: 00 00:29:40.739 (1780.739 Seconds)

[Shelwien]

What about this then?
http://shelwien.googlepages.com/paq9a_p3_91.exe
Prev version was built with IntelC 10, and this one is 9.1 -
could be better for old CPUs.

[LovePimple]

Thanks Shelwien! Results below...

enwik8 100000000 -> 20689913
-> 20689924 in 1769.71 sec
HashTable<16> 99.6114% full, 43.8024% utilized of 65536 KiB
LZP hash table 99.3974% full of 16384 KiB
LZP buffer 100.0000% full of 16384 KiB
LZP 76831446 literals, 23168554 matches (23.1686% matched)
Used 111093 KiB memory

Elapsed Time: 00 00:29:31.715 (1771.715 Seconds)

Mirror of all three optimised versions: Download

[toffer]

Hi!

You said, that lzp lengths are modeled best (best in the sense of order n) under an order 2 context? Have you tried to approximate the length model by quantization?

Some terminilogy: what is a match length? Just the matching length starting past the lzp pointer, or matching context (preceeding the pointer) and the length succseeding the pointer.

[VistaSucks]

> Here is a preview of PAQ9
> http://cs.fit.edu/~mmahoney/compression/paq9a.zip
> It uses the same archive format and command line interface as lpq1
> (based on lpaq1) with similar compression ratio, but a little slower

And the benefit is ???

Tests:

{B} BLUE.PNG
209'409 bytes


{H} HDPMI.TAR
733'696
Source code

 
PKZIP 2.50 -exx DPMI32 
 
{B} 0.5s gave up 
{H} 0.7s 188'342 
 
KZIP default 
 
{B}  1s gave up 
{H} 20s 181'360 
 
7-ZIP LZMA 
 
{B} 0.5s 211'978 :-((( 
{H}   2s 153'822 
 
PAQ 
 
{B}  8  s 209'247 -5 :-) 
{H} 11  s 119'321 -5 
{H} 12.5s 119'262 -6

PAQ can "compress" even hard-core optimized PNG
7-ZIP miserably fails here

PAQ9 seems faster than older versions. Algorithm looks promisingly simple

Some (sorry if stupid) questions:

1. Why do you use C++ rather than C ?

2. How much faster could it be if written in ASM instead of C++ ?

3. It's a memory hog. Does it really use all the required almost 2 GiB of RAM (-9), even if the file to compress is < 1 MiB ?

[maadjordan]

png is already compressed and the 2731b diff. is rather typical even if you compress bigger PNG .. so its the archive format result ..

[nimdamsk]

My 2 cents:
1. C is no way faster then C++ today. May be C is easier to optimise, but modern complilers make the job with C++ rather good. And C++, of course, has much more insruments to make developement more rapid.
2. ASM as language has no preferences comparing with C/C++. Most optimising compilers produce better machine code than intermediate ASM programmer. Anyway, some part of PAQ7-8 is written in ASM, because no compiler can beat experienced
human brains The advantage is not as big as it could be some time ago. Modern processors are too complex and don't allow even ASM programmer to take 100% control over them.
3. It's no sense esimating compressors on such a small files. Test them on your most common data, or on big enough files. And i don't see much sense compressing already compressed data too.

[Piotr Tarsa]

C is no way faster then C++ today.

i would say rather that well written c++ code has equal speed to pure c code. rtti or other things in c++ that are done at runtime slows down programs but theyre optional (and rarely used).

c++ libraries can be faster than c libs. for eqample take sorting into consideration. std::sort is way faster than stdlib qsort() because c++ has operator overloading which makes comparing elements with std::sort way faster than executing external function as its done in qsort.

and c++ allows to write fast code faster than in pure c.

Anyway, some part of PAQ7-8 is written in ASM, because no compiler can beat experienced
human brains

its mainly caused by the fact that c++ doesnt have native support for streaming processing - simd: mxx, sse and others. particularly c++ doesnt have support for packed data types.

Modern processors are too complex and dont allow even ASM programmer to take 100% control over them.

what are you saying??? i (as asm programmer) have 100 % control over the processor and system. its just getting harder.



matt:
i would rather concentrate on speeding up match model and abandon lzp model.

eg. if there was lots of redundancy seen in the recent data (and of course all bits was matched by match model) then use only one (longest) context in match model. and i suggest using rather short contexts.

for compressing repetitions that are over (say) 120 bytes long i would use preprocessing. ie. use some special symbol for marking lzp match (as in lzp preprocessor for ppmdj). and use some heuristics for determining the beginning of a match (ie. we can delay outputting a match when we know that well get higher probability of a match/ match code in later contexts).

[nimdamsk]

what are you saying??? i (as asm programmer) have 100 % control over the processor and system. its just getting harder.

As you have no CPU microcode sources you have to believe CPU vendor, and they must not tell you all the truth. As you dont have full CPU scheme you cant think about 100% control over it. All you can is believing manuals and try to analyse yours "black box" CPU output.

[Piotr Tarsa]

i haven't? look at: http://agner.org/optimize/
there's optimization manual for all intel x86 intel processors starting from pentium (afaik first x86 processor with risc core). and they tells how any instruction is decoded and executed.

i don't have cpu scheme but i have all timings and other information (about instruction decoding, microcode execution and data flow) so i can compute exact number of processor ticks needed to execute code without actually executing it.

optmizing for 486 and earlier processors was simpler because they executed only one instruction at once. newer processors can execute few instructons at once (more than one) but programmers know how they're executed.