Ist Codeduplizierung ein notwendiges Übel in C?

16

Ich bin ziemlich neu in C und frage mich, ob das Kopieren von Code ein notwendiges Übel ist, wenn es darum geht, allgemeine Datenstrukturen und C im Allgemeinen zu schreiben.

Ich könnte hash mapzum Beispiel versuchen, eine generische Implementierung für eine zu schreiben , aber ich finde das Endergebnis immer chaotisch. Ich könnte auch eine spezielle Implementierung für diesen speziellen Anwendungsfall schreiben, den Code klar und einfach zu lesen und zu debuggen. Letzteres würde natürlich zu einigen Code-Duplikaten führen.

Sind generische Implementierungen eine Norm oder schreiben Sie unterschiedliche Implementierungen für jeden Anwendungsfall?

Gerstmann
quelle
11
Das moralische Dilemma, das Sie beschreiben, ist nicht nur für C. Anekdotischerweise finde ich, dass die Messlatte für die Erstellung einer generischen Implementierung ziemlich hoch ist, es sei denn, Sie haben ein Publikum dafür. Der Aufwand für die Erstellung einer guten generischen Implementierung übersteigt die Punktlösung IME bei weitem.
Robert Harvey
1
@ Kevincline: Nun, Java hat Generika. Zugegeben, es ist die Art von Generika, bei der man nicht auf den Mann hinter dem Vorhang achtet.
Robert Harvey
1
Und vor Generics hätten Sie Object bzw. Float, Double, Integer und Long übergeben können.
Daniel Kaplan
3
Deja vu ist eine Code-Geruchsprüfung und eine Präferenz für DRY ist die Wurzel aller Best Practices, die es wert sind, IMO Beachtung zu schenken. Aber ich habe mir in OOP-orientierten Sprachen in den Fuß geschossen und versucht, Doppelarbeit zu vermeiden. Wenn Sie nicht unnötig miteinander in Beziehung stehende Bedenken binden oder die Lesbarkeit zerstören, damit aus zwei ähnlichen Funktionen eine wird, würde ich mich in fast jeder Sprache an den Instinkt halten.
Erik Reppen

Antworten:

27

C erschwert das Schreiben von generischem Code. Im Gegensatz zu C ++, das Ihnen Vorlagen und virtuelle Funktionen bietet, verfügt C nur über drei Mechanismen zum Schreiben von generischem Code:

  1. void* Zeiger
  2. Präprozessor-Makros
  3. Funktionszeiger

void* Zeiger sind alles andere als ideal, da Sie die gesamte vom Compiler bereitgestellte Typensicherheit verlieren, was zu einem schwer zu debuggenden undefinierten Verhalten führen kann, das sich aus ungültigen Typumwandlungen ergibt.

Präprozessor-Makros weisen bekannte Nachteile auf. Die Präprozessor-Erweiterung ist im Grunde genommen nur ein Such- / Ersetzungsmechanismus, der vor der Kompilierungsphase ausgeführt wird und wiederum zu schwer zu debuggenden Fehlern führen kann. Das archetypische Beispiel ist so etwas wie :, #define add(x) (x+x)wo xzweimal inkrementiert werden kann, wenn Sie anrufen add(i++). Sie können generischen Code im Vorlagenstil vollständig mit C-Makros schreiben, aber das Ergebnis ist wirklich abscheulich und schwer zu pflegen .

Funktionszeiger bieten eine gute Möglichkeit , generischen Code zu schreiben, aber leider sie nicht mit bieten Typ Allgemeinheit - sie bieten lediglich die Möglichkeit des Laufzeit - Polymorphismus (weshalb zum Beispiel ist die Standardbibliothek qsortnoch eine Funktion benötigt , die dauern void*Zeiger.)

Sie können Klassenhierarchien in C auch mithilfe von Strukturen implementieren, wie dies in der GLib-Bibliothek erfolgt, die eine generische GObjectBasisklasse bereitstellt . Dies hat jedoch ähnliche Probleme wie die Verwendung von void*Zeigern, da Sie sich beim Up- und Downcast immer noch auf potenziell unsichere manuelle Casts verlassen müssen.

Also ja, C macht es schwierig, Code zu schreiben, der sowohl allgemein als auch sicher und leicht zu warten ist. Leider kann dies zu einer Duplizierung des Codes führen. Große C-Projekte verwenden häufig Skriptsprachen, um sich wiederholenden Code während des Erstellungsprozesses zu generieren.

Charles Salvia
quelle
1
Man könnte auch repetitiven C-Code mit externen Template-Sprachen / Tools oder einem Shell-Skript oder mit ant oder ... generieren
Job
Was ist diese von Google verschleierte russische URL, die Sie in Ihre Antwort eingefügt haben? Wenn ich darauf klicke, wird in meinem Browser eine Aufforderung zum Öffnen angezeigt. Ist das sicher?
Robert Harvey
2
@RobertHarvey Meine Antivirus- und Sicherheitsscans sind der Meinung, dass dies in Ordnung ist. Es ist eine C-Sprache Header-Datei mit der Erweiterung .h. Es scheint echt.
maple_shaft
@maple_shaft: OK. Ich habe die Googlisierung um den Link entfernt.
Robert Harvey
Es ist nur eine Klartext-.h-Datei (C-Header)
Charles Salvia
15

Ich kann nicht für andere sprechen, aber nach meiner persönlichen Erfahrung mit C war das Kopieren von Code kein großes Problem. Ob dies an Projektgrößen liegt, oder an einem bezaubernden Sampleset kann ich nicht sagen. Es gibt jedoch drei Faustregeln, denen ich folge und die meines Erachtens anwendbar sind. In keiner bestimmten Reihenfolge sind sie ...

  1. Schreiben Sie für das, was benötigt wird. Allgemeinheit kann später kommen, wenn es benötigt wird.
  2. Wenn Allgemeingültigkeit erforderlich ist, können Leerzeiger, Funktionszeiger und Strukturgrößen von unschätzbarem Wert sein. Die Routine qsort () verwendet beispielsweise alle drei.
  3. Geben Sie Gewicht, um Ihren Code klar zu machen.
Sparky
quelle
5

Es ist erwähnenswert, dass Sie möglicherweise keine vollständig generische Lösung benötigen, um die Codeduplizierung zu reduzieren. Manchmal sind gewöhnliches Refactoring und ein wenig Generalisierung der Methoden ausreichend.

Wenn Sie eine verallgemeinerte Lösung für ein breites Publikum schreiben, müssen Sie Folgendes berücksichtigen:

  1. Auf welche neuartigen Arten könnte der Verbraucher Ihren Code verwenden, und wie begegnen Sie ihnen?
  2. Welche Fehler muss ich abfangen? Welche Fehler sollte ich nicht fangen?
  3. Wie robust muss die API sein? Wie viele Überladungen muss ich bereitstellen?
  4. Welche Sicherheitsmaßnahmen muss ich treffen, damit der Code nicht für böse Zwecke verwendet werden kann?

Eric Lippert hat einen ganzen Artikel über eine einzelne Entwurfsentscheidung im .NET Framework-Code geschrieben. Alles in allem ist es oft einfacher, nur umzugestalten.

Robert Harvey
quelle
3

Normalerweise verwende ich eine generische Implementierung wie glib's . Wenn das Casting dann zu nervig wird, erstelle einen kleinen typspezifischen Wrapper dafür. In C ist jedoch viel Casting zu erwarten, ebenso wie bei der Verwendung von a void*als generischer Typ. Was in einer anderen Sprache als "chaotisch" angesehen wird, ist also nur typisch C. Erschreckenderweise sieht es bei Ihnen viel natürlicher aus Erfahren Sie mehr in der Sprache.

Karl Bielefeldt
quelle
2
"Was in einer anderen Sprache als" chaotisch "angesehen wird, ist nur ein typisches C. Es sieht beängstigend viel natürlicher aus, wenn Sie mehr Erfahrung in der Sprache haben." Hahaha! C war schon immer eine meiner Lieblingssprachen, aber das ist immer noch ziemlich lustig!
GlenPeterson
0

Ihr Problem der Wiederverwendbarkeit ist nicht nur in C. Es gibt jedoch einige ausgezeichnete und sehr wiederverwendbare HashMap-Implementierungen, auf die Sie sich stützen können. Eine, die es seit ein oder zwei Jahrzehnten gibt, ist in Java: http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

Alle Java-Sammlungen, einschließlich HashMap, werden für Java 8 neu geschrieben, um die Idee eines Iterators loszuwerden. Stattdessen müssen Sie der Sammlung eine Funktion übergeben, damit sie intern iterieren kann. Dies ist ein großer Gewinn für das Schreiben von gleichzeitigem Code - die Sammlung kann die Parallelität intern verwalten, sodass der Client dies nicht muss. Die meisten Programmierer sind es jedoch nicht gewohnt, Funktionszeiger zu übergeben. Dies ist eine gute Erklärung dafür, wohin HashMap führt: http://cr.openjdk.java.net/~briangoetz/lambda/collections-overview.html

Die Syntax von Scala macht es möglicherweise schwierig, so etwas in C zu übersetzen. Hier ist jedoch ein Beispiel für eine Sammlung, die bereits so funktioniert wie die Java 8-Sammlungen - standardmäßig unveränderlich, mit verschiedenen Transformationsmethoden, unter Verwendung von Funktionszeigern und anderen coole Sachen wie teilweise Bewerbung: http://www.scala-lang.org/api/current/index.html#scala.collection.Map

Wenn Sie mit HashMaps und anderen erweiterten Datenstrukturen viel arbeiten, sollten Sie sich eine Sprache ansehen, die diese unterstützt.

Zurück zur Idee der Code-Vervielfältigung im Allgemeinen: Sie können wirklich schnell Code schreiben, indem Sie ihn ausschneiden und einfügen, aber es entsteht schrecklicher Code. Ich würde sagen, dass es in Wegwerf-Code wie Einmalberichten akzeptabel ist. Manchmal ist es auch in Ordnung, wenn kein Code nachgelagert ist, wie z. B. UI-Code, der nur einen Bildschirm erstellt, von dem nichts anderes abhängt, aber das ist im besten Fall ein sehr grauer Bereich.

Ich halte es nicht für zu stark vereinfacht, zu sagen, dass Sie jedes Mal, wenn Sie feststellen, dass Sie Code duplizieren, eine Funktion erstellen sollten. Die Fehler, die Sie in einer Kopie des Codes und nicht in der anderen beheben, reichen aus, um eine Funktion zu erstellen.

GlenPeterson
quelle
1
- "Ich halte es nicht für zu stark vereinfacht, zu sagen, dass Sie jedes Mal, wenn Sie feststellen, dass Sie Code duplizieren, eine Funktion erstellen sollten" - In C ist dies eine zu starke Vereinfachung. Versuchen Sie, einen Stapel in C für Ganzzahlen, Doppelzahlen und Zeichenfolgen zu erstellen, ohne die Push- und Pop-Funktionen für jeden Datentyp zu duplizieren.
mike30
@mike Ist das nicht möglich mit leeren Zeigern?
Sakisk
@mike - guter Punkt. Ein Kontrapunkt wäre jedoch, dass Sie Stack für jeden Datentyp so implementieren könnten, dass Sie Stack nicht erneut implementieren müssen. Das Ziel ist also nicht numberOfImplementations = 1, sondern eher 5. Möglicherweise können Sie die intImplementierung für chars zum Laufen bringen ... Es ist so lange her, dass ich C verwendet habe, dass ich mich nicht mehr erinnern kann.
GlenPeterson
1
@faif. Ja, aber die Notwendigkeit, leere Zeiger zu verwenden, macht den Punkt für C aus. Casting-Zeiger sind langsamer und weniger elegant als Alternativen in C ++. Das Duplizieren des Codes steht etwas höher in der Liste der möglichen Optionen, wenn in C codiert wird.
mike30
@ mike30 Gibt es Beweise / Referenzen zu: "Das Umsetzen von Zeigern in C ist langsamer als das Umsetzen von Alternativen in C ++?"
Sakisk
0

Ich frage mich, ob das Kopieren von Code ein notwendiges Übel ist, wenn es darum geht, gemeinsame Datenstrukturen und C im Allgemeinen zu schreiben.

In C absolut für mich, als jemand, der zwischen C und C ++ springt. Ich dupliziere auf jeden Fall täglich mehr triviale Dinge in C als in C ++, aber absichtlich, und ich sehe es nicht unbedingt als "böse" an, da es zumindest einige praktische Vorteile gibt - ich halte es für einen Fehler, alle Dinge zu berücksichtigen als streng "gut" oder "böse" - fast alles ist eine Frage von Kompromissen. Das Verständnis dieser Kompromisse ist der Schlüssel, um bedauerliche Entscheidungen im Nachhinein nicht zu vermeiden, und die bloße Kennzeichnung von Dingen als "gut" oder "böse" ignoriert im Allgemeinen alle derartigen Feinheiten.

Während das Problem nicht nur für C gilt, wie andere betonten, könnte es in C erheblich verschärft werden, da nichts Eleganteres als Makros oder leere Zeiger für Generika, die Unbeholfenheit nicht-trivialer OOP und die Tatsache, dass die Die C-Standardbibliothek enthält keine Container. In C ++ wird eine Person, die ihre eigene verknüpfte Liste implementiert, möglicherweise wütend und fragt sich, warum sie nicht die Standardbibliothek verwenden, es sei denn, sie sind Schüler. In C würden Sie einen wütenden Mob einladen, wenn Sie eine elegante Implementierung einer verknüpften Liste nicht sicher in Ihrem Schlaf implementieren können, da von einem C-Programmierer häufig erwartet wird, dass er diese Art von Dingen mindestens täglich ausführen kann. Es' Es liegt nicht an einer merkwürdigen Besessenheit in Bezug auf verknüpfte Listen, dass Linus Torvalds die Implementierung der SLL-Suche und -Entfernung unter Verwendung der doppelten Indirektion als Kriterium zur Bewertung eines Programmierers verwendete, der die Sprache versteht und "guten Geschmack" hat. Dies liegt daran, dass C-Programmierer diese Logik möglicherweise tausendmal in ihrer Karriere implementieren müssen. In diesem Fall ist es für C so, als würde ein Koch die Fähigkeiten eines neuen Kochs bewerten, indem er ihn dazu bringt, nur ein paar Eier zuzubereiten, um zu sehen, ob er zumindest die grundlegenden Dinge beherrscht, die er die ganze Zeit tun muss.

Zum Beispiel habe ich diese grundlegende "indizierte freie Liste" -Datenstruktur wahrscheinlich ein Dutzend Mal in C lokal für jeden Standort implementiert, der diese Zuweisungsstrategie verwendet (fast alle meine verknüpften Strukturen, um die Zuweisung von jeweils einem Knoten zu vermeiden und den Speicher zu halbieren Kosten der Links auf 64-Bit):

Bildbeschreibung hier eingeben

In C wird jedoch nur eine sehr geringe Menge Code für reallocein erweiterbares Array benötigt, um Speicher daraus zu bündeln. Dabei wird ein indizierter Ansatz für eine freie Liste verwendet, wenn eine neue Datenstruktur implementiert wird, die diese verwendet.

Jetzt habe ich das gleiche in C ++ implementiert und dort habe ich es nur einmal als Klassenvorlage implementiert. Aber es ist eine sehr viel komplexere Implementierung auf der C ++ - Seite mit Hunderten von Codezeilen und einigen externen Abhängigkeiten, die sich auch über Hunderte von Codezeilen erstrecken. Und der Hauptgrund dafür, dass es viel komplizierter ist, ist, dass ich es gegen die Idee codieren muss, dass es Tsich um jeden möglichen Datentyp handeln könnte. Es kann jederzeit ausgelöst werden (außer wenn es zerstört wird, was ich explizit wie bei den Standard-Bibliothekscontainern tun muss). Ich musste über die richtige Ausrichtung nachdenken, um Speicher zuzuweisenT (obwohl dies ab C ++ 11 glücklicherweise einfacher ist), könnte es nicht trivial konstruierbar / zerstörbar sein (erfordert das Platzieren neuer und manueller dtor-Aufrufe). und ich muss Iteratoren hinzufügen, sowohl veränderbare als auch schreibgeschützte (const) Iteratoren und so weiter und so fort.

Anbaubare Arrays sind keine Hexenwerkzeuge

In C ++ klingt es so, als wäre std::vectores die Arbeit eines Raketenwissenschaftlers, der auf den Tod optimiert wurde, aber es funktioniert nicht besser als ein dynamisches C-Array, das gegen einen bestimmten Datentyp codiert ist und nur reallocdazu dient, die Array-Kapazität bei Push-Backs mit einem zu erhöhen Dutzend Codezeilen. Der Unterschied besteht darin, dass eine sehr komplexe Implementierung erforderlich ist, um nur eine erweiterbare Direktzugriffssequenz vollständig mit dem Standard zu vereinbaren. Vermeiden Sie den Aufruf von ctors für nicht eingefügte Elemente. Ausnahmesicher. Geben Sie sowohl konstante als auch nicht konstante Direktzugriffsiteratoren ein. Verwenden Sie type Merkmale zur Disambiguierung von Füllungskennzahlen von Entfernungskennzahlen für bestimmte integrale Typen vonTBehandeln Sie PODs möglicherweise anders, indem Sie Typmerkmale usw. usw. usw. verwenden. Zu diesem Zeitpunkt benötigen Sie tatsächlich eine sehr komplexe Implementierung, um ein erweiterbares dynamisches Array zu erstellen, aber nur, weil versucht wird, jeden denkbaren Anwendungsfall zu behandeln. Positiv zu vermerken ist, dass Sie mit diesem zusätzlichen Aufwand eine ganze Menge Meilen sammeln können, wenn Sie wirklich sowohl PODs als auch nicht-triviale UDTs speichern müssen und generische iteratorbasierte Algorithmen verwenden müssen, die mit jeder kompatiblen Datenstruktur arbeiten. Profitieren Sie von der Ausnahmebehandlung und RAII, zumindest manchmal überschreiben Sie sie std::allocatormit Ihrem eigenen benutzerdefinierten Allokator usw. usw. In der Standardbibliothek zahlt es sich auf jeden Fall aus, wenn Sie überlegen, wie viel Nutzen Sie habenstd::vector hat die ganze Welt von Leuten erfasst, die es benutzt haben, aber das ist etwas, das in der Standardbibliothek implementiert ist und auf die Bedürfnisse der ganzen Welt zugeschnitten ist.

Einfachere Implementierungen für sehr spezifische Anwendungsfälle

Da ich mit meiner "indizierten freien Liste" nur sehr spezifische Anwendungsfälle behandelt habe, habe ich wahrscheinlich weniger Code geschrieben, obwohl ich diese freie Liste ein Dutzend Mal auf der C-Seite implementiert habe und einige triviale Codes dupliziert habe Insgesamt in C, um dies ein Dutzend Mal zu implementieren, als ich es nur einmal in C ++ implementieren musste, und ich musste weniger Zeit für die Wartung dieser Dutzend C-Implementierungen aufwenden als für die Wartung dieser einen C ++ -Implementierung. Einer der Hauptgründe, warum die C-Seite so einfach ist, ist, dass ich normalerweise mit PODs in C arbeite, wenn ich diese Technik verwende und im Allgemeinen nicht mehr Funktionen als insertund benötigeerasean den spezifischen Standorten, an denen ich dies lokal umsetze. Grundsätzlich kann ich nur die kleinste Teilmenge der Funktionalität implementieren, die die C ++ - Version bietet, da ich so viele weitere Annahmen darüber machen kann, was ich mache und was nicht, wenn ich das Design für eine ganz bestimmte Verwendung implementiere Fall.

Jetzt ist die C ++ - Version so viel netter und typsicherer zu verwenden, aber es war immer noch eine wichtige Aufgabe von PITA, ausnahmesichere und bidirektionale Iteratoren zu implementieren und zu machen, z mehr Zeit, als es in diesem Fall tatsächlich spart. Und ein Großteil dieser Kosten für die allgemeine Implementierung wird nicht nur im Voraus verschwendet, sondern wiederholt in Form von Dingen wie eskalierten Build-Zeiten, die jeden Tag neu bezahlt werden.

Kein Angriff auf C ++!

Dies ist jedoch kein Angriff auf C ++, da ich C ++ liebe, aber wenn es um Datenstrukturen geht, bevorzuge ich C ++ hauptsächlich wegen der wirklich nicht trivialen Datenstrukturen, für deren Implementierung ich viel Zeit im Voraus aufwenden möchte auf eine sehr verallgemeinerte Art Tund Weise ausnahmesicher zu machen gegen alle möglichen Arten von , standardkonform und iterabel zu machen, usw., wobei sich diese Art von Vorlaufkosten in Form einer Tonne Kilometer wirklich auszahlen.

Das fördert aber auch eine ganz andere Design-Denkweise. Wenn ich in C ++ ein Octree für die Kollisionserkennung erstellen möchte, tendiere ich dazu, es bis zum n-ten Grad zu verallgemeinern. Ich möchte nicht, dass es indizierte Dreiecksnetze speichert. Warum sollte ich es auf nur einen Datentyp beschränken, mit dem es arbeiten kann, wenn ich über einen leistungsstarken Mechanismus zur Codegenerierung verfüge, der zur Laufzeit alle Abstraktionsnachteile beseitigt? Ich möchte, dass prozedurale Kugeln, Würfel, Voxel, NURBs-Oberflächen, Punktwolken usw. usw. gespeichert werden und versucht wird, alles in Ordnung zu bringen, da es verlockend ist, es so zu gestalten, wenn Sie Vorlagen zur Hand haben. Ich möchte es möglicherweise nicht einmal auf die Kollisionserkennung beschränken - wie wäre es mit Raytracing, Picking usw.? C ++ lässt es zunächst "leicht" aussehen eine Datenstruktur bis zum n-ten Grad zu verallgemeinern. Und so habe ich solche räumlichen Indizes in C ++ entworfen. Ich habe versucht, sie so zu gestalten, dass sie den Hunger der ganzen Welt stillen, und im Gegenzug habe ich in der Regel einen "Alleskönner" mit äußerst komplexem Code erhalten, um ihn mit allen denkbaren Anwendungsfällen in Einklang zu bringen.

Witzigerweise habe ich die in C implementierten räumlichen Indizes im Laufe der Jahre immer wieder verwendet, und zwar ohne Fehler von C ++, aber nur in meiner Sprache, die mich dazu verleitet. Wenn ich so etwas wie ein Oktree in C codiere, neige ich dazu, es nur mit Punkten arbeiten zu lassen und damit zufrieden zu sein, weil die Sprache es zu schwierig macht, es überhaupt bis zum n-ten Grad zu verallgemeinern. Aufgrund dieser Tendenzen habe ich im Laufe der Jahre tendenziell Dinge entworfen, die effizienter und zuverlässiger sind und für bestimmte Aufgaben wirklich gut geeignet sind, da sie sich nicht darum kümmern, bis zum n-ten Grad allgemein zu sein. Sie werden zu Assen in einer speziellen Kategorie anstelle eines Alleskönners. Auch das liegt nicht an C ++, sondern einfach an den menschlichen Neigungen, die ich habe, wenn ich es im Gegensatz zu C verwende.

Trotzdem liebe ich beide Sprachen, aber es gibt unterschiedliche Tendenzen. In CI habe die Tendenz, nicht genug zu verallgemeinern. In C ++ neige ich dazu, zu viel zu verallgemeinern. Beides zu nutzen hat mir irgendwie geholfen, mich auszugleichen.

Sind generische Implementierungen eine Norm oder schreiben Sie unterschiedliche Implementierungen für jeden Anwendungsfall?

Für triviale Dinge wie einfach verknüpfte indizierte 32-Bit-Listen mit Knoten aus einem Array oder einem Array, das sich selbst neu zuordnet (analog std::vectorzu C ++), oder beispielsweise ein Octree, in dem nur Punkte gespeichert werden und das nichts weiter tun soll. ' t sich die Mühe machen, bis zum Speichern eines beliebigen Datentyps zu verallgemeinern. Ich implementiere diese, um einen bestimmten Datentyp zu speichern (obwohl es abstrakt sein kann und in einigen Fällen Funktionszeiger verwendet, aber zumindest spezifischer als Enten-Typisierung mit statischem Polymorphismus).

Und ich bin mit ein bisschen Redundanz in diesen Fällen absolut zufrieden, vorausgesetzt , ich teste es gründlich. Wenn ich keinen Komponententest durchführe, fühlt sich die Redundanz viel unangenehmer an, da möglicherweise redundanter Code vorhanden ist, der Fehler dupliziert, z. Möglicherweise müssen noch Änderungen vorgenommen werden, da es defekt ist. Ich neige dazu, gründlichere Komponententests für C-Code zu schreiben, den ich als Grund schreibe.

Für nicht-triviale Dinge greife ich normalerweise zu C ++, aber wenn ich es in C implementieren würde, würde ich in Betracht ziehen, nur void*Zeiger zu verwenden, möglicherweise eine Schriftgröße zu akzeptieren, um zu wissen, wie viel Speicher für jedes Element und möglicherweise copy/destroyFunktionszeiger zugewiesen werden muss die Daten tief zu kopieren und zu zerstören, wenn sie nicht trivial konstruierbar / zerstörbar sind. Meistens störe ich nicht und verwende nicht so viel C, um die komplexesten Datenstrukturen und Algorithmen zu erstellen.

Wenn Sie eine Datenstruktur häufig genug für einen bestimmten Datentyp verwenden, können Sie auch eine typsichere Version über eine void*umbrechen, die nur mit Bits und Bytes und Funktionszeigern arbeitet, und z. B. die Typensicherheit durch den C-Wrapper wieder einführen.

Ich könnte zum Beispiel versuchen, eine generische Implementierung für eine Hash-Map zu schreiben, aber ich finde das Endergebnis immer chaotisch. Ich könnte auch eine spezielle Implementierung für diesen speziellen Anwendungsfall schreiben, den Code klar und einfach zu lesen und zu debuggen. Letzteres würde natürlich zu Code-Duplikaten führen.

Hash-Tabellen sind etwas fragwürdig, da die Implementierung möglicherweise trivial oder sehr komplex ist, je nachdem, wie komplex Ihre Anforderungen in Bezug auf Hashes und Rehashes sind, wenn Sie die Tabelle implizit automatisch wachsen lassen müssen oder die Tabellengröße antizipieren können Dabei spielt es keine Rolle, ob Sie offene Adressierung oder separate Verkettung usw. verwenden. Beachten Sie jedoch, dass eine Hash-Tabelle, die perfekt auf die Anforderungen einer bestimmten Site zugeschnitten ist, in der Implementierung häufig nicht so komplex ist und häufig gewonnen wird Seien Sie nicht so überflüssig, wenn es genau auf diese Bedürfnisse zugeschnitten ist. Zumindest ist das die Entschuldigung, die ich mir gebe, wenn ich etwas vor Ort implementiere. Andernfalls können Sie die oben beschriebene Methode mit void*und Funktionszeigern verwenden, um Objekte zu kopieren / zu zerstören und zu verallgemeinern.

Oft ist es nicht sehr aufwändig oder mit viel Code verbunden, eine sehr verallgemeinerte Datenstruktur zu übertreffen, wenn Ihre Alternative für Ihren konkreten Anwendungsfall äußerst eng anwendbar ist. Zum Beispiel ist es absolut trivial, die Leistung der Verwendung mallocfür jeden einzelnen Knoten zu übertreffen (im Gegensatz zum Poolen einer Menge Speicher für viele Knoten), und zwar ein für allemal mit Code, den Sie nie für einen sehr, sehr genauen Anwendungsfall erneut aufrufen müssen auch als neuere umsetzungen von malloccome out. Es kann ein Leben lang dauern, es zu übertreffen und nicht weniger komplex zu programmieren, wenn Sie einen großen Teil Ihres Lebens darauf verwenden müssen, es zu warten und auf dem neuesten Stand zu halten, wenn Sie seiner Allgemeingültigkeit entsprechen möchten.

Als weiteres Beispiel fand ich es oft sehr einfach, Lösungen zu implementieren, die zehnmal schneller oder schneller sind als die von Pixar oder Dreamworks angebotenen VFX-Lösungen. Ich kann es im Schlaf tun. Aber das liegt nicht daran, dass meine Implementierungen überlegen sind - weit davon entfernt. Sie sind den meisten Menschen absolut unterlegen. Sie sind nur für meine sehr, sehr spezifischen Anwendungsfälle überlegen. Meine Versionen sind weitaus weniger allgemein anwendbar als die von Pixar oder Dreamwork. Es ist ein lächerlich unfairer Vergleich, da ihre Lösungen im Vergleich zu meinen dumm-einfachen Lösungen absolut brillant sind, aber das ist genau der Punkt. Der Vergleich muss nicht fair sein. Wenn Sie nur ein paar sehr spezifische Dinge benötigen, müssen Sie keine Datenstruktur erstellen, die eine endlose Liste von Dingen verarbeitet, die Sie nicht benötigen.

Homogene Bits und Bytes

Eine Sache, die in C ausgenutzt werden muss, da es einen solchen inhärenten Mangel an Typensicherheit aufweist, ist die Idee, Dinge basierend auf den Eigenschaften von Bits und Bytes homogen zu speichern. Es gibt mehr Unschärfe als Ergebnis zwischen Speicherzuweisung und Datenstruktur.

Aber eine Reihe von variabler Größe Dinge zu speichern, oder sogar Dinge , die nur könnte variabler Größe sein, wie eine polymorphe Dogund Catist schwierig effizient zu tun. Sie können nicht davon ausgehen, dass sie eine variable Größe haben und zusammenhängend in einem einfachen Container mit wahlfreiem Zugriff gespeichert werden können, da der Schritt zum Wechseln von einem Element zum nächsten unterschiedlich sein kann. Um eine Liste zu speichern, die sowohl Hunde als auch Katzen enthält, müssen Sie möglicherweise drei separate Datenstruktur- / Zuweisungsinstanzen verwenden (eine für Hunde, eine für Katzen und eine für eine polymorphe Liste von Basiszeigern oder intelligenten Zeigern oder noch schlimmer , ordnen Sie jeden Hund und jede Katze einem Allzweck-Zuweiser zu und verteilen Sie sie im gesamten Speicher. Dies wird teuer und verursacht einen Teil der vervielfachten Cache-Ausfälle.

Eine Strategie, die in C verwendet werden kann, ist die Verallgemeinerung auf der Ebene von Bits und Bytes, obwohl sie eine verringerte Typenvielfalt und Sicherheit bietet. Sie könnten in der Lage sein , das zu übernehmen Dogsund Catsdie gleiche Anzahl von Bits und Bytes erfordern, haben die gleichen Felder, den gleichen Zeiger auf eine Funktion Zeigertabelle. Im Gegenzug können Sie dann weniger Datenstrukturen codieren, aber genauso wichtig, alle diese Dinge effizient und zusammenhängend speichern. In diesem Fall behandeln Sie Hunde und Katzen wie analoge Gewerkschaften (oder Sie verwenden einfach eine Gewerkschaft).

Und das ist mit hohen Kosten für die Typensicherheit verbunden. Wenn es eine Sache gibt, die ich in C mehr als alles andere vermisse, dann ist es Typensicherheit. Es rückt näher an die Baugruppenebene, wo die Strukturen lediglich anzeigen, wie viel Speicher zugewiesen ist und wie jedes Datenfeld ausgerichtet ist. Aber das ist eigentlich mein Hauptgrund für die Verwendung von C. Wenn Sie wirklich versuchen, Speicherlayouts zu steuern und wo alles zugeordnet und wo alles relativ zueinander gespeichert ist, ist es oft hilfreich, nur an Dinge auf der Ebene von Bits und zu denken Bytes und wie viele Bits und Bytes Sie benötigen, um ein bestimmtes Problem zu lösen. Dort kann die Dummheit des C-Typ-Systems eher nützlich als ein Handicap werden. In der Regel führt dies dazu, dass weniger Datentypen verarbeitet werden müssen.

Scheinbare / Scheinbare Vervielfältigung

Jetzt habe ich "Vervielfältigung" in einem losen Sinn für Dinge verwendet, die möglicherweise nicht einmal redundant sind. Ich habe gesehen, wie Leute Begriffe wie "zufällige / scheinbare" Vervielfältigung von "tatsächlicher Vervielfältigung" unterschieden haben. Ich sehe es so, dass es in vielen Fällen keine so klare Unterscheidung gibt. Ich finde die Unterscheidung eher wie "potenzielle Einzigartigkeit" oder "potenzielle Vervielfältigung" und es kann in beide Richtungen gehen. Oft hängt es davon ab, wie sich Ihre Designs und Implementierungen entwickeln und wie perfekt sie für einen bestimmten Anwendungsfall zugeschnitten sind. Aber ich habe oft festgestellt, dass sich das, was später als Code-Duplizierung erscheint, nach mehreren Wiederholungen von Verbesserungen als nicht mehr redundant herausstellt.

Nehmen Sie eine einfache Implementierung eines erweiterbaren Arrays mit reallocdem analogen Äquivalent von std::vector<int>. Anfangs ist es möglicherweise überflüssig, wenn Sie beispielsweise std::vector<int>in C ++ arbeiten. Durch Messen kann es jedoch von Vorteil sein, 64 Bytes vorab zuzuweisen, damit sechzehn 32-Bit-Ganzzahlen eingefügt werden können, ohne dass eine Heap-Zuordnung erforderlich ist. Jetzt ist es nicht mehr überflüssig, zumindest nicht mit std::vector<int>. Und dann könnten Sie sagen: "Aber ich könnte dies einfach auf ein neues verallgemeinern SmallVector<int, 16>, und Sie könnten es. Aber dann sagen wir, Sie finden es nützlich, weil dies für sehr kleine, kurzlebige Arrays ist, um die Array-Kapazität auf Heap-Zuweisungen zu vervierfachen, anstatt Erhöhung um 1,5 (ungefähr die Menge, die vielevectorImplementierungen verwenden), während davon ausgegangen wird, dass die Array-Kapazität immer eine Zweierpotenz ist. Jetzt ist Ihr Container wirklich anders und es gibt wahrscheinlich keinen ähnlichen Container. Und vielleicht könnten Sie versuchen, solche Verhaltensweisen zu verallgemeinern, indem Sie mehr und mehr Vorlagenparameter hinzufügen, um das Vorbelegungsverhalten, das Neubelegungsverhalten usw. usw. anzupassen, aber an diesem Punkt finden Sie möglicherweise etwas wirklich unhandliches, verglichen mit einem Dutzend Zeilen einfachen C Code.

Und Sie könnten sogar einen Punkt erreichen, an dem Sie eine Datenstruktur benötigen, die 256-Bit-ausgerichteten und gepolsterten Speicher reserviert, ausschließlich PODs für AVX 256-Befehle speichert, 128 Byte vorbelegt, um Heap-Zuweisungen für häufig auftretende kleine Eingabegrößen zu vermeiden, wenn sich die Kapazität verdoppelt voll und ermöglicht sicheres Überschreiben von nachfolgenden Elementen, die die Array-Größe überschreiten, aber die Array-Kapazität nicht überschreiten. Wenn Sie zu diesem Zeitpunkt immer noch versuchen, eine Lösung zu verallgemeinern, um das Duplizieren einer kleinen Menge von C-Code zu vermeiden, haben die Programmiergötter möglicherweise Erbarmen mit Ihrer Seele.

Es gibt also auch Zeiten wie diese, in denen das, was anfänglich redundant aussieht, zu wachsen beginnt, wenn Sie eine Lösung für einen bestimmten Anwendungsfall maßschneidern, die immer besser und besser zu etwas Einzigartigem und überhaupt nicht redundantem passt. Dies gilt jedoch nur für Dinge, bei denen Sie es sich leisten können, sie perfekt auf einen bestimmten Anwendungsfall abzustimmen. Manchmal brauchen wir einfach eine "anständige" Sache, die für unseren Zweck verallgemeinert ist, und dort profitiere ich am meisten von sehr verallgemeinerten Datenstrukturen. Aber für außergewöhnliche Dinge, die perfekt für einen bestimmten Anwendungsfall gemacht wurden, wird die Idee von "Allzweck" und "perfekt für meinen Zweck gemacht" zu inkompatibel.

PODs und Primitive

Jetzt finde ich in C oft Ausreden, um PODs und insbesondere Grundelemente in Datenstrukturen zu speichern, wann immer dies möglich ist. Das mag wie ein Anti-Pattern erscheinen, aber ich habe es tatsächlich als versehentlich hilfreich empfunden, um die Wartbarkeit von Code gegenüber den Arten von Dingen zu verbessern, die ich früher in C ++ häufiger ausgeführt habe.

Ein einfaches Beispiel ist das Internieren kurzer Zeichenfolgen (wie es normalerweise bei Zeichenfolgen für Suchschlüssel der Fall ist - diese sind in der Regel sehr kurz). Warum sollten Sie sich mit all diesen Zeichenfolgen variabler Länge befassen, deren Größe sich zur Laufzeit ändert, was eine nicht triviale Konstruktion und Zerstörung impliziert (da wir möglicherweise Heap reservieren und freigeben müssen)? Wie wäre es, wenn Sie diese Dinge einfach in einer zentralen Datenstruktur speichern, wie z. B. einer thread-sicheren Trie oder Hash-Tabelle, die nur für das Internieren von Zeichenfolgen entwickelt wurde, und dann auf Zeichenfolgen verweisen, die ein einfaches altes int32_toder:

struct IternedString 
{
    int32_t index;
};

... in unseren Hash-Tabellen, rot-schwarzen Bäumen, Skip-Listen usw., wenn wir keine lexikografische Sortierung benötigen? Jetzt können alle unsere anderen Datenstrukturen, die wir für die Arbeit mit 32-Bit-Ganzzahlen codiert haben, diese internen Zeichenfolgenschlüssel speichern, die effektiv nur 32-Bit sind ints. Und ich habe es zumindest in meinen Anwendungsfällen gefunden (könnte nur meine Domäne sein, da ich in Bereichen wie Raytracing, Mesh-Verarbeitung, Bildverarbeitung, Partikelsystemen, Bindung an Skriptsprachen, Implementierungen von Multithread-GUI-Kits auf niedriger Ebene usw. arbeite). Dinge auf niedriger Ebene, aber nicht so niedrig wie ein Betriebssystem), dass der Code zufällig effizienter und einfacher wird, wenn nur Indizes zu solchen Dingen gespeichert werden. Das macht es so, dass ich oft arbeite, sagen wir mal 75% der Zeit, mit nur int32_tundfloat32 in meinen nicht-trivialen Datenstrukturen, oder einfach nur Dinge zu speichern, die die gleiche Größe haben (fast immer 32-Bit).

Und natürlich können Sie, wenn dies für Ihren Fall zutreffend ist, vermeiden, dass eine Reihe von Datenstrukturimplementierungen für verschiedene Datentypen vorhanden sind, da Sie in erster Linie mit so wenigen arbeiten.

Prüfung und Zuverlässigkeit

Eine letzte Sache, die ich anbieten würde und die möglicherweise nicht für jedermann geeignet ist, ist die Bevorzugung des Schreibens von Tests für diese Datenstrukturen. Machen Sie sie wirklich gut in etwas. Stellen Sie sicher, dass sie extrem zuverlässig sind.

In diesen Fällen kann auf geringfügige Code-Duplikationen sehr viel mehr verzichtet werden, da Code-Duplikationen nur dann eine Wartungslast darstellen, wenn Sie kaskadierende Änderungen am duplizierten Code vornehmen müssen. Sie eliminieren einen der Hauptgründe für die Änderung eines solchen redundanten Codes, indem Sie sicherstellen, dass er äußerst zuverlässig und für die jeweiligen Aufgaben wirklich gut geeignet ist.

Mein Sinn für Ästhetik hat sich im Laufe der Jahre verändert. Ich ärgere mich nicht mehr, weil ich sehe, wie eine Bibliothek ein Punktprodukt oder eine triviale SLL-Logik implementiert, die bereits in einer anderen implementiert ist. Ich ärgere mich nur, wenn die Dinge schlecht getestet und unzuverlässig sind, und ich habe festgestellt, dass dies eine viel produktivere Denkweise ist. Ich habe mich wirklich mit Codebasen befasst, die Fehler durch duplizierten Code dupliziert haben, und die schlimmsten Fälle von Copy-and-Paste-Codierung gesehen, die aus einer trivialen Änderung an einer zentralen Stelle eine fehleranfällige Kaskadenänderung für viele gemacht haben sollten. In vielen Fällen war dies jedoch das Ergebnis unzureichender Tests, da der Code nicht zuverlässig und überhaupt nicht in der Lage war, das zu tun, was er tat. Vorher, als ich in fehlerhaften alten Codebasen arbeitete, Mein Verstand bezog sich auf alle Formen der Code-Vervielfältigung, die eine sehr hohe Wahrscheinlichkeit für die Vervielfältigung von Fehlern aufwiesen und kaskadierende Änderungen erforderten. Eine Miniaturbibliothek, die eines sehr gut und zuverlässig macht, wird jedoch nur sehr wenige Gründe finden, sich in Zukunft zu ändern, selbst wenn sie hier und da über redundant aussehenden Code verfügt. Meine Prioritäten blieben damals aus, als mich die Verdoppelung mehr irritierte als die schlechte Qualität und der Mangel an Tests. Letzteres sollte oberste Priorität haben.

Code-Vervielfältigung für Minimalismus?

Dies ist ein lustiger Gedanke, der mir durch den Kopf ging, aber stellen Sie sich einen Fall vor, in dem wir möglicherweise auf eine C- und C ++ - Bibliothek stoßen, die ungefähr dasselbe tun: Beide haben ungefähr dieselbe Funktionalität, dieselbe Menge an Fehlerbehandlung, eine davon ist nicht signifikant effizienter als die anderen usw. Und vor allem sind beide kompetent implementiert, erprobt und zuverlässig. Leider muss ich hier hypothetisch sprechen, da ich nie etwas gefunden habe, das einem perfekten Nebeneinander nahe kommt. Aber die C-Bibliothek, die diesem Nebeneinander-Vergleich am nächsten kam, war oft viel, viel kleiner als das C ++ - Äquivalent (manchmal 1/10 seiner Codegröße).

Und ich glaube, der Grund dafür ist, dass, um ein Problem auf eine allgemeine Art und Weise zu lösen, die die unterschiedlichsten Anwendungsfälle anstelle eines genauen Anwendungsfalls behandelt, möglicherweise Hunderte bis Tausende von Codezeilen erforderlich sind, während letztere möglicherweise nur erforderlich sind ein Dutzend. Trotz der Redundanz und trotz der Tatsache, dass die C-Standardbibliothek bei der Bereitstellung von Standarddatenstrukturen miserabel ist, wird häufig weniger Code in menschlichen Händen erzeugt, um dieselben Probleme zu lösen, und ich denke, das liegt in erster Linie daran zu den Unterschieden in den menschlichen Tendenzen zwischen diesen beiden Sprachen. Der eine fördert das Lösen von Dingen anhand eines ganz bestimmten Anwendungsfalls, der andere fördert abstraktere und allgemeinere Lösungen für die unterschiedlichsten Anwendungsfälle, aber das Endergebnis dieser Fälle ist nicht der Fall. '

Ich habe mir neulich einen Raytracer auf Github angesehen, der in C ++ implementiert war und so viel Code für einen Toy Raytracer benötigte. Und ich habe nicht so viel Zeit damit verbracht, mich mit dem Code zu befassen, aber es gab eine Schiffsladung von Allzweckstrukturen, die viel mehr handhabten, als ein Raytracer benötigen würde. Und ich kenne diesen Codierungsstil, weil ich C ++ auf die gleiche Art und Weise von unten nach oben verwendet habe, wobei ich mich darauf konzentrierte, zuerst eine vollständige Bibliothek von sehr universellen Datenstrukturen zu erstellen, die weit über das unmittelbare hinausgeht Problem zur Hand und dann das eigentliche Problem zweitens angehen. Aber während diese allgemeinen Strukturen hier und da einige Redundanzen beseitigen und in neuen Kontexten häufig wiederverwendet werden, im Gegenzug treiben sie das Projekt enorm in die Höhe, indem sie ein wenig Redundanz gegen eine Schiffsladung unnötigen Codes / unnötiger Funktionalität austauschen, und letztere ist nicht unbedingt einfacher zu warten als die erstere. Im Gegenteil, ich finde es oft schwieriger zu pflegen, da es schwierig ist, ein Design von etwas Allgemeinem zu pflegen, bei dem Designentscheidungen mit den unterschiedlichsten Anforderungen in Einklang gebracht werden müssen.


quelle