Bug 703246 - Inefficient implementation of endbfchar
Summary: Inefficient implementation of endbfchar
Status: RESOLVED FIXED
Alias: None
Product: Ghostscript
Classification: Unclassified
Component: PS Interpreter (show other bugs)
Version: master
Hardware: PC Linux
: P4 normal
Assignee: Peter Cherepanov
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2020-12-10 04:02 UTC by Peter Cherepanov
Modified: 2021-03-24 04:13 UTC (History)
1 user (show)

See Also:
Customer:
Word Size: ---

Attachments
Patch (706 bytes, patch)
2020-12-10 04:09 UTC, Peter Cherepanov 		Details | Diff
Patch for endbfchar and endbfrange (2.35 KB, patch)
2020-12-10 06:14 UTC, Peter Cherepanov 		Details | Diff
Show Obsolete (1) Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Peter Cherepanov 2020-12-10 04:02:09 UTC 
This is bug report for a new sample file, attached to a unrelated bug 702381 as the comment #8.

Ghostscript takes extremely long time to parse a CMap with 38917 entries in a single beginbfchar ... endbfchar range. This inefficiency is caused by repeated use of --roll-- on the whole data set, which results in quadratic complexity.

A simple rewrite of beginbfchar restores linear complexity and reduces parsing time to 1 sec. The function endbfrange has the same problem, but it is not changed, since it is not used by the sample file.
Comment 3 Ray Johnston 2021-03-24 04:13:02 UTC 
Fixed in commit fd919a2ed. Thanks, Peter.