Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 16:51

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: Mini Collector
BeitragVerfasst: Di Okt 07, 2014 20:47 
Offline
DGL Member
Benutzeravatar

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:
  1.  
  2. //This is free and unencumbered software released into the public domain.
  3. //
  4. //Anyone is free to copy, modify, publish, use, compile, sell, or
  5. //distribute this software, either in source code form or as a compiled
  6. //binary, for any purpose, commercial or non - commercial, and by any
  7. //means.
  8. //
  9. //In jurisdictions that recognize copyright laws, the author or authors
  10. //of this software dedicate any and all copyright interest in the
  11. //software to the public domain.We make this dedication for the benefit
  12. //of the public at large and to the detriment of our heirs and
  13. //successors.We intend this dedication to be an overt act of
  14. //relinquishment in perpetuity of all present and future rights to this
  15. //software under copyright law.
  16. //
  17. //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18. //EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19. //MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20. //IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  21. //OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  22. //ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  23. //OTHER DEALINGS IN THE SOFTWARE.
  24. //
  25. //For more information, please refer to <http://unlicense.org/>
  26.  
  27.  
  28. #include <Windows.h>
  29.  
  30. typedef unsigned char byte;
  31.  
  32.  
  33. #define PTR_RSHIFT(ptr,offset) ((void*)(((byte*)ptr) + offset))
  34. #define PTR_LSHIFT(ptr,offset) ((void*)(((byte*)ptr) - offset))
  35.  
  36.  
  37. struct mem_block_s;
  38. struct mem_zone_s;
  39. struct gc_list_s;
  40.  
  41. //the following 2 data structures provide a 2 dimensional
  42. //dynamic ring-buffer for memory allocations. each allocation
  43. //will search a zone that has a free block of required size, if
  44. //no block was found a new zone is added to the zone-ring. If
  45. //the block can store more than the required size, it maybe
  46. //be split by the allocator.
  47.  
  48. typedef struct mem_block_s {
  49.     bool isfree;
  50.     size_t size;
  51.     struct mem_block_s * prev;
  52.     struct mem_block_s * next;
  53.     struct mem_zone_s * zone;
  54. } mem_block_t;
  55.  
  56. typedef struct mem_zone_s {
  57.     size_t size;
  58.     size_t used;
  59.     struct mem_zone_s * prev;
  60.     struct mem_zone_s * next;
  61.     mem_block_t list;
  62.     mem_block_t * active;
  63. } mem_zone_t;
  64.  
  65. //list structure used by the garbage collector
  66.  
  67. typedef struct gc_list_s {
  68.     void * head; //current element
  69.     size_t size; //size of the current element
  70.     struct gc_list_s * next; //next element (if any)
  71. } gc_list_t;
  72.  
  73.  
  74. static char * stack_base = NULL; //lowest address of the stack
  75. static char * stack_end = NULL; //highest address of the stack
  76. static HANDLE gc_thread = NULL; //garbage collector thread
  77. static HANDLE gc_lock = NULL; //garbage collector mutex
  78. static gc_list_t * list_gc_mem = NULL; //list of all existing memory
  79. static gc_list_t * list_found_mem = NULL; //list of memory marked by the GC
  80. static gc_list_t * list_gc_roots = NULL; //list of additional GC roots
  81. static mem_zone_t * active_zone = NULL; //zone with highest priority
  82. static size_t mem_used = 0; //total amount of memory used by the application
  83. static size_t mem_size = 0; //total amount of memory allocated by the zones
  84. static size_t mem_count = 0; //total number of living allocations
  85. //readonly public interface :-)
  86. const size_t * m_used = &mem_used;
  87. const size_t * m_size = &mem_size;
  88. const size_t * m_count = &mem_count;
  89.  
  90.  
  91. //some shortcuts for mutex handling
  92. #define lock(handle) WaitForSingleObject(handle, INFINITE)
  93. #define unlock(handle) ReleaseMutex(handle)
  94.  
  95.  
  96. void zone_create(size_t size) {
  97.     mem_zone_t * zone = NULL;
  98.     if (size < 0xFFFFFF) {
  99.         size = 0xFFFFFF;
  100.     }
  101.     size += sizeof(mem_block_t);
  102.     zone = (mem_zone_t*)malloc(size + sizeof(mem_zone_t));
  103.     mem_size += size;
  104.     //initialize zone data by creating a new
  105.     //ring-buffer of blocks
  106.     mem_block_t * block;
  107.     zone->list.next = zone->list.prev = block = (mem_block_t*)PTR_RSHIFT(zone, sizeof(mem_zone_t));
  108.     zone->list.isfree = false;
  109.     zone->list.size = 0;
  110.     zone->active = block;
  111.     zone->size = size;
  112.     zone->used = sizeof(mem_block_t);
  113.     block->prev = block->next = &(zone->list);
  114.     block->isfree = true;
  115.     block->size = size - sizeof(mem_zone_t);
  116.     block->zone = zone->list.zone = zone;
  117.     //add zone to the ring-buffer
  118.     if (active_zone) {
  119.         zone->next = active_zone;
  120.         zone->prev = active_zone->prev;
  121.         active_zone->prev = zone;
  122.         zone->prev->next = zone;
  123.     } else {
  124.         zone->prev = zone->next = zone;
  125.     }
  126.     //give the new zone the highest priority as it is completly empty
  127.     active_zone = zone;
  128. }
  129.  
  130.  
  131. void mem_free(void * ptr) {
  132.     if (ptr) {
  133.         mem_block_t * block;
  134.         mem_zone_t * zone;
  135.         block = (mem_block_t*)PTR_LSHIFT(ptr, sizeof(mem_block_t));
  136.         zone = block->zone;
  137.         if (block->isfree) { //nothing todo here
  138.             return;
  139.         }
  140.         //update counters
  141.         zone->used -= block->size;
  142.         mem_count--;
  143.         mem_used -= block->size;
  144.         memset(ptr, 0xFF, block->size - sizeof(mem_block_t));
  145.         block->isfree = true;
  146.         //merge nodes so they form a larger block of memory
  147.         while (block->prev->isfree) {
  148.             block = block->prev;
  149.             block->size += block->next->size;
  150.             block->next->prev = block;
  151.             block->next = block->next->next;
  152.         }
  153.         while (block->next->isfree) {
  154.             block->size += block->next->size;
  155.             block->next->prev = block;
  156.             block->next = block->next->next;
  157.         }
  158.         //give the node the highest priority
  159.         zone->active = block;
  160.     }
  161. }
  162.  
  163. void * mem_alloc(size_t size) {
  164.     if (size) {
  165.         mem_zone_t * zone = active_zone;
  166.         mem_block_t * start;
  167.         mem_block_t * pout;
  168.         size += sizeof(mem_block_t);
  169.         size = (size + 7) & ~7; //align size
  170.         do {
  171.             //search a zone that fits the required size
  172.             pout = NULL;
  173.             start = NULL;
  174.             if (zone->size > (size + zone->used)) {
  175.                 pout = zone->active;
  176.                 start = pout->prev;
  177.                 do {
  178.                     //search a block that fits the size and is free
  179.                     if (start == pout) {
  180.                         pout = NULL;
  181.                         break;
  182.                     }
  183.                     if (pout->isfree && pout->size >= size) {
  184.                         break;
  185.                     }
  186.                     pout = pout->next;
  187.                 } while (pout->size < size || !pout->isfree);
  188.                 if (pout) {
  189.                     //we have a result so lets mark it as non-free
  190.                     pout->isfree = false;
  191.                     break;
  192.                 }
  193.             }
  194.             if (zone->next == active_zone) {
  195.                 zone_create(size);
  196.             }
  197.             zone = zone->next;
  198.         } while (true);
  199.         //split node if enough memory is left
  200.         if (pout->size > (size + 128)) {
  201.             mem_block_t * tmp = (mem_block_t*)PTR_RSHIFT(pout, size);
  202.             tmp->size = pout->size - size;
  203.             tmp->isfree = true;
  204.             tmp->prev = pout;
  205.             tmp->zone = pout->zone;
  206.             tmp->next = pout->next;
  207.             tmp->next->prev = tmp;
  208.             pout->next = tmp;
  209.             pout->size = size;
  210.         }
  211.         //update counters
  212.         zone->used += pout->size;
  213.         mem_used += pout->size;
  214.         mem_count++;
  215.         zone->active = pout->next;
  216.         return PTR_RSHIFT(pout, sizeof(mem_block_t));
  217.  
  218.     }
  219.     return NULL;
  220. }
  221.  
  222. //checks if a list of memory is referenced
  223. //by the given range of memory.
  224. gc_list_t * gc_mark(gc_list_t * check, char * start, char * end) {
  225.     char * i = start;
  226.     char ** p = NULL;
  227.     gc_list_t * not_found = check; //initially all pointers are unmarked
  228.     gc_list_t * cmem = NULL;
  229.     gc_list_t * tmem = NULL;
  230.  
  231.     end -= sizeof(char*) - 1;
  232.     check = list_found_mem;
  233.  
  234.     //walk through each possible pointer value of the range
  235.     for (; i < end && not_found; i += 1) {
  236.         p = (char**)i;
  237.         if (*p) {
  238.             cmem = not_found;
  239.             not_found = NULL;
  240.             while (cmem) { //update our lists
  241.                 tmem = cmem;
  242.                 cmem = cmem->next;
  243.                 if (*p == tmem->head) { //mark pointer
  244.                     tmem->next = list_found_mem;
  245.                     list_found_mem = tmem;
  246.                 } else { //leave pointer unmarked
  247.                     tmem->next = not_found;
  248.                     not_found = tmem;
  249.                 }
  250.             }
  251.         }
  252.     }
  253.     //check marked pointer for references to unmarked pointers
  254.     if (list_found_mem != check) {
  255.         cmem = list_found_mem;
  256.  
  257.         while (cmem && not_found) {
  258.             not_found = gc_mark(not_found, (char*)cmem->head, (char*)cmem->head + cmem->size);
  259.             cmem = cmem->next;
  260.         }
  261.     }
  262.     //return unmarked pointers
  263.     return not_found;
  264. }
  265.  
  266. //main function of the gc thread
  267. void gc_collect(void) {
  268.     while (true) {
  269.         lock(gc_lock);
  270.         gc_list_t * tmp = list_gc_mem;
  271.         gc_list_t * not_found = NULL;
  272.         list_gc_mem = NULL;
  273.         list_found_mem = NULL;
  274.         not_found = gc_mark(tmp, stack_base, stack_end);
  275.         tmp = list_gc_roots;
  276.         while (tmp) {
  277.             not_found = gc_mark(not_found, (char*)tmp->head, (char*)tmp->head + tmp->size);
  278.             tmp = tmp->next;
  279.         }
  280.         while (list_found_mem) {
  281.             tmp = list_found_mem;
  282.             list_found_mem = list_found_mem->next;
  283.             tmp->next = list_gc_mem;
  284.             list_gc_mem = tmp;
  285.         }
  286.         while (not_found) {
  287.             void * tmp = not_found;
  288.             not_found = not_found->next;
  289.             mem_free(tmp);
  290.         }
  291.  
  292.         unlock(gc_lock);
  293.         Sleep(2);
  294.     }
  295. }
  296.  
  297. //called when the main thread exits
  298. void mem_finish(void) {
  299.     mem_zone_t * zone = active_zone;
  300.     TerminateThread(gc_thread, 0);//stop gc thread
  301.     //clear all allocated zones
  302.     do {
  303.         void * tmp = zone;
  304.         zone = zone->next;
  305.         free(tmp);
  306.     } while (zone != active_zone);
  307. }
  308.  
  309.  
  310. //called you use ref_alloc the first time.
  311. void mem_init(void) {
  312.     //get addresses of the stack
  313.     NT_TIB* tib = NULL;
  314. #if _WIN64
  315.     unsigned __int64 tib_p = __readgsqword(0x30);
  316. #else
  317.     unsigned __int32 tib_p = __readfsdword(0x18);
  318. #endif
  319.     memcpy(&tib, &tib_p, sizeof(tib_p));
  320.     if (tib->StackBase < tib->StackLimit) {
  321.         stack_base = (char*)tib->StackBase;
  322.         stack_end = (char*)tib->StackLimit;
  323.     } else {
  324.         stack_base = (char*)tib->StackLimit;
  325.         stack_end = (char*)tib->StackBase;
  326.     }
  327.     //create first zone with default size
  328.     zone_create(0);
  329.     //create GC mutex and thread
  330.     gc_lock = CreateMutex(NULL, false, NULL);
  331.     gc_thread = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)& gc_collect, NULL, 0, 0);
  332.  
  333. }
  334.  
  335. void ref_push_root(void *ptr, size_t size) {
  336.     lock(gc_lock);
  337.     gc_list_t * item = (gc_list_t *)malloc(sizeof(gc_list_t));
  338.     item->head = ptr;
  339.     item->size = size;
  340.     item->next = list_gc_roots;
  341.     list_gc_roots = item;
  342.     unlock(gc_lock);
  343. }
  344.  
  345.  
  346. //retrieves memory from a zone and updates the GC list
  347. void * ref_alloc(size_t size) {
  348.     if (stack_base == NULL) {
  349.         mem_init();
  350.         atexit(mem_finish);
  351.     }
  352.     if (size) {
  353.         lock(gc_lock);
  354.         gc_list_t * pout = (gc_list_t *)mem_alloc(size + sizeof(gc_list_t));
  355.         if (pout) {
  356.             pout->head = PTR_RSHIFT(pout, sizeof(gc_list_t));
  357.             pout->size = size;
  358.             memset(pout->head, 0, size);
  359.             pout->next = list_gc_mem;
  360.             list_gc_mem = pout;
  361.             unlock(gc_lock);
  362.             return pout->head;
  363.         }
  364.         unlock(gc_lock);
  365.     }
  366.     return NULL;
  367. }
  368.  
  369.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Okt 14, 2014 10:12 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Sieht interessant aus, ich würde noch
Code:
  1. //readonly public interface :-)
  2. const size_t * m_used = &mem_used;
  3. const size_t * m_size = &mem_size;
  4. const size_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

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Okt 14, 2014 19:20 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Mhh ja Performance-Technisch würde ich da nicht viel Ändern.
Hier mal noch einmal das Ganze plus die Änderungen aus meiner Engine.


Code:
  1.  
  2. //This is free and unencumbered software released into the public domain.
  3. //
  4. //Anyone is free to copy, modify, publish, use, compile, sell, or
  5. //distribute this software, either in source code form or as a compiled
  6. //binary, for any purpose, commercial or non - commercial, and by any
  7. //means.
  8. //
  9. //In jurisdictions that recognize copyright laws, the author or authors
  10. //of this software dedicate any and all copyright interest in the
  11. //software to the public domain.We make this dedication for the benefit
  12. //of the public at large and to the detriment of our heirs and
  13. //successors.We intend this dedication to be an overt act of
  14. //relinquishment in perpetuity of all present and future rights to this
  15. //software under copyright law.
  16. //
  17. //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18. //EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19. //MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20. //IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  21. //OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  22. //ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  23. //OTHER DEALINGS IN THE SOFTWARE.
  24. //
  25. //For more information, please refer to <http://unlicense.org/>
  26.  
  27. #include "runtime.h"
  28. #include <Windows.h>
  29. #include <omp.h>
  30.  
  31. #define BT_MEM_MAGIC "BTGCMEM"
  32. #define BT_MEM_MAGIC_LEN 7
  33. #define BT_MEM_SET_MAGIC(magic) \
  34.     magic[0] = 'B';             \
  35.     magic[1] = 'T';             \
  36.     magic[2] = 'G';             \
  37.     magic[3] = 'C';             \
  38.     magic[4] = 'M';             \
  39.     magic[5] = 'E';             \
  40.     magic[6] = 'M';            
  41.  
  42. struct mem_block_s;
  43. struct mem_zone_s;
  44. struct gc_list_s;
  45.  
  46. //the following 2 data structures provide a 2 dimensional
  47. //dynamic ring-buffer for memory allocations. each allocation
  48. //will search a zone that has a free block of required size, if
  49. //no block was found a new zone is added to the zone-ring. If
  50. //the block can store more than the required size, it maybe
  51. //be split by the allocator.
  52.  
  53. typedef struct mem_block_s {
  54.     bool isfree;
  55.     size_t size;
  56.     void * self;
  57.     f_thiscall finalizer; //finalizer that is to be called upon deallocation
  58.     struct mem_block_s * prev;
  59.     struct mem_block_s * next;
  60.     struct mem_zone_s * zone;
  61. } mem_block_t;
  62.  
  63. typedef struct mem_zone_s {
  64.     size_t size;
  65.     size_t used;
  66.     struct mem_zone_s * prev;
  67.     struct mem_zone_s * next;
  68.     mem_block_t list;
  69.     mem_block_t * active;
  70. } mem_zone_t;
  71.  
  72. //list structure used by the garbage collector
  73.  
  74. typedef struct gc_list_s {
  75.     void * head; //current element
  76.     size_t size; //size of the current element
  77.     bool marked; //was this item found by the GC?
  78.     char magic[BT_MEM_MAGIC_LEN+1]; //magic number of this pointer
  79.     struct gc_list_s * next; //next element (if any)
  80. } gc_list_t;
  81.  
  82.  
  83. static char * stack_base = NULL; //lowest address of the stack
  84. static char * stack_end = NULL; //highest address of the stack
  85. static HANDLE gc_thread = NULL; //garbage collector thread
  86. static HANDLE gc_lock = NULL; //garbage collector mutex
  87. static gc_list_t * list_gc_mem = NULL; //list of all existing memory
  88. static gc_list_t * list_found_mem = NULL; //list of memory marked by the GC
  89. static mem_zone_t * active_zone = NULL; //zone with highest priority
  90. static size_t mem_used = 0; //total amount of memory used by the application
  91. static size_t mem_size = 0; //total amount of memory allocated by the zones
  92. static size_t mem_count = 0; //total number of living allocations
  93. static size_t num_gc_threads = 0; //total number of available worker threads
  94. static gc_list_t * class_finalizer = NULL;
  95. //readonly public interface :-)
  96. static bool mem_done = false;
  97. const size_t * const m_used = &mem_used;
  98. const size_t * const m_size = &mem_size;
  99. const size_t * const m_count = &mem_count;
  100.  
  101.  
  102. const int _fltused = 0; //required by the crt
  103.  
  104.  
  105. //some shortcuts for mutex handling
  106. #define lock(handle) WaitForSingleObject(handle, INFINITE)
  107. #define unlock(handle) ReleaseMutex(handle)
  108.  
  109. bool zone_create(size_t size) {
  110.     mem_zone_t * zone = NULL;
  111.     if (size < 0xFFFFFF) {
  112.         size = 0xFFFFFF;
  113.     }
  114.     size += sizeof(mem_block_t);
  115.     zone = (mem_zone_t*)HeapAlloc(GetProcessHeap(), 0,size + sizeof(mem_zone_t));
  116.     if (zone == NULL) {
  117.         return false;
  118.     }
  119.     mem_size += size;
  120.     //initialize zone data by creating a new
  121.     //ring-buffer of blocks
  122.     mem_block_t * block;
  123.     zone->list.next = zone->list.prev = block = (mem_block_t*)PTR_RSHIFT(zone, sizeof(mem_zone_t));
  124.     zone->list.isfree = false;
  125.     zone->list.size = 0;
  126.     zone->active = block;
  127.     zone->size = size;
  128.     zone->used = sizeof(mem_block_t);
  129.     block->prev = block->next = &(zone->list);
  130.     block->isfree = true;
  131.     block->size = size - sizeof(mem_zone_t);
  132.     block->zone = zone->list.zone = zone;
  133.     //add zone to the ring-buffer
  134.     if (active_zone) {
  135.         zone->next = active_zone;
  136.         zone->prev = active_zone->prev;
  137.         active_zone->prev = zone;
  138.         zone->prev->next = zone;
  139.     } else {
  140.         zone->prev = zone->next = zone;
  141.     }
  142.     //give the new zone the highest priority as it is completly empty
  143.     active_zone = zone;
  144.     return true;
  145. }
  146.  
  147. void mem_fin(void * ptr, f_thiscall finalizer) {
  148.     if (ptr) {
  149.         gc_list_t * gc = PTR_LSHIFT(ptr, sizeof(gc_list_t));
  150.         if (gc->head == ptr && mem_cmp(gc->magic, BT_MEM_MAGIC, BT_MEM_MAGIC_LEN) == 0) {
  151.             mem_fin(gc, finalizer);
  152.         } else {
  153.             mem_block_t * block = PTR_LSHIFT(ptr, sizeof(mem_block_t));
  154.             block->finalizer = finalizer;
  155.         }
  156.     }
  157. }
  158.  
  159. void mem_free(void * ptr) {
  160.     if (ptr) {
  161.         gc_list_t * gc = PTR_LSHIFT(ptr, sizeof(gc_list_t));
  162.         mem_block_t * block;
  163.         mem_zone_t * zone;
  164.  
  165.         if (gc->head == ptr && mem_cmp(gc->magic, BT_MEM_MAGIC, BT_MEM_MAGIC_LEN) == 0) {
  166.             mem_free(gc);
  167.             return;
  168.         }
  169.         block = (mem_block_t*)PTR_LSHIFT(ptr, sizeof(mem_block_t));
  170.         zone = block->zone;
  171.         if (block->isfree) { //nothing todo here
  172.             return;
  173.         }
  174.         if (block->finalizer && block->self) {
  175.             block->finalizer(block->self);
  176.             block->finalizer = NULL;
  177.         }
  178.         //update counters
  179.         zone->used -= block->size;
  180.         mem_count--;
  181.         mem_used -= block->size;
  182.         mem_set(ptr, 0xFF, block->size - sizeof(mem_block_t));
  183.         block->isfree = true;
  184.         //merge nodes so they form a larger block of memory
  185.         while (block->prev->isfree) {
  186.             block = block->prev;
  187.             block->size += block->next->size;
  188.             block->next->prev = block;
  189.             block->next = block->next->next;
  190.         }
  191.         while (block->next->isfree) {
  192.             block->size += block->next->size;
  193.             block->next->prev = block;
  194.             block->next = block->next->next;
  195.         }
  196.         //give the node the highest priority
  197.         zone->active = block;
  198.     }
  199. }
  200.  
  201. void * mem_alloc(size_t size) {
  202.     if (size) {
  203.         mem_zone_t * zone = active_zone;
  204.         mem_block_t * start;
  205.         mem_block_t * pout;
  206.         size += sizeof(mem_block_t);
  207.         size = (size + 7) & ~7; //align size
  208.  
  209.         do {
  210.             //search a zone that fits the required size
  211.             pout = NULL;
  212.             start = NULL;
  213.             if (zone->size > (size + zone->used)) {
  214.                 pout = zone->active;
  215.                 start = pout->prev;
  216.                 do {
  217.                     //search a block that fits the size and is free
  218.                     if (start == pout) {
  219.                         pout = NULL;
  220.                         break;
  221.                     }
  222.                     if (pout->isfree && pout->size >= size) {
  223.                         break;
  224.                     }
  225.                     pout = pout->next;
  226.                 } while (pout->size < size || !pout->isfree);
  227.                 if (pout) {
  228.                     //we have a result so lets mark it as non-free
  229.                     pout->isfree = false;
  230.                     break;
  231.                 }
  232.             }
  233.             if (zone->next == active_zone) {
  234.                 if (!zone_create(size)) {
  235.                     return NULL;
  236.                 }
  237.             }
  238.             zone = zone->next;
  239.         } while (true);
  240.         //split node if enough memory is left
  241.         if (pout->size > (size + 128)) {
  242.             mem_block_t * tmp = (mem_block_t*)PTR_RSHIFT(pout, size);
  243.             tmp->size = pout->size - size;
  244.             tmp->isfree = true;
  245.             tmp->prev = pout;
  246.             tmp->zone = pout->zone;
  247.             tmp->next = pout->next;
  248.             tmp->next->prev = tmp;
  249.             pout->next = tmp;
  250.             pout->size = size;
  251.         }
  252.         //update counters
  253.         zone->used += pout->size;
  254.         mem_used += pout->size;
  255.         mem_count++;
  256.         zone->active = pout->next;
  257.         pout->finalizer = NULL;
  258.         pout->self = PTR_RSHIFT(pout, sizeof(mem_block_t));
  259.         return pout->self;
  260.  
  261.     }
  262.     return NULL;
  263. }
  264.  
  265. //checks if a list of memory is referenced
  266. //by the given range of memory.
  267.  
  268. gc_list_t * gc_mark(gc_list_t * check, char * start, char * end) {
  269.     INT64 i = (INT64)(start - NULL);
  270.     INT64 s = i;
  271.     INT64 e = (INT64)(end - NULL) - (sizeof(char*) - 1);
  272.     gc_list_t * imem = NULL;
  273.     gc_list_t * tmp = NULL;
  274.     gc_list_t * not_found = NULL;
  275.     bool has_found = false;
  276.     if (check) {
  277.         //check all content for a pointer in our list
  278. #pragma omp parallel for
  279.         for (i = s; i < e; i += sizeof(void*)) {
  280.             void * p = *((void**)i);
  281.             if (p) {
  282.                 gc_list_t * cmem = check;
  283.                 while (cmem) {
  284.                     if (p >= cmem->head && p <= PTR_RSHIFT(cmem->head, cmem->size)) {
  285.                         cmem->marked = true;
  286.                         has_found = true;
  287.                     }
  288.                     cmem = cmem->next;
  289.                 }
  290.             }
  291.         }
  292.     }
  293.     if (has_found) {
  294.         imem = check;
  295.         while (imem) {
  296.             tmp = imem;
  297.             imem = imem->next;
  298.             if (tmp->marked) {
  299.                 tmp->next = list_found_mem;
  300.                 list_found_mem = tmp;
  301.             } else {
  302.                 tmp->next = not_found;
  303.                 not_found = tmp;
  304.             }
  305.         }
  306.         imem = list_found_mem;
  307.         while (imem && not_found) {
  308.             not_found = gc_mark(not_found, (char*)imem->head, (char*)PTR_RSHIFT(imem, imem->size));
  309.             imem = imem->next;
  310.         }
  311.     } else {
  312.         return check;
  313.     }
  314.     return not_found;
  315. }
  316.  
  317. //main function of the gc thread
  318.  
  319. void gc_collect(void) {
  320.     while (!mem_done) {
  321.         lock(gc_lock);
  322.         gc_list_t * tmp = list_gc_mem;
  323.         gc_list_t * not_found = NULL;
  324.         list_gc_mem = NULL;
  325.         list_found_mem = NULL;
  326.         bool not_full = false;
  327.         if (not_full) {
  328.             unlock(gc_lock);
  329.         }
  330.         not_found = gc_mark(tmp, stack_base, stack_end);
  331.         while (tmp) {
  332.             not_found = gc_mark(not_found, (char*)tmp->head, (char*)tmp->head + tmp->size);
  333.             tmp = tmp->next;
  334.         }
  335.         if (not_full) {
  336.             lock(gc_lock);
  337.         }
  338.         while (list_found_mem) {
  339.             tmp = list_found_mem;
  340.             tmp->marked = false;
  341.             list_found_mem = list_found_mem->next;
  342.             tmp->next = list_gc_mem;
  343.             list_gc_mem = tmp;
  344.         }
  345.         while (not_found) {
  346.             void * tmp = not_found;
  347.             not_found = not_found->next;
  348.             mem_free(tmp);
  349.         }
  350.  
  351.         unlock(gc_lock);
  352.         Sleep(2);
  353.     }
  354. }
  355.  
  356. //called when the main thread exits
  357.  
  358. void mem_finish(void) {
  359.     mem_zone_t * zone = active_zone;
  360.     mem_done = true;
  361.     lock(gc_thread);
  362.     while (list_gc_mem) {
  363.         mem_free(list_gc_mem);
  364.         list_gc_mem = list_gc_mem->next;
  365.     }
  366.     do {
  367.         void * tmp = zone;
  368.         zone = zone->next;
  369.         HeapFree(GetProcessHeap(),0,tmp);
  370.     } while (zone != active_zone);
  371. }
  372.  
  373.  
  374. //called you use ref_alloc the first time.
  375.  
  376. void mem_init(void) {
  377.     //get addresses of the stack
  378.     NT_TIB* tib = NULL;
  379. #if _WIN64
  380.     tib = (NT_TIB*)(__readgsqword(0x30));
  381. #else
  382.     tib = (NT_TIB*)(__readfsdword(0x18));
  383. #endif
  384.     if (tib->StackBase < tib->StackLimit) {
  385.         stack_base = (char*)tib->StackBase;
  386.         stack_end = (char*)tib->StackLimit;
  387.     } else {
  388.         stack_base = (char*)tib->StackLimit;
  389.         stack_end = (char*)tib->StackBase;
  390.     }
  391.     num_gc_threads = 1;
  392. #ifdef _OPENMP
  393.     int iCPU = omp_get_num_procs();
  394.     if (iCPU > 1) {
  395.         num_gc_threads = iCPU - 1;
  396.     }
  397.     omp_set_num_threads(num_gc_threads);
  398. #endif
  399.     //create first zone with default size
  400.     zone_create(0);
  401.     //create GC mutex and thread
  402.     gc_lock = CreateMutex(NULL, false, NULL);
  403.     gc_thread = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)& gc_collect, NULL, 0, 0);
  404.     Sleep(100); //give some time for startup
  405. }
  406.  
  407. //retrieves memory from a zone and updates the GC list
  408.  
  409. void * mem_allocs(size_t size) {
  410.     if (size) {
  411.         lock(gc_lock);
  412.         gc_list_t * pout = (gc_list_t *)mem_alloc(size + sizeof(gc_list_t) + 8);
  413.         if (pout) {
  414.             pout->head = PTR_RSHIFT(pout, sizeof(gc_list_t));
  415.             pout->size = size;
  416.             mem_set(pout->head, 0, size + 8);
  417.             BT_MEM_SET_MAGIC(pout->magic);
  418.             ((mem_block_t*)PTR_LSHIFT(pout, sizeof(mem_block_t)))->self = pout->head;
  419.             pout->marked = false;
  420.             pout->next = list_gc_mem;
  421.             list_gc_mem = pout;
  422.             unlock(gc_lock);
  423.             return pout->head;
  424.         }
  425.         unlock(gc_lock);
  426.     }
  427.     return NULL;
  428. }
  429.  
  430. size_t mem_len(void* ptr) {
  431.     if (ptr) {
  432.         gc_list_t * l = (gc_list_t*)PTR_LSHIFT(ptr, sizeof(gc_list_t));
  433.         return l->size;
  434.     }
  435.     return 0;
  436. }
  437.  
  438.  
  439.  
  440. void before_exit(f_callback fun) {
  441.     gc_list_t * tmp = (gc_list_t *)HeapAlloc(GetProcessHeap(), 0, sizeof(gc_list_t*));
  442.     tmp->head = (void*)fun;
  443.     tmp->next = class_finalizer;
  444.     class_finalizer = tmp;
  445. }
  446.  
  447. bool main(char * args);
  448.  
  449.  
  450.  
  451. void __cdecl mainCRTStartup() {
  452.     int mainret;
  453.     timeBeginPeriod(1);
  454.     mem_init();
  455.     mainret = main(GetCommandLine());
  456.     mem_finish();
  457.     gc_list_t * tmp = NULL;
  458.     f_callback fun = NULL;
  459.     while (class_finalizer) {
  460.         tmp = class_finalizer;
  461.         ((f_callback)(tmp->head))();
  462.         class_finalizer = class_finalizer->next;
  463.         HeapFree(GetProcessHeap(), 0, tmp);
  464.     }
  465.     timeEndPeriod(1);
  466.     ExitProcess(mainret);
  467. }
  468.  
  469. void __cdecl WinMainCRTStartup() {
  470.     mainCRTStartup();
  471. }
  472.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Sa Dez 27, 2014 14:56 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Ganz frisch ausm Ofen (deswegen keine Comments):

Code:
  1.  
  2.  
  3. struct memroot_t {
  4.     thread_id_t tid;
  5.     char * min;
  6.     char * max;
  7.     memroot_t * rnext;
  8. };
  9.  
  10. struct memhdr_t : memroot_t {
  11.     bool isused;
  12.     bool mark;
  13.     memhdr_t * next;
  14.     size_t size;
  15. };
  16.  
  17. static int num_roots = 0;
  18. static memroot_t * roots = NULL;
  19. static memhdr_t * pool = NULL;
  20. static lock_t gclock;
  21.  
  22. void GCCollect_IMP(void) {
  23.     if (pool && num_roots) {
  24.         memhdr_t * cur = pool;
  25.         char * ps = pool->min;
  26.         char * pe = ps + MEMORY_POOL_SIZE;
  27.         memroot_t * root = NULL;
  28.         memroot_t * troot = NULL;
  29.         int mc = 0;
  30.         int tc = 0;
  31.         int r = 0;
  32.         while (cur) {
  33.             if (cur->isused) {
  34.                 cur->mark = true;
  35.                 cur->isused = false;
  36.                 ++mc;
  37.             }
  38.             cur = cur->next;
  39.         }
  40.         for (; r < num_roots; r++) {
  41.             roots[r].rnext = root;
  42.             root = &(roots[r]);
  43.         }
  44.         while (root && mc) {
  45.             char * c = root->min;
  46.             char * e = root->max;
  47.             troot = root;
  48.             while (c < e && mc) {
  49.                 char * ptr = *((char**)c++);
  50.                 if (ptr) {
  51.                     if (ptr >= ps && ptr <= pe) {
  52.                         cur = pool;
  53.                         while (cur) {
  54.                             if (cur->mark) {
  55.                                 if (ptr >= cur->min && ptr <= cur->max) {
  56.                                     cur->isused = true;
  57.                                     cur->mark = false;
  58.                                     --mc;
  59.                                     tc++;
  60.                                     cur->rnext = root;
  61.                                     root = cur;
  62.                                 }
  63.                             }
  64.                             cur = cur->next;
  65.                         }
  66.                     }
  67.                 }
  68.             }
  69.             if (troot == root) {
  70.                 root = root->rnext;
  71.             }
  72.         }
  73.     }
  74. }
  75.  
  76.  
  77. void GCCollect(void) {
  78.     gclock.lock();
  79.     GCCollect_IMP();
  80.     gclock.unlock();
  81. }
  82.  
  83. void GCRegisterRoot(thread_id_t id, char * min, char * max) {
  84.     gclock.lock();
  85.     for (int i = 0; i < num_roots; i++) {
  86.         if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t)) == 0) {
  87.             roots[i].min = min;
  88.             roots[i].max = max - sizeof(char*);
  89.             gclock.unlock();
  90.             return;
  91.         }
  92.     }
  93.     if (num_roots % 10 == 0) {
  94.         int nr = (num_roots / 10 + 1) * 10 + 1;
  95.         memroot_t * tmp = roots;
  96.         roots = (memroot_t*)calloc(nr, sizeof(memroot_t));
  97.         if (tmp) {
  98.             memcpy(roots, tmp, sizeof(memroot_t)*num_roots);
  99.             free(tmp);
  100.         }
  101.     }
  102.     roots[num_roots].min = min;
  103.     roots[num_roots].max = max - sizeof(char*);
  104.     memcpy(&(roots[num_roots].tid), &id, sizeof(thread_id_t));
  105.     roots[num_roots++].rnext = NULL;
  106.     gclock.unlock();
  107. }
  108.  
  109. void GCUnregisterRoot(thread_id_t id) {
  110.     gclock.lock();
  111.     for (int i = 0; i < num_roots; i++) {
  112.         if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t))) {
  113.             continue;
  114.         }
  115.         for (int j = i; j < num_roots; j++) {
  116.             memcpy(&(roots[j]), &(roots[j + 1]), sizeof(memroot_t));
  117.         }
  118.         break;
  119.     }
  120.     num_roots--;
  121.     gclock.unlock();
  122. }
  123.  
  124. void * GCAlloc(size_t size) {
  125.     if (pool) {
  126.         if (size) {
  127.             int tries = 0;
  128.             size += (sizeof(char*)) - (size % sizeof(char*));
  129.             gclock.lock();
  130.             for (; tries < 2; ++tries) {
  131.                 memhdr_t * cur = pool;
  132.                 while (cur) {
  133.                     if (!cur->isused) {
  134.                         cur->mark = false;
  135.                         while (cur->next && !cur->next->isused) {
  136.                             cur->size += sizeof(memhdr_t);
  137.                             cur->size += cur->next->size;
  138.                             cur->next = cur->next->next;
  139.                         }
  140.                         if (cur->size > size) {
  141.                             size_t left = cur->size - size;
  142.                             if (left > sizeof(memhdr_t)) {
  143.                                 memhdr_t * split = (memhdr_t*)(cur->min + size);
  144.                                 split->next = cur->next;
  145.                                 split->size = left - sizeof(memhdr_t);
  146.                                 split->isused = false;
  147.                                 split->min = ((char*)split) + sizeof(memhdr_t);
  148.                                 split->mark = false;
  149.                                 split->max = split->min + split->size - sizeof(char*);
  150.                                 cur->size = size;
  151.                                 cur->next = split;
  152.                                 cur->max = cur->min + cur->size - sizeof(char*);
  153.                             }
  154.                             cur->isused = true;
  155.                             gclock.unlock();
  156.                             return (void*)cur->min;
  157.                         }
  158.                     }
  159.                     cur = cur->next;
  160.                 }
  161.                 GCCollect_IMP();
  162.             }
  163.             gclock.unlock();
  164.         }
  165.     } else {
  166.         pool = (memhdr_t*)calloc(MEMORY_POOL_SIZE,1);
  167.         if (pool) {
  168.             pool->size = MEMORY_POOL_SIZE - sizeof(memhdr_t);
  169.             pool->min = ((char*)pool) + sizeof(memhdr_t);
  170.             pool->isused = false;
  171.             pool->max = pool->min + pool->size;
  172.             return GCAlloc(size);
  173.         }
  174.     }
  175.     return NULL;
  176. }
  177.  
  178. void GCFree(void * ptr) {
  179.     if (ptr) {
  180.         gclock.lock();
  181.         memhdr_t * hdr = (memhdr_t*)((char*)ptr - sizeof(memhdr_t));
  182.         hdr->isused = false;
  183.         gclock.unlock();
  184.     }
  185. }
  186.  


Die locks habe ich übrigens mit dem InterlockedCompareExchange gestaltet :)

Die thread id ist bei mir wie folgt definiert
Code:
  1.  
  2. struct thread_id_t {
  3. #ifdef _WIN64
  4.     long long tid;
  5.     long long fid;
  6. #else
  7.     long tid;
  8.     long fid;
  9. #endif
  10. };
  11.  
  12. NT_TIB * tib = NULL;
  13. #if _WIN64
  14.     tib = (NT_TIB*)(__readgsqword(0x30));
  15. #else
  16.     tib = (NT_TIB*)(__readfsdword(0x18));
  17. #endif
  18.     if (tib->StackBase < tib->StackLimit) {
  19.         self->stack_min = (char*)tib->StackBase;
  20.         self->stack_max = (char*)tib->StackLimit;
  21.     } else {
  22.         self->stack_max = (char*)tib->StackBase;
  23.         self->stack_min = (char*)tib->StackLimit;
  24.     }
  25. #if _WIN64
  26.     self->id.tid = (long long) GetCurrentThreadId();
  27.     self->id.tid = (long long) tib->FiberData;
  28. #else
  29.     self->id.tid = (long) GetCurrentThreadId();
  30.     self->id.tid = (long) tib->FiberData;
  31. #endif
  32.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Sa Dez 27, 2014 18:56 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Sieht wesentlich übersichtlicher aus als vorher :)

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: So Dez 28, 2014 13:20 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Fehlt aber noch einiges von dem was ich mir so vorgenommen habe :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: So Dez 28, 2014 14:36 
Offline
DGL Member
Benutzeravatar

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

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: So Dez 28, 2014 20:15 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Nu ich arbeite gerade an einer nicht-blockierenden Variante. Ich denke das ist ein must-have wenn es um Multithreading geht.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: So Dez 28, 2014 23:00 
Offline
DGL Member
Benutzeravatar

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 :)


Code:
  1.  
  2. //BroodTech ZweigEngine
  3. //created by Alex 'Yunharla' Schmidt
  4.  
  5. #include "shared.h"
  6.  
  7. struct memrng_t {
  8.     char * min;
  9.     char * max;
  10.     memrng_t * gcnext;
  11. };
  12.  
  13. struct memroot_t : memrng_t {
  14.     thread_id_t tid;
  15. };
  16.  
  17. struct memhdr_t : memrng_t, public lock_t {
  18.     bool isused;
  19.     bool mark;
  20.     size_t size;
  21.     lock_t plock;
  22.     memhdr_t * hskip;
  23.     memhdr_t * hnext;
  24. };
  25.  
  26. lock_t rlock = lock_t();
  27. static int num_roots = 0;
  28. static memroot_t *  roots = NULL;
  29. static memhdr_t * pool = NULL;
  30. static char * ps = NULL;
  31. static char * pe = NULL;
  32. int num_objects = 0;
  33.  
  34. void GCInit(void) {
  35.     pool = (memhdr_t*)calloc(MEMORY_POOL_SIZE, 1);
  36.     pool->min = ((char*)pool) + sizeof(memhdr_t);
  37.     pool->size = MEMORY_POOL_SIZE - sizeof(memhdr_t);
  38.     pool->max = pool->min + pool->size - sizeof(char*);
  39.     ps = pool->min;
  40.     pe = pool->max;
  41.     pool->unlock();
  42. }
  43.  
  44. void GCShutdown(void) {
  45.     free(pool);
  46.     pool = NULL;
  47.     ps = pe = NULL;
  48. }
  49.  
  50. void GCRegisterRoot(thread_id_t id, char * min, char * max) {
  51.     rlock.lock();
  52.     for (int i = 0; i < num_roots; i++) {
  53.         if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t)) == 0) {
  54.             roots[i].min = min;
  55.             roots[i].max = max - sizeof(char*);
  56.             rlock.unlock();
  57.             return;
  58.         }
  59.     }
  60.     if (num_roots % 10 == 0) {
  61.         if (num_roots == 0) {
  62.             GCInit();
  63.         }
  64.         int nr = (num_roots / 10 + 1) * 10 + 1;
  65.         memroot_t * tmp = roots;
  66.         roots = (memroot_t*)calloc(nr, sizeof(memroot_t));
  67.         if (tmp) {
  68.             memcpy(roots, tmp, sizeof(memroot_t)*num_roots);
  69.             free(tmp);
  70.         }
  71.     }
  72.     roots[num_roots].min = min;
  73.     roots[num_roots].max = max - sizeof(char*);
  74.     memcpy(&(roots[num_roots].tid), &id, sizeof(thread_id_t));
  75.     roots[num_roots++].gcnext = NULL;
  76.     rlock.unlock();
  77. }
  78.  
  79. void GCUnregisterRoot(thread_id_t id) {
  80.     rlock.lock();
  81.     if (num_roots == 1) {
  82.         GCShutdown();
  83.         free(roots);
  84.         roots = NULL;
  85.     } else {
  86.         for (int i = 0; i < num_roots; i++) {
  87.             if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t))) {
  88.                 continue;
  89.             }
  90.             for (int j = i; j < num_roots; j++) {
  91.                 memcpy(&(roots[j]), &(roots[j + 1]), sizeof(memroot_t));
  92.             }
  93.             break;
  94.         }
  95.         num_roots--;
  96.     }
  97.     rlock.unlock();
  98. }
  99.  
  100. void GCCollect(void) {
  101.     rlock.lock();
  102.     if (pool && num_roots) {
  103.         memhdr_t * cur = pool;
  104.         memhdr_t * prev = NULL;
  105.         memrng_t * root = NULL;
  106.         memrng_t * troot = NULL;
  107.         int mc = 0;
  108.         int tc = 0;
  109.         while (cur) {
  110.             if (cur->isused) {
  111.                 cur->lock();
  112.                 if (prev) {
  113.                     prev->hskip = cur;
  114.                 }
  115.                 prev = cur;
  116.                 cur->mark = true;
  117.                 cur->isused = false;
  118.                 ++mc;
  119.             }
  120.             cur = cur->hnext;
  121.         }
  122.         for (int r = 0; r < num_roots; r++) {
  123.             roots[r].gcnext = root;
  124.             root = &(roots[r]);
  125.         }
  126.         while (root && mc) {
  127.             char * c = root->min;
  128.             char * e = root->max;
  129.             troot = root;
  130.             while (c < e && mc) {
  131.                 char * ptr = *((char**)c++);
  132.                 if (ptr) {
  133.                     if (ptr >= ps && ptr <= pe) {
  134.                         cur = pool;
  135.                         prev = NULL;
  136.                         while (cur) {
  137.                             if (cur->mark) {
  138.                                 if (ptr >= cur->min && ptr <= cur->max) {
  139.                                     cur->isused = true;
  140.                                     cur->mark = false;
  141.                                     cur->unlock();
  142.                                     --mc;
  143.                                     tc++;
  144.                                     if (prev) {
  145.                                         prev->hskip = cur->hskip;
  146.                                     }
  147.                                     cur->gcnext = root;
  148.                                     root = cur;
  149.                                 } else {
  150.                                     prev = cur;
  151.                                 }
  152.                             }
  153.                             cur = cur->hskip;
  154.                         }
  155.                     }
  156.                 }
  157.             }
  158.             if (troot == root) {
  159.                 root = root->gcnext;
  160.             }
  161.         }
  162.  
  163.         num_objects = tc;
  164.         cur = pool;
  165.         while (cur) {
  166.             if (cur->mark) {
  167.                 cur->mark = false;
  168.                 cur->unlock();
  169.             }
  170.             cur = cur->hskip;
  171.         }
  172.     }
  173.     rlock.unlock();
  174. }
  175.  
  176. void * GCAlloc(size_t size) {
  177.     if (size) {
  178.         bool first = true;
  179.         memhdr_t * cur = pool;
  180.     second:
  181.         size += (sizeof(char*)) - (size & sizeof(char*));
  182.         while (cur) {
  183.             if (cur->isused) {
  184.                 cur = cur->hnext;
  185.                 continue;
  186.             } else if(cur->trylock()) {
  187.                 while (cur->hnext) {
  188.                     if (cur->hnext->isused) {
  189.                         break;
  190.                     } else if (cur->hnext->trylock()) {
  191.                         cur->size += sizeof(memhdr_t);
  192.                         cur->size += cur->hnext->size;
  193.                         cur->hnext = cur->hnext->hnext;
  194.                     } else {
  195.                         break;
  196.                     }
  197.                 }
  198.                 if (cur->size > size) {
  199.                     size_t left = cur->size - size;
  200.                     if (left > sizeof(memhdr_t)) {
  201.                         memhdr_t * split = (memhdr_t*)(cur->min + size);
  202.                         split->unlock();
  203.                         split->lock();
  204.                         split->hnext = cur->hnext;
  205.                         split->size = left - sizeof(memhdr_t);
  206.                         split->isused = false;
  207.                         split->min = ((char*)split) + sizeof(memhdr_t);
  208.                         split->mark = false;
  209.                         split->max = split->min + split->size - sizeof(char*);
  210.                         cur->size = size;
  211.                         cur->hnext = split;
  212.                         cur->max = cur->min + cur->size - sizeof(char*);
  213.                         split->unlock();
  214.                     }
  215.                     cur->isused = true;
  216.                     cur->unlock();
  217.                     num_objects++;
  218.                     return (void*)cur->min;
  219.                 }
  220.                 cur->unlock();
  221.             }
  222.             cur = cur->hnext;
  223.         }
  224.         if (first) {
  225.             first = false;
  226.             GCCollect();
  227.             goto second;
  228.         }
  229.     }
  230.     return NULL;
  231. }
  232.  
  233. void GCFree(void * ptr) {
  234.     if (ptr) {
  235.         memhdr_t * hdr = (memhdr_t*)((char*)ptr - sizeof(memhdr_t));
  236.         hdr->isused = false;
  237.     }
  238. }
  239.  
  240. void * operator new(size_t size){
  241.     return GCAlloc(size);
  242. }
  243.  
  244. void * operator new[](size_t size) {
  245.     return GCAlloc(size);
  246. }
  247.  
  248. void operator delete(void * ptr) {
  249.     GCFree(ptr);
  250. }
  251.  
  252. void operator delete[](void * ptr) {
  253.     GCFree(ptr);
  254. }
  255.  
  256.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Mo Dez 29, 2014 01:08 
Offline
DGL Member
Benutzeravatar

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

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Mo Dez 29, 2014 14:43 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
ersma bugs fixxen oder :D
[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) :D
Code:
  1.  
  2.  
  3.  
  4. //This is free and unencumbered software released into the public domain.
  5. //
  6. //Anyone is free to copy, modify, publish, use, compile, sell, or
  7. //distribute this software, either in source code form or as a compiled
  8. //binary, for any purpose, commercial or non - commercial, and by any
  9. //means.
  10. //
  11. //In jurisdictions that recognize copyright laws, the author or authors
  12. //of this software dedicate any and all copyright interest in the
  13. //software to the public domain.We make this dedication for the benefit
  14. //of the public at large and to the detriment of our heirs and
  15. //successors.We intend this dedication to be an overt act of
  16. //relinquishment in perpetuity of all present and future rights to this
  17. //software under copyright law.
  18. //
  19. //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20. //EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21. //MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  22. //IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  23. //OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  24. //ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25. //OTHER DEALINGS IN THE SOFTWARE.
  26. //
  27. //For more information, please refer to <http://unlicense.org/>
  28.  
  29. #include "shared.h"
  30. //a simple linked list used by the garbage collector to build and
  31. //handle searches for references. Each reference found by the GC, will
  32. //be added to the list so we can search for children.
  33. struct memrng_t {
  34.     char * min;
  35.     char * max;
  36.     memrng_t * gcnext;
  37. };
  38.  
  39. struct memroot_t : memrng_t {
  40.     thread_id_t tid;
  41. };
  42.  
  43. //the following defines a ring-buffer for memory allocations. Each
  44. //node contains a lock so we can use it for "none-blocking" garbage
  45. //collection.
  46. struct memhdr_t : memrng_t {
  47.     size_t size; //includes header and fragments
  48.     bool isunused;
  49.     memhdr_t * next;
  50.     memhdr_t * skip;
  51.     lock_t plock;
  52. };
  53.  
  54. static lock_t rlock = lock_t();
  55. volatile int num_roots = 0;
  56. static memroot_t *  roots = NULL;
  57. static memhdr_t * pool = NULL;
  58. static memhdr_t * pcur = NULL;
  59. static char * ps = NULL;
  60. static char * pe = NULL;
  61. volatile int num_objects = 0;
  62. volatile int num_deallocs = 0;
  63.  
  64. void GCCollect(void) {
  65.     if (rlock.trylock()) {
  66.         memhdr_t * cur = pool;
  67.         memhdr_t * prev = NULL;
  68.         memhdr_t * fnd[NUM_SCAN_BUFFER + 1];
  69.         char * min[NUM_SCAN_BUFFER + 1];
  70.         char * max[NUM_SCAN_BUFFER + 1];
  71.         memrng_t * check = NULL;
  72.         char * ptr = NULL;
  73.         int mc = 0;
  74.         int tc = 0;
  75.         bool found = false;
  76.         memset(max, 0, sizeof(max));
  77.         memset(min, 0xFFFFFF, sizeof(min));
  78.         memset(fnd, 0, sizeof(min));
  79.         size_t l = (pe - ps) / NUM_SCAN_BUFFER + 1;
  80.         size_t h = 0;
  81.         //walk through each node and mark used nodes
  82.         //for garbage collection. Each node will be
  83.         //locked. It becomes unlocked when the next
  84.         //is locked or when the operation is completed.
  85.         do {
  86.             cur->plock.lock();
  87.             if (prev) {
  88.                 prev->plock.unlock();
  89.                 prev = NULL;
  90.             }
  91.             if (cur->isunused) {
  92.                 prev = cur;
  93.             } else {
  94.                 h = ((size_t)cur->min) / l;
  95.                 if (cur->min < min[h]) {
  96.                     min[h] = cur->min;
  97.                 }
  98.                 if (cur->max > max[h]) {
  99.                     max[h] = cur->max;
  100.                 }
  101.                 cur->skip = fnd[h];
  102.                 fnd[h] = cur;
  103.                 cur->isunused = true;
  104.                 ++mc;
  105.             }
  106.             cur = cur->next;
  107.         } while (cur != pool);
  108.  
  109.         if (prev) {
  110.             prev->plock.unlock();
  111.             prev = NULL;
  112.         }
  113.         //The following searches each node of a list for
  114.         //references to previously allocated memory. Each
  115.         //list item represents a range for memory from which
  116.         //each byte is searched for references to a block of
  117.         //memory.
  118.         for (int r = 0; r < num_roots; r++) {
  119.             roots[r].gcnext = check;
  120.             check = &(roots[r]);
  121.         }
  122.         tc = mc;
  123.         while (check && tc) {
  124.             char * c = check->min;
  125.             char * e = check->max;
  126.             while (c < e && tc) {
  127.                 ptr = *((char**)c++);
  128.                 h = ((size_t)ptr) / l;
  129.                 found = false;
  130.                 for (int i = h; i <= NUM_SCAN_BUFFER && !found; i++) {
  131.                     if (ptr >= min[h] && ptr <= max[h]) {
  132.                         cur = fnd[h];
  133.                         prev = NULL;
  134.                         while (cur) {
  135.                             //compare possible pointer with the values
  136.                             //of the current node
  137.                             if (ptr >= cur->min && ptr <= cur->max) {
  138.                                 cur->isunused = false;
  139.                                 --tc;
  140.                                 if (prev) {
  141.                                     prev->skip = cur->skip;
  142.                                 } else {
  143.                                     fnd[h] = cur->skip;
  144.                                 }
  145.                                 cur->gcnext = check->gcnext;
  146.                                 check->gcnext = cur;
  147.                                 cur->plock.unlock();
  148.                                 //there cannot be multiple references from a single
  149.                                 //pointer so lets skip the rest
  150.                                 found = true;
  151.                                 break;
  152.                             } else {
  153.                                 prev = cur;
  154.                             }
  155.                             cur = cur->skip;
  156.                         }
  157.                     }
  158.                 }
  159.             }
  160.             if (check == check->gcnext) {
  161.                 system("pause");
  162.             }
  163.             check = check->gcnext;
  164.         }
  165.  
  166.         num_objects = mc - tc;
  167.         mc = 0;
  168.         for (int i = 0; i < NUM_SCAN_BUFFER; i++) {
  169.             while (fnd[i]) {
  170.                 prev = fnd[i];
  171.                 fnd[i] = fnd[i]->skip;
  172.                 prev->plock.unlock();
  173.                 mc++;
  174.             }
  175.         }
  176.         num_deallocs = mc;
  177.     } else {
  178.         rlock.lock(); //just wait when gc is in progress
  179.     }
  180.     rlock.unlock();
  181. }
  182.  
  183. void * GCAlloc(size_t size) {
  184.     if (size) {
  185.         bool firstry = true;
  186.         if (num_objects > NUM_OBJECT_SLOWDOWN) { //slow down allocator when dealing with many objects
  187.             Sleep(num_objects / NUM_OBJECT_SLOWDOWN);
  188.         }
  189.         size += sizeof(memhdr_t); //add block header size
  190.         size += sizeof(char*);
  191.         size = (size + (sizeof(char*) - 1)) & ~(sizeof(char*) - 1); //align
  192.     secondtry:
  193.         //you might want to use pool instead of pcur
  194.         //when dealing with many small objects as it runs
  195.         //a bit smoother in this case.
  196.         memhdr_t * start = pcur;
  197.         memhdr_t * cur = start;
  198.         memhdr_t * prev = NULL;
  199.         do {
  200.             if (cur->plock.trylock()) {
  201.                 if (cur->isunused) {
  202.                     //merge coherent blocks
  203.                     while (cur < cur->next && cur->next->plock.trylock()) {
  204.  
  205.                         if (cur->next->isunused) {
  206.                             cur->size += cur->next->size;
  207.                             cur->next = cur->next->next;
  208.                         } else {
  209.                             cur->next->plock.unlock();
  210.                             break;
  211.                         }
  212.                     }
  213.                     if (cur->size >= size) {
  214.                         size_t left = cur->size - size;
  215.                         //split the block if its big enough to hold another value
  216.                         if (left > (sizeof(memhdr_t) + 64)) {
  217.                             memhdr_t * split = (memhdr_t*)(((char*)cur) + size);
  218.                             split->size = left;
  219.                             split->isunused = true;
  220.                             split->next = cur->next;
  221.                             split->min = ((char*)split) + sizeof(memhdr_t);
  222.                             split->max = ((char*)split) + split->size - sizeof(char*);
  223.                             split->plock.unlock();
  224.                             cur->size = size;
  225.                             cur->max = ((char*)cur) + cur->size - sizeof(char*);
  226.                             cur->next = split;
  227.                             pcur = split;
  228.                         }
  229.                         cur->isunused = false;
  230.                         cur->plock.unlock();
  231.                         num_objects++;
  232.                         return (void*)cur->min;
  233.                     }
  234.                 }
  235.                 prev = cur;
  236.                 cur = cur->next;
  237.                 prev->plock.unlock();
  238.             } else {
  239.                 cur = cur->next;
  240.             }
  241.         } while (cur != start);
  242.         if (firstry) {
  243.             firstry = false;
  244.             GCCollect();
  245.             goto secondtry;
  246.         }
  247.     }
  248.     return NULL;
  249. }
  250.  
  251.  
  252. void GCInit(void) {
  253.     pool = (memhdr_t*)calloc(MEMORY_POOL_SIZE + sizeof(memhdr_t) + 1, 1);
  254.     if (pool) {
  255.         pool->size = MEMORY_POOL_SIZE;
  256.         pool->next = pool;
  257.         pool->isunused = true;
  258.         ps = pool->min = ((char*)pool) + sizeof(memhdr_t);
  259.         pe = pool->max = pool->min + MEMORY_POOL_SIZE - sizeof(char*);
  260.         pool->plock.unlock();
  261.     }
  262.     pcur = pool;
  263.     num_objects = 0;
  264. }
  265.  
  266. void GCShutdown(void) {
  267.     free(pool);
  268.     pool = NULL;
  269.     pcur = NULL;
  270.     ps = pe = NULL;
  271.     num_objects = 0;
  272. }
  273.  
  274. void GCRegisterRoot(thread_id_t id, char * min, char * max) {
  275.     rlock.lock();
  276.     for (int i = 0; i < num_roots; i++) {
  277.         if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t)) == 0) {
  278.             roots[i].min = min;
  279.             roots[i].max = max - sizeof(char*);
  280.             rlock.unlock();
  281.             return;
  282.         }
  283.     }
  284.     if (num_roots % 10 == 0) {
  285.         if (num_roots == 0) {
  286.             GCInit();
  287.         }
  288.         int nr = (num_roots / 10 + 1) * 10 + 1;
  289.         memroot_t * tmp = roots;
  290.         roots = (memroot_t*)calloc(nr, sizeof(memroot_t));
  291.         if (tmp) {
  292.             memcpy(roots, tmp, sizeof(memroot_t)*num_roots);
  293.             free(tmp);
  294.         }
  295.     }
  296.     roots[num_roots].min = min;
  297.     roots[num_roots].max = max - sizeof(char*);
  298.     memcpy(&(roots[num_roots].tid), &id, sizeof(thread_id_t));
  299.     roots[num_roots++].gcnext = NULL;
  300.     rlock.unlock();
  301. }
  302.  
  303. void GCUnregisterRoot(thread_id_t id) {
  304.     rlock.lock();
  305.     if (num_roots == 1) {
  306.         GCShutdown();
  307.         free(roots);
  308.         roots = NULL;
  309.     } else {
  310.         for (int i = 0; i < num_roots; i++) {
  311.             if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t))) {
  312.                 continue;
  313.             }
  314.             for (int j = i; j < num_roots; j++) {
  315.                 memcpy(&(roots[j]), &(roots[j + 1]), sizeof(memroot_t));
  316.             }
  317.             break;
  318.         }
  319.         num_roots--;
  320.     }
  321.     rlock.unlock();
  322. }
  323.  
  324. void GCFree(void * ptr) {
  325.     if (ptr) {
  326.         memhdr_t * hdr = (memhdr_t*)(((char*)ptr) - sizeof(memhdr_t));
  327.         if (rlock.trylock() && hdr->min == ptr && hdr->plock.trylock()) {
  328.             hdr->isunused = false;
  329.             rlock.unlock();
  330.             hdr->plock.unlock();
  331.         }
  332.     }
  333. }
  334.  
  335. void * operator new(size_t size){
  336.     return GCAlloc(size);
  337. }
  338.  
  339. void * operator new[](size_t size) {
  340.     return GCAlloc(size);
  341. }
  342.  
  343. void operator delete(void * ptr) {
  344.     GCFree(ptr);
  345. }
  346.  
  347. void operator delete[](void * ptr) {
  348.     GCFree(ptr);
  349. }
  350.  
  351.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Dez 30, 2014 15:33 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Dez 30, 2014 19:58 
Offline
DGL Member
Benutzeravatar

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:
  1.  
  2. cur = (memhdr_t*)(ptr - sizeof(memhdr_t));
  3.                                 if (cur->min == ptr && cur->isunused) {
  4.                                     --tc;
  5.                                     cur->isunused = false;
  6.                                     cur->gcnext = check->gcnext;
  7.                                     check->gcnext = cur;
  8.                                     cur->plock.unlock();
  9.                                     break;
  10.                                 }
  11.  


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 :P

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Dez 30, 2014 20:47 
Offline
DGL Member
Benutzeravatar

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

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Dez 30, 2014 22:13 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
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.

Ich verweise da mal wieder auf die Präsentation des Clang-Entwicklers: https://www.youtube.com/watch?v=fHNmRkzxHWs&t=34m41s


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 26 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.

Suche nach:
Gehe zu:  
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.056s | 18 Queries | GZIP : On ]