9

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

10
  • 2
    Have you tried to profile the two implementations? To be honest just looking at code very often does not really help. Naving concrete data should point you in the general direction. Feb 17, 2012 at 22:24
  • 1
    Due to everything being inlined, my profiler gave me less information than I already had from the output. Feb 17, 2012 at 22:27
  • Excessive inlining can slow things down as you continually eject stuff from the CPU caches. Since you're on Windows compile for code size without forcing any inlining and measure.
    – JimR
    Feb 17, 2012 at 22:34
  • That should not obscure the issue too much depending on how you are profiling. What is your profiling methodology? Sample or Trace? In order to get a more accurate reading I would change your test. Just doing a simple comparison of 1 value to another is pointless. Run each test at least 100 times and then divide the result time by 100. It will give you a more accurate time. Feb 17, 2012 at 22:39
  • 1
    I see some problems with the the code ( ideone.com/41iKt ) you posted on ideone.com. (ideone actually shows vector as faster, but a local build with VS 2011 dp 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 VS2011 shows the vector as faster for the same number of elements (although the ideone time doesn't change significantly). ideone.com/b3OnH
    – bames53
    Feb 17, 2012 at 23:30

4 Answers 4

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.

4
  • With my WinXP 32bit, mapfind takes 266 ticks compared to vecfind's 391. With minGW on WinXP 32bit, mapfind takes 156 ticks compared to vecfind's 188 ticks. In either case, mapfind is significantly faster than vecfind Feb 17, 2012 at 23:34
  • Interesting. vecfind is significantly faster on my box and at ideone. I think ideone's machines are 32-bit too, so it wouldn't be the architecture. However, ideone's compiler is also gcc/g++ 4.5.1, so it could be the compiler. What compilers are you using? Feb 17, 2012 at 23:42
  • Those were MSVC++9 and G++ 4.5.4 20111030, and I also tested with MSVC++10. Feb 17, 2012 at 23:58
  • 1
    Aha. I wouldn't expect gcc 4.5.4 vs. 4.5.1 to make a huge difference in the relative performance of map and vector, so my best guess is it's a Windows vs. Linux thing. But here map is faster for small sizes too, however vector overtakes map already between 250 and 300 elements. Feb 18, 2012 at 0:14
2

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.

1
  • Bah, my previous tests used rand()*RAND_MAX+rand(), but didn't do that with this one because this test suite started with comparisons of 8 objects in each container. Oops. Good call. barmes53 found it first though, and another bug. Feb 18, 2012 at 0:00
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.

1
  • migrated to answer from comment, as requested
    – bames53
    Feb 17, 2012 at 23:56
0

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.

1
  • This does not explain the discrepancies in the tests, and does not explain why in my test, the vector with 8 pair<int,int> was 15% slower than the map with 8 pair<int,int>. Did you read the question? Feb 17, 2012 at 23:27

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.