3

I am a theoretical computer scientist. I have heard the following:

Practitioners do not like randomized algorithms because they are notoriously difficult to debug. So deterministic algorithms are much more preferred.

How true is this statement? If you have can provide examples or counter-examples that would be great.

  • When debugging is hard, it is often a sign that the code is missing some diagnostics/tracing functionality. This aspect of writing code is often overlooked because it is not "functional", but can save hours (and even days sometimes) of debugging time. – Caleb Oct 20 at 4:09
  • Let your tests control your random. – candied_orange Oct 20 at 8:01
  • The statement in stake (for which not even a reference is given) can mean a lot of different things to different people. This makes it more a basis for an open discussion, not for a question which for which a "correct" answer exists - thus I am voting to close as "too broad". – Doc Brown Oct 20 at 21:31
6

One big problem is reproducibility.

Let's say your code roughly works. Most of the time it gives the right result. But sometimes it gets into a situation where it goes wrong. For a deterministic algorithm, once you find an input that gives the wrong result, you can use the same input and use the debugger to follow all the steps until you find where it goes wrong.

With a probabilistic algorithm, you may run into a situation where there is no input that always gives the wrong result, but any input can sometimes give the wrong result. So you cannot provide an input that will go wrong. You cannot provide an input where you know that following all steps will end up at some step that goes wrong.

At the very least you need to be able to provide both input and the state of the random number generator to the code, which would make the algorithm deterministic. Of course in normal operation the algorithm should be as random as possible, but you need it to be reproducible.

3

I went about this answer in a bit of a different direction - not from a debugging, but a testing perspective:

Usually a pure function has a very simple setup:

Same input in, same result out.

That makes it very easy to define proper test cases - You select a set of standard test values and a few of special interest (depending on what your function does), write your testing methods for it, comparing what the function returns to what you expected it to return. This gives you a solid set of testing methods that you can run whenever you make any changes.

Once you start having randomness in your methods, you run into this issue:

Same input in, many possible values out.

Now you need to know ALL the possible values that your randomized function could return for a given input, and test against those. And depending on what your randomized function does, that's just either plainly unfeasible (due to many options that you need to manually or programmatically add in), or straight up impossible.

Suddenly the amount of effort to create a solid test suite went up dramatically, at which point it usually just gets straight skipped.

How would we avoid this?

To avoid this during writing your algorithms, you would encapsulate the piece of randomness. You would try to put the snippet that actually causes the random part inside its own object, outside of the algorithm. Now you can actually mock that object during your test suite - basically fixing the values that the "randomized" object would return. It's not ideal, and does not cover every scenario, but so does barely any testing. The effort to create your test suite went up only slightly, since the "randomness" is gone now, and you can treat it like a normal, pure function for testing purposes.

Similar principles apply to debugging a function manually: Most of the time you do not actually know what random value the algorithm generated, and thus it's difficult to recreate what exactly happened in the function that broke it. That makes manual debugging very difficult.

  • 1
    Often the seed is preserved somewhere to make the debugging easier. For example rspec will print out the seed if you ask it to run the tests in a random order so you can reproduce what it did. Games often preserve the randomness seed in save files for many reasons, but also to make debugging easier. – viraptor Oct 20 at 9:32
  • 1
    Yes, a seed is also a very valid way to control the randomness. The issue can be that if your implementation detail of the random algorithm changes, all your previously defined expected results could be invalidated too, even with the same seed. It always depends on the situation! – Joe Oct 20 at 12:47
1

I'll answer with the worst possible example I know: A race condition due to improper locking in kernel code.

A race condition is the very notion of non-determinism: You have no control on whether it occurs or not. You are not even putting in random input on purpose, but rather the machine itself acts as the random generator.

As such, if you have such a race condition, you cannot reliably reproduce it. Every time you try your code, the results will be different. Worse: The code may work fine in the majority of cases, but trigger a kernel panic or corrupted data in one-in-a-million cases.

How do you collect information about a condition that you can only observe once in a while? You absolutely must resort to logging, a debugger won't do you any good. As such, your perception is limited to the log output that you have introduced into the code. Worse, the very action of writing a log may well make the race condition next to impossible to trigger, the error may turn into a heisenbug.

Because the condition is non-deterministic, your log output will read different each time you run your code. That means, one time you might get a kernel panic, the next time you might get corrupted data, the third time you may get corrupted data in some other location, and so on, and so forth. Your bug is not so much a moving target, but rather a jumping target that shows up somewhere, and when you investigate, it's gone to pop up right behind your back the next time it shows itself.

Debugging such conditions can be very frustrating.


On the other hand, if you have a deterministic bug, you can always backtrace its genesis step by step. You see the result, you get a question about which input was responsible for the wrong result, you run again looking at those inputs, and then you recurse on the wrong input until you identify the place where good inputs lead to a wrong output.


In short:

  • Debugging nondeterministic code is a nondeterministic algorithm itself which is not guaranteed to terminate.

  • Debugging deterministic code is a deterministic algorithm.

  • With race conditions you have the additional problem that the fact you are debugging it can make the race condition go away. Just logging may make it go away. – gnasher729 Oct 21 at 8:46
  • 1
    @gnasher729 That's the point of the second part of my fourth paragraph, the one that ends in "heisenbug". – cmaster Oct 21 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.