search

luser-dr00g / xpost

A PostScript interpreter in C
Other
93 stars 12 forks source link

Increase performance of stack and memory-table algorithms #12

Closed GoogleCodeExporter closed 7 years ago

GoogleCodeExporter commented 9 years ago 
What steps will reproduce the problem?
1. All computation
2. Is slower than it ought to
3. bbbbbb eeeeeee .......

Both the stacks and the memory tables are designed as a linear chain of 
segments. 

Adding a new element to the collection involves traversing the chain to find 
the top segment, and for the tables at least, the 'top' index of the top 
segment from which to calculate an absolute index. Performance would likely 
improve (subject to measure) by caching the address of this topmost table in 
the "head" segment. And also cache the top-segment's 'top' index and current 
number of segments to quickly calculate indices.

If the stack is indexed from the bottom, the (necessary?) linear search from 
below going straight to the element. But indexing from above must first search 
the entire stack to produce a count in order to perform the bottom-up search. 
The count property of the stack, could be made much cheaper by caching the 
value in the "head" segment.

Indexing from the top might also make use of the top-segment address and top 
index to avoid linear searching on the top elements (up to a segment size). For 
more consistent application of this shortcut (at least 1 segment size, up to 2 
segment sizes), we could also cache the 2nd-topmost segment address.

Original issue reported on code.google.com by luser.droog on 1 Dec 2013 at 12:40

GoogleCodeExporter commented 9 years ago 
Hm. Another option would be to add reverse links. Top-down indexing could 
search linearly without a count. ... Yes. That works, I think. reverse-links, 
link-to-top: they can be the same field. 

And some of the above is unnecessary. If you have a link to the top segment, 
you don't need top_top, because you have top->top. Too much is too much.

Original comment by luser.droog on 16 Dec 2013 at 11:38

luser-dr00g commented 8 years ago

Algorithm improvements for the stack have been implemented!

luser-dr00g commented 7 years ago

Memory tables have been removed from VM entirely and exist in their own malloced space. About 50% speed boost.