1 /* Copyright (C) 1992, 1996, 1997, 1998, 1999, 2000 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: dstack.h,v 1.6 2004/08/04 19:36:12 stefan Exp $ */ 18 /* Definitions for the interpreter's dictionary stack */ 19 20 #ifndef dstack_INCLUDED 21 # define dstack_INCLUDED 22 23 #include "idstack.h" 24 #include "icstate.h" /* for access to dict_stack */ 25 26 /* Define the dictionary stack instance for operators. */ 27 #define idict_stack (i_ctx_p->dict_stack) 28 #define d_stack (idict_stack.stack) 29 30 /* Define the interpreter-specific versions of the generic dstack API. */ 31 #define min_dstack_size (idict_stack.min_size) 32 #define dstack_userdict_index (idict_stack.userdict_index) 33 #define dsspace (idict_stack.def_space) 34 #define dtop_can_store(pvalue) ((int)r_space(pvalue) <= dsspace) 35 #define dtop_keys (idict_stack.top_keys) 36 #define dtop_npairs (idict_stack.top_npairs) 37 #define dtop_values (idict_stack.top_values) 38 #define dict_set_top() dstack_set_top(&idict_stack); 39 #define dict_is_permanent_on_dstack(pdict)\ 40 dstack_dict_is_permanent(&idict_stack, pdict) 41 #define dicts_gc_cleanup() dstack_gc_cleanup(&idict_stack) 42 #define systemdict (&idict_stack.system_dict) 43 44 /* Define the dictionary stack pointers. */ 45 #define dsbot (d_stack.bot) 46 #define dsp (d_stack.p) 47 #define dstop (d_stack.top) 48 49 /* Macro to ensure enough room on the dictionary stack */ 50 #define check_dstack(n)\ 51 if ( dstop - dsp < (n) )\ 52 { d_stack.requested = (n); return_error(e_dictstackoverflow); } 53 54 /* 55 * The dictionary stack is implemented as a linked list of blocks; 56 * operators that access the entire d-stack must take this into account. 57 * These are: 58 * countdictstack dictstack 59 * In addition, name lookup requires searching the entire stack, not just 60 * the top block, and the underflow check for the dictionary stack 61 * (`end' operator) is not just a check for underflowing the top block. 62 */ 63 64 /* Name lookup */ 65 #define dict_find_name_by_index(nidx)\ 66 dstack_find_name_by_index(&idict_stack, nidx) 67 #define dict_find_name(pnref) dict_find_name_by_index(name_index(imemory, pnref)) 68 #define dict_find_name_by_index_inline(nidx, htemp)\ 69 dstack_find_name_by_index_inline(&idict_stack, nidx, htemp) 70 #define if_dict_find_name_by_index_top(nidx, htemp, pvslot)\ 71 if_dstack_find_name_by_index_top(&idict_stack, nidx, htemp, pvslot) 72 73 /* 74 Notes on dictionary lookup performance 75 ====================================== 76 77 We mark heavily used operations with a * below; moderately heavily used 78 operations with a +. 79 80 The following operations look up keys on the dictionary stack: 81 *(interpreter name lookup) 82 load 83 where 84 85 The following operations change the contents of dictionaries: 86 *def, +put 87 undef 88 restore 89 (grow) 90 We implement store in PostScript, and copy as a series of puts. Many 91 other operators also do puts (e.g., ScaleMatrix in makefont, 92 Implementation in makepattern, ...). Note that put can do an implicit 93 .setmaxlength (if it has to grow the dictionary). 94 95 The following operations change the dictionary stack: 96 +begin, +end 97 +?(context switch) 98 readonly (on a dictionary that is on the stack) 99 noaccess (on a dictionary that is on the stack) 100 We implement cleardictstack as a series of ends. 101 102 Current design 103 ============== 104 105 Each name N has a pointer N.V that has one of 3 states: 106 - This name has no definitions. 107 - This name has exactly one definition, in systemdict or userdict. 108 In this case, N.V points to the value slot. 109 - This name has some other status. 110 111 We cache some pointers to the top dictionary on the stack if it is a 112 readable dictionary with packed keys, which allows us to do fast, 113 single-probe lookups in this dictionary. We also cache a value that 114 allows us to do a fast check for stores into the top dictionary 115 (writability + space check). 116 117 Improved design 118 =============== 119 120 Data structures 121 --------------- 122 123 With each dictionary stack (or equivalently with each context), we 124 associate: 125 126 * A name lookup cache, C. Each entry C[i] in the cache consists of: 127 128 A key, K (a name index). 129 130 A dictionary stack level (depth), L. C[i] is valid iff the 131 current dictionary stack depth, |dstack|, is equal to L. 132 (L is always less than or equal to |dstack|.) 133 134 A value pointer, V, which points to some value slot of some 135 dictionary on the stack. 136 137 * A lookup cache restoration stack, R. Each entry R[j] on this stack 138 consists of: 139 140 An index i in C. 141 142 The previous (K,D,V) of C[i]. 143 144 C needs to be large enough to satisfy the overwhelming majority of name 145 lookups with only 1-3 probes. In a single-context system, C can be large 146 (perhaps 8K entries = 80K bytes, which is enough to accommodate every name 147 in a typical run with no reprobes). In a multiple-context system, one can 148 choose a variety of different strategies for managing C, such as: 149 150 A single cache that is cleared on every context switch; 151 152 A small cache (e.g., .5K entries) for each context; 153 154 A cache that starts out small and grows adaptively if the hit rate 155 is too low. 156 157 R needs to be able to grow dynamically; in the worst case, it may have |C| 158 entries per level of the dictionary stack. We assume that R will always be 159 able to grow as needed (i.e., inability to allocate space for R is a 160 VMerror, like inability to allocate space for the undo-save information for 161 'save'). 162 163 With each entry E[j] on the dictionary stack, we associate: 164 165 * A value U that gives the depth of R at the time that E[j] was pushed 166 on the stack. E[j].U = 0 for 0 <= j < the initial depth of the dictionary 167 stack (normally 3). 168 169 With each dictionary D we associate: 170 171 * A counter S that gives the total number of occurrences of D on all 172 dictionary stacks. If this counter overflows, it is pinned at its maximum 173 value. 174 175 In order to be effective, D.S needs to be able to count up to a small 176 multiple of the total number of contexts: 16 bits should be plenty. 177 178 As at present, we also maintain a pair of pointers that bracket the value 179 region of the top dictionary on the stack, for fast checking in def. If the 180 top dictionary is readonly or noaccess, the pointers designate an empty 181 area. We call this the "def region cache". 182 183 Now we describe the implementation of each of the above operations. 184 185 (name lookup) 186 ------------- 187 188 To look up a name with index N, compute a hash index 0 <= i < |C|. There 189 are three cases: 190 191 1. C[i].K == N and C[i].L == |dstack|. Nothing more is needed: 192 C[i].V points to the N's value. 193 194 2. C[i].K == N but C[i].L < |dstack|. Look up N in the top |dstack| 195 - L entries on the dictionary stack; push i and C[i] onto R; set 196 C[i].V to point to the value if found, and in any case set C[i].L = 197 |dstack|. 198 199 3. C[i].K != N. Reprobe some small number of times. 200 201 If all reprobes fail, look up N on the (full) dictionary stack. Pick an 202 index i (one of the probed entries) in C to replace. If C[i].L != |dstack|, 203 push i and C[i] onto R. Then replace C[i] with K = N, L = |dstack|, and V 204 pointing to N's value. 205 206 load 207 ---- 208 209 Proceed as for name lookup. However, it might be worth not making the new 210 cache entry in case 3, since names looked up by load will rarely be looked 211 up again. 212 213 where 214 ----- 215 216 Just do a full lookup, ignoring C. 217 218 def 219 --- 220 221 As at present: start by doing one or two fast probes in the def region 222 cache; if they succeed, just store the new value; otherwise, do a normal 223 dictionary lookup and access check. If a new dictionary entry is created 224 and the key is a name, check all possible probe slots of the name in C; if 225 the name is present, update its entry in C as for a lookup. Then if D.S > 226 1, scan as for 'grow' below. 227 228 put 229 --- 230 231 If the key is a name, the dictionary entry is new, and D.S != 0, scan as for 232 'grow' below. 233 234 undef 235 ----- 236 237 If the key is a name and D.S != 0, scan as for 'grow' below. It might be 238 worth checking for D.S == 1 and D = the top dictionary on the stack as a 239 special case, which only requires removing the name from C, similar to 240 'def'. 241 242 restore 243 ------- 244 245 The undo-save machinery must be enhanced so that grow, def/put, and undef 246 operations can be recognized as such. TBD. 247 248 (grow) 249 ------ 250 251 If D.S == 0, do nothing special. Otherwise, scan C, R, and the dictionary 252 stack (first for the current context, and then for other contexts if needed) 253 until D.S occurrences of D have been processed. (If D is in local VM, it is 254 only necessary to scan contexts that share local VM with the current one; if 255 D is in global VM, it is necessary to scan contexts that share global VM 256 with the current one.) Entries in C whose V pointed within D's old values 257 array are updated; entries in R whose V pointed within the old values array 258 are replaced with empty entries. 259 260 begin 261 ----- 262 263 After pushing the new dictionary, set dstack[|dstack| - 1].U = |R|. Reset 264 the def region cache. 265 266 end 267 --- 268 269 Before popping the top entry, for dstack[|dstack| - 1].U <= j < |R|, restore 270 C[R[j].i] from R[j].(K,L,V), popping R. Reset the def region cache. 271 272 (context switch) 273 ---------------- 274 275 Reset the def region cache. 276 277 readonly 278 -------- 279 280 If the dictionary is the top one on the stack, reset the def region cache. 281 282 noaccess 283 -------- 284 285 If D.S != 0, scan as for 'grow' above, removing every C and R entry whose V 286 points into D. Also reset the def region cache if the dictionary is the top 287 one on the stack. 288 289 (garbage collection) 290 -------------------- 291 292 The garbage collector must mark names referenced from C and R. Dictionaries 293 referenced from C and R are also referenced from the dictionary stack, so 294 they do not need to be marked specially; however, pointers to those 295 dictionaries' values arrays from C and R need to be relocated. 296 297 */ 298 299 #endif /* dstack_INCLUDED */ 300