Followup: In my parser tag callback, in the big loop, I replaced this style of code:
return wfMsg('my-message', $arg)
with this code that locally caches the message value:
static $msg = '';
if (! $msg) $msg = wfMsgGetKey('my-message', true);
return wfMsgReplaceArgs($msg, array($arg));
and got a 40% speedup in my loop.
DanB