[Bug c++/13823] New: Significant performance issue with std::map on multiple threads on dual processor - possibly default allocator

[devison at pacificit dot co dot nz]

C++, gcc 3.3.2, Red Hat Linux 7.2, kernel 2.4.20, dual AMD Athlon MP 2200+.

When two threads are simultaneously adding elements to local standard 
container objects (including map, set and ext/hash_map), I observe a 
performance degradation by a factor of 6x, when the program is running on two 
cpus compared to running on a single CPU.  (Whereas you may expect an 
improvement of 2x).

This seems to a problem with the default allocator, since running the program 
with GLIBCPP_FORCE_NEW set, removes the problem, and dramatically speeds up 
the program on two cpus.  (Whereas you may expect a slight degradation).

The example program creates a number of threads, each of which runs an 
infinite loop, repeatedly constructing a std::map<int,int> on the stack, 
inserting a number of elements, then letting it go out of scope.  It takes a 
single parameter specifying how many threads to create - if unspecified it 
defaults to two threads.

When the program is run with two threads, on my dual CPU machine, I observe 
both processors staying about 60% idle, with each at 15% user and 25% system 
load.  Why such high system load?  When I force the program onto a single CPU 
(by running another compute-bound app), the two threads each consume a full 
50% of the CPU, with only a minimal system load, and it runs 6x faster.

By the way, I observed the same problem with gcc-3.2.1, and on another machine 
running a different version of linux.

Following is the output of the g++ -v -save-temps command.  I will attach the 
compressed preprocessed .ii file after this bug is submitted (since I can't 
see how to do it on this page).  Further below is the unpreprocessed source 
file, in case that is useful too.

thanks,

Dan Evison
devison at pacificit dot co dot nz

---------------------------------------------------------------------

$ /usr/local/gcc-3.3.2/bin/g++ -v -save-temps -pthread -D _PTHREADS -D 
_REENTRANT maptest.cpp
Reading specs from /usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-
gnu/3.3.2/specs
Configured with: ../gcc-3.3.2/configure --enable-shared --with-gnu-as --with-
gnu-ld --enable-threads=posix --enable-languages=c++,java --disable-nls --
prefix=/usr/local/gcc-3.3.2
Thread model: posix
gcc version 3.3.2
 /usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/cc1plus -E -
D__GNUG__=3 -quiet -v -D__GNUC__=3 -D__GNUC_MINOR__=3 -D__GNUC_PATCHLEVEL__=2 -
D_GNU_SOURCE -D_REENTRANT -D _PTHREADS -D _REENTRANT maptest.cpp maptest.ii
ignoring nonexistent directory "/usr/local/gcc-3.3.2/i686-pc-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/gcc-3.3.2/include/c++/3.3.2
 /usr/local/gcc-3.3.2/include/c++/3.3.2/i686-pc-linux-gnu
 /usr/local/gcc-3.3.2/include/c++/3.3.2/backward
 /usr/local/include
 /usr/local/gcc-3.3.2/include
 /usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/include
 /usr/include
End of search list.
 /usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/cc1plus -
fpreprocessed maptest.ii -quiet -dumpbase maptest.cpp -auxbase maptest -
version -o maptest.s
GNU C++ version 3.3.2 (i686-pc-linux-gnu)
        compiled by GNU C version 3.3.2.
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
 as -V -Qy -o maptest.o maptest.s
GNU assembler version 2.11.93.0.2 (i386-redhat-linux) using BFD version 
2.11.93.0.2 20020207
 /usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/collect2 --eh-frame-
hdr -m elf_i386 -dynamic-linker /lib/ld-
linux.so.2 /usr/lib/crt1.o /usr/lib/crti.o /usr/local/gcc-3.3.2/lib/gcc-
lib/i686-pc-linux-gnu/3.3.2/crtbegin.o -L/usr/local/gcc-3.3.2/lib/gcc-lib/i686-
pc-linux-gnu/3.3.2 -L/usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-
gnu/3.3.2/../../.. maptest.o -lstdc++ -lm -lgcc_s -lgcc -lpthread -lc -lgcc_s -
lgcc /usr/local/gcc-3.3.2/lib/gcc-lib/i686-pc-linux-
gnu/3.3.2/crtend.o /usr/lib/crtn.o

--------------------------------------------------------------------

#include <iostream>
#include <map>
#include <pthread.h>

void *calc(void *n)
{
  int *num = static_cast<int *>(n);

  unsigned c = 0;
  
  while (true)
    {
      std::cerr << "Thread " << *num << ": " << ++c << std::endl;

      std::map<int, int> m;
      
      for (unsigned i = 0; i < 100000; ++i) 
      	m[i] = i;
    }

  return 0;
}

int main(int argc, char *argv[])
{
  int n = argc == 2 ? std::max(atoi(argv[1]), 1) : 2;

  pthread_t id;
  for (int i = 0; i < n; ++i)
    pthread_create(&id, 0, calc, new int(i));
  
  pthread_join(id, 0);
  
  return 0;
}

-- 
           Summary: Significant performance issue with std::map on multiple
                    threads on dual processor - possibly default allocator
           Product: gcc
           Version: 3.3.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: devison at pacificit dot co dot nz
                CC: gcc-bugs at gcc dot gnu dot org


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