Go 1.18: Unser eigener Container

Ausgestattet mit den Typ-Parametern und Constraints können wir uns an ein etwas anspruchsvolleres Unternehmen wagen. Go verfügt von sich aus über keinen Set-Datentypen. Sammlungen von einzigartigen Werten müssen per map[Typ]struct{} impementiert werden. Die Werte werden als Schlüssel verwendet, als Datentyp benutzen wir struct{} (so sparen wir uns wenigstens den Speicher). Die Nutzung wirkt etwas unelegant, also abstrahieren wir es als generischen Datentyp.

type Set[T comparable] map[T]struct{}

Allein ist der Typ natürlich nicht viel besser als die direkte Nutzung von Map. Also erweitern wir ihn um eine Methode, um einen Wert hineinzuschreiben.

func (s Set[T]) Put(elem T) {
    s[elem] = struct{}{}
}

Wir können, wie gehabt, Methoden auf unserem generischen Datentyp definieren. Die Besonderheit ist allerdings, dass der Type Receiver (der Teil in den ersten Klammern) unseren generischen Parameter enthalten muss. Den Constraint müssen wir nicht nochmal wiederholen. Anschließend lässt sich der Typ-Parameter wie gewöhnlich verwenden. Eigene Typ-Parameter sind in den Methoden nicht zugelassen. Das Go-Team ist sich der Einschränkung bewusst, wartet jedoch auf Feedback aus der Community.

Mit ein paar weiteren Methoden ist unser eigener kleiner Datentyp komplett. Eine Len-Funktion ermöglicht es uns, die Anzahl der Elemente zu erfahren, Has prüft, ob ein Element im Set ist, Any gibt ein zufälliges Element zurück.

func (s Set[T]) Len() int {
    return len(s)
}
 
func (s Set[T]) Has(elem T) bool {
    _, ok := s[elem]
    return ok
}
 
func (s Set[T]) Any() T {
    for k := range s {
        return k
    }
    var t T
    return t
}

Bei der Any-Methode laufen wir in ein kleines Problem. Ist das Set leer, müssen wir ein leeres Element zurückgeben. Go erlaubt es uns allerdings nicht, einen generischen Typ zu initialisieren. Während new(T) und make(T) funktionieren, ist die Anwendbarkeit in unserem Fall eingeschränkt. new würde uns einen Pointer auf die Variable zurückgeben. make funktioniert nur mit integrierten Container-Typen. Eine Kurzinitialisierung per T{} wird verhindert. Wir behelfen uns, indem wir uns eine Variable vom Typ T definieren, die wir aber uninitialisiert lassen. So bekommen wir den leeren Wert für T und können diesen zurückgeben.

Zu guter Letzt bauen wir noch eine Map-Funktion, die eine Funktion f auf jedes Element von s anwendet und das Ergebnis in ein neues Set schreibt. Hier spielt das Generics-System seine volle Stärke aus. Die Typ-Parameter beziehen sich auf die Basistypen des Sets und der Funktion. Der Typ des Zielsets wird erst im Rückgabetyp definiert.

func Map[T, U comparable](set Set[T], f func(T) U) Set[U] {
    result := make(Set[U], len(set))
    for s := range set {
        result.Put(f(s))
    }
    return result
}

Go kann auch hier bei einem normalen Funktionsaufruf alle Typen korrekt ableiten. Hier wandeln wir alle int in oldSet in entsprechende string in newSet um. Dazu wenden wir einfach die entsprechende Funktion aus der Standardbibliothek auf das alte Set an.

newSet := Map(oldSet, strconv.Itoa)

Performance

Die Go-Entwickler haben sich bei der Implementierung von Generics für Stencils entschieden. Statt für jeden Typ eine eigene Maschinencode-Version der Funktion zu generieren, werden die Typen nach Speichergröße gruppiert. Für jede der Gruppen wird eine separate Funktion generiert und für alle Typen dieser Gruppe benutzt. Findet ein Zugriff auf Attribute der Variablen statt, generiert der Compiler automatisch entsprechende Funktionen für die spezifischen Typen. Dieser Ansatz hat einen großen Vorteil und einen kleinen Nachteil. Der Vorteil ist, dass nicht für jede Kombination von Typen eine Variante der Funktion gebaut werden muss. Das wirkt sich positiv auf die Kompilierzeit und die Größe der Binärdateien aus. Der Nachteil ist, dass wir nicht die volle Geschwindigkeit einer nativen Implementierung bekommen.

Erste Benchmarks ordnen die Performance zwischen einer nativen Implementierung und der Nutzung von Reflection ein. Wie üblich können wir in den nächsten Versionen Optimierungen erwarten.

Fazit

Go 1.18 bringt trotz der großen Sprachänderung keine Anpassungen in der Standardbibliothek mit. Das neue Constraints-Paket wurde mit dem Release Candidate wieder entfernt. Nur die Umbenennung von interface{} in any deutet auf die Generics hin. Die Go-Macher wollten sich zunächst auf die Sprachänderungen konzentrieren, da rückwärtskompatible Änderungen in der Standardbibliothek nicht trivial umzusetzen sind.

Die stabile Version von Go 1.18 war schon für Februar 2022 angekündigt, diesen Termin konnte das Go-Team allerdings nicht halten. Die Release-Notes finden sich auf https://golang.org/doc/go1.18.

Tim Scheuermann ist Software-Entwickler aus Berlin und programmiert seit 2012 in Go. Seine Begeisterung für Computer wurde schon in der Grundschule geweckt und hat ihn durch das Informatikstudium begleitet. Er ist Mitorganisator des Berliner Go Meetups.