Bug 695906 - infill very slow in path made by strokepath
Summary: infill very slow in path made by strokepath
Status: RESOLVED FIXED
Alias: None
Product: Ghostscript
Classification: Unclassified
Component: Vectors (show other bugs)
Version: 8.71
Hardware: Macintosh MacOS X
: P4 enhancement
Assignee: Robin Watts
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-04-06 15:48 UTC by Julian D. A. Wiseman
Modified: 2017-10-16 06:58 UTC (History)
1 user (show)

See Also:
Customer:
Word Size: ---


Attachments
PostScript code that runs quickly under Distiller and slowly under Ghostscript. (1.11 KB, application/postscript)
2015-04-06 15:48 UTC, Julian D. A. Wiseman
Details
Output running in Distiller XI 11.0.10, 03/12/2014 (59.74 KB, application/pdf)
2015-04-06 15:50 UTC, Julian D. A. Wiseman
Details
Output running in ps2pdf / GS 8.71 (26.45 KB, application/pdf)
2015-04-06 15:50 UTC, Julian D. A. Wiseman
Details
PostScript code that runs quickly under Distiller and slowly under Ghostscript, v2. (1.15 KB, application/postscript)
2015-04-07 01:23 UTC, Julian D. A. Wiseman
Details
Output running in ps2pdf / GS 8.71 from v2 of the example code (39.09 KB, application/x-download)
2015-04-07 01:24 UTC, Julian D. A. Wiseman
Details
Output running in Distiller XI 11.0.10, 03/12/2014 from v2 of the example code (71.00 KB, application/x-download)
2015-04-07 01:25 UTC, Julian D. A. Wiseman
Details
CSV output from Very Sleepy (43.46 KB, text/plain)
2015-04-07 04:31 UTC, Ken Sharp
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Julian D. A. Wiseman 2015-04-06 15:48:31 UTC
Created attachment 11557 [details]
PostScript code that runs quickly under Distiller and slowly under Ghostscript.

PostScript at
http://www.jdawiseman.com/papers/bugs/20150406_infill_slow.ps
(also attached). 

Run using distiller XI take very little time. Once, 17 milliseconds. Once, ≤0.5 ms; once 16 ms. Quite fast.
http://www.jdawiseman.com/papers/bugs/20150406_infill_slow_Distiller_11_0_10.pdf

Run using ps2pdf calling Ghostscript 8.71, times around 7000ms. So multiple hundreds to thousands of times slower. 
http://www.jdawiseman.com/papers/bugs/20150406_infill_slow_Ghostscript_8_71.pdf

If one replaces in the Postscript ‘fill’ with ‘stroke’, it also clear that GS’s path is messier. Might this be cause the slowness?
Comment 1 Julian D. A. Wiseman 2015-04-06 15:50:11 UTC
Created attachment 11558 [details]
Output running in Distiller XI 11.0.10, 03/12/2014
Comment 2 Julian D. A. Wiseman 2015-04-06 15:50:42 UTC
Created attachment 11559 [details]
Output running in ps2pdf / GS 8.71
Comment 3 Ray Johnston 2015-04-06 16:11:23 UTC
Even though the Adobe PDF file prints a Start/End time 16 msec apart, the
actual time measured by my stopwatch was about 11 seconds.

In any case, this is a bogus hand constructed and we aren't going to pay
any attention to it.

BTW, we've released 9.16 and 8.71 is 5+ years out of date and would never be
supported anyway.

Please don't waste your time and ours.

If you have a real file that performs badly under the current release, we
_may_ look at it, but for free users, probably not. At least we won't close
the bug right away.
Comment 4 Julian D. A. Wiseman 2015-04-07 01:23:38 UTC
Created attachment 11560 [details]
PostScript code that runs quickly under Distiller and slowly under Ghostscript, v2.
Comment 5 Julian D. A. Wiseman 2015-04-07 01:23:51 UTC
It isn’t meant as bogus in any way. The problem was discovered in the wild, and simplified for presentation here. 

I have written, maintain, and use a Postscript program of about 12k lines. 
http://www.jdawiseman.com/papers/placemat/placemat.html
http://www.jdawiseman.com/papers/placemat/placemat.ps

A few months ago ps2pdf.com, an online Ghostscript, stopped working. I presumed, wrongly, that it was the fault of ps2pdf.com. No, I had changed a default parameter such that one routine (LineWidthThatCoversPath), was being used, having previously not been much used. That was causing Ghostscript but not Distiller to run slowly.

A recent report to me, and discussion, can be found at 
http://www.theportforum.com/viewtopic.php?t=175&start=913 

So the problem really was discovered in the wild. The submitted code is a simplification, as I thought you wouldn’t care for 12k lines.

You have disagreed about the times. I’ve slightly improved the example code
http://www.jdawiseman.com/papers/bugs/20150407_infill_slow.ps
putting the upper size of the nested loops in LoopMax, which has been set at 500 rather than the earlier 100, to hide better any fixed costs that the software might incur before executing the infills. This is about the effective size used in LineWidthThatCoversPath. 

On my machine clock Ghostscript needed about 4⅓ minutes, approximately agreeing with the reported usertimes. 
http://www.jdawiseman.com/papers/bugs/20150407_infill_slow_Ghostscript_8_71.pdf

On Distiller it seemed to take about 2 seconds, though the usertimes reported only 133ms. 
http://www.jdawiseman.com/papers/bugs/20150407_infill_slow_Distiller_11_0_10.pdf

This is a big difference. 

The complaint about the version number is fair, but I have not found a more recent version from a reputable source that is compiled for the Mac. So this might be incompetent, but is not bogus. 

Anyway, I apologise for failing to realise that bugs submitted by ‘free users’ are unwelcome.
Comment 6 Julian D. A. Wiseman 2015-04-07 01:24:49 UTC
Created attachment 11561 [details]
Output running in ps2pdf / GS 8.71 from v2 of the example code
Comment 7 Julian D. A. Wiseman 2015-04-07 01:25:14 UTC
Created attachment 11562 [details]
Output running in Distiller XI 11.0.10, 03/12/2014 from v2 of the example code
Comment 8 Ken Sharp 2015-04-07 02:07:52 UTC
A quick check by simply commenting out the 'infill' operator shows that this proceeds very quickly.

It is therefore not the strokepath or loop which is slow. Instead it must be the the *extremely* rarely used infill operator which is slow, as indicated by the subject.

Note that reducing the resolution (the default for pdfwrite is 720 dpi) reduces the time taken. This suggests that the problem is due to scan-conversion, especially of large/complex paths (the result of strokepath is always complex), which I believe we already know about, and there is some work already done in this area. Potentially completing this work would improve the situation here.

Running very sleepy on this, the majority of the time is spent in find_contacting_segments(), gx_path_merge_contacting_contours() and scan_contour(). The infill operator takes 91.75% of the time (including its children), the majority of that time is spent in fill_with_rule() which is fast when called from zfill() and slow when called from in_test() (from infill)

If anyone wants the results I have them saved as a csv and a sleepy file.

Since the file does complete correctly, albeit slowly, I'm changing this to an enhancement. I'm tempted to mark it as a duplicate of the scan-conversion work but I can't find a bug number for that. 

[later]

Hmm looks like its bug #691984, it might be helpful if robin was to try his prototype code out on this file. I'm not certain it would help but its worth trying, it does look like its something related to scan conversion.


As regards a Mac version of Ghostscript, its pretty easy to build it from source, it must be because I managed it :-)
Comment 9 Julian D. A. Wiseman 2015-04-07 04:21:49 UTC
Thank you for using the debugger to peer inside and locate the slowness. But please do attach the debugging files, just so that everything is kept together in one place.

The slowness causes the likes of ps2pdf.com to time out and hence return no output, so to me it really feels like a bug. One could argue that it is ps2pdf.com’s bug, but for the problem seen in the wild (as reported to me by my OP) waiting on a 17 minute distillation time (versus 10 seconds in Distiller) is a big ask of a web browser. However, I agree that infill is “*extremely* rarely used”, and I guess only by PostScript programmers and not by PostScript as an output from another program. So even as a bug it might not be of the highest priority. To conclude, I defer to the expertise of locals in labelling it an enhancement. 

You mention “reducing the resolution”: is that something that can be done within PostScript? (So the code would detect whether or not using Distiller, and if not temporarily change the resolution.)

Finally, perhaps I could build Ghostscript from source myself, but as it would probably take me a day to do, and as I have Distiller, I’ll label it an ‘enhancement’ to tackle later.

Thank you again. 

Oh, and why do I want this?
https://groups.google.com/forum/#!topic/comp.lang.postscript/86b7Sg8v7B0
Comment 10 Ken Sharp 2015-04-07 04:31:48 UTC
Created attachment 11564 [details]
CSV output from Very Sleepy

Well here's the CSV output from Very Sleepy, I didn't bother with the sleepy file as it can only be opened by someone using Very Sleepy.

Agreed its surprisingly slow, but it does complete, and the operator is not common. It would be nice to see it improved, and Robin's scan conversion  might help.

You can reduce the resolution in PostScript, the setpagedevice operator uses the (array) value associated with the HWResolution key in the page device dictionary. Although I used the command line to set it, it should be possible to do some programatically. Don't expect massive improvements, for me reducing the resolution to 72 dpi merely doubled the performance. Handling each glyph separately instead of as one string might also improve things by reducing the complexity of the path, I didn't try that.
Comment 11 Julian D. A. Wiseman 2015-04-07 04:54:56 UTC
> You can reduce the resolution in PostScript, the setpagedevice operator uses the (array) value associated with the HWResolution key in the page device dictionary.

Thank you for the pointer (PLRM3 p414 table 6.4), but setpagedevice erases the current page, which doesn’t work for me. And for only a small improvement too.
Comment 12 Ken Sharp 2015-04-07 05:19:25 UTC
(In reply to Julian D. A. Wiseman from comment #11)

> Thank you for the pointer (PLRM3 p414 table 6.4), but setpagedevice erases
> the current page, which doesn’t work for me. And for only a small
> improvement too.

You have to put it at the start of the file, you absolutely cannot change resolution during the course of a PostScript program, at least not without flushing the job to date. Although the scan conversion at a lower resolution is simpler, its not *that* much simpler....
Comment 13 Marcos H. Woehrmann 2015-11-29 18:37:33 UTC
This issue hasn't been resolved as of 237f98e6abb42407466240585b897b5190b68053.  Using Ghostscript to convert the input file to PostScript still takes 7000 ms vs < 20 ms with Acrobat Distiller or Apple Preview.

On the presumption that this issue is related to Bug 691984 I'm assigning it to Robin.
Comment 14 Chris Liddell (chrisl) 2017-10-16 06:58:15 UTC
Works fine with the new scan converter.