Traits-basierte Container in Ada

Inhaltsverzeichnis

Entwickler müssen beim Design von Container-Bibliotheken den Spagat zwischen Performance, Effizienz und Sicherheit meistern. Mithilfe von Templates und Policies können sie die Speicherverwaltung steuern und damit die Leistung des Containers auf gleichem Sicherheitsniveau erhöhen.

Alle zeitgemäßen Programmiersprachen besitzen in ihrer Standardbibliothek
eine Reihe von Containern, um die Realisierung von Anwendungen zu erleichtern. Solche Container enthalten in der Regel Listen, Vektoren, assoziative Arrays (oder Dictionaries oder Maps) und Mengen (Sets). Andere Bibliotheken umfassen auch Graph-Datenstrukturen. Die Autoren dieser Bibliotheken müssen Design-Entscheidungen treffen, die verschiedene Aspekte der Container beeinflussen:

• Effizienz: Wenn der Code nicht mindestens so effizient wie von Hand programierte Datenstrukturen ist, werden Entwickler neue, eigene Container implementieren.
• Sicherheit: Der Container muss es dem Benutzer leicht machen – wie Zeiger, die einen ungültigen Wert enthalten (Dangling pointer), oder den gleichzeitigen Zugriff auf Daten von verschiedenen Threads (Thread-Sicherheit). Da ein solches Design meist zusätzliche Laufzeitprüfungen erfordert, geht dies zu Lasten der Effizienz.
  
• Wiederverwendbarkeit: Die Container und vor allem ihre Algorithmen sollten sich in vielen Umgebungen einsetzen lassen. Typische Beispiele sind das Sortieren und Zusammenführen von zwei Datenstrukturen und Suche in Graphen.
• Verifizierbarkeit:Nutzer von Tools wie SPARK für die formale Verifikation der Korrektheit des Codes sollten diese Container ebenfalls nutzen können. Das allerdings beschränkt die Speicherverwaltung und benötigt Vorbedingungen und Nachbedingungen (Pre- und Postconditions).
  

Performance versus Sicherheit

Mehr Infos

Update

Zur Konkretisierung einiger Sachverhalte hat der Artikel an diversen Stellen Überarbeitungen gegenüber der ursprünglich online gestellten Version erfahren.

Die Programmiersprache C++ legt besonderes Augenmerk auf die Performance. Die STL (Standard Template Library) ist nicht sicher in dem Sinn, dass man beispielsweise weiterhin einen Iterator nutzen kann, nachdem das zugehörige Element gelöscht wurde. STL-Algorithmen sind dank des Konzepts der Iteratoren und Template-Spezialisierung in hohem Maße wiederverwendbar. Ein Algorithmus wie find erhält den Container als zusätzlichen Parameter; für einen Vektor wird er als Schleife implementiert, die alle Elemente der Reihe nach überprüft, während er sich für eine Menge viel effizienter implementieren lässt.

Ada wiederum legt großen Wert auf Sicherheit. Die Sprache verlangt standardmäßig eine große Zahl von Checks, um sicherzustellen, dass der Benutzer beispielsweise während der Iteration den Container nicht verändert. Diese zusätzlichen Überprüfungen wirken sich jedoch negativ auf die Performance aus. Die Wiederverwendbarkeit der Algorithmen lässt ebenfalls zu wünschen übrig, da eine Funktion immer spezifizieren muss, welche Art von Container erwartet wird; die Container teilen keinen Code. Es ist aber über Pragmas möglich, die zusätzlichen Checks des Containers zu deaktivieren und damit die Performance auf Kosten der Sicherheit zu verbessern.

Verschiedene Container-Typen

Container unterscheiden sich entlang folgender beiden Achsen: Erstens speichern sie Elemente entweder mit einer bekannten (bestimmte Elemente) oder unbekannten Größe (unbestimmte Elemente); zweitens speichern sie eine bekannte maximale Anzahl von Elementen (begrenzter Container) oder eine unbegrenzte Anzahl von Elementen (unbegrenzter Container). Diese Eigenschaften wirken sich darauf aus, wann und wie oft Speicher zugewiesen wird – mit Konsequenzen für die Performance.

C++ versteckt diese Achsen vor dem Benutzer. Dank Template-Spezialisierung wählt die STL automatisch die Implementierung jeder Container-Art, obwohl das nicht immer die beste Wahl sein muss. In Ada hingegen müssen die Nutzer wählen, welche Variante sie verwenden, wenn sie einen Container instanziieren. Das erlaubt zwar mehr Kontrolle, führt aber zu höherer Komplexität, da der Nutzer die Konzepte verstehen muss, und oft zu Code-Duplikation in der Bibliothek.

Es gibt noch andere Überlegungen bei der Gestaltung einer Container-Bibliothek, ob beispielsweise die Container Thread-sicher sein sollen, der Speicher einem speziellen Pool zugeordnet wird – Ada nennt sie storage_pools, C++ nennt sie allocators –, oder die Speicherung nicht flücht­ig sein soll, und vieles andere mehr.

Generische Listen

Eine Bibliothek könnte konzeptionell eine spezialisierte Anwendung für alle oben beschriebenen Aspekte bieten. Doch eine, die alle diese Kombinationen unterstützt, wäre sehr umfangreich. Einen Ausweg bildet der korrekte Einsatz von generischer Programmierung oder von Vorlagen beziehungsweise Templates. Für diesen Artikel hat der Autor einen einfachen Container erstellt: eine in Ada implementierte Liste. Er ignoriert dabei, dass es für diese Sprache bereits Standard-Container gibt.

Die Liste sollte in der Lage sein, jede Art von Element zu speichern, darunter beispielsweise eine Zeichenkette (String), deren Größe vor der Kompilierung nicht bekannt ist. Da der Typ Element nicht bekannt ist, muss es ein generisches Paket sein. Der anfängliche Code würde wie folgt aussehen:

generic
   type Element (<>) is private;
package Lists is
   type List is private;
   procedure Prepend (Self : in out List; E : Element);
private
   type Element_Access is access Element;
   type Node_Record;
   type Node is access Node_Record;
   type Node_Record is record
       Value : Element_Access;
       Next : Node;
   end record;
   type List is record
       Head : Node;
   end record;
end Lists;

package body Lists is
   procedure Prepend (Self : in out List; E : Element) is
   begin
       Self.Head := new Node_Record'
         (Value => new Element'(E), Next => Self.Head);
  end Prepend;
end Lists;

Der Code deklariert eine Liste als Zeiger zu einem Knoten (Node), der selbst ein Element enthält und auf den nächsten Knoten in der Liste verweist. Wenn man vor der Liste ein Element hinzufügt, wird nur der Anfang der Liste verändert. Das erfolgt mit der Ada Aggregation Syntax, damit alle Felder des Knotens korrekt initialisiert werden, selbst wenn Nutzer später ein anderes Feld wie Tail hinzufügen.

Diese Implementierung funktioniert sehr gut und ist in der Tat nahezu optimal für eine unbegrenzte Liste unbestimmter Elemente. Man benötigt eine Zuordnung für den Knoten und eine für das Element (da seine statische Größe nicht bekannt ist). Allerdings senken diese beiden Allokationen die Performance der Listen (im Vergleich zu anderen Implementierungen) für den Fall, in dem die Liste zur Speicherung von Integer-Werten verwendet werden soll. Da ein Integer immer die gleiche Größe hat, lässt er sich direkt in einem Knoten speichern; es ist nicht mehr notwendig, hier den entsprechenden Speicher zu allozieren.