Why is the update in-place faster than the out-of-place one in dynamic programming?

Question

In Barto and Sutton's book, it's written that we have two types of updates in dynamic programming

1. Update out-of-place
2. Update in-place

The update in-place is the faster one. Why is that the case?

This is the pseudocode that I used to test it.

if in_place:
    state_values = new_state_values
else:
    state_values = new_state_values.copy()
old_state_values = state_values.copy()

for i in range(WORLD_SIZE):
    for j in range(WORLD_SIZE):
        value = 0
        for action in ACTIONS:
            (next_i, next_j), reward = step([i, j], action)
            value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
        new_state_values[i, j] = value

max_delta_value = abs(old_state_values - new_state_values).max()
if max_delta_value < 1e-4:
    break

Why is the in-place version faster, and what is the difference? What I think is that it is only better for storage usage, I don't understand the speed increase part.

Answer 1

When you make updates in-place, then some of the entries in state_values[next_i, next_j] that you are referencing here

value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])

will already be updated earlier in the same loop. Which means you get to use the latest and likely more accurate values earlier.

The strength of this effect varies depending on the order that states and actions are visited. If you can manage to visit them in reverse order that they would appear in natural trajectories, then the speed improvement will be very noticeable.