Random idea:  For some range of array sizes (bigger than L3 cache), there might be a net benefit to sorting L1-sized clumps of pointers before making the Py_DECREF calls.  Possibly, the cost of sorting would be offset by improved memory access patterns.

On the other hand, this might just optimize an artificial benchmark that isn't representative of real code where the data is actually being used.  In that case, the program is already going to have to hop all over memory just to access the referred-to objects.