This is always a hard question and I see answers swinging one way, so I'll play the game for the other side, though I don't claim either answer is correct, it's a very soft and case-by-case topic.
One thing about a complex but high performance solution is you can always just document the ever living heck out of it. I'm generally a fan of self-documenting code, but I'm also a fan of software that responds in an amount of time that makes me feel like it's not slowing me down. If you do go with the complex but high performance solution, consider what you can do to make it not so bad:
Wrap it in an interface, put it in an assembly on it's own, possibly even a process all it's own. Make it as loosely coupled as possible with as thick an abstraction wall around it as possible to avoid leaks. Write lots of unit tests for it to save regressions in the future.
Document it in the code, even consider writing some real documentation. Think about complex data structures and how they're documented, imagine trying to understand the implementation of one of them from code without a data structures book/wikipedia article to explain it. And yet we all accept that these complex data structures are in fact good things and it's beneficial that someone did implement them in our languages.
Remember that we're all sending messages on a TCP/IP stack that is likely as harry as code can get if any of us were to look at it, expressly so it performs the way we all require it too. Perhaps your problem doesn't require this level of optimization, perhaps it does, but beware when tackling this question as we all have to from time to time: There be dragons there.