From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2806 invoked by alias); 6 Jul 2009 18:47:10 -0000 Received: (qmail 2785 invoked by uid 22791); 6 Jul 2009 18:47:07 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx2.redhat.com (HELO mx2.redhat.com) (66.187.237.31) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 06 Jul 2009 18:47:02 +0000 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.13.8/8.13.8) with ESMTP id n66Il0UF024866; Mon, 6 Jul 2009 14:47:00 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx2.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n66Il0VH011106; Mon, 6 Jul 2009 14:47:00 -0400 Received: from [127.0.0.1] (sebastian-int.corp.redhat.com [172.16.52.221]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n66IkxcI017070; Mon, 6 Jul 2009 14:46:59 -0400 Message-ID: <4A5246A3.60302@redhat.com> Date: Mon, 06 Jul 2009 18:58:00 -0000 From: Jason Merrill User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1b3pre) Gecko/20090513 Fedora/3.0-2.3.beta2.fc11 Thunderbird/3.0b2 MIME-Version: 1.0 To: Paolo Carlini CC: gcc-patches List Subject: Re: C++ PATCH to use hash tables for template specialization lookup References: <4A4CEE11.5040604@redhat.com> <4A511AFF.4020902@oracle.com> <4A51F06B.2080006@redhat.com> <4A51F1BA.4020301@oracle.com> <4A5242CD.4040602@oracle.com> In-Reply-To: <4A5242CD.4040602@oracle.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2009-07/txt/msg00294.txt.bz2 On 07/06/2009 02:30 PM, Paolo Carlini wrote: > actually, for that specific benchmark, on the i7 420 I have here at > hand, the results are extremely neat: an almost perfect linear vs > quadratic behavior: probably there is an explanation for it Well, the old code is dominated by linked-list lookup, which is quadratic. The new code is no longer dominated by lookup time; it seems to spend most of its time actually doing the substitution, which is linear in the amount of stuff being substituted. Jason