As I suspected, the performance impact is significant (although pretty small).  Based on Linux perf, it looks like the extra test+branch in _Py_Dealloc adds about 1% overhead.  pyperformance shows something similar, see attached reports (pypref-trashcan.txt and perf-annotate-trash.txt).

An idea I've been trying is to add another type slot, e.g. tp_call_dealloc.  It could be set by PyType_Ready().  It would be called by the Py_DECREF macro on refcnt going to zero.  If the object is non-GC and Py_TRACE_REFS is off, can make tp_call_dealloc actually be the tp_dealloc pointer.  If the type has the GC flag, point tp_call_dealloc to a _Py_Dealloc version that checks tp_is_gc and does the trashcan stuff.

Unfortunately, all types don't have PyType_Ready() called on them.  So, we cannot rely on tp_call_dealloc being set correctly.