From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: poffice@blade.nagaokaut.ac.jp Delivered-To: poffice@blade.nagaokaut.ac.jp Received: from kankan.nagaokaut.ac.jp (kankan.nagaokaut.ac.jp [133.44.2.24]) by blade.nagaokaut.ac.jp (Postfix) with ESMTP id 9BD331F0378 for ; Thu, 13 Mar 2008 02:25:45 +0900 (JST) Received: from funfun.nagaokaut.ac.jp (funfun.nagaokaut.ac.jp [133.44.2.201]) by kankan.nagaokaut.ac.jp (Postfix) with ESMTP id 446D1E0FF for ; Thu, 13 Mar 2008 02:24:15 +0900 (JST) Received: from localhost (localhost.nagaokaut.ac.jp [127.0.0.1]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id 9D8A98FC67 for ; Thu, 13 Mar 2008 02:24:17 +0900 (JST) X-Virus-Scanned: amavisd-new at funfun.nagaokaut.ac.jp Received: from funfun.nagaokaut.ac.jp ([127.0.0.1]) by localhost (funfun.nagaokaut.ac.jp [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BBpNzdHTMmaZ for ; Thu, 13 Mar 2008 02:24:17 +0900 (JST) Received: from voscc.nagaokaut.ac.jp (voscc.nagaokaut.ac.jp [133.44.1.100]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id 76DDC8FC66 for ; Thu, 13 Mar 2008 02:24:17 +0900 (JST) Received: from carbon.ruby-lang.org (carbon.ruby-lang.org [221.186.184.68]) by voscc.nagaokaut.ac.jp (Postfix) with ESMTP id 286CD630047 for ; Thu, 13 Mar 2008 02:24:14 +0900 (JST) Received: from beryllium.ruby-lang.org (beryllium.ruby-lang.org [127.0.0.1]) by carbon.ruby-lang.org (Postfix) with ESMTP id 4A00A3C21E7D3; Thu, 13 Mar 2008 02:24:01 +0900 (JST) Received: from nf-out-0910.google.com (nf-out-0910.google.com [64.233.182.184]) by carbon.ruby-lang.org (Postfix) with ESMTP id CC84D3C21EBA2 for ; Thu, 13 Mar 2008 02:23:52 +0900 (JST) Received: by nf-out-0910.google.com with SMTP id 4so1129142nfv.17 for ; Wed, 12 Mar 2008 10:24:00 -0700 (PDT) Received: by 10.78.90.10 with SMTP id n10mr22605274hub.79.1205342639526; Wed, 12 Mar 2008 10:23:59 -0700 (PDT) Received: from ?192.168.0.100? ( [62.195.225.81]) by mx.google.com with ESMTPS id 36sm15706249hub.16.2008.03.12.10.23.52 (version=TLSv1/SSLv3 cipher=RC4-MD5); Wed, 12 Mar 2008 10:23:56 -0700 (PDT) Delivered-To: ruby-core@ruby-lang.org Date: Thu, 13 Mar 2008 02:23:54 +0900 Posted: Wed, 12 Mar 2008 18:23:50 +0100 From: Hongli Lai Reply-To: ruby-core@ruby-lang.org Subject: Re: Copy-on-write friendly garbage collector Sender: Hongli Lai To: ruby-core@ruby-lang.org Message-Id: <47D811A6.1050805@plan99.net> In-Reply-To: <47D24561.9090909@dan42.com> References: <47D2255C.2010205@dan42.com> <47D24561.9090909@dan42.com> X-ML-Name: ruby-core X-Mail-Count: 15873 X-MLServer: fml [fml 4.0.3 release (20011202/4.0.3)]; post only (only members can post) X-ML-Info: If you have a question, send e-mail with the body "help" (without quotes) to the address ruby-core-ctl@ruby-lang.org; help= User-Agent: Thunderbird 2.0.0.12 (X11/20080227) X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on carbon.ruby-lang.org X-Spam-Level: X-Spam-Status: No, score=-1.1 required=7.0 tests=ARIN,AWL,BAYES_20, CONTENT_TYPE_PRESENT,QENCPTR2,RIPE_NCC autolearn=disabled version=3.1.7 X-Original-To: ruby-core@ruby-lang.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:sender; bh=qIInXLc0+VMFb2Q1otGc4SeSIevB1hY7Vtuvf4Hd2YU=; b=YEi3cb2b905F/WHqtr1JVixF4hGG10Q2IGb2Od+Gs03c8YoOxH294i9AjZg0iwsJKRIOc9RO2OhAhKJks2aPlmNn6qQLQF8NxGIKE/jarLzhxPTdBnuCe0BmgbnKAMvriEuBcuZCirRNpBpBplR3UFqj2V1GbR6LSWZh0/q8lkc= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:sender; b=ksOB3eGyPE3tAOjcJp2J7StdHpJIe8Zo8kAwhZ2PBy/u3NaEJ2RDK3Di/pzyiTyfTxJrbjbcHXhZgSElZIrHmSo/LgMoV1+fpX3XBmDjUlfvBPk2Nj2SgzzeJC01eQuli+vZOTG66X8vFzDIVPtI7A4+8GPdyCNtMNZFwNDkxZ8= Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------050506010506030303010701" Precedence: bulk List-Id: ruby-core.ruby-lang.org List-Software: fml [fml 4.0.3 release (20011202/4.0.3)] List-Post: List-Owner: List-Help: List-Unsubscribe: This is a multi-part message in MIME format. --------------050506010506030303010701 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Daniel DeLorme wrote: > 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 > Great work Daniel. I don't measure the same amount of speedup that you claim in your email, but there is definitely a small speedup. I've added some further further optimizations. find_position_in_bitfield() now uses bit operators instead of division and modulo operators. This should speed things up a little more. The attached patch is created against Ruby 1.8, but it shows what I've exactly changed. --------------050506010506030303010701 Content-Type: text/x-patch; name="gc-optimizations.diff" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="gc-optimizations.diff" diff --git a/gc.c b/gc.c index cb18a79..3ba5ec5 100644 --- a/gc.c +++ b/gc.c @@ -1142,6 +1142,7 @@ gc_sweep() int i; unsigned long live = 0; unsigned long free_min = 0; + struct heaps_slot *heap; for (i = 0; i < heaps_used; i++) { free_min += heaps[i].limit; @@ -1154,9 +1155,11 @@ gc_sweep() /* should not reclaim nodes during compilation if yacc's semantic stack is not allocated on machine 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) && BUILTIN_TYPE(p) == T_NODE) + if (!rb_mark_table_heap_contains(heap, p) && BUILTIN_TYPE(p) == T_NODE) gc_mark((VALUE)p, 0); p++; } @@ -1184,7 +1187,7 @@ gc_sweep() obj_free((VALUE)p); } if (need_call_final && FL_TEST(p, FL_FINALIZE)) { - rb_mark_table_add(p); /* remain marked */ + rb_mark_table_heap_add(heap, p); /* remain marked */ p->as.free.next = final_list; final_list = p; } diff --git a/marktable.c b/marktable.c index 7424633..412616f 100644 --- a/marktable.c +++ b/marktable.c @@ -34,10 +34,26 @@ find_position_in_bitfield(struct heaps_slot *hs, RVALUE *object, unsigned int *bitfield_index, unsigned int *bitfield_offset) { unsigned int index; - index = object - hs->slot; - *bitfield_index = index / (sizeof(int) * 8); - *bitfield_offset = index % (sizeof(int) * 8); + + /* + * We use bit operators to calculate the position in the bit field, whenever possible. + * This only works if sizeof(int) is a multiple of 2, but I don't know of any platform + * on which that is not true. + * + * The INT_BITS_LOG macro's value must be equal to the base 2 logarithm of sizeof(int). + */ + #ifdef __i386__ + #define INT_BITS_LOG 5 + #endif + + #ifdef INT_BITS_LOG + *bitfield_index = index >> INT_BITS_LOG; + *bitfield_offset = index & ((1 << INT_BITS_LOG) - 1); + #else + *bitfield_index = index / (sizeof(int) * 8); + *bitfield_offset = index % (sizeof(int) * 8); + #endif } @@ -81,6 +97,14 @@ rb_mark_table_add(RVALUE *object) } } +static inline void +rb_mark_table_heap_add(struct heaps_slot *hs, RVALUE *object) +{ + unsigned int bitfield_index, bitfield_offset; + find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset); + hs->marks[bitfield_index] |= (1 << bitfield_offset); +} + static inline int rb_mark_table_contains(RVALUE *object) { --------------050506010506030303010701--