The problem of memory. And some solutions.

[luserdroog]

The way memory works in xpost is complicated. It seems to me that a lot of this is necessary, though. But unfortunately, recent experience testing the program with simple drawing and few programs lying around in my directories leads me to conclude that there are severe shortcomings with the current system. And so it's going to have to get more complicated.

But, with care and attention, it should be possible to make the code cleaner and simpler while doing this.

 

The problem.

 

Xpost keeps running out of 'ents'. An ent is an index into the memory table and identifies a memory allocation. But these are stored in composite objects (array, dict, string, file, etc) in a "word"-sized field. For the normal configuration, this is 16bits on all platforms. There is support in the design for a larger object format which would use a 32bit field for the ent, but the large-object configuration has not been debugged, so it's not currently a viable alternative.

 

So, there are a maximum of 65535 global vm objects and 65535 local vm objects accessible from the postscript level.

 

The solutions.

 

Make separate 'ent' spaces for different types. With this change, there would be separate tables in the memory for arrays or dicts or string. This would make available 65535 global dicts, 65535 local dicts, 65535 global arrays, 65535 local arrays, 65535 global strings, 65535 local strings. It would involve changing the memory table functions to accept a reference to the table-head to use with the given ent number. Accessing arrays would need to call xpost_table_get_addr for the head of the array table from table-zero, and similarly for dicts and strings.

 

Change save/restore not to use 'ents' for allocation copies. The save mechanism creates a copy of arrays and dicts before any changes that will need to be reverted. It does this by allocating a new 'ent' of the same size and copying the data from the allocation. Then restore merely has to swap the address fields of the two ents in the memory table. Instead, it could store just the address of the preserved contents in the save-record, and create the ent only when freeing.

 

Translate the path data structure to C and use stacks instead of a tree of dicts. The path data structure uses lots and lots of ents. The top-level path structure is a dict. It contains sub-paths which are dicts. These sub-paths contain elements which are dicts. These element dicts contain arrays of [x y] arrays. While this would save a lot of ents, it could also get very complicated because the path is part of the gstate, and subject to gsave/grestore; and it is also subject to save/restore. So there would need to be several levels of stacks, and top-level pushing and popping (push needs to copy, but pop s.b. cheap, no 'ent's to free) need to be coordinated with gsave/grestore and save/restore.

 

Use extra bits from the tag to extend the ent field. This should be relatively easy, especially if combined with the separate tables for types. Extracting the ent from an object will need to be mediated by a function which also selects the correct table. So the bitwise manipulations needed to assemble the ent number from .ent field and bits from the .tag would be confined to one place in the code. This would increase the 65535 limit to a multiple of that number. In preparation, I've added a constant to the object header which indexes these extra bits. I've also added get/set functions to access the ent in an object more abstractly.   --Edit: *This solution has been implemented.* We should now have 8 * 65535 = 524287 as the maximum ent accessible by an object.  Edit: *much later, the last parts of the code that were using .ent directly have been changed to use the access function, and we can actually use all 524287 ents (ent 0 is the head of the free list, so we can consider the space 1-based and max=total).

 

Change names not to use ents to refer to the immutable string copy. Names are implemented as a ternary-search-tree which maps string data to integers, then these integers index a stack of string objects which contain the immutable copy. These 'namestring' objects are not directly accessible to ps, so there is no real *need* to have them as ps objects. These could instead be a new object type which addresses the memory directly, as described above for save-records. --Edit: This is probably not worth the effort. After runtest there are only a few hundred names. So this would only save a few hundred ents except in pathological cases (large numbers of distinct names).

 

[luserdroog]

Another way to improve the memory behavior, I think, is to change the way the free list works. Right now the free list starts in ent 0 and the next ent is stored in the first 32bit word in the allocated memory for that ent.

 

Kind of like this:

 

  0: -> 2

  1: [in use]

  2: -> 3

  3: -> 0

 

The change I propose is to use the existing free list mechanism just to track free ents. And copy the allocation information into a secondary table.

 

The problem this addresses is: unusable allocations holding ents that then cannot be used by ps objects. This gets back to some early design decisions which simplified the implementation. Allocations are basically permanent. They can be added to the free list and reused, but they maintain their originally-allocated size. I've added parameters to control "wastage" in selecting an allocation from the free list, but the result may be that certain oddly-sized allocations are never reused.

 

This change would reduce the accumulation of "dead" ents.