New patch in attachment takes care of modifying empty() and queue property according with the new implementation.
With this, the API behaves the same as before (this was my main concern).
Also, it's smarter when it comes to cleaning up too many pending cancelled items:

if self._cancellations > 50 \
  and self._cancellations > (len(self._queue) >> 1):
     ...

Also, I made a little benchmark script (in attachment) to make sure that the speed of the rest of the API hasn't been significantly affected by this change:


BEFORE THE PATCH

test_cancel                    : time=0.66648 : calls=1 : stdev=0.00000
test_empty                     : time=0.00026 : calls=1 : stdev=0.00000
test_enter                     : time=0.00309 : calls=1 : stdev=0.00000
test_queue                     : time=6.20777 : calls=1 : stdev=0.00000
test_run                       : time=0.00746 : calls=1 : stdev=0.00000


AFTER THE PATCH

test_cancel                    : time=0.00054 : calls=1 : stdev=0.00000
test_empty                     : time=0.00031 : calls=1 : stdev=0.00000
test_enter                     : time=0.00375 : calls=1 : stdev=0.00000
test_queue                     : time=6.30314 : calls=1 : stdev=0.00000
test_run                       : time=0.00716 : calls=1 : stdev=0.00000