Skip to content

gamut-deflate: with_optimal_parse_limit's real cost is memory, unbounded in the input, and the doc names only time #631

Description

@justin13888

DeflateEncoder::with_optimal_parse_limit documents its cost as time. The cost that scales with
the limit is memory, and once a caller raises the limit past the input length there is no
bound on it at all.

The mechanism

lz77::parse_optimal chunks the input into spans of max(limit, WINDOW) and hands each to
optimal_span, which runs parse_dp once per refinement pass. parse_dp allocates three
span-length vectors (crates/gamut-deflate/src/lz77.rs):

let mut f = vec![u64::MAX; n + 1];
let mut blen = vec![0u16; n + 1];
let mut bdist = vec![0u16; n + 1];

That is 12 bytes for every byte of span, live for the whole pass. The widest chunk
parse_optimal hands over is min(max(limit, WINDOW), input.len()), so once the limit exceeds the
input the limit stops bounding anything: a caller who sets usize::MAX has made one encode's peak
resident set grow linearly and without bound in the input.

Measured

Through gamut-png at Level::Best, one encode per process, peak resident set from
/usr/bin/time -v, square RGB photograph, refinement budget 1, one filter:

image filtered stream 1 MiB (default) 8 MiB 16 MiB usize::MAX
1024x1024 3 146 752 21.9 MiB 46.7 MiB 46.6 MiB 46.5 MiB
2048x2048 12 584 960 56.0 MiB 127.2 MiB 177.4 MiB 177.2 MiB
4096x4096 50 335 744 177.9 MiB 219.0 MiB 312.6 MiB 701.8 MiB

Against the 1 MiB column the extra resident set per extra byte of span is 12.3, 11.0 and 11.1
bytes across the three rows: 12 allocated, slightly less resident because blen and bdist are
zero-initialised and pages they never write are never faulted in. The formula, measured.

Wall time over the same twelve runs moved by less than 2% and not monotonically
(8.41 / 8.37 / 8.37 / 8.47 s; 34.65 / 34.08 / 33.92 / 33.95 s; 133.9 / 135.4 / 134.3 / 132.7 s):
the parse's work is linear in the input whatever the span, so time is not what the limit buys or
costs at a fixed refinement budget.

What the docs say now

  • with_optimal_parse_limit: "Raising the limit lets one cost model span more data — usually a
    small ratio win on homogeneous input — at a disproportionate time cost; lowering it does the
    reverse." No mention of memory.
  • DEFAULT_OPTIMAL_PARSE_LIMIT: "chosen so a single span's dynamic program stays cheap in both
    time and working set" — the right fact, stated only about the default, where a caller who is
    about to change it will not look.

Asked for

Name the memory cost at the setter, in the units a caller can compute with (bytes of working set
per byte of span), and say plainly that the limit is the only bound on it. gamut-png's own
PngEncoder::with_optimal_parse_limit carries that wording as of #625 and its top rung takes a
finite 8 MiB span for this reason; the crate where the allocation happens should not be the one
that omits it.

Found while reviewing the effort dial delivered in #625.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions