<p>For general protocol message exchange, which can tolerate some packet loss.  How much more efficient is UDP over TCP?</p>

UDP is slightly quicker in my experience, but not by much. The choice shouldn't be made on performance but on the message content and compression techniques.
If it's a protocol with message
exchange
, I'd suggest that the very slight performance hit you take with TCP is more than worth it. You're given a connection between two end points that will give you everything you need. Don't try and manufacture your own reliable two-way protocol on top of UDP unless you're really, really confident in what you're undertaking.