Re: map vs list performance

From:

Lars Tetzlaff <lars.tetzlaff@gmx.net>

Newsgroups:

comp.lang.c++

Date:

Thu, 31 Dec 2009 19:09:28 +0100

Message-ID:

<hhipco$67i$1@online.de>

Am 31.12.2009 00:17, schrieb barcaroller:

I have an STL list that contains about 1500 objects. To check if an object
exists in my list I iterate over it and check if a "key" matches. A key is
just a struct that contains four integers.

    typedef struct
    {
        int a;
        int b;
        int c;
        int d;
    } abcd;

    class C
    {
        abcd key;
        char data[100];
    }

    for i = list.begin(); i != list.end(); i++)
        if ( mya == i->key.a && myb == i->key.b &&
             myc == i->key.c && myd == i->key.d )
            // object has been found; access data[]

To improve performance, I converted the list to an STL map. I used the
struct as the map's key and I added the operator<() and operator==()
functions to allow the map to sort and find objects. I also replaced the
list's for loop with map's find() function.

    if (map.find(mykey) != map.end())
        // object has been found; access data[]

Everything is working correctly (adding, finding, deleting, etc) but the map
solution is over 100% slower than the list for searches (say 100,000
searches). I understand that a map has some additional overhead but I would
have expected this overhead to be negligible for 1500 elements. I can't
explain why a sequential list search is faster (the found objects are
randomly dispersed and are not at the beginning of the list).

Has anyone else noticed this performance issue? Using gcc on Linux.

I think you missed something. With the follwoing code

#include <cstdlib>
#include <list>
#include <map>
#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

struct abcd
{
  int a;
  int b;
  int c;
  int d;

  abcd( int a, int b, int c, int d ) : a(a), b(b), c(c), d(d) {}
  abcd() {}

  bool operator<(const abcd& k) const
  {
    if (a < k.a)
      return true;
    else
      if (a > k.a)
    return false;

    if (b < k.b)
      return true;
    else
      if (b > k.b)
    return false;

    if (c < k.c)
      return true;
    else
      if (c > k.c)
    return false;

    if (d < k.d)
      return true;

    return false;
  }
};

struct C
{
  abcd key;
  char data[100];
};

std::list<C> l;
std::map<abcd,C> m;
vector<abcd> k;

void init()
{
  srand( 42 );

  for( int i = 0; i < 1500; ++i ) {
    abcd aABCD( rand(), rand(), rand(), rand() );
    C aC;
    aC.key = aABCD;
    l.push_back( aC );
    m.insert( make_pair( aABCD, aC ) );
    if( i%10 == 0 ) k.push_back( aABCD );
  }
}

const int count = 1000;

int main()
{
  init();

  clock_t start = clock();

  int x = 0;
  for( int z = 0; z < count; ++z ) {
    x = 0;
    for( vector<abcd>::iterator j = k.begin(); j != k.end(); j++ ) {
      for( list<C>::iterator i = l.begin(); i != l.end(); i++) {
    if ( j->a == i->key.a && j->b == i->key.b &&
         j->c == i->key.c && j->d == i->key.d ){
      x++;
      continue;
    }
      }
    }
  }

  clock_t listtime = clock();

  int y = 0;

  for( int z = 0; z < count; ++z ) {
    y = 0;
    for( vector<abcd>::iterator j = k.begin(); j != k.end(); j++ ) {
      if( m.find( *j ) != m.end() ) {
    y++;
      }
    }
  }

  clock_t maptime = clock();

  std::cerr << "List: " << listtime - start << " " << x << std::endl;
  std::cerr << "Map: " << maptime - listtime << " " << y << std::endl;
}

i get:

List: 1780000 150
Map: 10000 150

so map is 178 times faster than map!

Testet on Linux with gcc 4.3.2, -O3 option, processor at a fixed clock.

Lars