Sharing Causes Contention

"Hey!" I exclaimed to Wendy. "Where's my Fellowship DVD?"

She shrugged. "You said Bahb could borrow it."

"Well, sure," I fumed, "but Bob took it over two weeks ago. I've been waiting for it, and I was sure it'd be back by now, but I can't find it. He must still be using it."

She shrugged again and repeated: "But you said Bahb could borrow it."

This time I didn't take the bait and only sighed in response.

"It's so nice of you to share your things, pardner," Wendy finished and flashed me a smile, winked, and went back to her desk. I fumed a little more and then went back to work too.

A few hours went by, and I gradually let the frustration go and managed to be fairly productive for the rest of the morning. All in all, I thought, life could be a lot worse. I even hummed a little as I ran some unit tests and checked in another piece of code under the new development branch and two good bug fixes into the shipping product's source tree.

Then, just before lunch, Kerry appeared at my desk. "Uh, got a minute?" he asked.

I looked up. "Sure, Kerry. Wassup?"

"I've got a performance problem in this code," he said and showed me a longish function that looked something like this:

void SomeFunc()
{
  // ... some processing ...
  if( condition )
  {
    UpdateSystemStatus();
  }
  // ... more processing ...
}

"Yes," Kerry said quickly. I gathered that he'd been caught out on that one before and wasn't about to repeat the mistake; that was good; he was learning fast. "This code is supposed to scale on multiprocessor machines, but it doesn't; performance is pretty much flat. When I ran the profiler on the thread executing this part, I found out that the most elapsed time in this module is being spent inside SomeFunc()."

"What part?"

"Uh... what 'what part'?" the young intern said, seeming less sure now.

"What part of SomeFunc()? Was the time almost all in SomeFunc() itself, or was there more information about how the time was distributed in the functions SomeFunc() calls?"

"Oh. Well, it only calls some of our internal common functions, so I didn't profile all of--"

It was just then that I caught a shadow out of the corner of my eye and jumped only slightly less than Kerry as a loud snap split the air behind us.

"Sharing causes contention," the Guru said softly, gesturing with the heavy book in her hand.

"Oh, uh, hi there..." we both greeted her lamely.

"My apprentice, my novice," she greeted us in return. "You wrote this code, my apprentice, did you not? Why are you using a global state here?" she asked, pushing a graying lock behind one ear and shifting her tome to her other hand.

"Global state?" I asked.

"Global state," she affirmed, "in your UpdateSystemStatus(), which, I believe, updates a program-wide setting."

"Oh, that. Of course. I knew I shouldn't hide away status information, so I made sure it would be available to every part of the program, and that every part could update it. 'All I really need to know I learned in Kindergarten,'" I added with a smile [1]. "The first three commandments are: 'Share everything, play fair, don't hit people.'"

"Alas, my apprentice," the Guru riposted, "software development is not always like life."

This made me uncomfortably remember some get-a-life advice I'd received recently, though I hadn't quite understood it. "It's... uh... not?"

"It is not," she said firmly as Kerry shrunk back slightly, glad to be only an observer at the moment. "Sharing everything is not always a good idea, even in life. If this you doubt, consider: ought married persons to share everything?"

"Well, a healthy marriage is all about sharing, so I guess the more the better," I answered hesitantly, aware of a possible trap but unable to quickly see it before I had to come up with some kind of answer.

"In many things, that is so. But consider colds and flus. Consider toothbrushes. Consider dresses. No," the Guru shook her head, "even in the most tightly coupled relationship, not all sharing is necessary or desirable. Indeed, as you grow to become a wise master, you will see clearly that shared state is the source of much corruption and injustice, not to mention run-time inefficiency."

"Shared state can cause injustice and inefficiency?"

"Yes," she agreed, "and corruption if mishandled, I said, too. As the wise poet put it:

One Thing to rule them all,
One Thing to find them,

One Thing to string them out
and in the shared state bind them.

"This," she added, "but hints at the perils of having dependency on a single precious object."

I suppressed a groan just as Kerry blurted: "String what? Bind what?"

"Serialization," she intoned, "shared state frequently leads to serialization, not to mention other effects of interdependency. In your code, the reason for your performance problem is in part that the shared state requires a lock/unlock operation for each update, and locks can be expensive. But in fact I observed Bob struggling with the same problem earlier today, so know that the main expense here is in fact not even that locking overhead, but the serialization -- that your system is performing its larger task by breaking it down into multiple threads that are designed to work independently and concurrently, potentially on different processors, but many of your threads are calling UpdateSystemStatus(). Which means...?" she prompted, looking at Kerry.

Kerry looked blank and nervous. I thought I saw what she was getting at, so I interjected: "Which means they're all wai--"

The Guru waved me off and interrupted, "Apprentice, I did not question you." She repeated to Kerry: "Novice, voice your thoughts: Which means...?"

"Uh," Kerry fumbled, "that they're all updating the global system status?"

"Of course, of course. Which means...?"

"Uh..." Kerry thought, and then I could see the penny drop and he brightened. "Which means... that maybe they're all waiting on the single lock on the global status, and backing up behind that?"

"A good beginning," the Guru acknowledged. "More specifically, because the single global lock is being accessed so frequently, much of the benefit of multithreading is being dissipated. Rather than allowing one thread to do work while another is blocked, threads are inherently serialized by access to a single frequently shared resource and thus on the whole perform little better than a single-threaded application... which is precisely what this is implicitly turning your program into."

"You are right, master," I said, just to get a reaction out of Kerry. He didn't disappoint; I wondered whether he would ever get used to the Guru shtick.

The Guru reached over and pulled up the code:

void UpdateSystemStatus()
{
  // ... some processing ...
  if( anotherCondition )
  {
    Lock<Mutex> lock( systemStatus );
    // ... update ...
  }
  // ... more processing ...
}

"Uhhh..." we uhhhed in unison.

"Consider that thread serialization... would you not consider all these threads 'strung out' serially, 'bound' by shared state? It is even as the poet said. Worse, each waiting thread has no control over the lock; they must all wait, not for an operating-system-controlled context switch, but for the locking thread to be good and ready to release the lock. This too is vanity and a striving after wind."

"Ohhh," we ohhhed together.

"And that," she added pointedly, "is also why your profile reports that the most elapsed time is being spent in the update. Yet you will find that the most active execution time is not being spent there at all. That profile disparity between elapsed and active execution time also should be a clue that a contention exists."

"I guess the same would be true even if we were using multiple processes instead of multiple threads, as long as they still shared some state like this?" I asked, showing off a little by trying to generalize and anticipate the next step.

"As you say, apprentice. Just using a fork() does not make the problem go away, as the Dining Philosophers will readily confirm." There was a twinkle in her eye, so there must have been a joke in there, but I didn't get it. When she saw that whatever it was had just sailed right over both our heads, she continued with a more businesslike: "But no matter. There are many examples of where sharing causes resource contention. Name several. Quick, now."

"Uh..." I racked my brains for another example. "String reference counting?" [2]

"Indeed," she agreed. "As is now well known in the literature. Also a good example of where failure to pay sufficient respect to the shared state can and does also cause corruption, not merely ineffeciency. What else?"

"I know," Kerry piped up, surprising me, "how about some bad memory allocators?"

"Well done, my child," the Guru rewarded him with a smile. "A program has but one default free store, which is therefore necessarily shared. Therefore a thread-safe memory allocator requires a lock on that common area to avoid corrupting it inadvertently. But a naïve implementation acquires the lock directly; more mature implementations use more advanced techniques, such as using thread-local storage to cache smaller pools for individual threads and only falling back to the main pool infrequently when the thread-local memory cache is empty. What else?"

"What about that old-style 'cooperative' multitasking," I threw in, warming to the game. "Each process, even the operating system, had to wait until the application with the lock was good and ready to let go of it."

"Well done, apprentice," the Guru nodded again. "And consider multiprocessor machines and how the multiple processors' work is easily neutralized if it must be serialized by access to the same shared memory. It is well known that shared-nothing architectures scale much better than shared-memory or shared-everything models."

Kerry leaned forward. "This is fascinating. There are so many examples. Tell me everything!"

The Guru raised a brow. "Everything? You are far too eager and curious for an intern. Most unnatural."

"But is sharing just always wrong?" I asked.

"Not at all," she said. "For example, if there is a single keyboard in the system, it is quite reasonable to have a single keyboard controller object. It is injudicious and ill-advised -- that is to say, needless -- sharing that is the root of all sorts of unwelcome coupling. In this case, consider alternatives to a single shared status... perhaps you will find that a per-thread status is equally effective and will cause less needless resource and time contention, and perhaps even less programmer contentiousness. So heed the warning about sharing Things over widely:

One Thing to rule them all, One Thing to find them,

One Thing to string them out and in the shared state bind them.

"The advice to 'share everything' may apply in kindergarten, but is slightly too broad for real life. When many share one Thing, they must wait until the current Thing-Bearer is good and ready to release his lock on it. When the lock is not released in time, or the One Thing destroyed before the one waiting can acquire it, even the most powerful threads have fallen. Besides," she added with another twinkle in her eye, "have you not noticed that even in life, sharing causes contention? Sharing of toothbrushes, of clothes... and of Fellowship DVDs, on the release of which you now find yourself waiting?"

"Touché," I groaned.

Satisfied with a lesson well taught, she turned to leave and reopened her book. "For now, you can but wait calmly for your DVD. I'm sure Bob will eventually release it and unblock you," her voice floated back as the turned the corner, "when he is good and ready to..."

"Say," Kerry asked after she left, sassing me a little, "wasn't it just a few weeks ago that I overheard the Guru chewing you out about Singleton abuse?" [3]

I reddened slightly. "Yes, but that was different... sort of. And she chewed us both out about locks, if you'll remember." [4]

Kerry reddened equally. "Uh, right. Maybe let's call it a draw and just go fix this."

"Maybe let's," I agreed.

References

[1] R. Fulghum. All I Really Need to Know I Learned in Kindergarten (HarperCollins, 1990).

[2] H. Sutter. More Exceptional C++, Items 13-16 (Addison-Wesley, 2002).

[3] J. Hyslop and H. Sutter. "Conversations: Once Is Not Enough," C/C++ Users Journal, March 2003.

[4] J. Hyslop and H. Sutter. "Conversations: Points of Order," C/C++ Users Journal, February 2003.

About the Authors

Jim Hyslop is a senior software designer with over 10 years programming experience in C and C++. Jim works at Leitch Technology International Inc., where he deals with a variety of applications, ranging from embedded applications to Windows programs. He can be reached at [email protected].