Re: map vs list performance

From:

Maxim Yegorushkin <maxim.yegorushkin@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Fri, 01 Jan 2010 23:13:49 +0000

Message-ID:

<4b3e81ad$0$9749$6e1ede2f@read.cnntp.org>

On 31/12/09 00:54, Branimir Maksimovic wrote:

AnonMail2005@gmail.com wrote:

On Dec 30, 6:17 pm, "barcaroller" <barcarol...@music.net> wrote:

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).

Because in map, search goes with random access in memory,
and with list it goes in sequential order.

Not so.

Both map and list store elements in nodes. Each node is allocated
separately.

> I have discovered

that by using bidirectional iterator for quick sort instead of
random access I gain double the speed of quick sort...

Can not be true. Quick sort requires random iterators, this is why you
can't pass std::list<> iterators into std::sort(). std::list<> has sort
member function for sorting which employs mergesort because quicksort
can not be used for lists.

[]

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

Yes. On list where nodes are sorted by address pass through list
is twice as fast as unordered nodes, no matter the size of list
and where nodes are.

Sounds unlikely. Can't ignore CPU cache effects.

--
Max