how do save/restore really work?
mij...@yahoo.com
I'm working on building a postscript interpreter
and I just can't wrap my noodle around how to
go about implementing the save and restore
operators.
My two hazy ideas are:
1. save: copy all stacks (and contents) to a container
in an array. restore: copy it all back out
2. save: push a mark on "undo" stack
additional: all memory accesses must add undo record. restore: apply
all "undo"s to the mark.
Both seem like a lot of work.
On the face of it, 2 looks like a better strategy
(more correct, somehow; possibly easier, too).
Ideas?
/Inside Postscript/ doesn't go this deep.
luser-ex-trog
ken
5e8311...@s36g2000vbp.googlegroups.com>, mij...@yahoo.com says...
> Hello all and any,
>
> I'm working on building a postscript interpreter
> and I just can't wrap my noodle around how to
> go about implementing the save and restore
> operators.
> My two hazy ideas are:
> 1. save: copy all stacks (and contents) to a container
> in an array. restore: copy it all back out
You also need to copy (for example) all fonts currently in the font
cache. You'll probably find that duplicating all the objects currently
held in VM will be prohibitively expensive of memory.
> 2. save: push a mark on "undo" stack
> additional: all memory accesses must add undo record. restore: apply
> all "undo"s to the mark.
>
> Both seem like a lot of work.
> On the face of it, 2 looks like a better strategy
> (more correct, somehow; possibly easier, too).
>
> Ideas?
Its complicated, a lot will depend on how your memory scheme works, how
composite objects are represented and so on.
I've worked on several interpreters, one has a memory scheme where
memory addresses for new objects were always greater then previous
addresses.
In this scheme a save makes a 'mark' in a memory manager stack, all new
objects are allocated above this point. Objects with memory addresses
below this point are copied when modified into a newly created object
above the mark. Restore causes the memory manager to discard all objects
whose memory address is higher than the mark. There are complexities
involved with retrieving the correct copy of an object of course.
Another scheme used a 'count' of save states; when an object is modified
its save level is compared to the current save level, if its less then a
new copy is made and modified, linked from the original. Restore tests
all objects and discards all those whose save level is greater than the
current level.
There are bound to be other possible schemes, but all the ones I've
experienced avoid your first suggestion, there can be an awful lot of
objects to copy, and memory usage used to be vitally important for
PostScript interpreters.
Your second suggestion is basically similar to the two schemes outlined
above. The major difference between these schemes is where the record
keeping takes place, and how the allocated memory is discarded.
Basically these generally boil down to 'copy on write'.
I presume this is a personal project ? Writing a new PostScript
interpreter is a lot of work, and there are several available to licence
(or indeed available under GPL in the case of Ghostscript).
Ken
mij...@yahoo.com
> In article <9f99ffc2-b8ba-4cdc-971d-
> 5e83113a8...@s36g2000vbp.googlegroups.com>, mijo...@yahoo.com says...
Thanks a bunch. Should be very helpful once fully grokked.
> I presume this is a personal project ? Writing a new PostScript
> interpreter is a lot of work, and there are several available to licence
> (or indeed available under GPL in the case of Ghostscript).
>
> Ken
Yes, personal project. Yes, lots of work. I've got a few
sources for various interpreters (Crispin Goswell's from
comp.sources.unix, rbuss (SunOS NeWS clone), and a few
amiga ones (in 68000 assembler), but so far I've only
found them useful when I already had a rough idea of
what I'm looking for (loops and the exec stack).
I confess I'm afraid of the ghostscript sources. I've been
unable to get it to compile on a couple of occasions
over the years (I now suspect this may have been due to
downloading from cvs rather than a "source ditribution").
For my ultimate goal (a NeWS clone with PSIBER), it
seemed to be to be more worthwhile to build from scratch.
I could spent months poring over the gs source and have
nothing to show for it. But doing it myself, I'm 2 months
in and 1000 lines into version 0.2 (reimplementation of
0.1 with reference counting).
My next decision is whether to stick with Xlib or switch
to PHIGS or Cairo.
Thanks again,
luser-eg-trog
ken
@y38g2000prg.googlegroups.com>, mij...@yahoo.com says...
> Yes, personal project. Yes, lots of work.
Last time I saw Aandi Inston's esitmate he was thinking 5-10 man years,
if I remember correctly, but I thnk that was for a full level 3 + PDF
RIP.
> I confess I'm afraid of the ghostscript sources. I've been
> unable to get it to compile on a couple of occasions
> over the years (I now suspect this may have been due to
> downloading from cvs rather than a "source ditribution").
Well, the GS sources ought to compile without problems from the
Subversion repository, its always possible that someone checked in a
change which broke a build, but its pretty rare.
> For my ultimate goal (a NeWS clone with PSIBER)
Hmm, I don't recall the details, but I think Display PostScript (which
is what NeWS used) was basically level 1.5 with extensions. That is it
supported the very basic colour operators, but not the more extensive
level 2 spaces such as CIE, nor patterns and forms. It does however have
some unique operarors (eg wait) which are not present in regular print
PostScript.
You also need to take account of display contextc, because the
interpreter is shared across different windows.
On the whole the lack of full level 2 makes the project much easier.
JaWS was written from scratch as a NeWS clone and took about 3-5 years I
think, I don't recall exactly what Ian said. Much of that was part time
though.
> I could spent months poring over the gs source and have
> nothing to show for it.
Probably true, though GS does have some rudimentary Display PostScript
support, but I doubt if it still works 100%.
Ken
mij...@yahoo.com
>
> > Yes, personal project. Yes, lots of work.
>
> Last time I saw Aandi Inston's esitmate he was thinking 5-10 man years,
> if I remember correctly, but I thnk that was for a full level 3 + PDF
> RIP.
>
> > I confess I'm afraid of the ghostscript sources. I've been
> > unable to get it to compile on a couple of occasions
> > over the years (I now suspect this may have been due to
> > downloading from cvs rather than a "source ditribution").
>
> Well, the GS sources ought to compile without problems from the
> Subversion repository, its always possible that someone checked in a
> change which broke a build, but its pretty rare.
I think it was a matter of the directories not being properly
organized. zlib or something was in the wrong place. I gave up.
With the goswell source and rbuss, I had plenty to try to
understand. So far the only use I've had for any of them is
figuring out how the control and loop operators use the execution
stack.
> > For my ultimate goal (a NeWS clone with PSIBER)
>
> Hmm, I don't recall the details, but I think Display PostScript (which
> is what NeWS used) was basically level 1.5 with extensions. That is it
> supported the very basic colour operators, but not the more extensive
> level 2 spaces such as CIE, nor patterns and forms. It does however have
> some unique operarors (eg wait) which are not present in regular print
> PostScript.
For now I'm sticking with plain-old Xlib for the backend.
I gotten so far as stroking and filling polygons from a
path built with movetos and linetos in a color set by
setrgbcolor, sethsbcolor or setgray. But there's some
weirdness happening when I try to stroke the same path
after filling. Half of it's ending up with the black
lines over the shifting color wheel, and on the other
half, they seem to be drawn interleaved such that the
black lines are totally obscured. I'm seriously
considering learning PHIGS or Cairo, or even using
IPC with gimp. Xlib is just irritating at every turn.
> You also need to take account of display contextc, because the
> interpreter is shared across different windows.
If I can just get a hold of the NeWS Manual, I can't at least
figure out how that's /supposed/ to work. The multithreading
aspect seems to be well described in PLRM, 2ed.
> On the whole the lack of full level 2 makes the project much easier.
> JaWS was written from scratch as a NeWS clone and took about 3-5 years I
> think, I don't recall exactly what Ian said. Much of that was part time
> though.
That's on a par with Ghostscript. I read somewhere that it took
Peter Deutsch 5 years for the initial release, again part-time.
I suppose I'm part-time as well, in that I have a job doing
something else, but I've got a lot of free time.
> > I could spent months poring over the gs source and have
> > nothing to show for it.
>
> Probably true, though GS does have some rudimentary Display PostScript
> support, but I doubt if it still works 100%.
>
> Ken
Yes, I thought about trying to do this as just a GUI front-end
to the ghostscript API. But, I really wanted to try my hand at
the whole thing. The name I've chosen reflects this: podvig
(the Russian title of a novel by Nabokov, alternately translated
exploit (noun not verb), feat, Glory (English title of the
novel)).
Bizarrely, with all the nested function calls, my C-language
Postscript interpreter looks a lot like LISP inside. So I'm
perusing LISP sources, too.
luser-X-trog
bugbear
> In article <9e428252-b480-408f-a359-7e74c6e50285
> @y38g2000prg.googlegroups.com>, mij...@yahoo.com says...
>
>> Yes, personal project. Yes, lots of work.
>
> Last time I saw Aandi Inston's esitmate he was thinking 5-10 man years,
> if I remember correctly, but I thnk that was for a full level 3 + PDF
> RIP.
A commercially viable level 1 postscript interpreter
can be done in 4 man years.
I think the "rutherford" one took less,
but was more proof of concept grade.
BugBear
bugbear
I was intrigued, did a google, and found:
http://stuff.mit.edu/afs/athena/astaff/project/xps/
BugBear
luser-ex-troll
> bugbear wrote:
> > ken wrote:
> >> In article <9e428252-b480-408f-a359-7e74c6e50285
>
> >>> Yes, personal project. Yes, lots of work.
>
> >> Last time I saw Aandi Inston's esitmate he was thinking 5-10 man
> >> years, if I remember correctly, but I thnk that was for a full level 3
> >> + PDF RIP.
>
> > A commercially viable level 1 postscript interpreter
> > can be done in 4 man years.
>
> > I think the "rutherford" one took less,
> > but was more proof of concept grade.
>
> I was intrigued, did a google, and found:http://stuff.mit.edu/afs/athena/astaff/project/xps/
>
> BugBear
I think that's one of the descendants of the "rutherford"
one. A search for "ralpage" should turn up something
very similar. For reading purposes, I went back to the
version posted on comp.sources.unix, with it's small
handful of patches. The later ones seem to have too many
fingerprints to easily see through the glass.
It's interesting because it uses dictionaries implement
the polymorphic operators. For now I'm just using switch
statements to keep everything simple. But the more
operator functions I write, the more tempting it becomes
to use dictionaries (or arrays of function-pointers).
As for the 3-10 man-years estimate, I can but hope that
I'm either smart enough to do it faster or patient enough
to keep it going.
I think I may need to order a 1st-edition PLRM. I've
already gotten my priorities confused by tackling
garbage-collection before save/restore!
l-x-t
ken
@f1g2000prb.googlegroups.com>, mij...@yahoo.com says...
> I think I may need to order a 1st-edition PLRM. I've
> already gotten my priorities confused by tackling
> garbage-collection before save/restore!
Garbage collection isn't essential at all, it depends how your memory
manager works. For example, Jaws uses a reference counted system for all
allocated objects, once they are deallocated they are freed, so no
garbage collection required.
Ken
bugbear
Doesn't that fail under circular references?
BugBear
ken
bugbear@trim_papermule.co.uk_trim says...
> > Garbage collection isn't essential at all, it depends how your memory
> > manager works. For example, Jaws uses a reference counted system for all
> > allocated objects, once they are deallocated they are freed, so no
> > garbage collection required.
>
> Doesn't that fail under circular references?
Special detection for circular reference where it matters (mostly
fonts), in general a circular reference is a bad thing anyway. A bigger
problem is lack of memory relocation, which can cause large allocations
to fail after many small allocations leave 'sandbars' in memory.
Ken
luser-ex-troll
> In article <aqmdnT0FrcBrcC3UnZ2dnUVZ8jCWn...@posted.plusnet>,
I have decided on reference-counting instead of a tracing
collector. I had thought that garbage-collection was a
more general term including both tracing and counting.
According to /Distributed Window Systems/, NeWS used
reference-counting with an extra mechanism called "soft-
references" to handle possibly circular structures.
The way I understand it, when all "hard" references are
removed, the object is passed back to the client through
an event, and the client must break the circle to give
the memory back.
I posted a prototype of my structures and allocators to
comp.lang.c about a week ago. Unfortunately, it was
horribly polluted with macros (most of which belonged in
another module), and the comments I received were
addressed to that rather than the reference-counting
per se.
I see what you mean about "sandbars" of small objects
obstructing the allocation of larger blocks. Rather like
two people occupying the entire breadth of the sidewalk
and completely oblivious to any others whom they may be
inconveniencing. I don't see an easy solution.
l-x-t
David Combs
There's now books on garbage-collection. EG, Appel has one.
Maybe also some ideas in Computing Surveys (ACM).
Also in the proceedings of various SIGPLAN and other ACM conferences.
David
luser-ex-troll
> In article <e46f83a1-a803-4aa2-89af-78adebc70...@h20g2000yqn.googlegroups.com>,
Thanks. I thought this thread had gone stale. I'll check
into those. I've found a few scattered resources on
the net, among which:
Overview of Linux-Kernel Reference Counting
http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2007/n2167.pdf
http://www.memorymanagement.org/
I'm still not sure how to go about the save/restore part.
My current line of thought is to store the save-level
as an integer in each composite data-structure. Then
when attempting to store an object while, say, level
3 is in effect, into a container holding a level-2
object, the old object (and its former memory
address) is added to a list of "reversions" which
gets traversed by the restore operator.
But the part that still stumps me is what to put in the
save-object itself: just an integer for the save-level,
or the structure holding the "reversion-list".
I'm not sure it really matters, but there must have
been some reason to have a save-object to begin with
instead of an implicit stack like gsave/grestore.
lxt