FWIW, there are two distinct issues.  As everyone has noted here, accessing memory in non-sequential order is a performance killer.

The other issue (the one I was working on) is that early-out first-char or last-char tests are a waste (almost never executed) if we already know that the string hashes match (i.e. in the string equality calls from the  dict and set lookup routines).  If the hashes match, the odds are 2**64 to 1 if favor of the strings being equal.