CODEWITHSUNDEEP
c++c++11boostuuidmemoization
justHelloWorld
justHelloWorld

Reputation: 6842

Uniquely identify an arbitrary object in c++

I'm trying to create a general memoizator for multiple and arbitrary functions.

For each function std::function<ReturnType(Args...)> that we want to memoize, we unordered_map<Args ..., ReturnType> (I'm keeping things simple on purpose).

The big problem comes when our memoized function has some really big argument Args ...: for example let suppose that our function sort a vector of 10 millions numbers and then returns the sorted vector, so something like std::function<vector<double>(vector<double>)>.

As you can imagine, after having inserted less than 100 vectors, we have already filled 8 GBS of memory. Notice that maybe this is given from the combination of huge vectors and the memory required by the sorting algorithm (I didn't investigate on the causes).

So what about if instead of the structure described above, we define unordered_map<UUID(Args ...), ReturnType> (where UUID= Universally Unique Identifier)? We should relax the deterministic feature (so maybe we return a wrong error), but with a very low probability.

The problem is that since I never used UUIDs, I don't know if there are suitable implementations for this application.

So my question is:

  1. There exists a better solution than UUIDs for this problem?
  2. Which UUID implementation is better suitable for this problem?
  3. boost uuid is a possible candidate?
  4. Unfortunately, the problem could be solved for Args ... but not for ReturnType, so there is a solution for memoized result?

Notice that the UUIDs generated for the object x should be the same even in different runs and machines.

Notice that if we have the same UUID for two different objects (and so we return the wrong value) with a really low probability, then it could be acceptable...let's say that this could be a "probabilistic memoizator".

I know that this application doesn't make sense in a memoization context (what are the odds that an user asks two times to sort the same 10 millions elements vector?), but it's time and memory expensive (so good for benchmarking and to introduce the memory problem that I stated above), so please don't whip and crucify me because this is an absurd memoization application.

Upvotes: 0

Views: 409

Answers (1)

sehe
sehe

Reputation: 393694

Identifying any object is easy. The address is "object identity" in C++. This is also the reason that even empty classes cannot have zero size.

Now, what you want is value equivalence. That's strictly not in the language domain. It's solidly in the application/library logic domain.

You should consider using something like boost::flyweights. It has precisely this facility, and makes it "easy" to customize the equivalence semantics for your types.

Upvotes: 3

Related Questions