RE: partial fix for 687105 setcolorspace optimizationproblem

Igor,


>> The use of a maximum recursion depth is a simple solution to this
>> situation.  
>
>Actually the use of a maximum recursion depth is a simple way 
>to get an exponential time expense.

I agree that this is a disadvantage of using a simple recursion
depth count.  However the special case that you created is far from
typical.  In many situations, a simple and quick to implement solution
is preferable to spending time creating a more complex solution which
is not really needed.  If there is a real need for the more complex
solution then it is always possible to implement it at a latter time.


>If you want my opinion, I believe that such kind of
>programming may be acceptable for a first year student exercise,
>but it is definitely unacceptable in a software.

Personal insults are inappropriate in a professional discussion.


>> It is very easy to create PostScript objects that point back to
>> themselves.  
>
>In my example none of objects points back to itself,
>neither directly nor indirectly.

However you ignored my example which did.  My point is that there are
real world examples of PostScript objects that contain reference loops.
These can be a simple case like my example or the more complex cases of
objects which point to other objects which in turn point back to the
first, etc.

My example object is:  1 array dup dup 0 exch put


>> A possible solution to this problem would be to create an internal copy
>> of the color space object.
>
>Excellent. It allows to apply the strong equality.

Yes.  This should be a part of a full solution to this problem.  It is
not required for my method.  It is necessary for your method.  However
that is moot since there is a need for the internal copy.


>> There are other solutions which are more elegant but they
>> are also more complicated to implement.
>
>Not sure what do you mean saying "more complicated".
>I will explain my algorithm in a pseudocode.

Actually my comment was simply about ways to limit infinite looping
with reference loops.

Your algorithm limits the reference looping by creating a dictionary
with elements which keep track of every object (which can references other
objects) which has been examined.  There is an apparent bug in your
algorithm in that for arrays and dictionaries you recursively call
is_isomorphic for the individual elements before you insert the top
level object into your reference tracking dictionary.  Thus the infinite
recursion loop is still present with my example.  A fix is simply to
move the insertion of the top level object into the reference tracking
dictionary prior to the recursive calls to is_isomorphic.

I could also create pathological cases of objects that would cause
your algorithm to use large amounts of time expanding its reference
tracking dictionary.  Practically I do not think that these cases
represent real world situations.


Dan


-----Original Message-----
From: Igor V. Melichev [mailto:[email protected]]
Sent: Wednesday, June 23, 2004 1:07 AM
To: [email protected]; Gs-Code-Review
Subject: Re: [gs-code-review] partial fix for 687105 setcolorspace
optimizationproblem (xefitra)


Dan,

> The use of a maximum recursion depth is a simple solution to this
> situation.  

Actually the use of a maximum recursion depth is a simple way 
to get an exponential time expense.

/buildlattice                   % <obj> m <lattice>
{
  30 {   
    dup 2 array astore
  } repeat
} bind def

 /x buildlattice      

16 string exch 30 exch 
objectmd5sum       % computes an md5 sum of 2^30 objects.
                              % 

/x buildlattice 16 string exch 28 exch objectmd5sum
/y buildlattice 16 string exch 28 exch objectmd5sum
eq                          % gives a wrong result (true) after 2^29 iterations.

If you want my opinion, I believe that such kind of
programming may be acceptable for a first year student exercise,
but it is definitely unacceptable in a software.
I assume "ware" is something to be sold.

> It is very easy to create PostScript objects that point back to
> themselves.  

In my example none of objects points back to itself,
neither directly nor indirectly.

> A possible solution to this problem would be to create an internal copy
> of the color space object.

Excellent. It allows to apply the strong equality.

> There are other solutions which are more elegant but they
> are also more complicated to implement.

Not sure what do you mean saying "more complicated".
I will explain my algorithm in a pseudocode.

input : any 2 PS objects o1, o2
output : true if they are isomorphic or equal, false otherwise. 
CPU expense : O(n * log(n))
{
 Allocate a temporary dictionary d. Use a reasonable initial size of 100 entries.
 r = is_isomprphic(o1, o2, d);
 Free d;
 return r;
}

bool is_isomprphic(o1, o2, d)
{
 If (o1 == o2) return true;
 if (d(o1) exists and d(o1) == o2) return true;
 if (d(o1) exists) return false;
 if (type(o1) == arraytype || type(o1) == packedarraytype) return compare_arrays(o1, o2, d);
 if (type(o1) == dicttype) return compare_dicts(o1, o2, d);
 return false;
}

bool compare_arrays(o1, o2, d)
{ if (type(o2) != arraytype) return false;
  if (size(o1) != size(o2)) return false;
  for (int i = 0; i < size(o1); i++)
     if (!is_isomorphic(o1[i], o2[i], d))
        return false;
  d[o1]:=o2; /* .growput */
  return true;
}

bool compare_dicts(o1, o2, d)
{ if (type(o2) != dicttype) return false;
  if (size(o1) != size(o2)) return false;
  for (all {key, val} in o1) {
     if (!exist(o2[key]))
       return false;
     if (!is_isomorphic(val, o2[key], d))
        return false;
  }
  d[o1]:=o2; /* .growput */
  return true;
}

Hope this helps.
Note that 'd' works for .objectmd5sum as well.

This may be coded in either PS or C, but the PS implementation
has one unpleasant feature : it creates a garbage with
thrown temporary dictionaries. 
Apply save, restore against it.

Igor.

----- Original Message ----- 
From: "Dan Coby" <[email protected]>
To: "Igor V. Melichev" <[email protected]>; "Gs-Code-Review" <[email protected]>
Sent: Wednesday, June 23, 2004 2:15 AM
Subject: RE: [gs-code-review] partial fix for 687105 setcolorspace optimizationproblem (xefitra)


> 
> Igor,
> 
> >I'm strongly against this approach because it substitutes a strong
> >equality with a probabilistic comparison.
> >So formally it can't fix the reported problem in general,
> >but only reduces the probability of the failure.
> 
> Since the MD5 sum creates a 128 bit value (128 bits holds numbers
> greater than 10**38) the odds are very small that a mistake would
> occur even if all of our users were constantly running Ghostscript and
> had been doing so since the beginning of the universe.  (The current
> estimated age of the universe is 13.7 x 10**9 years.)  I consider
> this to be adequate.
> 
> 
> >Also the strong equality takes a smaller processor time
> >(1) with non-equal objects, (2) with same objects or when
> >a part of compared object appears same, (3) due to not
> >performing a hashing of tiny pieces of source objects.
> 
> I also do not like the extra CPU time required for calculating the
> MD5 sum.  However with a PostScript strong equality operator (which
> you suggest just below) and with equal objects, the strong equality
> can take longer due to the overhead of the PostScript interpreter.
> The worst case situation occurs with files that are repeatedly
> setting the color space to the same thing.  I am not sure how the
> execution time of the two methods would actually compare.  The
> execution time of the strong equality operator could be reduced by
> implementing it in C instead of PostScript (however you also are
> objecting to creating new C operators - see below).
> 
> 
> >if you code a strong equality in Postscript, 
> >you can store the path in estack, which works
> >with no recursion depth limit artifact.
> 
> It is very easy to create PostScript objects that point back to
> themselves.  A simple example is an array which has an entry which is
> the array.  Without some method for limiting recursion, then we would
> have an infinite loop.  This happens now with the === operator.  I.e.
> try:  1 array dup dup 0 exch put ===
> 
> The use of a maximum recursion depth is a simple solution to this
> situation.  There are other solutions which are more elegant but they
> are also more complicated to implement.
> 
> 
> >Also there is no need to add a new operator to the interpreter.
> >At last, the strong comparison doesn't need tricks with
> >qsort.
> 
> I am not bothered by adding another C operator nor do I consider the
> qsort logic 'tricky'.
> 
> 
> >Can you bring any objections against implementing the strong equality ?
> 
> 1.  See my previous comment about the execution time of the strong
> equality operator.
> 
> 2.  See my comments below about the fact that we do not have a color
> space object that really represents the currently installed color
> space.
> 
> 
> >BUG: 
> >obj_string_data can't apply to dictionary entries,
> >which have keys of one of the following types :
> >number, null, dictionary, FID. So either zobjectmd5sum
> >has a smaller domain or compare_key_names
> >to be rewritten.
> 
> Yes, this is a problem in the current implementation.  I had only
> considered the cases where keys are names or strings.  Thank you.
> 
> 
> >> Two PostScript objects can be compared for equality by first
> >> creating an MD5 sum for each object and then comparing the two
> >> sums.
> >
> >The md5 sum would have some use if the compared objects 
> >don't exist simultaneously. But it isn't true with 687105.
> 
> That is actually the situation that we have here.  As Alex's bug report
> shows, the reason that the current color space equality check is failing
> to operate properly is because the PostScript color space object is being
> modified after the color space was installed in the graphics library.  But
> the real requirement of the setcolorspace optimization logic is that we
> need to be able to compare a new color space object with the color space
> that was installed.
> 
> My plan for the implementation of the remainder of the fix for this problem
> was to calculate the MD5 sum when a color space is installed and to save
> this sum in the graphics state.
> 
> 
> A final note:
> 
> Alex does not mention it directly but this discussion and Alex's example
> also point out that if a file modifies the color space object after a
> color space is installed and then does a 'currentcolorspace', the modified
> object will be returned.
> 
> A possible solution to this problem would be to create an internal copy
> of the color space object.  It would be necessary to clone all of the
> subobjects along with the top level object.  It is also necessary to copy
> the internal color space object again when 'currentcolorspace' is executed
> since we cannot return the internal object.  If we returned the original
> object, then it could be modified by the file.  This also has the
> disadvantage of a nasty CPU penalty for creating these objects.
> 
> 
> Dan
> 
> 
> -----Original Message-----
> From: Igor V. Melichev [mailto:[email protected]]
> Sent: Tuesday, June 22, 2004 9:26 AM
> To: [email protected]; Gs-Code-Review
> Subject: Re: [gs-code-review] partial fix for 687105 setcolorspace
> optimizationproblem 
> 
> 
> I'm strongly against this approach because it substitutes a strong
> equality with a probabilistic comparison.
> So formally it can't fix the reported problem in general,
> but only reduces the probability of the failure.
> Also the strong equality takes a smaller processor time
> (1) with non-equal objects, (2) with same objects or when
> a part of compared object appears same, (3) due to not
> performing a hashing of tiny pieces of source objects.
> if you code a strong equality in Postscript, 
> you can store the path in estack, which works
> with no recursion depth limit artifact.
> Also there is no need to add a new operator to the interpreter.
> At last, the strong comparison doesn't need tricks with
> qsort.
> 
> Can you bring any objections against implementing the strong equality ?
> 
> BUG: 
> obj_string_data can't apply to dictionary entries,
> which have keys of one of the following types :
> number, null, dictionary, FID. So either zobjectmd5sum
> has a smaller domain or compare_key_names
> to be rewritten.
> 
> > Two PostScript objects can be compared for equality by first
> > creating an MD5 sum for each object and then comparing the two
> > sums.
> 
> The md5 sum would have some use if the compared objects 
> don't exist simultaneously. But it isn't true with 687105.
> 
> Igor.
> 
> 
> ----- Original Message ----- 
> From: "Dan Coby" <[email protected]>
> To: "Gs-Code-Review" <[email protected]>
> Sent: Saturday, June 19, 2004 11:35 AM
> Subject: [gs-code-review] partial fix for 687105 setcolorspace optimizationproblem 
> 
> 
> > 
> > Partial fix for 687105 setcolorspace optimization problem.
> > 
> > DETAILS:
> > 
> > Currently the PostScript interpreter checks to see if a color
> > space is changed whenever a call is made to setcolorspace.
> > This greatly increase throughput on some files which set the
> > same color space before every drawing operation.
> > 
> > However the logic for comparing if two color spaces are the
> > same is not perfect.  It misses the case where a color space
> > is specified by an array and one or more of the elements in
> > the array is changed afterward.
> > 
> > This change creates a new PostScript operator which calculates
> > an MD5 sum for any PostScript object.  The description of this
> > operator is in src/zmd5.c.  See the comments prior to
> > zobjectmd5sum.
> > 
> > Two PostScript objects can be compared for equality by first
> > creating an MD5 sum for each object and then comparing the two
> > sums.
> > 
> > Since this operator may be used for other purposes besides
> > comparing color spaces, I am submitting just this operator to
> > code review.
> > 
> > 
> > Dan
> 
> 
> --------------------------------------------------------------------------------
> 
> 
> > _______________________________________________
> > gs-code-review mailing list
> > [email protected]
> > http://www.ghostscript.com/mailman/listinfo/gs-code-review
> > 
> 
>