Hutter Prize submission

[Matt Mahoney]

Alexander Rhatusnyak has posted a Hutter Prize submission to https://sites.google.com/site/lossle...P_2017_May.zip
The submission is open for a 30 day comment period before a prize is awarded according to the rules at http://prize.hutter1.net/

The submission consists of a compressed file and a decompressor as a 64 bit Linux executable. The total size is slightly over 3% smaller than the previous submission made 23 May 2009. In my test, decompression takes 8 hours and 10 minutes on a 2.67 GHz Core i7 M620 with 4 GB memory running 64 bit Ubuntu. The program uses 1 GB memory and a 1 GB temporary file. EDIT: 256 MB temporary file.

15,420,822 compressed_enwik8
49,992 phda
15,470,814 total size

The previous best submission was 15,949,688 bytes. New submissions must improve by at least 3%.

To run: ./phda compressed_enwik8 enwik8.out
A progress counter will count to 110.

[Shelwien]

Any more information about the algorithm?

1. Linux/x64/SSE was a bad choice - unpacked exe size is ~108k,
while previous version was only ~34k.
Also, unpacked phda_ram can be compressed from 49,936 to 35,345 with paq8p-6

Should be possible to save 10-20k more using VC6 on windows instead.

Btw, linux/x64 binaries don't make reverse engineering harder -
more like it helps.

2. Header generation:
" <timestamp>%d-%02d-%02dT%02d:%02d:%02dZ</timestamp>\n",

3. mod_ppmd confirmed, so I didn't post it for nothing :)

4. no mod_SSE or paq_rc though. Maybe perl scripts helped at least?

[Matt Mahoney]

Hopefully Alexander Rhatushnyak will comment on the program. He used a Linux executable because a Windows executable, although smaller when compressed with Upack, did not meet the time requirements due to going through Wine for random disk access. (I would prefer the contest allowed source code).

[pothos2]

I think the rules should be changed to require source code submission to reproduce the binary submission - not only for scientific reasons but also for security (But maybe running random executables from the net is a Windows habit in this forum which I will never understand).

[Shelwien]

> Windows executable, although smaller when compressed with Upack, did not meet the time requirements

This is your problem, sorry. Please test it on native windows.
prize.hutter1.net clearly says "Create a Linux or Windows executable".
There's nothing about running windows executables under emulation and then applying time constraints.

> compressed with Upack

That's hardly the best compressor.
Please at least try
http://www.crinkler.net/
http://www.farbrausch.de/~fg/kkrunchy/

[Christoph Diegelmann]

> In my test, decompression takes 8 hours and 10 minutes on a 2.67 GHz Core i7 M620.

Hardly seems to fit "Must run in <10 hours on a 2GHz P4".

[Shelwien]

P4 also doesn't support x64/SSE4 :)

I never considered these requirements to be fair though.
In this case, I'm much more concerned about the fact that the result could be 20-30k better,
using VC6/x86 + better exe compressor on windows.

[Christoph Diegelmann]

I think that it doesn't meet official time requirements which disqualifies it as much as using too much RAM is more of an concern than "a few" bytes that everyone can shave off with a publicly available tool.

[Shelwien]

> I think that it doesn't meet official time requirements

Well, what Matt posted _does_ meet the requirements - 8h is less than required 10h.
Sure, P4 would be slower, but then we could use some fast SSD with it - there're no requirements about storage type.

Also, you can't properly apply crinkler without source - its a linker replacement.

And with extra 30k, I'd not be surprised if its possible to reduce the size of hashtable (or ppmd tree) at the cost of worse compression, and thus fit in 1G
without swapping, or whatever it does.

[Shelwien]

Apparently they changed the rules: http://prize.hutter1.net/hrules.htm

[Christoph Diegelmann]

So they changed it to exactly fit the submission. Seriously?

[Shelwien]

Well, it looks like they did it at least a month before - http://web.archive.org/web/201705052...net/hrules.htm

[Mike]

So they changed it to exactly fit the submission. Seriously?

Well, it looks like they did it at least a month before - http://web.archive.org/web/201705052...net/hrules.htm

And Last-Modified: Mon, 29 May 2017 23:51:27 GMT

[Shelwien]

Here I tried diffing 05-May version with current one ('<' lines are old version, '>' new).

196,197c70
<       </li><li>Documented source code of (de)compressor and usage/compilation instructions and all other relevant files must be made available to the H-prize committee.</li>
---
232,234c105,108
<       <li>Description of the test machine (processor, memory, operating system). </li>
<       <li>Links where files can be downloaded. </li>
---
>       <li>Description of the test machine (processor, memory, operating system). </li>
>       <li>Links where files can be downloaded:<br>
>              Executables and documented source code of (de)compressor and all other relevant files.</li>
>       <li>Usage/compilation instructions.</li>
238,239c112
<     inner workings of the (de)compressor, the source code, etc, is highly appreciated. </a>
---
>     inner workings of the (de)compressor, is highly appreciated. </a>

I guess Alex didn't agree to give the source even to Matt :)

[JamesB]

So they changed it to exactly fit the submission. Seriously?

To be fair, I'm sure Matt changed it to fit his own hardware as the time limit is hard to enforce otherwise. I think this is reasonable and it also promotes more research as over time CPUs become more powerful and what would once have been inappropriate time becomes more acceptable.

[Christoph Diegelmann]

Well, it looks like they did it at least a month before - http://web.archive.org/web/201705052...net/hrules.htm

I looked it up before I was posting about it because I was unsure about how many GHz the P4 has in order to check if 8h 10min is within a somewhat reasonable time for 10h P4 (it's not). On the front page at least it's still

Restrictions: Must run in <10 hours on a 2GHz P4 with 1GB RAM and 10GB free HD.

To be fair, I'm sure Matt changed it to fit his own hardware as the time limit is hard to enforce otherwise. I think this is reasonable and it also promotes more research as over time CPUs become more powerful and what would once have been inappropriate time becomes more acceptable.

I'm totally agreeing that updating the prize to a more modern requirement would be interessting even though it makes it harder to track how the algorithms improve over time. Changing it to fit a certain submission is what's absolutely not acceptable. Would it have been changed if someone else had posted it ? Maybe even a few years earlier ? I think if there's enough money for a price than there should be enough money to keep the requirements constant (e.g. keep the original pc). At least the score is now somewhat future proof.

Too make my point clear: An Intel P4 630 (from Q4'2005) has a a Geekbench4 score of around 900. That means with the new rules the programs would be allowed to take 22 hours on the old machine instead of 10. And the P4 630 has 3 GHz instead of 2 ! That means this is an effective trippling of the allowed time which means the new submission would be nowhere within the original rules.

[Shelwien]

I really don't care that much about time and memory.
I think that forcing Alex to write custom swapping as a workaround for memory limit is plain dumb - it has no relation to compression or AI for sure.

But what's more interesting is algorithm description.
For example, I suspect that there's some influence from cmix in this version - there's a lot of float-point code in phda, and cmix has a float-point model.
So maybe Alex used LSTM mixer from cmix, or some such.
But he doesn't want to share the source, and doesn't want to describe the algorithm.
Is that okay?

[Matt Mahoney]

We had some discussion about the rules, but Marcus Hutter is funding the prize so he has the final decision. We did agree to change the hardware requirements to a newer machine I can actually test on, and it (barely) passed.

Originally LTCB and Hutter prize were to be the same but we disagreed on the rules. I wanted to allow unlimited hardware but you can see the problem if you give prize money. I also allow either source or executables.

I tested several earlier submissions which were too slow. You could also argue that using a temporary file for the disk cache space wouldn't work on a machine that only had 1 GB of actual RAM. I'd rather just see the hardware restrictions relaxed to keep up with modern computers.

[byronknoll]

I asked Alex for some more information about the program. Here is his reply:

16 facts about the algorithm.

1. Overall it's a hugely improved algorithm of the previous (2009) submission, with a couple new features.
2. Everything was revised, from pre-DRT enwik-specific preprocessing, to arithmetic coder.
3. The latter is simpler than before, because Predictor returns a floating-point number:
U32 d = (U32)((x2_ - x1_) * predictor->predict()), xmid = x1_ + d;
4. There are floating-point mixers that operate basically on the same input as
fixed-point mixers, plus or minus a percent or so, and
5. a floating point SSE, that's why predictor->predict() returns a f.p. number.
6. Enwik-specific preprocessing is about twice more complex than in 2009.
7. The NLP part of the algorithm (DRT mostly) is still rather primitive.
8. There's a ppmd implementation (with order 7 and 247.125 Mb memory allocated), and
9. it's the least efficient memory user in the submission code. In March when RAM + scratch file
were close to 2 GiB, it was not, but now when RAM + scratch file = 1.25 GiB, every other
component is much more memory efficient. So if I had a couple more months,
ppmd would be either eliminated completely, or made more memory efficient.
For example, RestoreModelRare() leaves about half of allocated memory unused. This happens thrice.
10. A big number of contexts are of the form "Condition? 0 : something" - this helps reduce memory usage.
Especially the most important contexts, used by models that consume more memory than the average.
11. Almost half of contexts are using the compressed 2-bit and 3-bit representations of symbols:
U32 DRT_to3bits[256]= {
0,0,0,0,0,0,0,4, 6,2,0,0,3,0,0,0,
// 14 lines skipped
7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,
};
and then s3bits = DRT_to3bits[symbol]. Such representations are really ubiquitous in the code.
12. There is a tiny LSTM implementation, it's used in one place in the code,
but I think it could be* used in three places, including SSE.
* if HDD in Matt's Dell E6510 was as fast as an SSD, and decompression time was close to 5 hours.
13. Unlike lpaq9, there are just two types of state tables, both are 8-bit ST's.
One is sort of "for stationary models", another "for non-stationary".
14. An alphabet reorder is present, but it could be much better than now.
After DRT there are no capital letters, that's why more than 35 symbols are never used.
15. There are 105 models currently (the version to be released at the end of June), and
16. they produce 450 probabilities.

the name phda evolved from HPDec, and it currently stands for Pack Hundred Days Ahead

[Shelwien]

> 16 facts about the algorithm.

Cool, finally we have some info - somehow Matt didn't have any.

> it's [ppmd] the least efficient memory user in the submission code.

Sure, as ppmd requires ~18N memory.

There multiple ways to save memory in ppmd.

1. PPM_CONTEXT removal.

Afair Shkarin did this in ppms - ppmd has separate
"context" structures, which hold pointers to actual symbol tables.
Once upon a time, it made some sense as a speed optimization.

And now we can merge context structures with symbol tables, and
thus save 4 bytes per context.

Also, NumStats, Flags, SummFreq fields are not very efficient
either - NumStats can be removed by using separate memory pools per NumStats value,
Flags are not very useful in ppmd in any case, and SummFreq is 16-bit, which could be reduced
(maybe merged with some flags).

2. Dynamic context reconstruction.

Like in https://encode.su/threads/541-Simple...xt-mixing-demo
But its also possible to cache frequently used contexts.

3. Stats compression

Ppmd symbol tables are stored sequentially, so we can apply some compression there.
Maybe convert symbol codes and suffix pointers into deltas with variable-length codes.

4. BWT-based data structures

Its actually possible to compute BWT incrementally, by shifting input data around.
Obviously its slow, but likely faster than swapping, and only needs 5N memory.

Though in this case, its easier to drop the PPM idea, and just use BWT data
to dynamically compute the stats for prediction, by scanning BWT symbols
around current position and passing them to a postcoder model.

> So if I had a couple more months, ppmd would be either eliminated completely,
> or made more memory efficient.

Eliminating it could be nice too - I still don't understand why it improves
the paq model so much. But somehow it seems unlikely.

> For example, RestoreModelRare() leaves about half of allocated memory unused.
> This happens thrice.

Actually its controlled by this code:

  // free up 25% of memory

  do {

    PrepareTextArea();

    cutOff( MaxContext[0], 0, _MaxOrder ); // MaxContext is a tree root here, order0

    ExpandTextArea();

  } while( GetUsedMemory()>3*(SubAllocatorSize>>2) ); 

3*(N>>2) = 3*N/4 = 0.75*N - its an arbitrary value,
maybe it can be tweaked to improve overall results,
like run it 2 times instead of 3.

Another solution is completely resetting the model, then
updating the model with 90% (or whatever you want) of already decoded data.
As a bonus, stats also would be more precise like this.

[Alexander Rhatushnyak]

An improved version is here. 7 hours 41 minute instead of 8:10, and 3.4% improvement instead of 3.0%

[Shelwien]

Can you write some description for the new version, like what Knoll posted before?
Its interesting to know whether my previous post here helped, etc.

[Matt Mahoney]

Verified on my Dell E6510 in 64 bit Linux.

[byronknoll]

An improved version is here. 7 hours 41 minute instead of 8:10, and 3.4% improvement instead of 3.0%

Nice improvement! Any plans to release the source code? I bet there are a lot of components and implementation details that would help improve other compression programs.

[Alexander Rhatushnyak]

> whether my previous post here helped

Not yet. Nothing new with ppmd memory usage.

> Any plans to release the source code?

No. Maybe next year, and more likely only some components.

[Alexander Rhatushnyak]

Here is a dictionary that seemingly works better for enwik8 (and maybe enwik9)
than the dictionary from paq8hp12.
The latter is a little bit damaged: you can find a long sequence of 0's in the middle of it, right after 'yearwa@'.
And as far as I can see, cmix uses a bit-exact copy of the damaged dictionary from paq8hp12.

[byronknoll]

Thanks Alex. I tried using the new dictionary with cmix on enwik8:

damaged dictionary: 15291981
new dictionary: 15297535

Unfortunately the results are a bit worse. Perhaps cmix has some over-fitting with the damaged dictionary...

[Alexander Rhatushnyak]

Maybe it's also because in phda
1. There's an enwik-specific pre-processing,
2. Dictionary is compressed after the main data, it's not used for pre-training, and
2a. the biggest part of dictionary (40960/44880 words) is in the barely-sorted state, as in to_train_models.dic from paq8hp12

[byronknoll]

Any updates on the prize? http://prize.hutter1.net/ hasn't been updated.

[Alexander Rhatushnyak]

3.88% improvement was confirmed on Oct.1,
and there'll be a ~4.2 % next week.