From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-patches-return-244414-listarch-gcc-patches=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 29055 invoked by alias); 6 Jul 2009 12:45:00 -0000
Received: (qmail 29046 invoked by uid 22791); 6 Jul 2009 12:45:00 -0000
X-SWARE-Spam-Status: No, hits=-2.2 required=5.0 	tests=AWL,BAYES_00,J_CHICKENPOX_91
X-Spam-Check-By: sourceware.org
Received: from acsinet12.oracle.com (HELO acsinet12.oracle.com) (141.146.126.234)     by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 06 Jul 2009 12:44:51 +0000
Received: from acsinet15.oracle.com (acsinet15.oracle.com [141.146.126.227]) 	by acsinet12.oracle.com (Switch-3.3.1/Switch-3.3.1) with ESMTP id n66Cib40021582 	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); 	Mon, 6 Jul 2009 12:44:38 GMT
Received: from abhmt007.oracle.com (abhmt007.oracle.com [141.146.116.16]) 	by acsinet15.oracle.com (Switch-3.3.1/Switch-3.3.1) with ESMTP id n66CkUQ6009002; 	Mon, 6 Jul 2009 12:46:30 GMT
Received: from [192.168.0.4] (/79.33.221.222) 	by default (Oracle Beehive Gateway v4.0) 	with ESMTP ; Mon, 06 Jul 2009 05:44:44 -0700
Message-ID: <4A51F1BA.4020301@oracle.com>
Date: Mon, 06 Jul 2009 13:19:00 -0000
From: Paolo Carlini <paolo.carlini@oracle.com>
User-Agent: Thunderbird 2.0.0.19 (X11/20081227)
MIME-Version: 1.0
To: Jason Merrill <jason@redhat.com>
CC: gcc-patches List <gcc-patches@gcc.gnu.org>
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>
In-Reply-To: <4A51F06B.2080006@redhat.com>
Content-Type: multipart/mixed;  boundary="------------040306050906060907090000"
X-IsSubscribed: yes
Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-patches.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-patches/>
List-Post: <mailto:gcc-patches@gcc.gnu.org>
List-Help: <mailto:gcc-patches-help@gcc.gnu.org>
Sender: gcc-patches-owner@gcc.gnu.org
X-SW-Source: 2009-07/txt/msg00265.txt.bz2

This is a multi-part message in MIME format.
--------------040306050906060907090000
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-length: 245

Hi,
> Sounds good, thanks.
For now, I'm collecting some data for the attached. When N grows (I
tried up to ~1000) the difference between patched / unpatched is
impressive, like O(N) vs O(N^2). Some numbers later...

Paolo.

////////////////////

--------------040306050906060907090000
Content-Type: text/x-c++src;
 name="memoizing2.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="memoizing2.cpp"
Content-length: 1123

#if defined(__MWERKS__)
#   pragma template_depth(2000)
#endif

#if defined(_MSC_VER)
#   pragma warning(disable: 4307)
#endif

#if defined(__ICL)
#   pragma warning(disable: 68)
#endif

#if !defined(N)
#   error "N is not defined!"
#endif

typedef unsigned long ulong;

// re-arranged recursive branches
template< int i, int test > struct fibonacci
{
#ifndef DIFF
    enum { v = ulong(fibonacci<i-2,test>::value) };
    enum { value = ulong(v) + ulong(fibonacci<i-1,test>::value) };
#else
    enum { value = ulong(fibonacci<i-1,test>::value) };
#endif
};

template< int test > struct fibonacci<0,test>
{
    enum { value = 0 };
};

template< int test > struct fibonacci<1,test>
{
    enum { value = 1 };
};

template< int n > struct test
    : fibonacci<N,n>
{
};

int main()
{
    return 
          ulong(test<0>::value)
        + ulong(test<1>::value)
        + ulong(test<2>::value)
        + ulong(test<3>::value)
        + ulong(test<4>::value)
        + ulong(test<5>::value)
        + ulong(test<6>::value)
        + ulong(test<7>::value)
        + ulong(test<8>::value)
        + ulong(test<9>::value)
        ;
}

--------------040306050906060907090000--