Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #2109

Re: designing a data structure in C for PS paths.

Show all headers | View raw

On Thursday, December 26, 2013 1:27:41 PM UTC-6, luser- -droog wrote:
> This is I think is of general interest, although motivated by work on Xpost.
> 
> I want to implement in C a data structure for PS paths. 
> 
> Here's the version from the draft interpreter xpost0c, before I rewrote it to use Cairo for graphics. This isn't my earliest version because there was something in flips that make Xlib calls, but I'm not finding any copies of that at the moment.
> 
> These are xpost0c's operator functions. They receive a pointer to a C-array of the object arguments from the ps operand stack, and place their return values into the same array (which is, in fact part of the ps operand stack directly accessed by the pointer).
> 
[snip]
> So this code just uses a global array (curpath) and a pointer (tailpath) and an auxiliary pointer (subpath) into an array of structs containing an enum and up to 6 coordinate values.
> 
> My current code implements the path entirely in postscript, using dictionaries for almost everything due to their nice properties: named elements, auto-growing, support for integer keys.
> 
> I won't quote everything here, you can browse it at code.google.com/p/xpost in data/path.ps.
> 
[snip]> 
> 
> You see that the dict has very nice properties for a simulating a growing array. The key for the tail is always at `length 1 sub`. The element dict can hold a size=2 or size=6 array as needed. And everything interacts naturally with save/restore.
> 
> The idea I've been toying with for a "new way" is to use stacks. That's the basic auto-growing structure at the C level of the interpreter (lower overhead than a dict because it doesn't exist as a postscript object, so it doesn't take up a slot in the memory table).
> 
> With stacks, I think I can arrange the objects to pretty much match the normal postscript syntax.
> 
> [0]:0
> [1]:0
> [2]:moveto
> [3]:100
> [4]:100
> [5]:lineto
> [6]:200
> [7]:100
> [8]:lineto
> [9]:closepath
> 
> This would be a "subpath" stack or in the original Warnock/Wyatt language, a trajectory as distinct from a complete shape.
> 
> To make it nestable, I suppose we have to violate the "no overhead" description above, and wrap the stack in an object. There is precendent for this elsewhere in the interpreter. A savetype object contains a vm address for a stack. Ok, that's still pretty low for overhead. It still doesn't need a memory table slot (aka 'ent').
> 
[snip]> 
> So if there's a pathtype object implemented the same way, the "current" path could be a stack of "subpaths" which are pathtype stacks.
> 
> [0]:path
> [1]:path
> [2]:path
> 
> And this stack would then be stacked in a top-level "path stack", which is pushed (dup) and popped (... free the stack? ...) in coordination with gsave/grestore and save/restore, since it's no longer contained in the ps-level adt implementation of the gstate stack....
> 
> ... Hm. Or is that a bad choice? Maybe it can still be in the ps-level gstate dict. I'll have to think on that. That would seem to take care of the (g)*(save/restore) issue.


Buttoning-up this thread for the archive. 

The stack nonsense was way too complicated and never happened.
Instead, we translated the functions directly to C, using
the same postscript-level data structures. This had the
effect of factoring out many cycles of the main interpreter
loop from the execution of each operator. Crude testing
showed a 50% speed-up in the drawing tests.

So it's still growing dicts with the same member names in the
element dicts.

Now, a lot of my old links to code are going dead as stuff
gets moved from src/bin to src/lib. But everything is in /lib
now so current links should be stable for the forseeable.
http://code.google.com/p/xpost/source/browse/src/lib/xpost_op_path.c

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2013-12-26 11:27 -0800
  Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2013-12-26 11:38 -0800
  Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-07 22:09 -0800
    Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-08 15:53 +0100
      Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-08 23:32 -0800
        Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-09 14:49 +0100
          Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:08 -0800
            Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:40 -0800
              Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:49 -0800
                Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-11 00:18 +0100

csiph-web