Support larger (and maybe finer grained) window sizes

[benrg]

LZMA supports sliding window sizes up to (I think) 1.5 GiB. I've found window sizes of hundreds of MiB to be useful. It can have a large effect on the compression ratio for some kinds of data. LZMA also supports non-power-of-2 window sizes, which can be useful when you have enough RAM for a 50% larger window but not for a 100% larger window.

Of course huge windows should never be the default at any compression level, but could they be accepted if set explicitly in ZSTD_parameters?

If you don't want to use 4 header bytes for the window size (as LZMA does), you could use a tiny floating-point format, e.g. dict_size = (8 + (packed_dict_size & 7)) << (8 + (packed_dict_size >> 3)). I don't know whether that's the biggest technical obstacle to non-power-of-2 window sizes, though.

[Cyan4973]

There are several obstacles to overcome.

• Compression Format limitation : if the current format doesn't evolve, maximum possible distance will be 2 GB
• Implementation limitation : with current distance decoder, the 32-bits version is limited to 32 MB, the 64-bits version can go up to 256 MB. Larger distances will require a rewrite of this part, and likely be slower.
• Frame Format limitation : this is the part your are mentioning and proposing to change. Indeed, a change will be required to support such distances.
• Ability to search such large distances requires huge amount of memory
  • Another possibility would be to write a specific search method for very large distances

Good news :

• non-power-of-2 is not an obstacle
  • but API would need to be modified, since currently advanced parameters only allow power of 2

Take-away :
None of these limitations is a blocker.
That being said, there is a significant amount of work required to get there.
So over the longer term, yes, but currently, it's hard to make it a priority.

[Bulat-Ziganshin]

I suggest to make format more flexible, supporting at least distances up to 4GB (btw, lzma supports them too). It was one of my mistakes in Tornado development - i limited dist to 1 GB available in first implementation, so support of larger distances required to add another format.

You don't need to support compression or even extraction with large distances now, just leave the room in the format. I also vote for finer-grained values, for the same reason.

The same applies to other compression parameters, stored in the format. Also, i suggest to store values rather than logarithms in ZSTD_parameters, and prefer memory sizes over counts (for example hashSize=4MB rather than hashSize=1M elements). That needs a bit more checks but will give you more flexibility for the future development, and memory sizes tell me, the library user, more than counts of some internal library datatypes.

[Cyan4973]

Thanks for your hindsight @Bulat-Ziganshin .

Actually, it's currently difficult to cleanly support very large window sizes, due to some subtle limitation. Let me explain the first one :

Offset are decoded through an offcode table which can have 1 in 4 states :

• Regular (FSE compressed)
• RLE (single value repeated N times)
• Repeated (re-use previous FSE statistics)
• Default (pre-defined table)

The last 3 modes have the important benefit of being free of "statistics header", hence almost no startup cost, which can be fairly important when the number of offsets to encode is small (small blocks, or simply very few long matches).

The problem is the "default" table : since it's predefined, it's difficult to select a static table which can adapt any window size. A choice had to be made. The pre-defined offcode table is unable to encode offsets beyond 256 MB.

There are 2 solutions to this problem :

• In presence of offsets > 256 MB, never use "default" offset table. Since "repeat" and "rle" are situational, it basically translates into "use regular almost all the time", with its associated header cost, even when detrimental.
• "default" offset table is not static. It dynamically adapts to maximum offset code.
  • Pros : no window size limitation, could be better tuned for each maximum
  • Cons : more complex. How to build such a table ? Rules needs to be simple, as complexity can be a killer from a specification perspective.

It's a small issue, but one that must be solved to make large window sizes (>256 MB) possible.

[Cyan4973]

Completed in v0.7.x .
Now, the format allows basically any value, and there is no limit to the window size,
although the decoder is free to decide which maximum window size it wants to support.