C - Array Inhalt verschieben, Quellwert neu setzen

[Timon3]

@Brother John: Trotzdem musst du im Destruktor immer noch manuell deine Speicherbereiche freigeben. Generell ist der Konstruktor-/Destruktoraufruf natürlich praktisch, würde ich aber nicht zu automatischem Speichermanagement zählen.

 

[theSplit]

Wieso Fragmentierung?
Fragmentierung ist, wenn Du viele mallocs und frees machst und dann irgendwann sich allokierte und unbenutze Speicherbereiche wild abwechseln. Aber innerhalb der Struct - dann sind da halt ein paar unbenutzte Bytes.

Genau, mit Fragmentierung meine ich eigentlich einen freien Speicherbereich der zwischen zwei belegten Speichersegmenten liegt weil zum Beispiel ein Block nicht in eine Lücke passt, aber da wird C vermutlich schon genug selbst unter der Haube managen. Was das Strukturieren der Struct angeht, das mag zwar in heutiger Sicht eher einer untergeordnete Rolle spielen, klar - aber es ist doch gut zu wissen das es überhaupt solche Fälle gibt und auch die Reihenfolge berücksichtigt wird wir diese deklariert werden. War mir vorher nicht bewusst bzw. finde ich das auch nicht selbst erklärend oder habe ich nicht darüber gelesen (so weit bin ich im erwähnten Buch auch noch nicht ).

Du solltest den Code besser strukturieren, diese endlos geschachtelten if-Schleifen - grauenvoll, mach mal ein paar Subroutinen.

Ich hab den Code jetzt, meiner Meinung nach etwas mehr strukturiert, heißt die Mainloop ist sauberer und greift auf Funktionen zu. Genau wie auch die grundlegenden Sachen des Gruppierens.

Und vom Design: dieses ewige memmove und realloc ist auch ein Performancekiller. Wenn es wichtig ist, sollte man solche Funktionen nur mit Bedacht einsetzen.
Anscheinend geht es ja vor allem darum, Elemente an die Arrays anzufügen (realloc) bzw. zu entfernen (memmove nach vorne). Du solltest mal überlegen, ob dies mit (doppelt-)verketteten Listen nicht viel eleganter und fehlerunanfälliger zu lösen wäre.

Das Memmove sorgt halt dafür das Daten nicht im Speicher schwimmen die nicht mehr verwendet werden, also in diesem Fall gelöschte Gruppen. Aber ich versuche deinen Hinweis bezüglich der Performance zu berücksichtigen. Es gibt auch eigentlich keine anderen Fälle mehr in der bisherigen Anwendung wo man sonst Einträge löschen bzw. überschreiben müsste.

Allerdings hab ich mir jetzt auch die verketteten Listen angesehen..
Aber rein von der Logik her würde ich schon gerne eine Gruppe bzw. Kollektion der Elemente einer Gruppe direkt griffbereit haben, so war jedenfalls die Idee mit dem Struct einer Gruppe von Elementen. Ich will aber nicht ausschließen das es nicht mit verketten Listen auch geht, ist halt nur etwas unpraktikabel wenn man alle Elemente einer Gruppe haben will und immer über die Elemente iterieren muß um die Reihenfolge zu ermitteln oder zu erfahren ob Element sich in der Kette befindet (im Gegensatz zum iterieren über ein unsigned int Array); auch wenn die Arbeit wie in deinem Link von Funktionen ausgeführt werden kann. Ich muß es mir einfach nochmal genauer ansehen und bei Zeiten mal irgendwie testen was besser funktioniert.

Gibt es eventuell Performance Tools mit denen man Messungen anstellen kann wie effizient der C Code ausführt?
Wäre (auch zum lernen) interessant.

 

[Brother John]

Allerdings hab ich mir jetzt auch die verketteten Listen angesehen..
Aber rein von der Logik her würde ich schon gerne eine Gruppe bzw. Kollektion der Elemente einer Gruppe direkt griffbereit haben, so war jedenfalls die Idee mit dem Struct einer Gruppe von Elementen. Ich will aber nicht ausschließen das es nicht mit verketten Listen auch geht, ist halt nur etwas unpraktikabel

Guter Vergleich zwischen Array und verketteter Liste: http://www.stroustrup.com/bs_faq.html#list
Kurzfazit daraus: Entgegen der ersten Intuition ist beim Einfügen/Entfernen mitten in der Datenstruktur das Array (oft massiv) schneller als die Liste, obwohl beim einen alle nachfolgenden Elemente komplett kopiert und beim anderen nur ein paar wenige Zeiger verbogen werden müssen. Das liegt am unglaublichen Schneckentempo des RAM im Vergleich zur CPU, weshalb man möglichst viele Datenzugriffe auf die schnelleren Caches anstatt den Hauptspeicher haben will. Je enger gepackter die Datenstruktur, desto höher ist die Wahrscheinlichkeit eines (schnellen) Cache Hit.

Davon abgesehen stell dir auch mal die Frage, wer in deinem Programm auf wen wartet: Der Benutzer auf den Computer oder umgekehrt? Wenn der Mensch im Sekundentakt klickt und die Rechenzeit für die ausgelösten Aktionen im 100-ms-Bereich liegt, dann ist eine Optimierung auf 50ms aus menschlicher Sicht für die Katz. Zumindest für die reine Geschwindigkeit. Gerade in mobil, wo Batterielaufzeit wichtig ist, wird das schon wieder komplexer.

Solange du mit Gruppen von ein paar Dutzend Elementen arbeitest, wirst du kaum einen Unterschied feststellen können. Der Link von oben verlinkt eine PDF mit Beispieldaten. Dort geht die Skala bei 100000 Elementen los und Array und Liste sind an der Stelle noch grob gleichauf.

Da du GCC verwendest, ist als Performance-Profiler sicher gprof einen Blick wert, weil der dabei ist. Bin dafür aber nicht wirklich ein Experte.

Ein Objekt, das ich mit new anlege geht aber erst mit Beendigung des Programms "out-of-scope", ansonsten musst Du es mit delete zerstören (analog zu *alloc/free)

@Brother John: Trotzdem musst du im Destruktor immer noch manuell deine Speicherbereiche freigeben.

Ich habe das Gefühl, ihr denkt zu sehr in C-Logik. Warum würde ich ein Objekt manuell mit new erzeugen wollen? C++ lebt von RAII, das wiederum darauf aufbaut, dass Stack-Objekte out-of-scope gehen und dabei automatisch Destruktoren aufgerufen werden. Konsequent angewendet führt das in modernem C++ dazu, dass man praktisch nie mehr manuell new’t und delete’t und selten Destruktoren schreibt. Wenn ich persönlich in die Lage komme, einen Destruktor schreiben zu müssen, weil ich Ressourcen wegräumen muss, dann geht die rote Warnflagge hoch. Das ist ein Hinweis auf ein potenzielles Design- oder Implementierungsproblem. Der compilergenerierte Default-Destruktor plus das Ressourcenmanagement, das mir die Standard Library abnimmt, ist in der überwältigenden Anzahl aller Fälle vollkommen ausreichend.

Für die Fälle, wo ich wirklich mal ressourcenverwaltende Pointer braucht, gibt es unique_ptr und shared_ptr als Wrapper. Darüber kann man auch recht gut malloc/free-lastigen C-Code anbinden.

Man muss sich nur auf die Fähigkeiten von C++ einlassen, dann kann Ressourcenmanagement (übrigens nicht nur Speicher, sondern auch Handles, Sockets, DB-Verbindungen usw.) tatsächlich vollautomatisch vonstatten gehen.

 

[Skipjack]

Ich habe das Gefühl, ihr denkt zu sehr in C-Logik.

Ich fürchte, da hast Du recht.
Zur Entschuldigung kann man wohl nur sagen, dass es ja eine C-Frage war.
Und C++ ist tatsächlich nicht meine Domäne, also führe ich den Teil des Diskussionsfadens besser nicht weiter fort, bevor ich mich richtig blamiere.

Zur Performancebetrachtung:
Man muss halt immer abwägen, wie wichtig Performance und Ressourcenverbrauch bei der jeweiligen Anwendung sind.
Und ggf. ist dann eine einfache "langsame" Implementierung, die schneller realisiert und einfacher zu warten - also billiger - ist, der coolen technologisch ausgefuchsten (aber höherer Aufwand bei Erstellung und Wartung) vorzuziehen.

Aber wenn ich es richtig verstanden habe, möchte der TS ja auch lernen und ausprobieren, so dass man tatsächlich mal Dinge ins Feld führen kann, die vielleicht etwas oversized wären. Wobei ich jetzt nicht behaupten möchte, dass Linked-Lists die Krone der Informatik und Arrays nur Handwerk wären.

 

[drfuture]

Hm, wenn die Frage für theSplit hier soweit erstmal gelöst ist - würde ich noch eine off-Topic frage in den Raum werfen.
@TheSplit oder auch die anderen - warum implementieren man so etwas in c / c++? Ist der Code *wirklich* spürbar schneller? (Also auch dem Benutzer gegenüber nicht nur bei einem Performance-Test)

Ist es in diesem Fall nötig die Anwendung auf embedded Systemen laufen zu lassen dir nur ein paar kb Platz bieten?
Oder ist es einfach aus Interesse an der Sprache, da du später z.B. Hardwarenah oder auf System-Grundlagen aufbauend Entwickeln möchtest?

Java jetzt mal außen vor (das könnte man von mir aus komplett vernichten ) Gibt es doch jede menge Hochsprachen die einem die Speicherverwaltung vollständig abnehmen und für vieles recht optimierte Funktionen zur Verfügung stellen über die sich dann div. Professoren und Wissenschaftler vielleicht schon bessere Gedanken gemacht haben als man es persönlich je könnte (Klar nicht durchgängig und jeder Mensch macht Fehler ^^).

An sich hinterfrage ich auch erst mal alles und nehme es nicht als *gegeben* hin aber solange man sein geplantes Ziel erreicht kann man ja evtl. den Weg mit dem geringsten Aufwand nehmen.

Will keine *Was ist die beste Sprache* Diskussion - ich bin mir durchaus bewusst das auch C / C++ sehr wohl ihre Berechtigung haben, mich interessieren eher die persönlichen Beweggründe.

 

[theSplit]

@drfuture:

Da ich selbst erst mit C wirklich anfange, kann ich dir gar nichts zu vielen deine Fragen sagen was die Hardwareunabhängigkeit anbelangt oder ab welchen Punkt sich die Performance äußert. Für mich ist es erst einmal nur Hobby und ich bin kein Informatiker.

Ich finde es aber schon interessant nach zu vollziehen zu können wie man System näher arbeiten und vor allem auch etwas unabhängiger werden kann. Ich hab viel, aber auch nicht professionell, mit Python gemacht und es war super das man gleich so viel out-of-the-box machen kann und die Sprache ist super und würde ich jedem empfehlen. Aber wenn es dann wirklich mal Limitierungen gegeben hat wo es dann mal keine Bibliothek/Modul für gibt - dann ist man aufgeschmissen weil man selbst nur mit dem Arbeiten kann was andere sich ausgedacht haben oder man versucht etwas mit dem zu machen was vorhanden ist so gut es geht.

Auch möchte ich meine Bandbreite erweitern und wenn man ein Problem findet das man so nicht lösen kann mit den Werkzeugen die man zu Verfügung hat, es dann aber vielleicht selbst lösen könnte weil man nicht darauf angewiesen ist sich auf den Code anderer zu verlassen bzw. zu warten bis etwas implementiert ist. Im schlimmsten Fall könnte man vielleicht auch mit den richtigen Know-How selbst mit Rat und Tat dabei helfen das Problem zu lösen.

Ohne jetzt mit Assembler anzufangen was, meiner Meinung nach, noch einen Step härter wäre, kann man langsam verstehen wie etwas unter der Haube funktioniert. Zumindest könnte man sich nun die Python Source ansehen und etwas nachvollziehen. Ich stelle mal außer Frage das ich es mit meinem Wissen besser könnte, aber ich stehe nicht vor komplett verschlossenen Toren weil ich den Code überhaupt nicht deuten kann.

Aber viel Wiederholung bei dem was ich schrieb
Im Grunde würde ich ja auch gern so etwas wie SDL selbst schreiben bzw. gleich nen ganzen Desktop entwerfen - aber dazu fehlt mir das Know-How.
Ein Punkt vielleicht noch, ich habe viel mit Javascript gearbeitet und bin dabei ständig an irgendeine Grenze einer Implementierung gestoßen bzw. geht es aufgrund der Grenzen eines Browsers schon nicht oder man hätte mit einem Add-On arbeiten müssen anstelle es direkt in Javascript zu implementieren.

Java hatte ich mir mal angesehen und hab auch etwas damit programmiert, aber gefiel mir einfach nicht.
Zu viel Sachen die einfach so nicht logisch waren bei dem womit ich gearbeitet hatte und alles von einer anderem Klasse ableiten bzw. erst zu deklarieren und dann damit zu arbeiten - wie auch in Flash, schrecklich fand ich das. Aber jemand der mit Java fit ist wird vermutlich anders denken und sagen das ist normal, ich empfand es einfach als umständlich - obwohl ich heute noch ab und an mit Flash programmiere.

Wollte gar nicht so viel schreiben, aber das sind nur mal meine spontanen Eindrücke. So weit bin ich jetzt auch nicht um irgendwas hoch qualifiziertes von mir zu geben.

Ich glaube die anderen Herren könnten da eher auf deine Fragen eingehen.

 

[Skipjack]

mich interessieren eher die persönlichen Beweggründe.

Es ist zwar kein persönlicher, sondern eher ein wirtschaftlicher Hintergrund. Ich habe hier ein embedded System (ein Hardware-Sicherheitsmodul) mit limitierten Ressourcen.
Da auch der Source bis auf OS-Ebene (ebenfalls custom-made) begutachtet wird, sind komplexe Laufzeitumgebungen oder virtuelle Maschinen keine Alternative.
Deshalb gutes altes C und K&R ist immer noch die Referenz.

 

[drfuture]

@Skipjack das war ja auch das wofür ich in meinem etwas wirren Text c / c++ gesehen habe,
bei TheSplit fand ich nur das vb.net oder c# da neuerdings ja Quelloffen auch über mono dann recht gut unter linux zu nutzen und "quasie" auch Plattformunabhängig - und Limitierungen gibt es dort auch erst mal nicht (das kann ich bei javascript z.B. nachvollziehen....) die bessere Wahl. Da könnte man sich dann um das "Problem" selber kümmern und das Thema dieses Threads der Sprache überlassen ;D