The only optimisation idea I came up with (other than the addition of a tp_format slot) is for string objects to be able to cache their (lookup:subformat) pairs rather than having to parse themselves every time. That has obvious memory consumption implications though.
If a string is used as a formatting template, it is bound to be used again as such. So IMHO it sounds quite reasonable. In order to avoid memory consumption issues there could be a centralized cache as for regular expressions. It makes it easier to handle eviction based on various parameters, and it saves a few bytes for string objects which are never used as a formatting template. Regards Antoine.