From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-407483-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 22101 invoked by alias); 22 Nov 2012 16:28:47 -0000
Received: (qmail 22068 invoked by uid 48); 22 Nov 2012 16:28:26 -0000
From: "david at aitellu dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/55442] New: G++ uses up all my RAM when compiling a constexpr with exponential call graph
Date: Thu, 22 Nov 2012 16:28:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: david at aitellu dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Changed-Fields:
Message-ID: <bug-55442-4@http.gcc.gnu.org/bugzilla/>
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
X-SW-Source: 2012-11/txt/msg02145.txt.bz2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55442

             Bug #: 55442
           Summary: G++ uses up all my RAM when compiling a constexpr with
                    exponential call graph
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: david@aitellu.com


I have compiled the following program on GCC 4.7.2 and the latest 4.8, using
Ubuntu 12.10 with Linux kernel 3.5.0:

const int MAXD = 24;

constexpr int count(int n, int depth=1){
  return depth == MAXD ? n + 1: count(count(n, depth + 1), depth + 1) + 1;
}

#include<iostream>

int main(){
  constexpr int i = count(0);
  std::cout << i << std::endl;
}

Both versions of GCC will use over 3.3 gig RAM in about 30 seconds. For each
step I increase MAXD, the RAM usage will double until my computer swaps or the
kernel kills the process.

It will never reach a recursion depth of more than 24, but the call graph is
sort of a binary tree, so it will visit 2^MAXD - 1 nodes. Since the recursion
is so shallow, it should not have to use any memory. Clang 3.1 compiles it
without using "any" memory.

Before posting this report, I asked on Stackoverflow, where it was suggested I
report it here.

My guess is that this has something to do with unlimited memoization?