Static variables and functions that are called once for each choice of arguments

Question

Here is a simple C++ question.

Description of the problem: I have a function that takes as input an integer and returns a vector of zeros with length the input. Assume that I call the function many times with the same argument. What I want to avoid is that my function creates the vector of zeroes each time it is called. I want this to happen only the first time the function is called with the given input.

How I approached it: This brought to mind static variables. I thought of creating a static vector that holds the required zero vectors of each size, but wasn't able to figure out how to implement this. As an example I want something that "looks" like [ [0], [0,0], ...].

If there is a different way to approach such a problem please feel free to share! Also, my example with vectors is a bit specialised but replies that are more generic (concerning static variables that depend on the argument) would be greatly appreciated.

Side question: To generalise further, is it possible to define a function that is only called once for each choice of arguments?

Thanks a lot.

A static vector (or better a map) of vectors is the right idea, you just need to initialize it lazily. — n. m. could be an AI, Aug 31 '15 at 13:07
It is not clear what your are after, are the vectors you return `const`? Otherwise you will need to make a copy every time anyways. Unless copying if faster than zero-initialization then it might make sense. And it is impossible to make a function that gets executed once per argument set, but it is possible to make a function that does nothing if it is passed same set of arguments as before. It will execute, but make a check and immediately return, or provide a cached result, etc. — luk32, Aug 31 '15 at 13:17
This technique is called "memoization". See for example http://stackoverflow.com/questions/17805969/writing-universal-memoization-function-in-c11. — Alan Stokes, Aug 31 '15 at 13:24
There are three ways of interpreting this question that I can see. 1) You want a function that returns a `vector` by-value, a copy that you then want to change. 2) You want a function that returns a const reference to a vector of zeros that you don't need to change. 3) You want a function that returns a non-const reference to a vector that is initially full of zeros but can be changed. It would probably help to show your code. — Chris Drew, Aug 31 '15 at 15:38

Hrant · Answer 1 · 2015-08-31T14:21:43.603

2

You can have a map of sizes and vectors, one vector for each size:

#include <vector>
#include <map>
#include <cstddef>

std::vector<int>& get_vector(std::size_t size)
{
    static std::map<size_t, std::vector<int> >  vectors;
    std::map<size_t, std::vector<int> >::iterator iter = vectors.find(size);
    if (iter == vectors.end())
    {
        iter = vectors.insert(std::make_pair(size, std::vector<int>(size, 0))).first;
    }
    return iter->second;
}

edited Aug 31 '15 at 14:21

answered Aug 31 '15 at 13:49

Hrant

496
1
5
13

You may reuse `find`/`insert` result to avoid to re find with `operator[]` – Jarod42 Aug 31 '15 at 14:10
Note that this returns a non-const reference which means the caller can make changes to the vector in the map and subsequent calls will not get a vector of zeros. This may not be what OP wants. – Chris Drew Aug 31 '15 at 16:07

score 1 · Accepted Answer · answered Aug 31 '15 at 16:00

If I understand correctly what you are trying to do, I don't think you will get the benefit you are expecting.

I wrote a quick benchmark to compare the performance of repeatedly creating a vector of zeros. The first benchmark uses the standard vector constructor. The second uses a function that only creates the vector the first time and stores it in a map:

const std::vector<int>& zeros(std::size_t size) {
    static std::unordered_map<size_t, std::vector<int>> vectors;
    auto find = vectors.find(size);
    if (find != vectors.end())
        return find->second;
    auto insert = vectors.emplace(size, std::vector<int>(size));
    return insert.first->second;
}

std::chrono::duration<float> benchmarkUsingMap() {
  int sum = 0;
  auto start = std::chrono::high_resolution_clock::now();

  for (int i = 0; i != 10'000; ++i) {
    auto zeros10k = zeros(10'000);
    zeros10k[5342] = 1;
    sum += zeros10k[5342];    
  }

  auto end = std::chrono::high_resolution_clock::now();                      
  std::cout << "Sum: " << sum << "\n";
  return end - start;
}

std::chrono::duration<float> benchmarkWithoutUsingMap() {
  int sum = 0;
  auto start = std::chrono::high_resolution_clock::now();

  for (int i = 0; i != 10'000; ++i) {
    auto zeros10k = std::vector<int>(10'000);
    zeros10k[5342] = 1;
    sum += zeros10k[5342];    
  }

  auto end = std::chrono::high_resolution_clock::now();                                   
  std::cout << "Sum: " << sum << "\n";
  return end - start;
}                          

int main() {
  std::cout << "Benchmark without map: " << benchmarkWithoutUsingMap().count() << '\n';
  std::cout << "Benchmark using map: " << benchmarkUsingMap().count() << '\n';
}

Output:

Benchmark without map: 0.0188374
Benchmark using map: 0.134966

So, in this case, just creating the vector each time was almost 10x faster. This is assuming you want to create a mutable copy of the vector of zeros.

Thanks! Indeed, I was really interested in improving the speed at which performs that's why I wanted to avoid to recreate the zero vectors. — Alex Apas, Sep 01 '15 at 17:44

NathanOliver · Answer 3 · 2015-08-31T13:24:24.340

0

If each vector needs to be a separate instance then you will have to have a construction for each instance. Since you will have to construct each instance you can make a simple make_int_vector function like:

std::vector<int> make_int_vector(std::size_t size, int fill = 0) 
{ 
    return std::vector(size, fill); 
}

The returned vector will either be moved or be elided with copy elision

edited Aug 31 '15 at 13:24

answered Aug 31 '15 at 13:13

NathanOliver

171,901
28
288
402

3

Does that make any sense? I mean what is the difference from using `std::vector(size)` in-place? – luk32 Aug 31 '15 at 13:15
That sounds useful, but does it answer the question? – Alan Stokes Aug 31 '15 at 13:47

Serge Ballesta · Answer 4 · 2015-09-01T13:12:40.983

What you are asking for is a cache. The hard part is how long an entry should exist in the cache. Your current requirement seems to be an eternal cache, meaning that each entry will persist for ever. For such a simple use case, à static map is enough:

template<typename T, typename U>
T cached(T (*funct)(U arg)) {
    static unordered_map<U, T> c;
    if (c.count(arg) == 0) {
        c[arg] = funct(arg);
    }
    return c[arg];
}

The above is returning a value,which will require à copy. If you want to avoid the copy, just return a reference, but then, if you change one of the vectors, the next call will return the modified value.

template<typename T, typename U>
&T cached(T (*funct)(U arg)) {
    static unordered_map<U, T> c;
    if (c.count(arg) == 0) {
        c[arg] = funct(arg);
    }
    return c[arg];
}

Static variables and functions that are called once for each choice of arguments

4 Answers4