std::vector versus std::map performance

std::vector versus std::map performance

• vsnetdeveloper

  Well, there isn't much insertion, so there isn't much actually going on inside the map itself. However, the other programmer here is trying to go down to the hardware level, making the point that vector gives contiguous physical memory space, but a map does not. Therefore, any cache-miss that would read in part of a vector would read in a good portion of the other elements in that vector, but would probably not with a similar situation using a map.

  I am inclined to believe the argument, but am maybe curious if there is anything about the map's internal workings that might save it. Maps are logically wonderful things and would hate to see us sacrifice code readability for the sake of performance if there was no real gain to be had.

  Jonathan Scott

  
  

• Bart Vercauteren

  Jonathan Scott wrote:

  Well, there isn't much insertion, so there isn't much actually going on inside the map itself. However, the other programmer here is trying to go down to the hardware level, making the point that vector gives contiguous physical memory space, but a map does not. Therefore, any cache-miss that would read in part of a vector would read in a good portion of the other elements in that vector, but would probably not with a similar situation using a map.

  Yes, that's what I'm saying above. Vector will cause less overhead both size- and page fault wise.

  Jonathan Scott wrote:

  I am inclined to believe the argument, but am maybe curious if there is anything about the map's internal workings that might save it. Maps are logically wonderful things and would hate to see us sacrifice code readability for the sake of performance if there was no real gain to be had.

  There's nothing in std::map which saves it. I'd recommend you to look into some hash_map class for the sake of speedy lookups, and also consider writing a custom (low fragmentation) allocator if cache hits is a real issue.

  
  
  

• leclerc9

  If your integers are scattered (not sequential), then you can make a hash key from it by taking it mod the size of the array. e.g. value % array_size. For readability, you can overload operator[] so that this lookup occurs when you do myHashTable[ value ].
  

• ItsMe!!!

  The problem with std::map, at least Microsoft's implementation, is that it uses a binary tree, giving it an O(log n) lookup.  Even worse, every call made an allocation, making the per-insert cost much more than std::vector which grows the array in large chunks.  Performance on std::map was such an issue for me that I stopped using it in a particular area of my code.  (Edit: well, actually, I did keep using it in a couple places, but I changed the allocator to use a memory pool which allocated in chunks.)

  For faster lookup, use a hash table.  Decide how many elements in a std::vector (say a prime number at least twice as many as the number of elements you will actually store), come up with some function that "evenly" maps the elements to indices in the array.  Handle collisions either by bucketing, where each element is a linked list of elements with the same hash, or by probing, where you just march down the array looking for the match.

  (If something isn't in the standard implementation of STL, I tend to write it manually and customize it for my real needs.  But on the other hand going with a stock implementation is safer and faster.)

  
  

• IXOYE333

  What I mean by "magic numbers" is the indices. Instead of a free-form key, I can only use integers. Other than #define or const data members, I can't think of a way to keep the readability of a particular part of the code using a map, where it seemed natural.

  I will read the article, thank you.

  Jonathan Scott

  
  

• Ambalavanar

  The vector and map classes are obviously somewhat different, given that map is associative and yield logarithmic time lookups, and vector is a sequence which will yield constant time lookup -- granted a "key". The problem with replacing map with a magic number vector, is the amount of dummy items you will have to add to the sequence to achieve truly unique keys for the "real" items. There's likely to be quite extensive overhead in that scenario.

  I'd rather argue the use of

  1. a sorted vector on which you use binary searches to locate items
  2. a map and use of operator[] or map::find

  Both techniques will yield logarithmic time lookups, but a map will consume more memory per item than that of the vector. In addition, while the vector is consequtive, the map is a linked list. This means that the items in the map are likely to be spread across more than one memory page. This in turn means that lookups in a map will cause more page faults than lookups in a vector (the latter of which is likely to have all items in much fewer pages).

  The most apparent problem with the sorted vector is the sorting, and this will seriously cripple your performance if your application mixes insertions, deletions and reads to a greater extent. Generally, the vector approach will save you both time and memory if your application goes through a staged lifetime: 1. initialize the vector, 2. use the vector (lookup items), 3. clear the vector.

  What you should consider, though, is replacing map with stdext::hash_map (or any other third party STL'ish hash container), instead of the vector variation you mention. In essence your vector would be trying to assimilate a hashmap either way, so it's better to use something which does the job "out of the box", rather than to adapt an entirely different (and largely unfit) container.

  
  
  

• onlineanuj

  magic numbers to associate elements (vector)

  What is that suppose to mean What magic numbers I think you need a good article on std::vector.

  
  
  
• std::vector versus std::map performance