General-purpose short-circuit

[HighDiceRoller]

Originally posted by @posita in #26 (reply in thread)

Looks great! I look forward to the update.

FYI, the update to the dyce's README that includes a link to icepool will go out with its next release.

After reading the paper, I was wondering if you considered a mechanism by which to short circuit your callbacks (or if it's even necessary). I'm thinking of something like this:

class KeepHighest(icepool.OutcomeCountEvaluator):
    def __init__(self, num_highest: int):
        super().__init__()
        self._num_highest = num_highest
    def direction(self, *generators: icepool.OutcomeCountGenerator) -> int:
        # I'm not sure I understand this interface, but the intention is to get larger outcomes before smaller ones
        return -1
    def next_state(self, state, outcome, count):
        if state is None:
            state = ()
        state = (outcome,) * count + state
        if len(state) >= self._num_highest:
            raise NoNeedToLookAnyFurtherOnThisBranchWeCanStopNow(state[-self._num_highest:])
        return state  # Perhaps in case our pool doesn't have enough dice?

Where NoNeedToLookAnyFurtherOnThisBranchWeCanStopNow would recognized by the callback mechanism (currently, OutcomeCountEvaluator._eval_internal and OutcomeCountEvaluator._eval_internal_iterative, I believe) to stop delving and accept the raised state as final. The intention is that for KeepHighest(3)(icepool.d4.pool(4)) the callbacks might look something like:

state = None
state = next_state(state, 4, 4)
# done; final state is (4, 4, 4)

state = None
state = next_state(state, 4, 3)
# done; final state is (4, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 2)
# done; final state is (3, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 1)
# done; final state is (3, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 0)  # not sure if this call is actually made
state = next_state(state, 2, 2)
# done; final state is (2, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 0)  # not sure if this call is actually made
state = next_state(state, 2, 1)
# done; final state is (2, 4, 4)

# etc. …

The code's a bit hard to follow, but I think you could do something like this:

# <omitted>

UPDATE: Nope. I got the execution order wrong. I'll have to go back and think about how one might implement something like this.

Apologies if you already have something that performs that function and I missed it.

(By the way, I acknowledge that there are likely more efficient ways to perform something like "keep highest". I'm using it in this example because it's a useful vehicle for conveying the short circuit functionality I'm proposing.)

[HighDiceRoller]

Great suggestion!

I'm not sure I understand this interface, but the intention is to get larger outcomes before smaller ones

That's correct, this controls whether the outcomes are seen in ascending order (1), descending order (-1), or it doesn't matter to the evaluator (0). The 0 case has some extra room for optimization by dynamically choosing which side to pop from at each step, but I haven't gotten around to trying this out and thinking about the cache behavior.

Maybe I should use the word order instead?

Apologies if you already have something that performs that function and I missed it.

By the way, I acknowledge that there are likely more efficient ways to perform something like "keep highest".

At current I don't have a general-purpose short-circuit, though the thought has at least crossed my mind.

Currently there are two specific short-circuit mechanisms:

First, when next_state() returns the special value icepool.Reroll, that state / branch is immediately dropped from the computation. Though unlike the proposed short-circuit, this doesn't produce an outcome for that branch.

Second, the sorted_roll_counts mechanism (currently called the count-list in the paper) does implement the short-circuit; when it sees that all of the remaining dice are counted zero times, it immediately dumps all the remaining dice in the pool in exchange for the remaining denominator, since these dice will not be visible to next_state no matter what happens.

This is done on the pool side rather than the evaluator side; while not a general short-circuit mechanism, this does have some advantages of its own:

• Keep-highest or any other sorted_roll_counts can be composed with any evaluator with no modification of the evaluator necessary.
• Since the cache key is based on the pool, this can allow multiple queries to reuse cached values. Of course, the extent to which this actually helps depends on the query pattern.

The explicit pool syntax would be

icepool.d4.pool(4)[-3:]
# or
icepool.d4.pool(4)[0, 1, 1, 1]
# or
icepool.d4.pool(4)[..., 1, 1, 1]

(Un?)fortunately, this does steal a good deal of the thunder of the general case. Though there are some cases that don't fall under this, e.g. Neon City Overdrive. The potential benefits seem to come in two aspects:

• It could make certain expressions easier to write. While it is possible to duplicate the behavior by adding a "done" flag part of the state, this does add extra code to next_state. This will have to be weighed versus adding the extra bit of complexity to the API.
• Performance. I haven't conclusively determined how much a general short-circuit mechanism would save; would it only save a few calls to next_state or would it be able to eliminate big parts of the computation?

[posita]

• Performance. I haven't conclusively determined how much a general short-circuit mechanism would save; would it only save a few calls to next_state or would it be able to eliminate big parts of the computation?

This is probably the most significant factor. It very well could be that so few cases benefit from the complexity (and possible overhead, depending on implementation) of a short circuit like the one I propose that they deserve explicit specialization (e.g., Die.keep_highest).

[bszonye]

Regarding the use of exceptions to signal the shortcut case: I like that approach, although I think it a small tweak would make it more pythonic. The example code uses an exception as a sort of "long-distance return" statement, both signaling the end of iteration and returning the final value in the exception arguments. Contrast that with the Python generator protocol, which returns the final iteration on one pass and then raises StopIteration to signal that you're past the end.

Here's an alternate example using that protocol:

    def next_state(self, state, outcome, count):
        if state is None:
            state = ()
        if len(state) >= self._num_highest:
            raise StopIteration
        return (outcome,) * count + state

This approach has advantages and disadvantages. On the negative side, it means that you get an extra level of fan-out in the traversal, because you'll be signaling one past the end, instead of signaling at the end. On the other hand, this iteration protocol is so common in Python that it may be the cleanest way to implement shortcuts, especially for cases that have an underlying generator, iterator, or sequence, because those are all cases that naturally lend themselves to a terminal StopIteration or IndexError at the one-past-end point.