GetRNGState() / PutRNGstate() should be handled by the R interface instead of the C core

[szhorvat]

Currently, the C core uses the BEGIN_RNG() and END_RNG() macros to ensure that GetRNGState() / PutRNGstate() are called. Managing this from the C core is quite difficult:

• Nested GetRNGState() / PutRNGstate() pairs will lead to reduced randomness, as discussed at https://igraph.discourse.group/t/consistency-of-rng-begin-and-rng-end/641 Avoiding nesting is problematic because it limits function reuse.
• The pressure to avoid accidental nesting leads to a very granular and error prone usage pattern.
• The correct pairing of BEGIN_RNG() and END_RNG() is not currently testable in pure C. There are likely mistakes.

The best solution here would be if the R interface called these functions before / after every igraph function, through Stimulus. The only disadvantage of this approach is that sometimes the call is unnecessary.

I would suggest adding an R-specific stimulus flag in R-functions.yaml to opt-out from usingGetRNGState() / PutRNGstate(). This way, if an igraph function is verified not to use the RNG in any way, these called can be skipped.

CC @krlmlr @ntamas

[krlmlr]

GetRNGState() and PutRNGState() calls are expensive.

Agree that this should be handled by the R interface. Can we make accessing the RNG throw an error if GetRNGState() has not been called, and make calling GetRNGState() opt-in instead of opt-out?

[szhorvat]

GetRNGState() and PutRNGState() calls are expensive.

There are now cases where these are called in a loop, unfortunately.

Can we make accessing the RNG throw an error if GetRNGState() has not been called

Does the R API make this possible?

Since the RNG is customizable, in principle this is possible by using random generators that check that a flag (set by entering functions and cleared when existing) was properly set. But it would be quite messy to do it ourselves.

and make calling GetRNGState() opt-in instead of opt-out?

That's your call of course :-) We just need to be very careful as some functions make "hidden" use of the RNG. For example, ARPACK functions use a randomly generated initial vector, but they should converge to the same solution regardless of what this initial vector was.

[ntamas]

We can make it opt-in or opt-out, whichever you prefer. I think that on the Stimulus side we can start annotating functions in functions.yaml with something like FLAGS: RNG. The R code generator can check whether this flag is set on a function and add the appropriate GetRNGState() and PutRNGState() calls. Other code generators can ignore the flag completely. Does that sound reasonable?

[szhorvat]

If this could be done before the C/igraph 1.0 release this spring/summer, then we could finally rip out all those RNG_BEGIN/END calls. Can we make it a goal for whatever R/igraph release is based on C/igraph 1.0?

[maelle]

@Antonov548 do you think it's a feasible goal? How hard is this according to you?

[szhorvat]

This should be easy with Stimulus. Note that when this is done, RNG_BEGIN/END should be redefined not to call the GetRNGState() / PutRNGstate() functions. Otherwise we'll end up with nested calls with the problems this brings (see top post).

[ntamas]

I've started annotating the functions that use the RNG in functions.yaml in the feat/rng-begin-end-removal of the C core. There are a few surprising revelations:

1. Doing this is probably unsafe. It is hard to detect cases when an igraph function does not call the RNG directly but calls some igraph function that calls the RNG -- in that case, the top-level function should be marked with FLAGS: RNG in functions.yaml, but it is not immediately obvious from reading the source. Furthermore, changing the internals of a function that did not use the RNG yet such that the new version calls the RNG would require the function to be annotated with FLAGS: RNG - another case that is easy to miss.
2. Some functions like igraph_pseudo_diameter() only use the RNG in very specific circumstances. For the case of igraph_pseudo_diameter() needs the RNG only to pick a random starting vertex when the user has specified one. Still, we need to annotate it as FLAGS: RNG.
3. Any igraph function that receives an attribute combination list may potentially use the RNG if the attribute combination list contains a combiner function that uses the RNG.
4. Any igraph function that can call a callback may eventually call back into R and thus use the RNG - I don't know whether these would require a FLAGS: RNG annotation or not.

All in all, it feels somewhat dangerous to me to leave this up to the maintainers of the C core if we cannot come up with a mechanism that would automatically detect functions in functions.yaml that should be flagged with FLAGS: RNG but are not flagged yet.

[Antonov548]

@Antonov548 do you think it's a feasible goal? How hard is this according to you?

As guys mentioned above. This requires maybe some preperation on igraph/C side and proper design of feature on stimulus/R side. I guess I will start to check what should be implemented in stimulus to resolve this.

[szhorvat]

I agree with Tamás that this is risky. That is why I originally suggested that this should be opt-out.

[ntamas]

...meaning that we should flag functions in functions.yaml that are known not to use the RNG with something like FLAGS: NO_RNG, and generate GetRNGState() and PutRNGState() calls in the R interface by default?

[szhorvat]

If we do this at all, then that's what I would do, and focus attention only on functions where there's a reason to believe that this may make a difference for performance. Whether that's the case depends on how fast GetRNGState() and PutRNGState() are.

I don't think that this needs to be a prerequisite for moving the GetRNGState() and PutRNGState() calls to R, unless we already know that the performance impact is significant. It'd be good to have an idea about how significant it is, so we'd know how much effort to put into sorting RNG-using functions from others. Could we have a measurement for something trivial and constant time like igraph_is_directed() or igraph_vcount()? How about for something simple but linear time like igraph_degree(), called on small graphs? Someone could perhaps insert these calls manually into the generated glue code for the time of a single local benchmark, and report back on the performance impact?