From: Daniel DeLorme <dan-ml@dan42.com>
To: ruby-core@ruby-lang.org
Subject: Re: Copy-on-write friendly garbage collector
Date: Sat, 8 Mar 2008 16:50:47 +0900 [thread overview]
Message-ID: <47D24561.9090909@dan42.com> (raw)
In-Reply-To: <47D2255C.2010205@dan42.com>
[-- Attachment #1: Type: text/plain, Size: 262 bytes --]
I believe I managed to close the performance gap to only 6% slower than
the current implementation (but I must admit I have trouble getting
consistently reproducible benchmarks). The attached patch should be
added on top of the one in Matz' email.
--
Daniel
[-- Attachment #2: cow-dan.patch --]
[-- Type: text/x-patch, Size: 3855 bytes --]
--- gc.c.1 2008-03-08 16:18:18.000000000 +0900
+++ gc.c.2 2008-03-08 16:40:20.000000000 +0900
@@ -151,6 +151,7 @@
void *membase;
RVALUE *slot;
int limit;
+ RVALUE *slotlimit;
int *marks;
int marks_size;
} *heaps;
@@ -457,31 +458,26 @@
find_heap_slot_for_object(RVALUE *object)
{
struct heaps_slot *heap;
- register long hi, lo, mid;
+ register int i;
/* Look in the cache first. */
if (last_heap != NULL && object >= last_heap->slot
- && object < last_heap->slot + last_heap->limit) {
+ && object < last_heap->slotlimit) {
return last_heap;
}
- /* find heap_slot for object using bsearch*/
- lo = 0;
- hi = heaps_used;
- while (lo < hi) {
- mid = (lo + hi) / 2;
- heap = &heaps[mid];
+ /* find heap_slot for object using linear search
+ * (faster than bsearch because there are only a few heaps)
+ */
+ for(i=0; i<heaps_used; i++) {
+ heap = &heaps[i];
if (heap->slot <= object) {
- if (object < heap->slot + heap->limit) {
+ if (object < heap->slotlimit) {
/* Cache this result. According to empirical evidence, the chance is
* high that the next lookup will be for the same heap slot.
*/
last_heap = heap;
return heap;
}
- lo = mid + 1;
- }
- else {
- hi = mid;
}
}
return NULL;
@@ -598,6 +594,7 @@
p = (RVALUE*)((VALUE)p + sizeof(RVALUE) - ((VALUE)p % sizeof(RVALUE)));
heaps[heaps_used].slot = p;
heaps[heaps_used].limit = heap_slots;
+ heaps[heaps_used].slotlimit = p + heap_slots;
heaps[heaps_used].marks_size = (int) (ceil(heap_slots / (sizeof(int) * 8.0)));
heaps[heaps_used].marks = (int *) calloc(heaps[heaps_used].marks_size, sizeof(int));
break;
@@ -837,13 +834,15 @@
gc_mark_all(void)
{
RVALUE *p, *pend;
+ struct heaps_slot *heap;
int i;
init_mark_stack();
for (i = 0; i < heaps_used; i++) {
- p = heaps[i].slot; pend = p + heaps[i].limit;
+ heap = &heaps[i];
+ p = heap->slot; pend = heap->slotlimit;
while (p < pend) {
- if (rb_mark_table_contains(p) && (p->as.basic.flags != 0)) {
+ if (rb_mark_table_heap_contains(heap, p) && (p->as.basic.flags != 0)) {
gc_mark_children((VALUE)p, 0);
}
p++;
@@ -1338,10 +1337,11 @@
int n = 0;
RVALUE *free = freelist;
RVALUE *final = final_list;
+ struct heaps_slot *heap = &heaps[i];
- p = heaps[i].slot; pend = p + heaps[i].limit;
+ p = heap->slot; pend = heap->slotlimit;
while (p < pend) {
- if (!rb_mark_table_contains(p)) {
+ if (!rb_mark_table_heap_contains(heap, p)) {
if (p->as.basic.flags) {
obj_free((VALUE)p);
}
@@ -1368,7 +1368,7 @@
/* do nothing here */
}
else {
- rb_mark_table_heap_remove(&heaps[i], p);
+ rb_mark_table_heap_remove(heap, p);
live++;
}
p++;
@@ -2161,6 +2161,7 @@
rb_gc_call_finalizer_at_exit(void)
{
RVALUE *p, *pend;
+ struct heaps_slot *heap;
int i;
/* finalizers are part of garbage collection */
@@ -2184,13 +2185,14 @@
}
/* run data object's finalizers */
for (i = 0; i < heaps_used; i++) {
- p = heaps[i].slot; pend = p + heaps[i].limit;
+ heap = &heaps[i];
+ p = heap->slot; pend = heap->slotlimit;
while (p < pend) {
if (BUILTIN_TYPE(p) == T_DATA &&
DATA_PTR(p) && RANY(p)->as.data.dfree &&
RANY(p)->as.basic.klass != rb_cThread) {
p->as.free.flags = 0;
- rb_mark_table_remove(p);
+ rb_mark_table_heap_remove(heap, p);
if ((long)RANY(p)->as.data.dfree == -1) {
RUBY_CRITICAL(free(DATA_PTR(p)));
}
@@ -2202,7 +2204,7 @@
else if (BUILTIN_TYPE(p) == T_FILE) {
if (rb_io_fptr_finalize(RANY(p)->as.file.fptr)) {
p->as.free.flags = 0;
- rb_mark_table_remove(p);
+ rb_mark_table_heap_remove(heap, p);
VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
}
}
next prev parent reply other threads:[~2008-03-08 7:52 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-03-03 9:48 Copy-on-write friendly garbage collector Hongli Lai
2008-03-03 12:38 ` Daniel DeLorme
2008-03-03 13:11 ` Yukihiro Matsumoto
2008-03-04 11:31 ` Gonzalo Garramuño
2008-03-07 12:04 ` Hongli Lai
2008-03-07 15:20 ` Paul Brannan
2008-03-07 16:22 ` Hongli Lai
2008-03-07 18:47 ` Joel VanderWerf
2008-03-08 5:34 ` Daniel DeLorme
2008-03-08 7:50 ` Daniel DeLorme [this message]
2008-03-08 10:01 ` Daniel DeLorme
2008-03-08 15:39 ` Yukihiro Matsumoto
2008-03-12 17:23 ` Hongli Lai
2008-03-12 17:38 ` Yukihiro Matsumoto
2008-03-13 0:48 ` Daniel DeLorme
2008-03-13 11:04 ` Hongli Lai
2008-03-15 16:15 ` Hongli Lai
2008-03-13 11:18 ` Hongli Lai
2008-03-14 3:20 ` Hongli Lai
2008-03-14 4:44 ` Daniel DeLorme
2008-03-14 11:25 ` Hongli Lai
2008-03-14 12:01 ` Meinrad Recheis
2008-03-14 15:00 ` Daniel Berger
2008-03-14 15:53 ` Hongli Lai
2008-03-14 17:34 ` Joel VanderWerf
2008-03-20 10:59 ` Hongli Lai
2008-03-20 11:55 ` Yukihiro Matsumoto
2008-03-20 12:54 ` Hongli Lai
2008-03-20 14:24 ` Yukihiro Matsumoto
2008-03-20 14:45 ` Hongli Lai
2008-03-20 15:28 ` Joel VanderWerf
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.ruby-lang.org/en/community/mailing-lists/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=47D24561.9090909@dan42.com \
--to=ruby-core@ruby-lang.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).