Zurückgestellt

Obwohl dieser PEP eine nette Idee ist, hat sich bisher niemand gemeldet, der die Unterschiede zwischen diesem PEP, PEP 266 und PEP 267 ausarbeiten könnte. Daher wird er zurückgestellt.

Zusammenfassung

Dieser PEP beschreibt einen weiteren Ansatz zur Optimierung des Zugriffs auf globale Variablen eines Moduls, der eine Alternative zu PEP 266 (Optimizing Global Variable/Attribute Access von Skip Montanaro) und PEP 267 (Optimized Access to Module Namespaces von Jeremy Hylton) darstellt.

Die Erwartung ist, dass schließlich ein Ansatz ausgewählt und implementiert wird; möglicherweise werden zuerst mehrere Ansätze prototypisiert.

Description

(Hinweis: Jason Orendorff schreibt: „Ich habe das einmal implementiert, vor langer Zeit, glaube ich für Python 1.5-ish. Ich habe es so weit gebracht, dass es nur 15% langsamer war als gewöhnliches Python, dann habe ich es aufgegeben. ;) In meiner Implementierung waren „cells“ echte First-Class-Objekte und „celldict“ war eine Kopie und Hack-Version eines Dictionary. Ich vergesse, wie der Rest funktionierte.“ Referenz: https://mail.python.org/pipermail/python-dev/2002-February/019876.html)

Sei eine Zelle ein wirklich einfaches Python-Objekt, das einen Zeiger auf ein Python-Objekt und einen Zeiger auf eine weitere Zelle enthält. Beide Zeiger können NULL sein. Eine Python-Implementierung könnte so aussehen:

class cell(object):

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

Das Attribut `cellptr` wird zum Verketten von Zellen für die Suche nach Built-ins verwendet; dies wird später erklärt.

Sei ein `celldict` eine Abbildung von Strings (den Namen der globalen Variablen eines Moduls) auf Objekte (die Werte dieser globalen Variablen), implementiert als Dictionary von Zellen. Eine Python-Implementierung könnte so aussehen:

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.

Es ist möglich, dass eine Zelle für einen gegebenen Schlüssel existiert, aber der `objptr` der Zelle ist NULL; nennen wir eine solche Zelle leer. Wenn das `celldict` als Abbildung verwendet wird, ist es so, als ob leere Zellen nicht existieren. Sobald eine Zelle jedoch zu einem `celldict` hinzugefügt wurde, wird sie niemals gelöscht, und es ist möglich, auf leere Zellen über die Methode getcell() zuzugreifen.

Die `celldict`-Implementierung verwendet niemals das `cellptr`-Attribut von Zellen.

Wir ändern die Modulimplementierung, um ein `celldict` für sein __dict__ zu verwenden. Die Operationen `getattr`, `setattr` und `delattr` des Moduls werden nun auf `getitem`, `setitem` und `delitem` des `celldict` abgebildet. Der Typ von <module>.__dict__ und globals() ist wahrscheinlich die einzige Rückwärtsinkompatibilität.

Wenn ein Modul initialisiert wird, wird sein __builtins__ aus dem __dict__ des Moduls __builtin__ initialisiert, welches selbst ein `celldict` ist. Für jede Zelle in __builtins__ fügt das __dict__ des neuen Moduls eine Zelle mit einem NULL objptr hinzu, deren `cellptr` auf die entsprechende Zelle von __builtins__ zeigt. Python-Pseudocode (rexec ignoriert)

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]

Der Compiler generiert `LOAD_GLOBAL_CELL` (und `STORE_GLOBAL_CELL` usw.) Opcodes für Referenzen auf globale Variablen, wobei ` ein kleiner Index ist, der nur innerhalb eines Codeobjekts eine Bedeutung hat, ähnlich dem Konstantenindex in `LOAD_CONST`. Das Codeobjekt hat ein neues Tupel, `co_globals`, das die Namen der globalen Variablen enthält, auf die durch ` verwiesen wird. Es sind keine neuen Analysen erforderlich, um dies tun zu können.

Wenn ein Funktions-Objekt aus einem Code-Objekt und einem `celldict` erstellt wird, erstellt das Funktions-Objekt ein Array von Zellenzeigern, indem es das `celldict` nach Zellen abfragt, die den Namen im `co_globals` des Code-Objekts entsprechen. Wenn das `celldict` noch keine Zelle für einen bestimmten Namen hat, erstellt es eine leere. Dieses Array von Zellenzeigern wird im Funktions-Objekt als `func_cells` gespeichert. Wenn ein Funktions-Objekt aus einem regulären Dictionary und nicht aus einem `celldict` erstellt wird, ist `func_cells` ein `NULL`-Zeiger.

Wenn die VM eine `LOAD_GLOBAL_CELL` ` Anweisung ausführt, holt sie die Zelle Nummer ` aus `func_cells`. Sie schaut dann in den `PyObject`-Zeiger der Zelle, und wenn dieser nicht NULL ist, ist dies der Wert der globalen Variable. Wenn er NULL ist, folgt sie dem `cell`-Zeiger der Zelle zur nächsten Zelle, und wenn dieser nicht NULL ist, schaut sie in den `PyObject`-Zeiger in dieser Zelle. Wenn auch dieser NULL ist oder wenn es keine zweite Zelle gibt, wird ein `NameError` ausgelöst. (Sie könnte der Kette von `cell`-Zeigern folgen, bis ein NULL `cell`-Zeiger gefunden wird; aber ich habe keinen Nutzen dafür.) Ähnlich für `STORE_GLOBAL_CELL` `, außer dass sie der `cell`-Zeigerkette nicht folgt – sie speichert immer in der ersten Zelle.

Es gibt Fallbacks in der VM für den Fall, dass die globalen Variablen der Funktion kein `celldict` sind und daher `func_cells` NULL ist. In diesem Fall wird `co_globals` des Code-Objekts mit ` indiziert, um den Namen der entsprechenden globalen Variable zu finden, und dieser Name wird verwendet, um das Dictionary der globalen Variablen der Funktion zu indizieren.

Zusätzliche Ideen

• Mach niemals `func_cell` zu einem NULL Zeiger; erstelle stattdessen ein Array von leeren Zellen, damit `LOAD_GLOBAL_CELL` `func_cells` indizieren kann, ohne eine NULL-Prüfung durchführen zu müssen.
• Setze `c.cellptr` gleich `c`, wenn eine Zelle erstellt wird, damit `LOAD_GLOBAL_CELL` `c.cellptr` ohne NULL-Prüfung dereferenzieren kann.

  Mit diesen beiden zusätzlichen Ideen ist hier der Python-Pseudocode für `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
  

• Sei aggressiver: packe die tatsächlichen Werte von Built-ins in Modul-Dictionaries, nicht nur Zeiger auf Zellen, die die tatsächlichen Werte enthalten.

  Dafür gibt es zwei Punkte: (1) Vereinfachung und Beschleunigung des Zugriffs, was die häufigste Operation ist. (2) Unterstützung der getreuen Emulation extremer bestehender Eckfälle.

  Bezüglich #2 wird der Satz von Built-ins im obigen Schema zu dem Zeitpunkt erfasst, an dem ein Modul-Dictionary zum ersten Mal erstellt wird. Mutationen am Satz von Built-in-Namen, die danach erfolgen, spiegeln sich nicht in den Modul-Dictionaries wider. Beispiel: Betrachte die Dateien main.py und cheater.py:

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

  Wenn main.py unter Python 2.2 (oder früher) ausgeführt wird, wird 666 ausgegeben. Unter dem Vorschlag existiert __builtin__.pachinko jedoch nicht, wenn main`s __dict__ initialisiert wird. Wenn das Funktions-Objekt für f erstellt wird, wächst main.__dict__ um eine Pachinko-Zelle, die auf zwei NULLs abgebildet ist. Wenn cheat() aufgerufen wird, wächst __builtin__.__dict__ ebenfalls um eine Pachinko-Zelle, aber main.__dict__ weiß nichts davon – und wird es auch nie erfahren. Wenn die Return-Anweisung von f auf Pachinko verweist, findet sie immer noch die doppelten NULLs in der Pachinko-Zelle von main.__dict__ und löst somit NameError aus.

  Ein ähnlicher Bruch der Kompatibilität (in der Ursache) kann auftreten, wenn eine Modul-Globale `foo` gelöscht wird, aber eine Built-in `foo` vor diesem Zeitpunkt, aber nach der ersten Erstellung des Modul-Dictionaries erstellt wurde. Dann wird die Built-in `foo` im Modul unter 2.2 und davor sichtbar, bleibt aber unter dem Vorschlag unsichtbar.

  Das Mutieren von Built-ins ist extrem selten (die meisten Programme mutieren die Built-ins nie, und es ist schwer vorstellbar, einen plausiblen Nutzen für häufiges Mutieren der Built-ins zu finden – ich habe noch nie einen gesehen oder davon gehört). Daher spielt es keine Rolle, wie teuer das Mutieren der Built-ins wird. Andererseits ist das Referenzieren von globalen Variablen und Built-ins sehr häufig. Aus diesen Beobachtungen kombiniert ergibt sich ein aggressiveres Caching von Built-ins in Modul-Globalen, was den Zugriff auf Kosten der (potenziell viel) teureren Mutationen der Built-ins zur Synchronisation der Caches beschleunigt.

  Ein Großteil des obigen Schemas bleibt gleich, und der Rest ist nur ein wenig anders. Eine Zelle ändert sich zu:

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

  und ein `celldict` bildet Strings auf diese Version von Zellen ab. `builtinflag` ist wahr, wenn und nur wenn `objptr` einen Wert enthält, der von den Built-ins erhalten wurde; mit anderen Worten, es ist wahr, wenn und nur wenn eine Zelle als gecacheter Wert fungiert. Wenn `builtinflag` falsch ist, ist `objptr` der Wert einer Modul-Globalen (möglicherweise NULL). `celldict` ändert sich zu:

  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 expense 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.
  

  Der Geschwindigkeitsvorteil kommt von der Vereinfachung von `LOAD_GLOBAL_CELL`, von dem ich erwarte, dass er häufiger ausgeführt wird als alle anderen Namespace-Operationen zusammen.

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

  Das heißt, der Zugriff auf Built-ins und der Zugriff auf Modul-Globale sind gleich schnell. Für Modul-Globale wird ein NULL-Zeiger-Test+Verzweigung eingespart. Für Built-ins wird auch ein zusätzlicher Zeiger-Chase eingespart.

  Der andere Teil, der notwendig ist, damit dies funktioniert, ist teuer: die Weitergabe von Mutationen von Built-ins an die Modul-Dictionaries, die aus den Built-ins initialisiert wurden. Dies ähnelt dem, was in 2.2 geschah, um Änderungen in neuen Basisklassen an ihre Nachkommen weiterzugeben: Die Built-ins müssen eine Liste von Weakrefs zu den Modulen (oder Modul-Dictionaries) pflegen, die aus dem Built-in-Dictionary initialisiert wurden. Bei einer Mutation des Built-in-Dictionaries (Hinzufügen eines neuen Schlüssels, Ändern des Werts eines vorhandenen Schlüssels oder Löschen eines Schlüssels) traversieren Sie die Liste der Modul-Dictionaries und nehmen entsprechende Mutationen vor. Dies ist unkompliziert; wenn beispielsweise ein Schlüssel aus den Built-ins gelöscht wird, führen Sie `reflect_bltin_del` in jedem Modul aus:

  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.
  

  Beachten Sie, dass `c.builtinflag` uns davor schützt, fälschlicherweise eine Modul-Globale mit demselben Namen zu löschen. Das Hinzufügen eines neuen (Schlüssel, Wert) Built-in-Paares ist ähnlich:

  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
  

  Das Ändern des Werts eines bestehenden Built-ins:

  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

• F: Wird es immer noch möglich sein,

  a) neue Built-ins im `__builtin__`-Namespace zu installieren und sie sofort in allen bereits geladenen Modulen verfügbar zu haben?

  b) Built-ins (z.B. `open()`) durch eigene Kopien zu überschreiben (z.B. zur Erhöhung der Sicherheit) auf eine Weise, die diese neuen Kopien die vorherigen in allen Modulen überschreiben lässt?

  A: Ja, das ist der Sinn dieses Designs. Im ursprünglichen Ansatz, wenn `LOAD_GLOBAL_CELL` ein `NULL` in der zweiten Zelle findet, sollte es zurückgehen, um zu prüfen, ob das `__builtins__`-Dictionary geändert wurde (der Pseudocode hat dies noch nicht). Tims „aggressivere“ Alternative kümmert sich ebenfalls darum.

• F: Wie kommt das neue Schema mit dem eingeschränkten Ausführungsmodell zurecht?

  A: Es ist beabsichtigt, dieses vollständig zu unterstützen.

• F: Was passiert, wenn eine globale Variable gelöscht wird?

  A: Das `celldict` des Moduls hätte für diesen Schlüssel eine Zelle mit einem `NULL` `objptr`. Dies gilt für beide Varianten, aber die „aggressive“ Variante prüft weiter, ob dies eine Built-in mit demselben Namen freilegt, und wenn ja, kopiert sie deren Wert (nur eine Zeigerkopie des endgültigen `PyObject*`) in den `objptr` der Zelle und setzt die `builtinflag` der Zelle auf wahr.

• F: Wie würde der C-Code für `LOAD_GLOBAL_CELL` aussehen?

  A: Die erste Version, mit den ersten beiden Aufzählungspunkten unter „Zusätzliche Ideen“ integriert, könnte so aussehen:

  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;
  

  Wir könnten es sogar so schreiben (Idee von 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;
  

  Auf modernen CPU-Architekturen reduziert dies die Anzahl der Verzweigungen für Built-ins, was ein wirklich guter Punkt sein könnte, während jeder anständige Cache feststellen sollte, dass `cell->cellptr` dasselbe ist wie `cell` für reguläre globale Variablen, und daher sollte dies in diesem Fall auch sehr schnell sein.

  Für die aggressive Variante:

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

• F: Was passiert im Top-Level-Code des Moduls, wo es vermutlich kein `func_cells`-Array gibt?

  A: Wir könnten eine Code-Analyse durchführen und ein `func_cells`-Array erstellen, oder wir könnten `LOAD_NAME` verwenden, was `PyMapping_GetItem` auf dem globalen Dictionary verwenden sollte.

Grafiken

Ka-Ping Yee lieferte eine Zeichnung des Zustands der Dinge nach `import spam`, wobei `spam.py` Folgendes enthält:

import eggs

i = -2
max = 3

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

Die Zeichnung ist unter http://web.lfw.org/repo/cells.gif; eine größere Version unter http://lfw.org/repo/cells-big.gif; die Quelle unter http://lfw.org/repo/cells.ai.

Vergleich

XXX Hier könnte ein Vergleich der drei Ansätze hinzugefügt werden.

Urheberrecht

Dieses Dokument wurde gemeinfrei erklärt.