Re: partial fix for 687105 setcolorspace optimizationproblem

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
> > 
> 
>