Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern
Gestern damit begonnen den boehm garbage collector in meiner Engine zu ersetzen. Hintergrund war halt das ich das auch gerne in einigen Visual Studio Geschichten benutzen wollte. Naja wer meinen Ansatz mal ausprobieren oder weiterentwickeln will... have fun,für mich reichts es so erst einmal aus.
Das Ganze ist im Prinzip eine bessere Version von "alloca". Die Funktion ref_alloc alloziert Speicher der mindestens "size" bytes lang ist und gibt einen Zeiger auf den Anfang des Speicher zurück. Der Speicher wird automatisch freigegeben wenn der Zeiger nicht mehr vom Stack, oder einer der registrierten Roots, aus sichtbar ist.
Code:
//This is free and unencumbered software released into the public domain.
//
//Anyone is free to copy, modify, publish, use, compile, sell, or
//distribute this software, either in source code form or as a compiled
//binary, for any purpose, commercial or non - commercial, and by any
//means.
//
//In jurisdictions that recognize copyright laws, the author or authors
//of this software dedicate any and all copyright interest in the
//software to the public domain.We make this dedication for the benefit
//of the public at large and to the detriment of our heirs and
//successors.We intend this dedication to be an overt act of
//relinquishment in perpetuity of all present and future rights to this
//software under copyright law.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
//MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
//IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
//OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
//ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
//OTHER DEALINGS IN THE SOFTWARE.
//
//For more information, please refer to <http://unlicense.org/>
Registriert: Di Mai 18, 2004 16:45 Beiträge: 2621 Wohnort: Berlin
Programmiersprache: Go, C/C++
Sieht interessant aus, ich würde noch
Code:
//readonly public interface :-)
constsize_t* m_used =&mem_used;
constsize_t* m_size =&mem_size;
constsize_t* m_count =&mem_count;
ein weiteres const vor dem * setzen, damit weder pointer noch wert änderbar sind.
Ich mag das Mutex nicht, man kann das bestimmt noch mit atomic pointer lösen, damit keine hohen latenzen entstehen, wenn man speicher holt oder frei gibt und in dem moment der gc thread auf räumt und locked.
An sich sieht das sehr interessant aus aber mir fällt leider kein Verwendungszweck bei mir ein, um damit mal rum zu spielen :\
_________________ "Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren" Benjamin Franklin
Registriert: Di Mai 18, 2004 16:45 Beiträge: 2621 Wohnort: Berlin
Programmiersprache: Go, C/C++
Ist doch normal. Wenn ich überlege, was ich noch alles am Radon Framework, Radon Converter und Zero Prime machen will, dann müsste ich eigentlich noch ein paar Programmierer anheuern.
Du könntest z.B. die Performance, Speicherverbrauch oder lesbarkeit optimieren und da gibt es wenige Grenzen ^^ Du kannst z.B. mal PVS Studio drüber jagen.
_________________ "Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren" Benjamin Franklin
Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern
Ok ich habe jetzt den einzelnen Knoten einen lock verpasst. Die Ergebnisse sind nun wirklich sehr viel krasser. In meinen kleinen Testbenchmark schafft die vorherige Version bei mir etwa 20000- 30000 Objekte pro Sekunde. Diese Version schafft noch genauso viele... bei einen thread. Bei mehreren threads kann es aber auf bis 150000 hochziehen
Registriert: Di Mai 18, 2004 16:45 Beiträge: 2621 Wohnort: Berlin
Programmiersprache: Go, C/C++
Du könntest noch die memcpy und memcmp Funktion durch Agner Fog seine ASM lib variante ersetzen. Diese nutzt die höchst mögliche SIMD Variante die auf der jeweiligen CPU geht, um das zu beschleunigen.
_________________ "Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren" Benjamin Franklin
Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern
ersma bugs fixxen oder [edit] so, läuft jetzt alles wieder stabil. Ich konnte den Scanvorgang noch einmal wesentlich beschleunigen. Im Schnitt bleibt jetzt alles bei 100000 (große) Objekten pro Sekunden. Je nachdem wie voll der GC ist und welche Settings man benutzt, ist auch wesentlich mehr drinne
Die BTGE fährt mit folgenden Einstellungen etwa 50000 Objekte pro Sekunde, vorher waren es 10000 (Boehm sogar nur 2000): #define MEMORY_POOL_SIZE (1024 * 1024 * 1024) //defines the length of each memory pool #define NUM_SCAN_BUFFER 8 #define NUM_OBJECT_SLOWDOWN 400
Also, auf ganzer Linie ein Erfolg (jedenfalls bei mir)
Code:
//This is free and unencumbered software released into the public domain.
//
//Anyone is free to copy, modify, publish, use, compile, sell, or
//distribute this software, either in source code form or as a compiled
//binary, for any purpose, commercial or non - commercial, and by any
//means.
//
//In jurisdictions that recognize copyright laws, the author or authors
//of this software dedicate any and all copyright interest in the
//software to the public domain.We make this dedication for the benefit
//of the public at large and to the detriment of our heirs and
//successors.We intend this dedication to be an overt act of
//relinquishment in perpetuity of all present and future rights to this
//software under copyright law.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
//MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
//IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
//OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
//ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
//OTHER DEALINGS IN THE SOFTWARE.
//
//For more information, please refer to <http://unlicense.org/>
#include "shared.h"
//a simple linked list used by the garbage collector to build and
//handle searches for references. Each reference found by the GC, will
//be added to the list so we can search for children.
struct memrng_t {
char* min;
char* max;
memrng_t * gcnext;
};
struct memroot_t : memrng_t {
thread_id_t tid;
};
//the following defines a ring-buffer for memory allocations. Each
//node contains a lock so we can use it for "none-blocking" garbage
//collection.
struct memhdr_t : memrng_t {
size_t size;//includes header and fragments
bool isunused;
memhdr_t * next;
memhdr_t * skip;
lock_t plock;
};
static lock_t rlock = lock_t();
volatileint num_roots =0;
static memroot_t * roots =NULL;
static memhdr_t * pool =NULL;
static memhdr_t * pcur =NULL;
staticchar* ps =NULL;
staticchar* pe =NULL;
volatileint num_objects =0;
volatileint num_deallocs =0;
void GCCollect(void){
if(rlock.trylock()){
memhdr_t * cur = pool;
memhdr_t * prev =NULL;
memhdr_t * fnd[NUM_SCAN_BUFFER +1];
char* min[NUM_SCAN_BUFFER +1];
char* max[NUM_SCAN_BUFFER +1];
memrng_t * check =NULL;
char* ptr =NULL;
int mc =0;
int tc =0;
bool found =false;
memset(max, 0, sizeof(max));
memset(min, 0xFFFFFF, sizeof(min));
memset(fnd, 0, sizeof(min));
size_t l =(pe - ps)/ NUM_SCAN_BUFFER +1;
size_t h =0;
//walk through each node and mark used nodes
//for garbage collection. Each node will be
//locked. It becomes unlocked when the next
//is locked or when the operation is completed.
do{
cur->plock.lock();
if(prev){
prev->plock.unlock();
prev =NULL;
}
if(cur->isunused){
prev = cur;
}else{
h =((size_t)cur->min)/ l;
if(cur->min < min[h]){
min[h]= cur->min;
}
if(cur->max > max[h]){
max[h]= cur->max;
}
cur->skip = fnd[h];
fnd[h]= cur;
cur->isunused =true;
++mc;
}
cur = cur->next;
}while(cur != pool);
if(prev){
prev->plock.unlock();
prev =NULL;
}
//The following searches each node of a list for
//references to previously allocated memory. Each
//list item represents a range for memory from which
//each byte is searched for references to a block of
//memory.
for(int r =0; r < num_roots; r++){
roots[r].gcnext= check;
check =&(roots[r]);
}
tc = mc;
while(check && tc){
char* c = check->min;
char* e = check->max;
while(c < e && tc){
ptr =*((char**)c++);
h =((size_t)ptr)/ l;
found =false;
for(int i = h; i <= NUM_SCAN_BUFFER &&!found; i++){
if(ptr >= min[h]&& ptr <= max[h]){
cur = fnd[h];
prev =NULL;
while(cur){
//compare possible pointer with the values
//of the current node
if(ptr >= cur->min && ptr <= cur->max){
cur->isunused =false;
--tc;
if(prev){
prev->skip = cur->skip;
}else{
fnd[h]= cur->skip;
}
cur->gcnext = check->gcnext;
check->gcnext = cur;
cur->plock.unlock();
//there cannot be multiple references from a single
//pointer so lets skip the rest
found =true;
break;
}else{
prev = cur;
}
cur = cur->skip;
}
}
}
}
if(check == check->gcnext){
system("pause");
}
check = check->gcnext;
}
num_objects = mc - tc;
mc =0;
for(int i =0; i < NUM_SCAN_BUFFER; i++){
while(fnd[i]){
prev = fnd[i];
fnd[i]= fnd[i]->skip;
prev->plock.unlock();
mc++;
}
}
num_deallocs = mc;
}else{
rlock.lock();//just wait when gc is in progress
}
rlock.unlock();
}
void* GCAlloc(size_t size){
if(size){
bool firstry =true;
if(num_objects > NUM_OBJECT_SLOWDOWN){//slow down allocator when dealing with many objects
Ich würde an deiner Stelle einfach mal profilen. Außerdem ist meine Vermutung, dass es den Cache signifikant entlasten würde, wenn du gar keine Linked List mehr verwenden würdest oder als Alternative vlt. auch immer eine bestimmte Anzahl Objekte in einem Node vereinst.
An deiner Stelle würde ich auch mal schauen Atomics anstatt "volatile" zu verwenden. Das das funktioniert, ist nämlich nicht im Standard garantiert. Außer wenn du sehr alte Versionen von Compilern unterstützen willst, ist das eine sicherere und auch wesentlich flexiblere Alternative. Ich würde auch mal schauen, die "volatile" bzw. Atomic-Zugriffe zum Beispiel aus dem Loops herauszuziehen und vorher in einer lokalen Variable zu cachen. (Zum Beispiel bei "for (int r = 0; r < num_roots; r++)"). Der Compiler kann das nämlich nicht selbst machen, weil "volatile" ihn dazu zwingt die Variable jedes mal neu zu laden und nicht in einem Register zwischenzuspeichern.
Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern
Nach meiner bisherigen Erfahrung ist das wohl abhängig von der jeweiligen Applikation. Halt je nachdem wie Stark die einzelnen Threads alles fragmentieren oder wie groß deine Objekte sind etc..
Da müsste man wohl das Ganze etwas länger mit richtigen Anwendungen testen. Was allerdings bei allen meiner Versuchs... ähh Freunde richtig viel gebracht hat ist folgender Zusatz:
Code:
cur = (memhdr_t*)(ptr - sizeof(memhdr_t));
if (cur->min == ptr && cur->isunused) {
--tc;
cur->isunused = false;
cur->gcnext = check->gcnext;
check->gcnext = cur;
cur->plock.unlock();
break;
}
Die meisten verschieben den erstellen Pointer nicht mehr und von daher braucht man hier auch keine Range-Checks über die Liste ... eventuell sollte man hier auch eher eine Art perfect Hash bauen der komplett ohne Listen oder Arrays und co. auskommt.
Um die registrierten Roots brauchst du dich übrigens gar nicht kümmern. Da wird wohl so schnell kein Bottleneck entstehen ... jedenfalls nicht wenn jemand noch 3 Hirnzellen hat
Registriert: Di Mai 18, 2004 16:45 Beiträge: 2621 Wohnort: Berlin
Programmiersprache: Go, C/C++
Ich weiß, dass die neueren CPU's(Intel i5/i7 AMD K10) indirect pointer auflösen können. Dies war ne Optimierung um Objekt Orientierte Sprachen wie C#, C++ und Java zu beschleunigen, weil die in der Regel ein pointer(auf das Objekt) auf ein pointer(vtable/rtti) enthalten. Daher sind diese um einige % schneller bei jeglicher art von Software. Ich hab mich nicht weiter damit beschäftigt, als dass ich weiß das es existiert aber vieleicht greifen dort dann auch die Link Listen. In dem Fall könnte man sich eine Optimierung sparen.
Ich kann nur empfehlen AMD CodeXL auf einem AMD System mal laufen zu lassen. Die haben sehr viel für Intel CPU's nach gelegt aber für AMD bekommt man noch die Cache Effizienz für die einzelnen Level sowie weitere tiefliegende Profielinformationen. Ich hab auf Arbeit extra wegen GPU und CPU Profiling und Debugging ein AMD System bekommen und die anderen haben ein Intel & NV System.
Wegen GC würde ich vieleicht mal bei Java rein schauen, JRocket soll z.B. ein sehr guten GC haben. Vieleicht haben die ja noch Papers was so deren Erfahrung ist. JRockit Mission Control z.B. zeigt mir, dass die sich sehr wohl bewusst sind, was man so alles mit GC profilen und optimieren kann.
Es wäre praktisch den mal im Release gegen malloc/new/new[] laufen zu lassen. Wenn die auf gleiche Performance kommen, würde ich mir keine weiteren gedanken mehr machen.
_________________ "Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren" Benjamin Franklin
Um ehrlich zu sein, glaube ich eher nicht an die Optimierung in neueren Prozessoren. Es kann sein, dass solche Optimierungen das Problem leicht abschwächen, aber wohl kaum auflösen. Zum einen sind Linked Lists nicht bloß Doppelpointer sondern "Endlospointer", zum anderen ist auch die Zerstreuung und Verschwendung des Caches ein Problem.
Mitglieder in diesem Forum: 0 Mitglieder und 52 Gäste
Du darfst keine neuen Themen in diesem Forum erstellen. Du darfst keine Antworten zu Themen in diesem Forum erstellen. Du darfst deine Beiträge in diesem Forum nicht ändern. Du darfst deine Beiträge in diesem Forum nicht löschen. Du darfst keine Dateianhänge in diesem Forum erstellen.