Schnelle Map bzw. überlange Arrays (mehr als int)
lima-city → Forum → Programmiersprachen → C/C++ und D
adresse
aktivieren
array
bit
code
element
index
list
liste
null
nutzen
operation
pool
prinzip
problem
register
speichern
url
versuchen
verwalten
-
Hallo,
ich bin grade dabei (just for fun) einen eigenen Bytecodeinterpreter in Form einer Registermaschine mit "gepimpten" Befehlssatz möglichst in C zu entwickeln, allerdings hab ich noch so meine Probleme bei dem Wesentlichen: de(m|n) Register(n).
Die Registermaschine geht ja von unendlich aus, was nunmal nicht programmierbar ist. Deshalb suche ich eine Möglichkeit relativ schnelle Arrays mit mehr als int vielen Werten. Eine Map ist zum einen halt nicht so einfach zu machen und vor allem Rechen und Speicherintensiv, allerdings bei wenig zusammenhängenden Indexes wiederum recht speicherfreundlich. Rein theoretisch kann die Maschine by Design 2^255 Elemente in dem oder einem Register adressieren.
Klingt alles sowieso ziemlich langsam, aber ich möchte es trotzdem so schnell wie möglich gestalten. Es ist eher eine Art Forschungsprojekt von mir selbst und bei weitem noch nicht fertig oder reif, aber das ist ein Problem was ich nicht so recht lösen kann. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Hi,
vorneweg die Frage: Meinst du mit C wirklich reines C, oder geht c++ auch? Wenn ja, könntest du nämlich, wenn du letztendlich bei einer map bleiben willst, das std::map template nutzen, dann wäre das wieder einfacher zu machen. Wenn dir der Speicherbedarf der Map bei zusammenhängenden Registern zu hoch erscheint, könntest du es evtl. so lösen, dass du eine Map aus Arrays erstellst. Die ersten paar Bits des Registerindex sind dann der Schlüssel für die Map, die letzten dann der Index des Arrays (oder std::vector). Die rechnerei mit den "Bits" ließe sich in C++ dann auch ganz schön in eine Klasse packen, welche zur Addressierung dient: einen Basistypen mit 256 gibt es meines Wissens nach sowieso nicht (zumindest auf 32bit-Systemen, oder willst du 64bit nutzen? (da weiß ichs nicht)), sodass du diesen sowieso durch eine Kombination von Basistypen realisiern müsstest, wobei du dann gleich eine Variable (etwa ein char) als Array-Index nutzen könntest.
Wenn du kein C++ willst, dann denk über das da oben einfach garnicht weiter nach. Wobei sich in C bereits das Problem stellt, wie du denn deine Elemente adressieren willst. Wie gesagt: imo gibt es keinen Basistypen mit 256 Bits, also wird das bereits hier etwas komplizierter. -
Ja mit C++ wäre das vllt leichter zu machen, da man dort evtl. auch den Operator entsprechend überladen kann. Ich hab mich übrigens vertan. Eigentlich kann es sogar 256^255 Adressen verwalten. Im Prinzip ist jedes Register 8 Bit und da kann man 255 Bytes als Index verwenden. Ein Byte geht für die Länge drauf, also wieviel Bytes der Index hat.
Da es aber wahrscheinlich eh speicher- und rechenhungrig wird kann ich es wohl erstmal mit C++ versuchen.
Beitrag zuletzt geändert: 27.9.2011 20:13:56 von reimann -
Hallo reimann,
nur um zu sehen, ob ich es richtig verstehe:
- der Index ist sozusagen die Adresse eines Registers
- ein Register ist 8 bit groß
- du willst Theoretisch 256^255 Register verwalten können
- in Wahrheit werden nur relativ wenige Register belegt (hoffe ich jetzt mal)
- Du willst schnell auf die Register zugreifen können
Wenn das alles stimmt, dann würde ich es mit einer Baumstrucktur versuchen:
Wenn die Sache relativ dünn besiedelt ist sollte damit ein schneller Zugriff möglich sein. Sofern Du Dir zusätzlich einen Pool von register_tree_node_t's anlegst ist auch das Hinzufügen und Entfernen relativ schnell, da Du viele malloc() und free() Operationen einsparen kannst. Falls sich die Werte irgendwo häufen, dann ist das natürlich wegen der linearen Suche schlecht.typedef struct register_tree_node_ { unsigned char value; /* register value if children == NULL, address part otherwise */ struct register_tree_node_ * next_sibling; struct register_tree_node_ * first_child; } register_tree_node_t; -
@darkpandemic:
Naja wie stark besiedelt das ist hängt eben vom Benutzer bzw. auszuführenden Bytecodeprogrmam ab. Aber an sich finde ich die Baumstruktur Idee wirklich gut. Natürlich wird nie ein Programm diesen Speicher ausnutzen, da ja wohl kaum eine Maschine existiert, auf der da Funktionieren könnte, aber es ist ja auch eher hypotethischer Natur.
Der Index zw. die Adresse wird dann auch je nachdem entweder in einem char oder int Array befinden und demzufolge könnte man auch Einen Array von Pointern zu diesem Array von Pointern verwenden, also im Prinzip mehrdimensionale Arrays. Leider hab ich noch nicht soviel gemacht, um es einfach testen zu können, was schneller läuft und ich weiß nicht ob und wie man mehrdimensionale Arrays mit malloc, realloc und free handeln kann. -
Hallo reimann,
das Problem bei Arrays ist, dass man unter Umständen viel kopieren muss wenn man etwas einfügt. Das ist bei großen Datenmengen sehr langsam. Da sind Listen besser.
Ich habe hier einen Satz Templates für C die ich mir selber geschrieben habe. Da kannst Du Dir ja mal anschauen, wie man sowas evtl. machen könnte. list, queue und stack haben sogar eingebaute Element-Pools die man aktivieren kann um Einfüge- und Lösch-Operationen zu beschleunigen.
http://dl.dropbox.com/u/33460450/ctemplates.zip
Zugegebenermaßen ist das etwas schwer zu lesen, da es alles Makros sind aber hilfreich ist das Zeug auf jeden Fall.
Ein kleines Beispiel:
#include <stdlib.h> #include <stdio.h> #include "list.h" #include "vector.h" typedef unsigned char register_address_t[256]; DECLARE_GLOBAL_LIST(reg_addr_list_, reg_addr_list_t, RegAddrList, register_address_t *) DECLARE_GLOBAL_VECTOR(reg_addr_vector_, reg_addr_vector_t, RegAddrVector, register_address_t *) IMPLEMENT_GLOBAL_LIST(reg_addr_list_, reg_addr_list_t, RegAddrList, register_address_t *) IMPLEMENT_GLOBAL_VECTOR(reg_addr_vector_, reg_addr_vector_t, RegAddrVector, register_address_t *) register_address_t * register_address_create() { register_address_t * ra; if(!(ra = (register_address_t *)calloc(1, sizeof(register_address_t)))) { fprintf(stderr, "Error: register_address_create: calloc() for ra failed.\n"); return NULL; } return ra; } void register_address_free(register_address_t * ra) { if(!ra) { fprintf(stderr, "Error: register_address_free: ra = NULL.\n"); return; } free(ra); } int main() { long i; RegAddrList list; RegAddrListIterator it; RegAddrVector vector; /* Liste erzeugen: */ list = RegAddrList_Create(); /* Element-Pool aktivieren */ RegAddrList_SetPoolSize(list, 64); RegAddrList_EnablePool(list, true); /* Liste füllen: */ for(i=0;i<100;i++) { register_address_t * ra = register_address_create(); RegAddrList_PushBack(list, ra); } /* Adressen freigeben: */ it = list->front; do { register_address_free(it->value); }while(RegAddrListIterator_Next(&it)); /* Liste zerstören: */ RegAddrList_Free(list); /* Vector erzeugen: */ vector = RegAddrVector_Create(16,16); /* Vector füllen */ for(i=0;i<100;i++) { register_address_t * ra = register_address_create(); RegAddrVector_PushBack(vector, ra); } /* Adressen freigeben: */ for(i=0;i<vector->size;i++) { register_address_free(vector->value[i]); } /* Vector zerstören: */ RegAddrVector_Free(vector); return 0; }
Edit: Nachdem ich festgestellt habe, dass ich (noch) gar kein *_GetSize() Methode bei Vektoren habe, habe ich das Beispiel durch etwas mit mehr bezug zum Thema ersetzt.
Beitrag zuletzt geändert: 28.9.2011 20:44:57 von darkpandemic -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
