Why is vector faster than map in one test, but not

问题:

I've always been told vectors are fast, and in my years of programming experience, I've never seen anything to contract that. I decided to (prematurely optimize and) write a associative class that was a thin wrapper around a sequential container (namely ::std::vector and provided the same interface as ::std::map. Most of the code was really easy, and I got it working with little difficulty.

However, in my tests of various sized POD types (4 to 64 bytes), and std::strings, with counts varying from eight to two-thousand, ::std::map::find was faster than my ::associative::find, usually around 15% faster, for almost all tests. I made a Short, Self Contained, Correct (Compilable), Example that clearly shows this at ideone I checked MSVC9's implementation of ::std::map::find and confirmed that it matches my vecfind and ::std::lower_bound code quite closely, and cannot account for why the ::std::map::find runs faster, except for a discussion on Stack Overflow where people speculated that the binary search method does not benefit at all from the locality of the vector until the last comparison (making it no faster), and that it's requires pointer arithmetic that ::std::map nodes don't require, making it slower.

Today someone challenged me on this, and provided this code at ideone, which when I tested, showed the vector to be over twice as fast.

Do the coders of StackOverflow want to enlighten me on this apparent discrepancy? I've gone over both sets of code, and they seem euqivalent to me, but maybe I'm blind from playing with both of them so much.

(Footnote: this is very close to one of my previous questions, but my code had several bugs which were addressed. Due to new information/code, I felt this was different enough to justify a separate question. If not, I'll work on merging them.)

回答1:

I see some problems with the the code ( http://ideone.com/41iKt ) you posted on ideone.com. (ideone actually shows vector as faster, but a local build with the Visual Studio 11 Developer Preview shows map faster).

First I moved the map variable and used it to initialize the vector to get the same element ordering and uniquing, and then I gave lower_bound a custom comparator that only compares first, since that's what map will be doing. After these changes Visual Studio 11 shows the vector as faster for the same 100,000 elements (although the ideone time doesn't change significantly). http://ideone.com/b3OnH

With test_size reduced to 8 map is still faster. This isn't surprising because this is the way algorithm complexity works, all the constants in the function that truly describes the run time matter with small N. I have to raise test_size to about 2700 for vector to pull even and then ahead of map on this system.

回答2:

What makes you think that mapfind() is faster than vecfind()?

The ideone output for your code reports about 50% more ticks for mapfind() than for vecfind(). Running the code here (x86_64 linux, g++-4.5.1), mapfind() takes about twice as long as vecfind().

Making the map/vector larger by a factor of 10, the difference increases to about 3×.

Note however that the sum of the second components is different. The map contains only one pair with any given first component (with my local PRNG, that creates a map two elements short), while the vector can contain multiple such pairs.

回答3:

The number of elements you're putting into your test container are more than the number of possible outputs from rand() in Microsoft, thus you're getting repeated numbers. The sorted vector will contain all of them while the map will throw out the duplicates. Check the sizes after filling them - the vector will have 100000 elements, the map 32768. Since the map is much shorter, of course it will have better performance.

Try a multimap for an apples-to-apples comparison.

回答4:

A sorted std::vector has two advantages over std::map:

• Better data locality: vector stores all data contiguously in memory
• Smaller memory footprint: vector does not need much bookkeeping data (e.g., no tree node objects)

Whether these two effects matter depend on the scenario. There are two factors that are likely to have a major impact:

Data type

It is an advantage for the std::vector if the elements are primitive types like integers. In that case, the locality really helps because all data needed by the search is in a contiguous location in memory.

If the elements are say strings, then the locality does not help that much. The contiguous vector memory now only stores pointers objects that are potentially all over the heap.

Data size

If the std::vector fits into a particular cache level but the std::map does not, the std::vector will have an advantage. This is especially the case if you keep repeating the test over the same data.