Revert "Clean up insert_match() in deflate_medium" #1938

Dead2 · 2025-07-15T20:56:00Z

This reverts commits 56d3d98 and 322753f after reports of performance regressions, seemingly mostly affecting highly compressible data with a lot of very long matches (257+ bytes).

Fixes #1935

Summary by CodeRabbit

Bug Fixes
- Improved logic for string insertion during compression to ensure more accurate handling based on match length and lookahead, potentially enhancing compression efficiency and reliability.
Documentation
- Updated a comment to clarify the usage scope of the max_insert_length parameter for different compression levels.

This reverts commit 56d3d98.

…flate_medium()." This reverts commit 322753f.

coderabbitai · 2025-07-15T20:56:07Z

Walkthrough

The changes update a comment in deflate.h to correct the described usage range of max_insert_length and significantly revise the insert_match function in deflate_medium.c. The new logic introduces more selective and conditional string insertions into the hash table based on match length and lookahead, refining the compression process.

Changes

File(s)	Change Summary
deflate.h	Updated comment: `max_insert_length` now described as used for compression levels ≤ 6 (was ≤ 3).
deflate_medium.c	Refined `insert_match` logic: conditional insertion based on match length and lookahead, reordered increments/decrements, and added fallback quick insertion. No interface changes.

Sequence Diagram(s)

sequenceDiagram
    participant Compressor
    participant HashTable

    Compressor->>Compressor: Detect match (match_length, lookahead)
    alt match_length < WANT_MIN_MATCH
        Compressor->>Compressor: Increment strstart, decrement match_length
    else match_length >= WANT_MIN_MATCH
        alt match_length ≤ 16 * max_insert_length and lookahead ≥ WANT_MIN_MATCH
            loop For each match_length
                Compressor->>HashTable: Insert string
                Compressor->>Compressor: Increment strstart, decrement match_length
            end
        else
            Compressor->>Compressor: Advance strstart by match_length, reset match_length
            alt strstart ≥ STD_MIN_MATCH - 2
                Compressor->>HashTable: quick_insert_string at offset
            end
        end
    end

📜 Recent review details

Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between 58aab8d and 3ecf91c.

📒 Files selected for processing (2)

deflate.h (1 hunks)
deflate_medium.c (2 hunks)

🧰 Additional context used

🧠 Learnings (3)

📓 Common learnings

Learnt from: mtl1979
PR: zlib-ng/zlib-ng#1925
File: arch/loongarch/lasxintrin_ext.h:38-65
Timestamp: 2025-07-04T16:59:44.725Z
Learning: In zlib-ng, the policy for supporting old compilers is to maintain compatibility for up to two years after GitHub removes support for them in CI, or when there is no long-time contributor left testing for the architecture if the architecture was not supported by GitHub Actions at all.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:127-130
Timestamp: 2024-09-25T16:24:41.405Z
Learning: In the `inflate_state` structure, fields like `lenbits`, `lencode`, `distcode`, and `distbits` may be moved within the structure for optimization purposes; they are not necessarily new additions.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:127-130
Timestamp: 2024-10-08T19:37:14.998Z
Learning: In the `inflate_state` structure, fields like `lenbits`, `lencode`, `distcode`, and `distbits` may be moved within the structure for optimization purposes; they are not necessarily new additions.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:81-83
Timestamp: 2024-09-25T16:25:56.686Z
Learning: When `INFLATE_STRICT` is not defined, the variable `state->dmax` is completely removed from the code.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:81-83
Timestamp: 2024-10-08T19:37:14.998Z
Learning: When `INFLATE_STRICT` is not defined, the variable `state->dmax` is completely removed from the code.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:108-108
Timestamp: 2024-10-12T13:02:26.066Z
Learning: The variable `state->was` in the `inflate_state` structure is used in the `inflateMark()` function in `inflate.c`.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:108-108
Timestamp: 2024-10-08T10:58:06.857Z
Learning: The variable `state->was` in the `inflate_state` structure is used in the `inflateMark()` function in `inflate.c`.

Learnt from: KungFuJesus
PR: zlib-ng/zlib-ng#1872
File: arch/x86/chorba_sse2.c:0-0
Timestamp: 2025-02-18T02:53:23.621Z
Learning: In zlib-ng, when macro names and parameters are self-explanatory and scalar versions of the code provide context, additional documentation for the macros may not be necessary.

Learnt from: pps83
PR: zlib-ng/zlib-ng#0
File: :0-0
Timestamp: 2025-01-13T18:28:11.751Z
Learning: In zlib-ng, removing preprocessor guards (like HAVE_*) should be described as removing unused conditional compilation checks rather than removing functionality, as the underlying implementation often remains intact.

Learnt from: phprus
PR: zlib-ng/zlib-ng#1925
File: arch/loongarch/slide_hash_lsx.c:64-64
Timestamp: 2025-06-18T19:28:32.987Z
Learning: In zlib-ng's slide_hash functions, when calling slide_hash_chain(), the fourth parameter should be the window size (wsize) representing the number of entries in the prev table, not s->w_size directly. The local variable wsize is typically cast to the appropriate type (uint16_t) from s->w_size for this purpose.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1830
File: arch/generic/generic_functions.h:0-0
Timestamp: 2024-12-21T00:45:20.764Z
Learning: User Dead2 prefers English replies for code reviews, not Spanish.

deflate.h (10)

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:81-83
Timestamp: 2024-09-25T16:25:56.686Z
Learning: When `INFLATE_STRICT` is not defined, the variable `state->dmax` is completely removed from the code.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:81-83
Timestamp: 2024-10-08T19:37:14.998Z
Learning: When `INFLATE_STRICT` is not defined, the variable `state->dmax` is completely removed from the code.

Learnt from: KungFuJesus
PR: zlib-ng/zlib-ng#1872
File: arch/x86/chorba_sse2.c:0-0
Timestamp: 2025-02-18T02:53:23.621Z
Learning: In zlib-ng, when macro names and parameters are self-explanatory and scalar versions of the code provide context, additional documentation for the macros may not be necessary.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:127-130
Timestamp: 2024-09-25T16:24:41.405Z
Learning: In the `inflate_state` structure, fields like `lenbits`, `lencode`, `distcode`, and `distbits` may be moved within the structure for optimization purposes; they are not necessarily new additions.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:127-130
Timestamp: 2024-10-08T19:37:14.998Z
Learning: In the `inflate_state` structure, fields like `lenbits`, `lencode`, `distcode`, and `distbits` may be moved within the structure for optimization purposes; they are not necessarily new additions.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:108-108
Timestamp: 2024-10-12T13:02:26.066Z
Learning: The variable `state->was` in the `inflate_state` structure is used in the `inflateMark()` function in `inflate.c`.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:108-108
Timestamp: 2024-10-08T10:58:06.857Z
Learning: The variable `state->was` in the `inflate_state` structure is used in the `inflateMark()` function in `inflate.c`.

Learnt from: pps83
PR: zlib-ng/zlib-ng#0
File: :0-0
Timestamp: 2025-01-13T18:28:11.751Z
Learning: In zlib-ng, removing preprocessor guards (like HAVE_*) should be described as removing unused conditional compilation checks rather than removing functionality, as the underlying implementation often remains intact.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:84-86
Timestamp: 2024-10-08T19:37:14.998Z
Learning: When `INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR` is not defined, `state->sane` is completely removed from the codebase and does not need to be initialized.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:84-86
Timestamp: 2024-09-25T16:26:23.643Z
Learning: When `INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR` is not defined, `state->sane` is completely removed from the codebase and does not need to be initialized.

deflate_medium.c (10)

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:81-83
Timestamp: 2024-09-25T16:25:56.686Z
Learning: When `INFLATE_STRICT` is not defined, the variable `state->dmax` is completely removed from the code.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.c:81-83
Timestamp: 2024-10-08T19:37:14.998Z
Learning: When `INFLATE_STRICT` is not defined, the variable `state->dmax` is completely removed from the code.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:127-130
Timestamp: 2024-09-25T16:24:41.405Z
Learning: In the `inflate_state` structure, fields like `lenbits`, `lencode`, `distcode`, and `distbits` may be moved within the structure for optimization purposes; they are not necessarily new additions.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:127-130
Timestamp: 2024-10-08T19:37:14.998Z
Learning: In the `inflate_state` structure, fields like `lenbits`, `lencode`, `distcode`, and `distbits` may be moved within the structure for optimization purposes; they are not necessarily new additions.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:108-108
Timestamp: 2024-10-08T10:58:06.857Z
Learning: The variable `state->was` in the `inflate_state` structure is used in the `inflateMark()` function in `inflate.c`.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1797
File: inflate.h:108-108
Timestamp: 2024-10-12T13:02:26.066Z
Learning: The variable `state->was` in the `inflate_state` structure is used in the `inflateMark()` function in `inflate.c`.

Learnt from: phprus
PR: zlib-ng/zlib-ng#1925
File: arch/loongarch/slide_hash_lsx.c:64-64
Timestamp: 2025-06-18T19:28:32.987Z
Learning: In zlib-ng's slide_hash functions, when calling slide_hash_chain(), the fourth parameter should be the window size (wsize) representing the number of entries in the prev table, not s->w_size directly. The local variable wsize is typically cast to the appropriate type (uint16_t) from s->w_size for this purpose.

Learnt from: KungFuJesus
PR: zlib-ng/zlib-ng#1872
File: arch/x86/chorba_sse2.c:0-0
Timestamp: 2025-02-18T02:53:23.621Z
Learning: In zlib-ng, when macro names and parameters are self-explanatory and scalar versions of the code provide context, additional documentation for the macros may not be necessary.

Learnt from: pps83
PR: zlib-ng/zlib-ng#0
File: :0-0
Timestamp: 2025-01-13T18:28:11.751Z
Learning: In zlib-ng, removing preprocessor guards (like HAVE_*) should be described as removing unused conditional compilation checks rather than removing functionality, as the underlying implementation often remains intact.

Learnt from: Dead2
PR: zlib-ng/zlib-ng#1830
File: arch/generic/generic_functions.h:39-53
Timestamp: 2024-12-20T23:35:59.830Z
Learning: The `longest_match_unaligned_*` functions are templated using the LONGEST_MATCH macro in match_tpl.h, so their implementations are generated rather than explicitly defined.

🔇 Additional comments (3)

deflate.h (1)

230-230: LGTM! Comment accurately reflects the expanded usage scope.

The updated comment correctly documents that max_insert_length is now used for compression levels <= 6 (instead of <= 3), which aligns with the reverted logic in deflate_medium.c.

deflate_medium.c (2)

49-51: Good optimization for the common case.

Adding the LIKELY macro for the short match condition and moving the increment/decrement operations inside makes sense, as matches shorter than WANT_MIN_MATCH are probably the most common case.

66-94: Effective solution for the performance regression.

The reverted logic properly addresses the reported performance issues by:

Limiting string insertions based on max_insert_length threshold (16x multiplier)

Adding a lookahead check to ensure sufficient data for insertions

Using quick_insert_string for minimal hash table updates when skipping full insertion

The comment about ins_h being potentially invalid is helpful for future maintainers

This selective insertion strategy should significantly reduce the performance impact on highly compressible data with long matches (257+ bytes).

✨ Finishing Touches

📝 Generate Docstrings

🧪 Generate unit tests

Create PR with unit tests
Post copyable unit tests in a comment
Commit unit tests in branch revert_insert_match

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

🪧 Tips

Chat

There are 3 ways to chat with CodeRabbit:

Review comments: Directly reply to a review comment made by CodeRabbit. Example:
- I pushed a fix in commit <commit_id>, please review it.
- Explain this complex logic.
- Open a follow-up GitHub issue for this discussion.
Files and specific lines of code (under the "Files changed" tab): Tag @coderabbitai in a new review comment at the desired location with your query. Examples:
- @coderabbitai explain this code block.
- @coderabbitai modularize this function.
PR comments: Tag @coderabbitai in a new PR comment to ask questions about the PR branch. For the best results, please provide a very specific query, as very limited context is provided in this mode. Examples:
- @coderabbitai gather interesting stats about this repository and render them as a table. Additionally, render a pie chart showing the language distribution in the codebase.
- @coderabbitai read src/utils.ts and explain its main purpose.
- @coderabbitai read the files in the src/scheduler package and generate a class diagram using mermaid and a README in the markdown format.
- @coderabbitai help me debug CodeRabbit configuration file.

Support

Need help? Create a ticket on our support page for assistance with any issues or questions.

Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments.

CodeRabbit Commands (Invoked using PR comments)

@coderabbitai pause to pause the reviews on a PR.
@coderabbitai resume to resume the paused reviews.
@coderabbitai review to trigger an incremental review. This is useful when automatic reviews are disabled for the repository.
@coderabbitai full review to do a full review from scratch and review all the files again.
@coderabbitai summary to regenerate the summary of the PR.
@coderabbitai generate docstrings to generate docstrings for this PR.
@coderabbitai generate sequence diagram to generate a sequence diagram of the changes in this PR.
@coderabbitai auto-generate unit tests to generate unit tests for this PR.
@coderabbitai resolve resolve all the CodeRabbit review comments.
@coderabbitai configuration to show the current CodeRabbit configuration for the repository.
@coderabbitai help to get help.

Other keywords and placeholders

Add @coderabbitai ignore anywhere in the PR description to prevent this PR from being reviewed.
Add @coderabbitai summary to generate the high-level summary at a specific location in the PR description.
Add @coderabbitai anywhere in the PR title to generate the title automatically.

CodeRabbit Configuration File (`.coderabbit.yaml`)

You can programmatically configure CodeRabbit by adding a .coderabbit.yaml file to the root of your repository.
Please see the configuration documentation for more information.
If your editor has YAML language server enabled, you can add the path at the top of this file to enable auto-completion and validation: # yaml-language-server: $schema=https://coderabbit.ai/integrations/schema.v2.json

Documentation and Community

Visit our Documentation for detailed information on how to use CodeRabbit.
Join our Discord Community to get help, request features, and share feedback.
Follow us on X/Twitter for updates and announcements.

codecov · 2025-07-15T20:58:08Z

Codecov Report

Attention: Patch coverage is 90.00000% with 2 lines in your changes missing coverage. Please review.

Project coverage is 81.92%. Comparing base (58aab8d) to head (3ecf91c).

Files with missing lines	Patch %	Lines
deflate_medium.c	90.00%	1 Missing and 1 partial ⚠️

Additional details and impacted files

@@             Coverage Diff             @@
##           develop    #1938      +/-   ##
===========================================
+ Coverage    81.87%   81.92%   +0.05%     
===========================================
  Files          162      162              
  Lines        13915    13923       +8     
  Branches      3120     3122       +2     
===========================================
+ Hits         11393    11407      +14     
+ Misses        1561     1522      -39     
- Partials       961      994      +33

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

ericstj · 2025-07-22T19:24:42Z

Thank you for making this fix. Do you have an estimate when the next release will occur with this change?

Dead2 · 2025-07-23T18:50:31Z

Thank you for making this fix. Do you have an estimate when the next release will occur with this change?

Due to the amount of high-impact changes in develop, we are currently in the process of making a 2.3.x release. That has no ETA currently. (If you want to help test that, that would of course be appreciated)

I want to make a 2.2.5 release by backporting the fixes I think are most relevant for the 2.2-branch, and this will of course be included there. Due to the current heatwave and vacation time, I cannot promise a rapid release of that, but I hope to have one out within 2-4 weeks. Maybe less, but don't count on it.

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

Dead2 added 3 commits July 12, 2025 12:48

Revert "Clean up insert_match() in deflate_medium"

fb7dc6c

This reverts commit 56d3d98.

Revert "Inserting strings is not slow any longer, remove bypass in de…

3f92068

…flate_medium()." This reverts commit 322753f.

Update incorrect comment

3ecf91c

Dead2 added the Performance regression label Jul 15, 2025

Dead2 merged commit f7bd199 into develop Jul 21, 2025
375 of 376 checks passed

ericstj mentioned this pull request Jul 28, 2025

Update to zlib-ng 2.2.5 when ready dotnet/runtime#118131

Closed

Dead2 mentioned this pull request Aug 3, 2025

Backport stable release (2.2.5) #1943

Merged

Dead2 deleted the revert_insert_match branch August 23, 2025 17:22

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 13, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

d570241

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev mentioned this pull request Nov 13, 2025

Libz sys upgrade trifectatechfoundation/zlib-rs#423

Merged

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 13, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

e95c193

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

168efc4

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

34a93a3

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

a286a96

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

ecbaedb

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

f46aafb

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

d4e033a

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

8ae2122

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

38e5154

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

b9d5718

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

folkertdev added a commit to trifectatechfoundation/zlib-rs that referenced this pull request Nov 17, 2025

upgrade to libz-sys 1.1.23, using libz-ng 2.2.4

46db403

This release makes some changes to the medium algorithm, see zlib-ng/zlib-ng#1938

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Revert "Clean up insert_match() in deflate_medium" #1938

Revert "Clean up insert_match() in deflate_medium" #1938

Uh oh!

Dead2 commented Jul 15, 2025 •

edited by coderabbitai bot

Loading

Uh oh!

coderabbitai bot commented Jul 15, 2025 •

edited

Loading

Chat

Support

CodeRabbit Commands (Invoked using PR comments)

Other keywords and placeholders

CodeRabbit Configuration File (`.coderabbit.yaml`)

Documentation and Community

Uh oh!

codecov bot commented Jul 15, 2025 •

edited

Loading

Uh oh!

Uh oh!

ericstj commented Jul 22, 2025

Uh oh!

Dead2 commented Jul 23, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Revert "Clean up insert_match() in deflate_medium" #1938

Revert "Clean up insert_match() in deflate_medium" #1938

Uh oh!

Conversation

Dead2 commented Jul 15, 2025 • edited by coderabbitai bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary by CodeRabbit

Uh oh!

coderabbitai bot commented Jul 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Walkthrough

Changes

Sequence Diagram(s)

Chat

Support

CodeRabbit Commands (Invoked using PR comments)

Other keywords and placeholders

CodeRabbit Configuration File (.coderabbit.yaml)

Documentation and Community

Uh oh!

codecov bot commented Jul 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

ericstj commented Jul 22, 2025

Uh oh!

Dead2 commented Jul 23, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Dead2 commented Jul 15, 2025 •

edited by coderabbitai bot

Loading

coderabbitai bot commented Jul 15, 2025 •

edited

Loading

CodeRabbit Configuration File (`.coderabbit.yaml`)

codecov bot commented Jul 15, 2025 •

edited

Loading