Source

python-peps / pep-0280.txt

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
PEP: 280
Title: Optimizing access to globals
Version: $Revision$
Last-Modified: $Date$
Author: guido@python.org (Guido van Rossum)
Status: Deferred
Type: Standards Track
Created: 10-Feb-2002
Python-Version: 2.3
Post-History:


Deferral

    While this PEP is a nice idea, no-one has yet emerged to do the work of
    hashing out the differences between this PEP, PEP 266 and PEP 267.
    Hence, it is being deferred.


Abstract

    This PEP describes yet another approach to optimizing access to
    module globals, providing an alternative to PEP 266 (Optimizing
    Global Variable/Attribute Access by Skip Montanaro) and PEP 267
    (Optimized Access to Module Namespaces by Jeremy Hylton).

    The expectation is that eventually one approach will be picked and
    implemented; possibly multiple approaches will be prototyped
    first.


Description

    (Note: Jason Orendorff writes: """I implemented this once, long
    ago, for Python 1.5-ish, I believe.  I got it to the point where
    it was only 15% slower than ordinary Python, then abandoned it.
    ;) In my implementation, "cells" were real first-class objects,
    and "celldict" was a copy-and-hack version of dictionary.  I
    forget how the rest worked."""  Reference:
    http://mail.python.org/pipermail/python-dev/2002-February/019876.html)

    Let a cell be a really simple Python object, containing a pointer
    to a Python object and a pointer to a cell.  Both pointers may be
    NULL.  A Python implementation could be:

        class cell(object):

            def __init__(self):
                self.objptr = NULL
                self.cellptr = NULL

    The cellptr attribute is used for chaining cells together for
    searching built-ins; this will be explained later.

    Let a celldict be a mapping from strings (the names of a module's
    globals) to objects (the values of those globals), implemented
    using a dict of cells.  A Python implementation could be:

        class celldict(object):

            def __init__(self):
                self.__dict = {} # dict of cells

            def getcell(self, key):
                c = self.__dict.get(key)
                if c is None:
                    c = cell()
                    self.__dict[key] = c
                return c

            def cellkeys(self):
                return self.__dict.keys()

            def __getitem__(self, key):
                c = self.__dict.get(key)
                if c is None:
                    raise KeyError, key
                value = c.objptr
                if value is NULL:
                    raise KeyError, key
                else:
                    return value

            def __setitem__(self, key, value):
                c = self.__dict.get(key)
                if c is None:
                    c = cell()
                    self.__dict[key] = c
                c.objptr = value

            def __delitem__(self, key):
                c = self.__dict.get(key)
                if c is None or c.objptr is NULL:
                    raise KeyError, key
                c.objptr = NULL

            def keys(self):
                return [k for k, c in self.__dict.iteritems()
                        if c.objptr is not NULL]

            def items(self):
                return [k, c.objptr for k, c in self.__dict.iteritems()
                        if c.objptr is not NULL]

            def values(self):
                preturn [c.objptr for c in self.__dict.itervalues()
                        if c.objptr is not NULL]

            def clear(self):
                for c in self.__dict.values():
                    c.objptr = NULL

            # Etc.

    It is possible that a cell exists corresponding to a given key,
    but the cell's objptr is NULL; let's call such a cell empty.  When
    the celldict is used as a mapping, it is as if empty cells don't
    exist.  However, once added, a cell is never deleted from a
    celldict, and it is possible to get at empty cells using the
    getcell() method.

    The celldict implementation never uses the cellptr attribute of
    cells.

    We change the module implementation to use a celldict for its
    __dict__.  The module's getattr, setattr and delattr operations
    now map to getitem, setitem and delitem on the celldict.  The type
    of <module>.__dict__ and globals() is probably the only backwards
    incompatibility.

    When a module is initialized, its __builtins__ is initialized from
    the __builtin__ module's __dict__, which is itself a celldict.
    For each cell in __builtins__, the new module's __dict__ adds a
    cell with a NULL objptr, whose cellptr points to the corresponding
    cell of __builtins__.  Python pseudo-code (ignoring rexec):

        import __builtin__

        class module(object):

            def __init__(self):
                self.__dict__ = d = celldict()
                d['__builtins__'] = bd = __builtin__.__dict__
                for k in bd.cellkeys():
                    c = self.__dict__.getcell(k)
                    c.cellptr = bd.getcell(k)

            def __getattr__(self, k):
                try:
                    return self.__dict__[k]
                except KeyError:
                    raise IndexError, k

            def __setattr__(self, k, v):
                self.__dict__[k] = v

            def __delattr__(self, k):
                del self.__dict__[k]

    The compiler generates LOAD_GLOBAL_CELL <i> (and STORE_GLOBAL_CELL
    <i> etc.) opcodes for references to globals, where <i> is a small
    index with meaning only within one code object like the const
    index in LOAD_CONST.  The code object has a new tuple, co_globals,
    giving the names of the globals referenced by the code indexed by
    <i>.  No new analysis is required to be able to do this.

    When a function object is created from a code object and a celldict,
    the function object creates an array of cell pointers by asking the
    celldict for cells corresponding to the names in the code object's
    co_globals.  If the celldict doesn't already have a cell for a
    particular name, it creates and an empty one.  This array of cell
    pointers is stored on the function object as func_cells.  When a
    function object is created from a regular dict instead of a
    celldict, func_cells is a NULL pointer.

    When the VM executes a LOAD_GLOBAL_CELL <i> instruction, it gets
    cell number <i> from func_cells.  It then looks in the cell's
    PyObject pointer, and if not NULL, that's the global value.  If it
    is NULL, it follows the cell's cell pointer to the next cell, if it
    is not NULL, and looks in the PyObject pointer in that cell.  If
    that's also NULL, or if there is no second cell, NameError is
    raised.  (It could follow the chain of cell pointers until a NULL
    cell pointer is found; but I have no use for this.)  Similar for
    STORE_GLOBAL_CELL <i>, except it doesn't follow the cell pointer
    chain -- it always stores in the first cell.

    There are fallbacks in the VM for the case where the function's
    globals aren't a celldict, and hence func_cells is NULL.  In that
    case, the code object's co_globals is indexed with <i> to find the
    name of the corresponding global and this name is used to index the
    function's globals dict.


Additional Ideas

    - Never make func_cell a NULL pointer; instead, make up an array
      of empty cells, so that LOAD_GLOBAL_CELL can index func_cells
      without a NULL check.

    - Make c.cellptr equal to c when a cell is created, so that
      LOAD_GLOBAL_CELL can always dereference c.cellptr without a NULL
      check.

    With these two additional ideas added, here's Python pseudo-code
    for LOAD_GLOBAL_CELL:

        def LOAD_GLOBAL_CELL(self, i):
            # self is the frame
            c = self.func_cells[i]
            obj = c.objptr
            if obj is not NULL:
                return obj # Existing global
            return c.cellptr.objptr # Built-in or NULL

    - Be more aggressive:  put the actual values of builtins into module
      dicts, not just pointers to cells containing the actual values.

    There are two points to this:  (1) Simplify and speed access, which
    is the most common operation.  (2) Support faithful emulation of
    extreme existing corner cases.

    WRT  #2, the set of builtins in the scheme above is captured at the
    time a module dict is first created.  Mutations to the set of builtin
    names following that don't get reflected in the module dicts.  Example:
    consider files main.py and cheater.py:

    [main.py]
    import cheater
    def f():
        cheater.cheat()
        return pachinko()
    print f()

    [cheater.py]
    def cheat():
        import __builtin__
        __builtin__.pachinko = lambda: 666

    If main.py is run under Python 2.2 (or before), 666 is printed.  But
    under the proposal, __builtin__.pachinko doesn't exist at the time
    main's __dict__ is initialized.  When the function object for
    f is created, main.__dict__ grows a pachinko cell mapping to two
    NULLs.  When cheat() is called, __builtin__.__dict__ grows a pachinko
    cell too, but main.__dict__ doesn't know-- and will never know --about
    that.  When f's return stmt references pachinko, in will still find
    the double-NULLs in main.__dict__'s pachinko cell, and so raise
    NameError.

    A similar (in cause) break in compatibility can occur if a module
    global foo is del'ed, but a builtin foo was created prior to that
    but after the module dict was first created.  Then the builtin foo
    becomes visible in the module under 2.2 and before, but remains
    invisible under the proposal.

    Mutating builtins is extremely rare (most programs never mutate the
    builtins, and it's hard to imagine a plausible use for frequent
    mutation of the builtins -- I've never seen or heard of one), so it
    doesn't matter how expensive mutating the builtins becomes.  OTOH,
    referencing globals and builtins is very common.  Combining those
    observations suggests a more aggressive caching of builtins in module
    globals, speeding access at the expense of making mutations of the
    builtins (potentially much) more expensive to keep the caches in
    synch.

    Much of the scheme above remains the same, and most of the rest is
    just a little different.  A cell changes to:

        class cell(object):
            def __init__(self, obj=NULL, builtin=0):
                self.objptr = obj
                self.builtinflag = builtin

    and a celldict maps strings to this version of cells.  builtinflag
    is true when and only when objptr contains a value obtained from
    the builtins; in other words, it's true when and only when a cell
    is acting as a cached value.  When builtinflag is false, objptr is
    the value of a module global (possibly NULL).  celldict changes to:

        class celldict(object):

            def __init__(self, builtindict=()):
                self.basedict = builtindict
                self.__dict = d = {}
                for k, v in builtindict.items():
                    d[k] = cell(v, 1)

            def __getitem__(self, key):
                c = self.__dict.get(key)
                if c is None or c.objptr is NULL or c.builtinflag:
                    raise KeyError, key
                return c.objptr

            def __setitem__(self, key, value):
                c = self.__dict.get(key)
                if c is None:
                    c = cell()
                    self.__dict[key] = c
                c.objptr = value
                c.builtinflag = 0

            def __delitem__(self, key):
                c = self.__dict.get(key)
                if c is None or c.objptr is NULL or c.builtinflag:
                    raise KeyError, key
                c.objptr = NULL
                # We may have unmasked a builtin.  Note that because
                # we're checking the builtin dict for that *now*, this
                # still works if the builtin first came into existence
                # after we were constructed.  Note too that del on
                # namespace dicts is rare, so the expensse of this check
                # shouldn't matter.
                if key in self.basedict:
                    c.objptr = self.basedict[key]
                    assert c.objptr is not NULL # else "in" lied
                    c.builtinflag = 1
                else:
                    # There is no builtin with the same name.
                    assert not c.builtinflag

            def keys(self):
                return [k for k, c in self.__dict.iteritems()
                        if c.objptr is not NULL and not c.builtinflag]

            def items(self):
                return [k, c.objptr for k, c in self.__dict.iteritems()
                        if c.objptr is not NULL and not c.builtinflag]

            def values(self):
                preturn [c.objptr for c in self.__dict.itervalues()
                        if c.objptr is not NULL and not c.builtinflag]

            def clear(self):
                for c in self.__dict.values():
                    if not c.builtinflag:
                        c.objptr = NULL

            # Etc.

    The speed benefit comes from simplifying LOAD_GLOBAL_CELL, which
    I expect is executed more frequently than all other namespace
    operations combined:

        def LOAD_GLOBAL_CELL(self, i):
            # self is the frame
            c = self.func_cells[i]
            return c.objptr   # may be NULL (also true before)

    That is, accessing builtins and accessing module globals are equally
    fast.  For module globals, a NULL-pointer test+branch is saved.  For
    builtins, an additional pointer chase is also saved.

    The other part needed to make this fly is expensive, propagating
    mutations of builtins into the module dicts that were initialized
    from the builtins.  This is much like, in 2.2, propagating changes
    in new-style base classes to their descendants:  the builtins need to
    maintain a list of weakrefs to the modules (or module dicts)
    initialized from the builtin's dict.  Given a mutation to the builtin
    dict (adding a new key, changing the value associated with an
    existing key, or deleting a key), traverse the list of module dicts
    and make corresponding mutations to them.  This is straightforward;
    for example, if a key is deleted from builtins, execute
    reflect_bltin_del in each module:

        def reflect_bltin_del(self, key):
            c = self.__dict.get(key)
            assert c is not None # else we were already out of synch
            if c.builtinflag:
                # Put us back in synch.
                c.objptr = NULL
                c.builtinflag = 0
            # Else we're shadowing the builtin, so don't care that
            # the builtin went away.

    Note that c.builtinflag protects from us erroneously deleting a
    module global of the same name.  Adding a new (key, value) builtin
    pair is similar:

        def reflect_bltin_new(self, key, value):
            c = self.__dict.get(key)
            if c is None:
                # Never heard of it before:  cache the builtin value.
                self.__dict[key] = cell(value, 1)
            elif c.objptr is NULL:
                # This used to exist in the module or the builtins,
                # but doesn't anymore; rehabilitate it.
                assert not c.builtinflag
                c.objptr = value
                c.builtinflag = 1
            else:
                # We're shadowing it already.
                assert not c.builtinflag

    Changing the value of an existing builtin:

        def reflect_bltin_change(self, key, newvalue):
            c = self.__dict.get(key)
            assert c is not None # else we were already out of synch
            if c.builtinflag:
                # Put us back in synch.
                c.objptr = newvalue
            # Else we're shadowing the builtin, so don't care that
            # the builtin changed.


FAQs

    Q. Will it still be possible to:
       a) install new builtins in the __builtin__ namespace and have
          them available in all already loaded modules right away ?
       b) override builtins (e.g. open()) with my own copies
          (e.g. to increase security) in a way that makes these new
          copies override the previous ones in all modules ?

    A. Yes, this is the whole point of this design.  In the original
       approach, when LOAD_GLOBAL_CELL finds a NULL in the second
       cell, it should go back to see if the __builtins__ dict has
       been modified (the pseudo code doesn't have this yet).  Tim's
       "more aggressive" alternative also takes care of this.

    Q. How does the new scheme get along with the restricted execution
       model?

    A. It is intended to support that fully.

    Q. What happens when a global is deleted?

    A. The module's celldict would have a cell with a NULL objptr for
       that key.  This is true in both variations, but the "aggressive"
       variation goes on to see whether this unmasks a builtin of the
       same name, and if so copies its value (just a pointer-copy of the
       ultimate PyObject*) into the cell's objptr and sets the cell's
       builtinflag to true.

    Q. What would the C code for LOAD_GLOBAL_CELL look like?

    A. The first version, with the first two bullets under "Additional
       ideas" incorporated, could look like this:

       case LOAD_GLOBAL_CELL:
           cell = func_cells[oparg];
           x = cell->objptr;
           if (x == NULL) {
               x = cell->cellptr->objptr;
               if (x == NULL) {
                   ... error recovery ...
                   break;
               }
           }
           Py_INCREF(x);
           PUSH(x);
           continue;

       We could even write it like this (idea courtesy of Ka-Ping Yee):

       case LOAD_GLOBAL_CELL:
           cell = func_cells[oparg];
           x = cell->cellptr->objptr;
           if (x != NULL) {
               Py_INCREF(x);
               PUSH(x);
               continue;
           }
           ... error recovery ...
           break;

       In modern CPU architectures, this reduces the number of
       branches taken for built-ins, which might be a really good
       thing, while any decent memory cache should realize that
       cell->cellptr is the same as cell for regular globals and hence
       this should be very fast in that case too.

       For the aggressive variant:

       case LOAD_GLOBAL_CELL:
           cell = func_cells[oparg];
           x = cell->objptr;
           if (x != NULL) {
               Py_INCREF(x);
               PUSH(x);
               continue;
           }
           ... error recovery ...
           break;

    Q. What happens in the module's top-level code where there is
       presumably no func_cells array?

    A. We could do some code analysis and create a func_cells array,
       or we could use LOAD_NAME which should use PyMapping_GetItem on
       the globals dict.


Graphics

    Ka-Ping Yee supplied a drawing of the state of things after
    "import spam", where spam.py contains:

        import eggs

        i = -2
        max = 3

        def foo(n):
            y = abs(i) + max
            return eggs.ham(y + n)

    The drawing is at http://web.lfw.org/repo/cells.gif; a larger
    version is at http://lfw.org/repo/cells-big.gif; the source is at
    http://lfw.org/repo/cells.ai.


Comparison

    XXX Here, a comparison of the three approaches could be added.


Copyright

    This document has been placed in the public domain.



Local Variables:
mode: indented-text
indent-tabs-mode: nil
End:
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.