After some more tests I must qualify what I said. The freelist patch is
an improvement in some situations. In others it does not really have any
impact. On the other hand, the PyVarObject version handles memory-bound
cases dramatically better, see below.

With a small string:
./python -m timeit -s "s=open('INTBENCH', 'r').read()" "s.split()"
-> Unpatched py3k: 26.4 usec per loop
-> Freelist patch: 21.5 usec per loop
-> PyVarObject patch: 20.2 usec per loop

With a medium-sized string:
./python -m timeit -s "s=open('LICENSE', 'r').read()" "s.split()"
-> Unpatched py3k: 458 usec per loop
-> Freelist patch: 408 usec per loop
-> PyVarObject patch: 316 usec per loop

With a long string:
./python -m timeit -s "s=open('Misc/HISTORY', 'r').read()" "s.split()"
-> Unpatched py3k: 31.3 msec per loop
-> Freelist patch: 32.7 msec per loop
-> PyVarObject patch: 17.8 msec per loop

(the numbers are better than in my previous posts because the
split-accelerating patch has been integrated)

Also, given those results, it is also clear that neither pybench nor
stringbench really stress memory efficiency of strings, only processing
algorithms.

That said, the freelist patch is attached.