Can I revert mutations if error is raised inside a function?

General Usage
1

I am writing a few functions for fast median calculation (mostly replicating Alexandrescu’s paper on fast deterministic selection).

One of the methods includes assertions that certain assumptions are not violated, however, those assertions happen when the input has already been (partially) mutated. Is there a (simple) way to revert those changes if AssertionError is raised?

(as a side note, I’m using this project as a way to get back into Julia, with Documenter.jl, tests, coverage, etc. Is this forum the right venue to ask for optimization and development advice?)

2

The straightforward(?) way would be to record the minimal information for the original state at the beginning, use it to revert those changes if some critical condition is false, then throw the AssertionError. I’m not sure if it’s better to throw it explicitly or use @assert false "...", the docstring for @assert warns that asserts are disabled at some optimization levels but I don’t know if that refers to just the macro or all thrown AssertionError.

3

That’s the approach I was considering too; but it feels like I’m “going against the grain” and maybe it’s better to rethink those functions. Perhaps I could store the transpositions that have to take place and sacrifice a bit of memory in exchange for a more predictable behavior… hmm. In any case it seems like I wasn’t missing something obvious, so thanks for your response, I’ll mark it as the solution!

4

It’s a pretty natural approach knowing that mutations don’t naturally leave traces to reverse. But are you sure you want to close this so soon? It’s very possible that people can contribute more ideas. If you’re considering refactoring, sharing a (possibly reduced) example of the algorithm would help too. It’s hard to have ideas when we don’t know what the assertion is and how often you need to check it (for example, do you need to check it once before a loop, or is it an easily violated condition that must be checked between steps). It’s not even clear if throwing an AssertionError is appropriate for the use-case.

5

Oh, that’s very kind. I was trying to keep it contained to just the original question.

The function is basically Hoare’s partition but knowing that there’s an internal subarray that is already partitioned. So basically we have an array r, an index we want to partition around p, and two indices low, high such that we assume: r[low:p] .<= r[p] and r[p:high] .>= r[p]. The algorithm is basically swapping everything that needs to be swapped outside of this subarray and then clean up if needed one side. This works for speeding up a selection algorithm similar to median of medians (called median of ninthers) because the chunk of the array that is already properly partitioned grows. I’m a bit worried about recursion but I’ll check the quick sort implementation.

I could just assert these assumptions at the beginning honestly… I was just porting line by line the D implementation and I think now that I understand better what’s happening I can change a few things.

Here’s a simplified version of it (partitionrightside! and partitionleftside! modify input array and return new index of pivot, and assert one half of the assumptions in them):

function hoarepartitionwithassumptions!(
    arr::AbstractVector,
    low::Integer,
    pivot::Integer,
    high::Integer
)
    @assert (low <= pivot && pivot <= high) "Wrong indices provided."
    right_index = length(arr)
    left_index = 1
    while true
        while arr[left_index] <= arr[pivot]
            if left_index == low
                # Here I wanted to assert other half of assumptions
                return pivot + partitionrightside!(@view(arr[pivot:right_index]), high - pivot + 1) - 1
            end
            left_index += 1
        end
        while arr[right_index] >= arr[pivot]
            if right_index == high
                # Here I wanted to assert
                return left_index + partitionleftside!(@view(arr[left_index:pivot]), low - left_index + 1) - 1
            end
            right_index -= 1
        end
        arr[left_index], arr[right_index] = arr[right_index], arr[left_index]
        left_index += 1
        right_index -= 1
    end
end
6

Admittedly, I don’t know the full algorithm, but it’s not clear to me what you want to assert in the lines “# Here I wanted to assert other half of assumptions” and “# Here I wanted to assert” and where (replacing the comments? inside the partition methods?), there’s no descriptions. That part at least seems relevant to the question at hand.

On another note, you said that you assume r[low:p] .<= r[p] and r[p:high] .>= r[p], but it looks to me like you’re not assuming it. You check for those conditions in arr[left_index] <= arr[pivot] and arr[right_index] >= arr[pivot], and if neither is met and thus arr[left_index] > arr[pivot] > arr[right_index], you swap the elements so both become true.

7

Hm, so first of all sorry for the lack of clarity there. It was late evening and it had been a long day.

Regarding the comment: the partitionrightside! function has inside an assertion:

for i = 1:high
    @assert arr[i] >= arr[1] "Assumption broken"
end

block. Note that we send to it a view arr[pivot:right_index] and an index high (which we translate from the original high by pivot-1 units to the left). What that function does is basically move everything between (high+1):end that is smaller or equal than the pivot to the beginning, and move the pivot to the right place, so we end with a well partitioned vector.

Therefore, the “other half of assumptions” I would want to assert would replace the comment and be:

for i = low:pivot
    @assert arr[i] <= arr[pivot] "Assumption broken"
end

The partitionleftside! function does the opposite checks and works with the other side of the array, but the idea is the same. Honestly, I am considering either doing all the assertions at the beginning (I end up doing them all anyway) or not exporting the method and ignoring the assertions to avoid having to do O(N) comparisons.

Note that the while loops guarantee that left_index < low and right_index > high so those swaps happen outside the region that we assumed is already well partitioned.

I’ve been looking at the implementation of the sort algorithms (there’s a partition algorithm there too, I think it’s also Hoare’s partition) and found some other potential optimizations like using @inbounds macro. I’ve also seen how the Ordering type is used, and I think I’ll try to adapt my code to that as eventually what I’m implementing are QuickSelect algorithms so maybe I could do a PR to the sort module…

I hope this was clearer!

8

This is sensible, saves unnecessary work. Ideally you can do all the validation without changing anything then do all the mutations without a care, but algorithms aren’t always that convenient.