Bug 56671 - Gcc uses large amounts of memory and processor power with large C++11 bitsets
Summary: Gcc uses large amounts of memory and processor power with large C++11 bitsets
Status: RESOLVED DUPLICATE of bug 84281
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 4.7.2
: P3 normal
Target Milestone: 8.0
Assignee: Not yet assigned to anyone
URL:
Keywords: compile-time-hog, memory-hog
: 63728 68399 69486 79225 (view as bug list)
Depends on:
Blocks:
 
Reported: 2013-03-21 01:34 UTC by m101010a
Modified: 2018-06-26 19:50 UTC (History)
10 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2016-01-26 00:00:00


Attachments
callgraph (25.03 KB, image/png)
2013-03-21 08:31 UTC, Markus Trippelsdorf
Details

Note You need to log in before you can comment on or make changes to this bug.
Description m101010a 2013-03-21 01:34:48 UTC
When I attempt to instantiate std::bitset<1024*1024*1024> in C++98 mode, compilation takes a quarter-second and uses almost no RAM.  In C++11 mode, it takes 8 seconds and almost 2GB of RAM.  The time and memory usage appear to scale linearly with the size of the bitset.  No errors or warnings are reported in either mode.

Full code:
#include <bitset>
int main()
{
	std::bitset<1024*1024*1024> bs;
}

Compilation lines:
g++ -std=c++98 x.cpp
g++ -std=c++11 x.cpp

g++ -v:
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /build/src/gcc-4.7.2/configure --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/ --enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared --enable-threads=posix --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch --enable-libstdcxx-time --enable-gnu-unique-object --enable-linker-build-id --with-ppl --enable-cloog-backend=isl --disable-ppl-version-check --disable-cloog-version-check --enable-lto --enable-gold --enable-ld=default --enable-plugin --with-plugin-ld=ld.gold --with-linker-hash-style=gnu --enable-multilib --disable-libssp --disable-build-with-cxx --disable-build-poststage1-with-cxx --enable-checking=release
Thread model: posix
gcc version 4.7.2 (GCC)
Comment 1 Markus Trippelsdorf 2013-03-21 08:31:57 UTC
Created attachment 29703 [details]
callgraph

Looks like a bug in constant expression handling.

perf shows:
 15.51%   cc1plus  cc1plus            [.] gt_ggc_mx_lang_tree_node(void*)
 11.14%   cc1plus  cc1plus            [.] walk_tree_1(tree_node**, tree_node* (*)(tree_node**, int*, void*), void*, pointer_set_t*, tree_node* (*)(tree_node**, int*, tree_no
  9.54%   cc1plus  cc1plus            [.] htab_expand.1557810
  7.28%   cc1plus  cc1plus            [.] ggc_set_mark(void const*)
  6.35%   cc1plus  cc1plus            [.] lookup_page_table_entry(void const*) [clone .218759]
  6.32%   cc1plus  cc1plus            [.] build_int_cst(tree_node*, long)
  5.07%   cc1plus  [kernel.kallsyms]  [k] clear_page_c
  3.60%   cc1plus  cc1plus            [.] initializer_constant_valid_p_1(tree_node*, tree_node*, tree_node**) [clone .1222026]
  3.46%   cc1plus  cc1plus            [.] mostly_copy_tree_r(tree_node**, int*, void*) [clone .459380]
  2.57%   cc1plus  cc1plus            [.] gt_ggc_mx(constructor_elt_d&)
  2.21%   cc1plus  cc1plus            [.] vec<constructor_elt_d, va_gc, vl_embed>::copy() const [clone .local.823]
  1.97%   cc1plus  cc1plus            [.] int_cst_hash_hash(void const*) [clone .1202876]
  1.94%   cc1plus  cc1plus            [.] cxx_eval_vec_init_1(constexpr_call const*, tree_node*, tree_node*, bool, bool, bool, bool*, bool*) [clone .109131.20812] 


cxx_eval_outermost_constant_expr -> cxx_eval_constant_expression ->
-> cxx_eval_vec_init_1 -> build_int_cst 
(see attached callgraph)
Comment 2 Tudor Bosman 2013-09-10 19:02:03 UTC
We're encountering the same with huge (16M elements) std::array, I presume the issue is the same.
Comment 3 Jonathan Wakely 2016-01-26 15:11:30 UTC
*** Bug 69486 has been marked as a duplicate of this bug. ***
Comment 4 Jonathan Wakely 2016-01-26 15:12:27 UTC
Generating the array initialization for this constexpr constructor is the problem:

      constexpr _Base_bitset(unsigned long long __val) noexcept
      : _M_w{ _WordT(__val)
       } { }

Reduced example from PR 69486:

namespace std
{
  typedef decltype(sizeof(0)) size_t;

  template<size_t _Nw>
    struct _Base_bitset
    {
      typedef unsigned long _WordT;

      _WordT _M_w[_Nw];

      constexpr _Base_bitset() noexcept
      : _M_w() { }

      constexpr _Base_bitset(unsigned long long __val) noexcept
      : _M_w{ _WordT(__val)
       } { }
    };

  template<size_t _Nb>
    class bitset
    : private _Base_bitset<((_Nb) / (8 * 8) + ((_Nb) % (8 * 8) == 0 ? 0 : 1))>
    {
    public:
      constexpr bitset() noexcept
      { }
    };
}

std::bitset<2147483648> b;
int main() {}
Comment 5 Jonathan Wakely 2016-01-26 15:14:48 UTC
*** Bug 68399 has been marked as a duplicate of this bug. ***
Comment 6 Martin Sebor 2016-05-18 03:59:00 UTC
*** Bug 63728 has been marked as a duplicate of this bug. ***
Comment 7 Richard Biener 2017-01-25 10:23:25 UTC
*** Bug 79225 has been marked as a duplicate of this bug. ***
Comment 8 İsmail Dönmez 2017-01-25 10:24:32 UTC
Confirming with gcc7 trunk as of r244889.
Comment 9 Jason Merrill 2018-06-26 19:50:50 UTC
Fixed by patch for bug 84281.

*** This bug has been marked as a duplicate of bug 84281 ***