I looked into the topic in some detail year ago, because I copied Wikipedia's approach for an in-house CMS editor. I looked through the code, did loads of performance experiments, read through related forums posts, etc...
The wiki staff themselves admitted that the current parser is inefficient, partly because of PHP, partly because the underlying grammar was not designed to be efficient, and partly because the parser itself was built up over time and wasn't easy to optimise.
My approach was to write the parser and a matching "markdown inspired" format at the same time, optimised for speed. Just a handful of small tweaks to the syntax were all that was required to largely eliminate backtracking and achieve a nearly linear parsing time in most cases. If I remember correctly, I had it down to about 1-5ms for a typical 64 KB page, and then HTML generation was another 5-10ms depending on various factors.
What a lot of people are missing here is that Wikis are not at all like typical "ERP" applications. The latter sometimes requires dozens of API calls and thousands of database queries to generate just one kilobyte of output HTML. Wiki is very linear, with a single 1-100KB blob of text as input, a matching 1-100KB blob of HTML as output. It all boils down to the parsing and HTML generation efficiency, nothing else matters!