My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee fairness -- that is, they do not guarantee that in instances of contention, the lock will be acquired by threads in the order that they called lock(). In fact, it is even possible (although hopefully uncommon) that in cases of high contention, some of the threads waiting to acquire the mutex might never acquire it.
This seems like an unhelpful behavior to me -- it seems to me that a fair mutex would yield behavior more in line with what a programmer would want/expect.
The reason given for why mutexes are typically not implemented to be fair is "performance", but I'd like to understand better what that means -- in particular, how does relaxing the mutex's fairness requirement improve performance? It seems like a "fair" mutex would be trivial to implement -- just have lock() append the calling thread to the tail of the mutex's linked list before putting the thread to sleep, and then have unlock() pop the next thread from the head of that same list and wake it up.
What mutex-implementation insight am I missing here, that would explain why it was considered worthwhile to sacrifice fairness for better performance?