Re: [Boost-users] Assertion `invariant_()' failed. in boost multi index

Subject: Re: [Boost-users] Assertion `invariant_()' failed. in boost multi index
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2013-01-28 15:19:49

Sunil S Nandihalli <sunil.nandihalli <at> gmail.com> writes:

> 
> Hi Everybody, Boost multi index is a very nice library. But I have a
> situation where  the invariant_() assertion fails. One of the indices
> is ordered based on a score which is computed with a function. The score
> of the same element can change when computed at different times. but however,
> the scores change, score decay over time, such that the previously computed
> order will always be right. While I don't know if this is the issue, I
> wanted to make sure that this kind of scoring functions does not cause
> a problem because of some caching that boost may be doing internally ..
> and also, the return value of the scoring function is a double which I
> can imagine can introduce some comparison issues. I am digging into the
> code to make sure that that is not the problem .. any pointers from the
> community is greatly appreciated.

Hi Sunil,

The invariant_() code does not cache keys, but that's not the point really:
the very fact that the score changes over time can lead to inconsistencies
even if no caching is done because of some implicit caching happening
at the comparison point. Suppose your element looks like:

struct element
{
  double score()const; // decreases over time
};

and you have elements x and y such that x<y (for instance, at instant t0
x.score()==10.0 and y.score()==10.01). So, the invariant code (and
the whole library) asumes that

  x.score()<y.score()

*all the time*. Now, imagine we're internally evaluating this expression:

  std::less<double> comp;
  comp(x.score(),y.score()); //must always yield true

Before invoking comp(), the compiler must execute the subexpressions
x.score() and y.score(), and there's no guarantee on the order these
are done, so the following is in principle possible:

  // internal object pseudocode produced by the compiler
  double temp1_=x.score();
  double temp2_=y.score();
  return comp(temp1_,temp2_);

And the following can conceivably happen, then:

  // instant t1 after t0
  double temp1_=x.score(); // 9.00 (less than 10.00 because some time elapsed)
  // instant t2 after t1
  double temp2_=y.score(); // 8.01 (less than 10.01 *and* 9.01 because
                           // even more time elapsed)
  return comp(temp1_,temp2); // yields false!!!!

See? You'll see this happening in practice if the rate of score decay is
comparable to the time elapsed before two invocations of element::score()
(depends on how complex element::score() is, can be milliseconds,
microseconds, you probably know.)

The only safe way to mainain this weird scheme of yours is making sure
that scores don't change during *any* invocation of a member function
of the container --for instance, by making element::score depend on some
internal timer() function that you can pause before using the container
and resume afterwards.

Joaquín M López Muñoz
Telefónica Digital