3

I am using an std::map<int, T*> for frequent lookups and some emplacements. There are never any deletions. Since I know an upper bound for the int's used as key (which is around 16 million), I figured I could trade some memory for runtime by using:

std::vector<T*> mapReplacement;
mapReplacement.resize(max_int, nullptr);

However my runtime got significantly worse, even when not measuring the resize operation. Vector Lookups and "insertion" to already allocated space should be constant, while the map should have O(log(n)) insertion and lookup. The number of elements inserted is also in the hundreds of thousands, so it's not even that scarce... What am I not seeing here?

Edit 1: I am neither inserting, nor iterating/searching the vector, but only ever accessing by index. A somewhat representative use-case would look like this:

std::vector<T*> mapReplacement;

struct DataStructure {

    void getInfluenced(int neighbor);

    void doSomeWork(int vertex){
         for (int i : neighbors(vertex)){
            if (influence(vertex, i)){
                if (mapReplacement[i] == nullptr)
                    mapReplacement[i] = new DataStructure();
                mapReplacement[i]->getInfluenced(vertex);
            }
         }
    }
}

int main(){
    mapReplacement.resize(huge_scalar_field.vertex_count);
    for (int i : huge_scalar_field){
         if (isInterestingVertex(i)){
             if (mapReplacement[i] == nullptr)
                  mapReplacement[i] = new DataStructure();
             mapReplacement[i]->doSomeWork(i);
         }
    }
}

Basically I'm iterating over a huge scalar field (16777216 vertices). Some of the vertices (544008 entries in the vector/map) in the field are "interesting" and need a "DataStructure" to represent them. However per interesting vertex some neighborhood of that vertex is somehow influenced by it. Those influenced vertices now too need to be represented by a "DataStructure" and might be also "interesting". That's about every use of the vector/map in my code, however I did not have time to test if that's a minimal example for my problem, or if the problem only arises because of some weird interaction with the contents of "isInterestingVertex", "neighbor", "influence", "doSomeWork" and "getInfluenced".

Edit2: The specs of the system are: Kubuntu 17.04 64bit Kernel Version 4.10.0-42-generic, g++ 6.3.0-12ubuntu2, Intel Core I7-4770K, 16GB DDR3 RAM (of which around 4GB are used during runtime), imported and used libraries are Boost and HPX (however the problem occurs in a purely sequential run as well).

K. Werner
  • 39
  • 2
  • 6
    This looks like an interesting question. Please provide a [mcve] that highlights the problem. – Johan Dec 14 '17 at 12:22
  • How/where are you inserting into the vector? – odyss-jii Dec 14 '17 at 12:27
  • 1
    Can you add a bit more information about the environment you're running in as well. O/S, RAM, CPU etc. – Joe Dec 14 '17 at 12:30
  • Insertion into a map is a lookup O(log(n)) and insert O(1) {which may be very fast with a good allocator}, while insert in a vector needs to move every element above the insertion position, so it is O(log(n)) if you use a binary look up and then O(n/2) for the memory move. For small sets vectors tend to win, but for large sets map will win. – Justin Finnerty Dec 14 '17 at 12:44
  • Please share a minimal complete and compilable benchmark that reproduces the behavior for you. As it stands, there are too many possibilities to meaningfully answer the question. – François Andrieux Dec 14 '17 at 12:47
  • Possible duplicate of [vector or map which one to use](https://stackoverflow.com/questions/454762/vector-or-map-which-one-to-use) – Justin Finnerty Dec 14 '17 at 12:49
  • Search is O(n) for vector and O(log n) for map. Do your lookups "search" the vector or access by index? – Yashas Dec 14 '17 at 12:53
  • 5
    What is your access pattern? If your keys are random-like, then maybe you see the effect of cache-unfriendlyness. Perhaps the whole `map` fits into the cache, while the `vector` doesn't. – geza Dec 14 '17 at 12:58
  • Does your computer has enough RAM and doesn't swap with your huge vector ? – Jarod42 Dec 14 '17 at 13:15
  • @Jarod42: a 16million-sized pointer `vector` is just 64/128MB. – geza Dec 14 '17 at 13:29
  • According to [cppreference.com](http://en.cppreference.com/w/cpp/container/vector) vector has a complexity of `Random access - constant O(1)`, `Insertion or removal of elements at the end - amortized constant O(1)` and `Insertion or removal of elements - linear in the distance to the end of the vector O(n)`. Your assumption that an insertion should be constant is therefore wrong! I am assuming you are using `mapReplacement.insert()`. This fuction adds an element to the vector and has to shift the rest a few spaces. Hope that helps... – FloIsAwsm Dec 14 '17 at 13:29
  • How many elements does your map have? – Yashas Dec 14 '17 at 13:30
  • @FloIsAwsm I don't think the OP means `std::vector::insert`. The OP has already created the elements for the elements using `resize`. Probably meant setting the elements. – Yashas Dec 14 '17 at 13:31
  • @Yashas you are right, i should have phrased it differently :) I was just assuming he used insert. – FloIsAwsm Dec 14 '17 at 13:40
  • Do you iterate over your container ? – Jarod42 Dec 14 '17 at 13:47
  • Not an answer to your question, but if you know the size of the vector at compile time, why not just use `std::array`? – hadriel Dec 14 '17 at 16:05
  • @geza The map fitting into cache and the vector not sounds plausible to me. – K. Werner Dec 15 '17 at 11:55
  • @hadriel I will try using std::array but I would be surprised if it performs way better than vector (however I am surprised by the problem so what do I know :D ) – K. Werner Dec 15 '17 at 11:55
  • @K.Werner: we need to know the exact numbers. But it is plausible. A map's node is ~64 byte. If you have 200'000 nodes, it is 12.2MB, which is smaller than my CPU's cache. So it fits. On the other hand, vector would be 64/128MB, which is clearly larger. – geza Dec 15 '17 at 11:58
  • @geza I updated the question with some actual data of one specific data set that shows the behavior in question. As you can see the ~500.000 nodes will most probably not fit into the 8M Cache of the I7-4770K... – K. Werner Dec 15 '17 at 16:28
  • @K.Werner. it's still can be a cache-issue. Access pattern is important. But, I think that you need to add a reproducible sample code here, because without it, it's impossible to tell, what's going on, we can just only guess. Maybe you can analyze the issue with `perf stat`. – geza Dec 15 '17 at 16:49
  • @K.Werner oh I wouldn't expect it to perform a lot better ether - though I don't know why your `std::vector` perf is bad - but I was more just noting that if you know the size at compile time, using `std::array` would be better – hadriel Dec 15 '17 at 17:44
  • Please don't make us guess. It wastes time and it's not helpful to you. Post a Minimal, Complete, and Verifiable example, with output benchmark timings, of computing results two ways, with Map and with Vector. – J_H Dec 31 '17 at 16:21

0 Answers0