PostScript - How much faster is Proc{} bind def with 'bind' ?

Author

How much faster is Proc{} bind def with 'bind' ?

hoffmann@fho-emden.de

2005-11-23, 7:00 pm

One should think that a procedure with 'bind' is MUCH faster.
That's mostly not the case.
The example below shows a new generator for a 256x256
Hilbert-Peano curve. Roughly, by PSAlter:

3s without bind
2s with bind

Considering the trouble with not-initialized variables it' s IMO
often not necessary to use bind.
Opinions about this issue are appreciated.

Best regards --Gernot Hoffmann

Courier New !
---------------------------------------------------------------

%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 731 731 % 258 mm
%%Creator: Gernot Hoffmann
%%Title: Hilb01
%%CreationDate: November 23/2005

% Draw Hilbert-Peano Curve
% Modified algorithm, originally by Sei-ichiro Kamata, 1996

/mm {2.834646 mul} def

/Tx [0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1] def
/Ty [0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0] def
/Ti [4 0 0 12 0 4 4 8 12 8 8 4 8 12 12 0] def

/g8 0 def

/xo 0 def
/yo 0 def

0 0 0 1 setcmykcolor
true setstrokeadjust

/sx 1 mm def

1 mm 1 mm translate
sx sx scale
0.2 mm sx div setlinewidth

/DrawHilb
{
4
{ /x8 Tx g8 get def /y8 Ty g8 get def /g7 Ti g8 get def /g8 g8 1 add
def
4
{ /x7 Tx g7 get def /y7 Ty g7 get def /g6 Ti g7 get def /g7 g7 1 add
def
4
{ /x6 Tx g6 get def /y6 Ty g6 get def /g5 Ti g6 get def /g6 g6 1 add
def
4
4
{ /x5 Tx g5 get def /y5 Ty g5 get def /g4 Ti g5 get def /g5 g5 1 add
def
4
{ /x4 Tx g4 get def /y4 Ty g4 get def /g3 Ti g4 get def /g4 g4 1 add
def
4
{ /x3 Tx g3 get def /y3 Ty g3 get def /g2 Ti g3 get def /g3 g3 1 add
def
4
{ /x2 Tx g2 get def /y2 Ty g2 get def /g1 Ti g2 get def /g2 g2 1 add
def
4
{ /x1 Tx g1 get def /y1 Ty g1 get def /g1 g1 1 add
def

/xn 0 def
/yn 0 def

x1 1 eq {/xn xn 1 add def} if
x2 1 eq {/xn xn 2 add def} if
x3 1 eq {/xn xn 4 add def} if
x4 1 eq {/xn xn 8 add def} if
x5 1 eq {/xn xn 16 add def} if
x6 1 eq {/xn xn 32 add def} if
x7 1 eq {/xn xn 64 add def} if
x8 1 eq {/xn xn 128 add def} if

y1 1 eq {/yn yn 1 add def} if
y2 1 eq {/yn yn 2 add def} if
y3 1 eq {/yn yn 4 add def} if
y4 1 eq {/yn yn 8 add def} if
y5 1 eq {/yn yn 16 add def} if
y6 1 eq {/yn yn 32 add def} if
y7 1 eq {/yn yn 64 add def} if
y8 1 eq {/yn yn 128 add def} if

xo yo moveto xn yn lineto stroke
/xo xn def
/yo yn def

} repeat % 1
} repeat % 2
} repeat % 3
} repeat % 4
} repeat % 5
} repeat % 6
} repeat % 7
} repeat % 8

} bind def

DrawHilb

showpage
---------------------------------------------------------------------

hoffmann@fho-emden.de

2005-11-23, 7:00 pm

Tiny corrections:
1) one 'repeat' counter has double 4, remove one.
2) should be added: 2 setlinecap.

G.H.

Chapman Flack

2005-11-23, 7:00 pm

hoffmann@fho-emden.de wrote:
> One should think that a procedure with 'bind' is MUCH faster.
> That's mostly not the case.

It has likewise been my experience that any speed advantage
of bind is negligible, and the same for direct binding of
procedures with // and exec - I've rarely seen a difference
exceeding two percent. If you check the PLRM for the memory
consumption of a name, it is a few dozen bytes per name more
than you might expect, and my best guess is that they are used
for a caching scheme that makes the most common sort of name
lookup very, very fast.

IMO the chief argument for binding is to avoid problems of
name capture if your code gets run under a dictionary
stack that contains redefinitions of names you rely on, and
to permit writing reusable, modular library/resource code
that does not depend on or pollute the namespace of the
caller. I've written a bit more on that at
http://www.anastigmatix.net/postscr...source.html#ist

-Chap

hoffmann@fho-emden.de

2005-11-24, 3:58 am

Chap,

thanks for the feedback and the doc. Understanding this will take
longer.
Meanwhile I have replaced the logical structure in the kernel by
'bitshift'.
Surprisingly this doesn't speed up the algorithm considerably.
This leads again to the question 'which part in the interpreter
workflow consumes most of the time ?'

Best regards --Gernot Hoffmann

---------------------------------------------
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 731 731
%%Creator: Gernot Hoffmann
%%Title: Hilb01
%%CreationDate: November 24/2005

% Draw Hilbert-Peano Curve
% Modified algorithm, originally by Sei-ichiro Kamata, 1996
% Bounding box 258mm

/mm {2.834646 mul} def

0 0 0 1 setcmykcolor
true setstrokeadjust
2 setlinecap

/sx 1 mm def

1 mm 1 mm translate
sx sx scale
0.2 mm sx div setlinewidth

/DrawHilb
{/Tx [0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1] def
/Ty [0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0] def
/Ti [4 0 0 12 0 4 4 8 12 8 8 4 8 12 12 0] def
/g8 0 def
/xo 0 def
/yo 0 def
4
{/x8 Tx g8 get def /y8 Ty g8 get def /g7 Ti g8 get def /g8 g8 1 add def
4
{/x7 Tx g7 get def /y7 Ty g7 get def /g6 Ti g7 get def /g7 g7 1 add def
4
{/x6 Tx g6 get def /y6 Ty g6 get def /g5 Ti g6 get def /g6 g6 1 add def
4
{/x5 Tx g5 get def /y5 Ty g5 get def /g4 Ti g5 get def /g5 g5 1 add def
4
{/x4 Tx g4 get def /y4 Ty g4 get def /g3 Ti g4 get def /g4 g4 1 add def
4
{/x3 Tx g3 get def /y3 Ty g3 get def /g2 Ti g3 get def /g3 g3 1 add def
4
{/x2 Tx g2 get def /y2 Ty g2 get def /g1 Ti g2 get def /g2 g2 1 add def
4
{/x1 Tx g1 get def /y1 Ty g1 get def /g1 g1 1 add def

/xn x1 x2 1 bitshift add x3 2 bitshift add
x4 3 bitshift add x5 4 bitshift add
x6 5 bitshift add x7 6 bitshift add
x8 7 bitshift add def
/yn y1 y2 1 bitshift add y3 2 bitshift add
y4 3 bitshift add y5 4 bitshift add
y6 5 bitshift add y7 6 bitshift add
y8 7 bitshift add def

xo yo moveto xn yn lineto stroke
/xo xn def
/yo yn def

} repeat % 1
} repeat % 2
} repeat % 3
} repeat % 4
} repeat % 5
} repeat % 6
} repeat % 7
} repeat % 8
} bind def

DrawHilb

showpage

-----------------------------------------

François Robert

2005-11-24, 7:57 am

hoffmann@fho-emden.de wrote in news:1132813731.200640.106960
@g14g2000cwa.googlegroups.com:

....
> This leads again to the question 'which part in the interpreter
> workflow consumes most of the time ?'

I suspect that the summation in the inner loop is significant.

I changed the code so that the x and y sum is not recalculated for every
vertex (rather, I keep partial X and Y sums at each loop level).
The code in your original posting + patches (DrawHilb0) ran in about
1300+ ms on G8.14 on my machine.
The code in your second posting (DrawHilb1) ran in about 930+ ms.
The code below with partial sums (DrawHilb2) rans in about 700+ ms.
Note that there is another optimization : I changed since Tx, Ty and Ti
are constant, I substituted run-time name look-up with compile-time name
lookup (//Tx, //Ty and //Ti syntax and the arrays are now outside the
loop). That brings a small speedup too.
Maybe removing more name lookup and using the stack instead may bring
some improvement (not sure, since you typically trade name lookup for
twice as much "roll" calls...)

/DrawHilb2
{
/g8 0 def
/xo 0 def
/yo 0 def
4
{/x8 //Tx g8 get 7 bitshift def
/y8 //Ty g8 get 7 bitshift def
/g7 //Ti g8 get def
/g8 g8 1 add def
4
{/x7 //Tx g7 get 6 bitshift def
/y7 //Ty g7 get 6 bitshift def
/g6 //Ti g7 get def
/g7 g7 1 add def
/X7 x8 x7 add def
/Y7 y8 y7 add def
4
{/x6 //Tx g6 get 5 bitshift def
/y6 //Ty g6 get 5 bitshift def
/g5 //Ti g6 get def
/g6 g6 1 add def
/X6 X7 x6 add def
/Y6 Y7 y6 add def
4
{/x5 //Tx g5 get 4 bitshift def
/y5 //Ty g5 get 4 bitshift def
/g4 //Ti g5 get def
/g5 g5 1 add def
/X5 X6 x5 add def
/Y5 Y6 y5 add def
4
{/x4 //Tx g4 get 3 bitshift def
/y4 //Ty g4 get 3 bitshift def
/g3 //Ti g4 get def
/g4 g4 1 add def
/X4 X5 x4 add def
/Y4 Y5 y4 add def
4
{/x3 //Tx g3 get 2 bitshift def
/y3 //Ty g3 get 2 bitshift def
/g2 //Ti g3 get def
/g3 g3 1 add def
/X3 X4 x3 add def
/Y3 Y4 y3 add def
4
{/x2 //Tx g2 get 1 bitshift def
/y2 //Ty g2 get 1 bitshift def
/g1 //Ti g2 get def
/g2 g2 1 add def
/X2 X3 x2 add def
/Y2 Y3 y2 add def
4
{/x1 //Tx g1 get def
/y1 //Ty g1 get def
/g1 g1 1 add def

/xn x1 X2 add def
/yn y1 Y2 add def

xo yo moveto xn yn lineto stroke
/xo xn def
/yo yn def

} repeat % 1
} repeat % 2
} repeat % 3
} repeat % 4
} repeat % 5
} repeat % 6
} repeat % 7
} repeat % 8
} bind def

________________________________________
_______________
François Robert
(to mail me, reverse character order in reply address)

François Robert

2005-11-24, 7:57 am

"François Robert" <moc.sysinu@trebor.siocnarf> wrote in
news:Xns97188E57B64AEtreborsiocnarf@192.61.239.93:

....
> I suspect that the summation in the inner loop is significant.

Drawing is also a big chunk (on GS 8.14 at least) :
If I comment out the moveto / lineto / stroke, DrawHilb2 runs in 330+ ms.
If I leave the line but switch to "nulldevice" prior to calling DrawHilb2,
the execution time is 420+ ms.

For the timing I used "usertime" :
....
usertime ==
DrawHilb2
usertime ==
....
________________________________________
_______________
François Robert
(to mail me, reverse character order in reply address)

hoffmann@fho-emden.de

2005-11-24, 7:57 am

Fran=E7ois,

thanks for the interesting improvements and comments.
Didn't know the //Array trick.
I don't use 'roll' etc. because I want to retain under-
standability.

It seems that mainly the drawing is much time consuming.
So many calculations for one line segment, but the time
for drawing counts terribly.
Therefore it's not so effective to replace named variables
by stack operations.
If PostScript had a mode 'Draw axis aligned' then the
drawing would probably be faster in this application.

Last observation: very slow in Photoshop and Distiller.

As usual I don't need 'real time' for illustrations, but
the discussion clarifies gradually many issues.

Best regards --Gernot Hoffmann

François Robert

2005-11-24, 7:57 am

"François Robert" <moc.sysinu@trebor.siocnarf> wrote in
news:Xns97188E57B64AEtreborsiocnarf@192.61.239.93:

> Maybe removing more name lookup and using the stack instead
> may bring some improvement (not sure, since you typically
> trade name lookup for twice as much "roll" calls...)

Removing name lookup for the inner loop is easy and does bring some
additionnal speedup on GS 8.14 : 600+ ms for DrawHilb3.
(The coordinates of the current vertex are now on the stack and not in
xo/yo. I tried to use the current point in the graphical state, but in
GS 8.14 that is not as fast as directly tracking the coordinates on the
operande stack)

/DrawHilb3
{
/g8 0 def
0 0 % <x0> <y0>
4
{/x8 //Tx g8 get 7 bitshift def
/y8 //Ty g8 get 7 bitshift def
/g7 //Ti g8 get def
/g8 g8 1 add def
4
{/x7 //Tx g7 get 6 bitshift def
/y7 //Ty g7 get 6 bitshift def
/g6 //Ti g7 get def
/g7 g7 1 add def
/X7 x8 x7 add def
/Y7 y8 y7 add def
4
{/x6 //Tx g6 get 5 bitshift def
/y6 //Ty g6 get 5 bitshift def
/g5 //Ti g6 get def
/g6 g6 1 add def
/X6 X7 x6 add def
/Y6 Y7 y6 add def
4
{/x5 //Tx g5 get 4 bitshift def
/y5 //Ty g5 get 4 bitshift def
/g4 //Ti g5 get def
/g5 g5 1 add def
/X5 X6 x5 add def
/Y5 Y6 y5 add def
4
{/x4 //Tx g4 get 3 bitshift def
/y4 //Ty g4 get 3 bitshift def
/g3 //Ti g4 get def
/g4 g4 1 add def
/X4 X5 x4 add def
/Y4 Y5 y4 add def
4
{/x3 //Tx g3 get 2 bitshift def
/y3 //Ty g3 get 2 bitshift def
/g2 //Ti g3 get def
/g3 g3 1 add def
/X3 X4 x3 add def
/Y3 Y4 y3 add def
4
{/x2 //Tx g2 get 1 bitshift def
/y2 //Ty g2 get 1 bitshift def
/g1 //Ti g2 get def
/g2 g2 1 add def
/X2 X3 x2 add def
/Y2 Y3 y2 add def
4
{
moveto % -
//Tx g1 get X2 add % <xn'>
//Ty g1 get Y2 add % <xn'> <yn'>
2 copy % <xn'> <yn'> <xn'> <yn'>
lineto stroke % <xn'> <xn'>
/g1 g1 1 add def

} repeat % 1
} repeat % 2
} repeat % 3
} repeat % 4
} repeat % 5
} repeat % 6
} repeat % 7
} repeat % 8
pop pop
} bind def

________________________________________
_______________
François Robert
(to mail me, reverse character order in reply address)

François Robert

2005-11-24, 6:58 pm

hoffmann@fho-emden.de wrote in news:1132839081.582281.97310
@g43g2000cwa.googlegroups.com:

....
> Didn't know the //Array trick.
....
That works for any pre-existing name. It bypasses deferred execution (which
is what happens to code bracketted by {}).

For instance :

/Code { (Hello) show } bind def
/Dict << /a 1 >> def
/Array [ 11 (foo) ] def
/f { //Code //Dict //Array } bind def
/g { Code Dict Array } bind def
(f is: ) print /f load ==
(g is: ) print /g load ==

returns (in GS) :

f is: { {Hello) --show-- } -dict- [11 (foo)] }
g is: { Code Dict Array }

________________________________________
_______________
François Robert
(to mail me, reverse character order in reply address)

hoffmann@fho-emden.de

2005-11-24, 6:58 pm

Fran=E7ois,

thanks again for improving the code. Gradually it seems
that the implementation is hardly compliant with an already
existing algorithmical description.
Isn't it important as well that we can interpret the
implementation step by step by comparison with the general
description ?
IMO, an intermediate implementation, following your advice,
was already pretty good.
At present I'm struggling with the problem how to write the
data set as index and coordinate pairs [index,x,y] formatted
to the harddisk.

Thanks again and best regards --Gernot Hoffmann

François Robert

2005-11-24, 6:58 pm

hoffmann@fho-emden.de wrote in news:1132858229.413796.201270
@z14g2000cwz.googlegroups.com:

> François,
>
> thanks again for improving the code. Gradually it seems
> that the implementation is hardly compliant with an already
> existing algorithmical description.
> Isn't it important as well that we can interpret the
> implementation step by step by comparison with the general
> description ?
Very often in CS, there is a trade-off between efficiency and
understandability, yes.
I was actually wondering if your original definition was based on
'flatten' nested loops or was recursive ? (IMHO, a recursive definition
comes out quite naturally, and may not be that costly in terms of speed)

> IMO, an intermediate implementation, following your advice,
> was already pretty good.
> At present I'm struggling with the problem how to write the
> data set as index and coordinate pairs [index,x,y] formatted
> to the harddisk.

Write the output as a postscript program fragment (so that you can run
it, as well as read it, à la Illustrator 8) !

Something line-oriented like :
<index> <x> <y> VERTEX
Parsing is easy.
The file becomes PS code by prepending a VERTEX procedure body, that may
be a simple { pop pop pop } (not very useful) or something that draws
the curve, or does something entirely different yet.

You can write to standard ouput (with print), then redirect stdout to a
file (with > on the command line) :

/buf 30 string def

.... % loops
moveto % -
//Tx g1 get X2 add % <xn'>
//Ty g1 get Y2 add % <xn'> <yn'>
2 copy % <xn'> <yn'> <xn'> <yn'>
lineto stroke % <xn'> <yn'>
2 copy exch % <xn'> <yn'> <yn'> <xn'>
//buf cvs print
( ) print
//buf cvs print
( VERTEX\n) print
/g1 g1 1 add def % TODO : dump the index.
.... % loops

Or you can write directly to a file (you will need 'file',
'writestring' and 'closefile' operators)

________________________________________
_______________
François Robert
(to mail me, reverse character order in reply address)

hoffmann@fho-emden.de

2005-11-25, 7:57 am

Fran=E7ois,

the concept is based on the original articel by the Japanese
author:
non-recursive, valid not only for 2D but for any dimension.
In 3D one could visualize the line by tubes.
I had implemented the 2D case for dithering color images,
Pascal and mainly Assembly.

Now I have just one problem left: the file with indices k and
coordinates x,y is generated, but it doesn't appear on the
harddisk (I can open the file in PSAlter, can copy the content).

The structure is roughly:

/dest (C:\\hilb.txt) (w) file def

Loop:
dest stringk writefile
dest stringx writefile
dest stringy writefile
dest (\n) writefile
End of loop.

dest closefile ( tested with or without this line)

How can I save the file on the harddisk ?

Best regards --Gernot Hoffmann

Helge Blischke

2005-11-25, 7:00 pm

hoffmann@fho-emden.de wrote:
>
> François,
>
> the concept is based on the original articel by the Japanese
> author:
> non-recursive, valid not only for 2D but for any dimension.
> In 3D one could visualize the line by tubes.
> I had implemented the 2D case for dithering color images,
> Pascal and mainly Assembly.
>
> Now I have just one problem left: the file with indices k and
> coordinates x,y is generated, but it doesn't appear on the
> harddisk (I can open the file in PSAlter, can copy the content).
>
> The structure is roughly:
>
> /dest (C:\\hilb.txt) (w) file def
>
> Loop:
> dest stringk writefile
> dest stringx writefile
> dest stringy writefile
> dest (\n) writefile
> End of loop.
>
> dest closefile ( tested with or without this line)
>
> How can I save the file on the harddisk ?
>
> Best regards --Gernot Hoffmann

What does "writefile" mean? it is not a PostScripr operator nor a predefined procedure (like ==
and friends). If the stringk and friends are string objects, the writestring operator would
be appropriate.

Helge

--
Helge Blischke
Softwareentwicklung
SRZ Berlin | Firmengruppe besscom
http://www.srz.de

François Robert

2005-11-25, 7:00 pm

hoffmann@fho-emden.de wrote in news:1132923009.020472.310060
@z14g2000cwz.googlegroups.com:

....
> Now I have just one problem left: the file with indices
> k and coordinates x,y is generated, but it doesn't
> appear on the harddisk (I can open the file in PSAlter,
> can copy the content).
>
> The structure is roughly:
>
> /dest (C:\\hilb.txt) (w) file def
>
> Loop:
> dest stringk writefile
> dest stringx writefile
> dest stringy writefile
> dest (\n) writefile
> End of loop.
>
> dest closefile ( tested with or without this line)
>
> How can I save the file on the harddisk ?
....
As Helge noted, 'writefile' is not a standard PS operator. The operator
is 'writestring' for strings, 'write' for bytes. Either you have written
your own 'writefile' procedure or you are using a PSAlter-specific
operator, whose behavior may well be what you see. (?)

FWIW : my experience with file operation with GhostScript on Win32 is
that more often than not, it is necessary to quit the GS application
(otherwise files are not flushed and/or file locks are retained,
preventing other applications to read the data)

________________________________________
_______________
François Robert
(to mail me, reverse character order in reply address)

hoffmann@fho-emden.de

2005-11-25, 7:00 pm

Only a typo: not 'writefile' but 'writestring'.

It's a strange behaviour of PSAlter:
as long as PSAlter is used (maybe minimized)
the file appears in the folder Temp, using a dummy
name.
>From there it can be saved using any name.
The name as assigned in the PS code is meaningless.

G.H.

Aandi Inston

2005-11-25, 7:00 pm

hoffmann@fho-emden.de wrote:

>Now I have just one problem left: the file with indices k and
>coordinates x,y is generated, but it doesn't appear on the
>harddisk (I can open the file in PSAlter, can copy the content).

If using PSAlter, it will not write named files, to protect against
malicious code.

However, it will
(a) read a named file and
(b) open a window containing the contents of named written files.
These are available to the program to open (in preference to real
files of the same name). So long as you do not close PSAlter, the file
remains available.

Right click -> save as is also available in file windows. The default
name and path will taken from the filename specified.
----------------------------------------
Aandi Inston quite@dial.pipex.com http://www.quite.com
Please support usenet! Post replies and follow-ups, don't e-mail them.

hoffmann@fho-emden.de

2005-12-02, 9:56 pm

Yes, absolutely sufficient. It was a little disturbing that the
named file was not written as expected.

Best regards --Gernot Hoffmann

Sponsored Links