I’m interested to know what other devs do/think about this problem:
Some algorithms for modeling can have random aspects to them, so that the result can technically satisfy what the operation is supposed to do, but will/may not be repeatable: different runs of the algorithm can result in either permutations of the indices of vertices, edges, etc., or sometimes can even result in different results (while still technically satisfying the algorithm requirement).
Example: if you use a GHash with pointers as keys, then because pointers will very likely not be the same from run to run, then any algorithm that iterates over the elements of the GHash will encounter things in different orders from run to run. As another example, qsort is not guaranteed to stable sort and if it uses a random pivot strategy, may produce different orderings of equal elements on different runs (if seed is not reset to a known value each time).
I imagine similar issues come up with image rendering and processing algorithms that have random aspects to them, but I’m not familiar with this in Blender.
I can think of several different responses to this reality:
- Don’t worry about it. Since the algorithm satisfies its requirements, it doesn’t matter that it is not exactly repeatable. This is what an algorithm designer would typically. The problems with this attitude are:
- Things like modifiers run over and over, and it could be disconcerting to see different topologies come out at random times. The display could appear to flicker, for one thing. UV maps can change and invalidate the associated images.
- Similarly, if animating something that requires repeatedly running the algorithm, flickering can occur.
- Debugging problems with the algorithm is harder if results differ from run to run.
- The simple-minded regression test built into Blender tests for exact equality of topology and attribute values, and so regression tests using that will fail. [This problem could be solved for the case where indexes permute by working on the regression test framework to work when things are all the same except for index permutations. For image processing algorithms, a similar trick would be to use a comparison that is fuzzy enough to gloss over any differences that result from randomization.]
I would say, as a general thing, we should try as hard as possible to make algorithms repeatable. Agreed?
-
Don’t use pointers as hash keys if you are going to iterate over the elements and do something order dependent (this may involve adding or maintaining index values to use instead; but then you may need a table to go back from GHash keys to the original pointers). Or don’t iterate directly on the order that comes out of GHash’s iterator, but rather put the keys from that iterator into an array first and sort it in some repeatable way. Make qsort stable by adding a secondary sorting criterion that guarantees no two elements are equal (that secondary criterion needs to be repeatable from run to run).
-
Design the algorithm such that processing things in different orders makes no difference. This might be hard and/or it might be hard to recognize when all such possibilities have been taken care of.
I’m running into this dilemma right now with some major surgery I’m trying on Boolean. I’m thinking I have to do approach 2, though it is annoying. The other thing I could do is approach (1), with a fix to the regression test framework, since in this case the main problem is that the vertex indices for newly created vertices are permuted from run to run.