RE: partial fix for 687105 setcolorspace optimizationproblem

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
>