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 3476F1F0378 for ; Sun, 16 Mar 2008 01:17:03 +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 A1F66EA20 for ; Sun, 16 Mar 2008 01:15:32 +0900 (JST) Received: from localhost (localhost.nagaokaut.ac.jp [127.0.0.1]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id BBA328FC21 for ; Sun, 16 Mar 2008 01:15:34 +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 VNKSRk-0oI3K for ; Sun, 16 Mar 2008 01:15:34 +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 9928B8FC1B for ; Sun, 16 Mar 2008 01:15:34 +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 0A82C6300A4 for ; Sun, 16 Mar 2008 01:15:34 +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 18E643C223A7A; Sun, 16 Mar 2008 01:15:18 +0900 (JST) Received: from fk-out-0910.google.com (fk-out-0910.google.com [209.85.128.187]) by carbon.ruby-lang.org (Postfix) with ESMTP id 693833C223A61 for ; Sun, 16 Mar 2008 01:15:08 +0900 (JST) Received: by fk-out-0910.google.com with SMTP id f33so4492944fkf.7 for ; Sat, 15 Mar 2008 09:15:17 -0700 (PDT) Received: by 10.78.106.3 with SMTP id e3mr35398128huc.51.1205597717079; Sat, 15 Mar 2008 09:15:17 -0700 (PDT) Received: from ?192.168.0.100? ( [62.195.225.81]) by mx.google.com with ESMTPS id e10sm22452088muf.10.2008.03.15.09.15.14 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sat, 15 Mar 2008 09:15:14 -0700 (PDT) Delivered-To: ruby-core@ruby-lang.org Date: Sun, 16 Mar 2008 01:15:10 +0900 Posted: Sat, 15 Mar 2008 17:15:12 +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: <47DBF610.6070906@plan99.net> In-Reply-To: <47D811A6.1050805@plan99.net> References: <47D2255C.2010205@dan42.com> <47D24561.9090909@dan42.com> <47D811A6.1050805@plan99.net> X-ML-Name: ruby-core X-Mail-Count: 15913 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=-0.5 required=7.0 tests=ARIN,AWL,BAYES_40, 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=Vk7ZqZifznnVDTtDb2+yinOueAVEclVTgNrb5sWjKE8=; b=KM4+tgc8nFlsEMAmd7LTj4hx78EpO7LhrOoqDoBcZHfMKAioC8VxzkwO5ibKStA7Cun3DPz9wDYA6HVxEaX4NkWoYqErnE0ppKB6JVO1Wrfltr3cQyZ4DLgEBlkCPljcwUof0oY4tGOwKSWKRljThJn98CwxwvC3h9V30xdynmU= 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=EgTE1qA7U+33IRXhNw4UUeyburnMxCdvwznBi6gECcUhG/GCEZDoR+EobUtSTqQl5Q1/fqvF83ATyEtW1HlZH3ErLSQhIPbhJDLeIaTwB/pYbeuUcw62/U1RlD0YpppnfSC9glZ0OSe+znD+8I4CKJRnSYIcJM3g0IxZulG82V4= Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------020001080201060600020504" 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. --------------020001080201060600020504 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Hongli Lai wrote: > 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. I've been such a fool. The patch I sent uses platform-specific macros to figure out the base 2 log of sizeof(int)*8. Here is a new patch, which uses straight C code to figure out that value. There is no performance overhead because the code is easily optimizable by the compiler, and is a lot more portable. --------------020001080201060600020504 Content-Type: text/x-patch; name="ruby-portable-bitfield-operations.diff" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="ruby-portable-bitfield-operations.diff" diff --git a/marktable.c b/marktable.c index 84f88fe..5890835 100644 --- a/marktable.c +++ b/marktable.c @@ -51,20 +51,30 @@ find_position_in_bitfield(struct heaps_slot *hs, RVALUE *object, * 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 + if (sizeof(int) == 4 || sizeof(int) == 8 || sizeof(int) == 16) { + int int_bits_log; /* Must be equal to the base 2 logarithm of sizeof(int) * 8 */ + + switch (sizeof(int)) { + case 4: + int_bits_log = 5; + break; + case 8: + int_bits_log = 6; + break; + case 16: + int_bits_log = 7; + break; + default: + int_bits_log = 0; /* Shut up compiler warning. */ + abort(); + } + *bitfield_index = index >> int_bits_log; + *bitfield_offset = index & ((sizeof(int) * 8) - 1); + } else { *bitfield_index = index / (sizeof(int) * 8); *bitfield_offset = index % (sizeof(int) * 8); - #endif + } } --------------020001080201060600020504--