Bug 421057 - Infinite loop in garbage collection
Summary: Infinite loop in garbage collection
Status: NOTIFIED FIXED
Alias: None
Product: Ghostscript
Classification: Unclassified
Component: PS Interpreter (show other bugs)
Version: master
Hardware: All All
: P2 normal
Assignee: Ray Johnston
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2001-05-03 08:12 UTC by Alex Cherepanov
Modified: 2007-12-13 12:55 UTC (History)
0 users

See Also:
Customer:
Word Size: ---


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Alex Cherepanov 2001-05-03 08:12:19 UTC
Originally reported by: alexcher@users.sourceforge.net
GS 6.50, 6.60, 7.01 fall into the infinite loop in
garbage collection executing the attached file.
With -dNOGC GS ends normally.
Reported by Manfred Goetzie
Comment 1 Raph Levien 2001-05-10 09:55:57 UTC
Comment originally by raph@users.sourceforge.net
Logged In: YES 
user_id=379

The file is available here:

http://www.ghostscript.com/pipermail/bug-gs/2001-May/000383.html

An earlier attempt to attach this failed, because of a 250K
file size limit at SourceForge.
Comment 2 Jack Moffitt 2001-10-19 14:11:46 UTC
Comment originally by jackiem@users.sourceforge.net
Logged In: YES 
user_id=206537

Is this file available somewhere else?  That file is totally
corrupt now, as mailman has seemingly put <i>'s all over the
place and translated the whole thing.  inserting mailto
links here and there, etc.  I tried to do search replaces
but was still not able to get everything.
Comment 3 Ray Johnston 2002-04-09 22:56:46 UTC
Comment originally by rayjj@users.sourceforge.net
Logged In: YES 
user_id=11206

I was able to capture the file from the pipermail archives by
opening the page with my browser (netscape) then selecting
the file from the %!PS through the %%EOF, then use "copy"
and "paste" into an edit window. The file runs.

My timings are that with HEAD rev. with -dNOGC, the file runs
in 35 seconds, but with the default (GC enabled) it takes 235 seconds.
Characters are displayed with noticeable delay between each character
with GC on.

I don't think the problem is really an infinite loop, but rather just an
over aggressive 'vmreclaim' usage in the file. It could be that all that
is needed is to ignore the request for GC sometimes (for example
is there really hasn't been enough allocation since the last GC).
Comment 4 Ray Johnston 2002-04-16 14:39:43 UTC
Comment originally by rayjj@users.sourceforge.net
Logged In: YES 
user_id=11206

I tried the 7.20 build that had DEBUG=0 and the difference between
-dNOGC and with normal GC was not as dramatic, but still the timing
was:

	GC enabled:	81 seconds

	-dNOGC:		30 seconds

I added some timing to the ireclaim.c module in the function ireclaim
to time the GC runs.

With GC enabled, the GC was performed 1405 times, with an average
elapsed time of 0.142 seconds and a max time of 0.219 seconds.
The total elapsed time was 233 seconds, 200.6 of which was spent
doing GC.

I also added a message to the /vmreclaim definition in gs_lev2.ps
and it was only requested by PostScript 33 times.

I then investigated (with the debugger) why the GC was being run
and discovered that the default 'limit' was being set to 250000
(DEFAULT_VM_THRESHOLD_LARGE in zvmem2.c) and that this file really
needed a threshold of > 600000 in order to eliminate the excess
GC executions.

The simple change to fix this is to bump the DEFAULT_VM_THRESHOLD
value up to prevent excessive GC.

This is a tuned parameter that may need to be adjusted in the future
if -dNOGC runs significantly faster than the normal case

*** zvmem2.c    21 Feb 2002 22:24:54 -0000      1.5
--- zvmem2.c    16 Apr 2002 20:57:46 -0000
***************
*** 25,32 ****
  #include "store.h"

  /* Garbage collector control parameters. */
! #define DEFAULT_VM_THRESHOLD_SMALL 20000
! #define DEFAULT_VM_THRESHOLD_LARGE 250000
  #define MIN_VM_THRESHOLD 1
  #define MAX_VM_THRESHOLD max_long

--- 25,32 ----
  #include "store.h"

  /* Garbage collector control parameters. */
! #define DEFAULT_VM_THRESHOLD_SMALL 100000
! #define DEFAULT_VM_THRESHOLD_LARGE 1000000
  #define MIN_VM_THRESHOLD 1
  #define MAX_VM_THRESHOLD max_long

(changing the thresholds to something reasonable).

These 'tuning' parameters have been in place a long time, and have
been overdue for reevaluation for some time.

There are other areas we might 'improve' by preventing overly
aggression GC runs such as only running the GC if the amount
allocated since the last GC is sufficient to warrant the effort,
but for now, this fix should be adequate, and have few enough
side effects.

I am cc'ing gs-code-review to give reviewers a chance to comment on
this change.