Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

A classic tradeoff

September 21, 2009

If you have ever used music-production software such as Ableton Live or Cakewalk Sonar, you know that one of the important steps in making such a program useful is to choose the appropriate buffer size.  If it is too small, you will get crackles in your speakers whenever your operating system has to do something in the background.  If it is too large, there will be an unacceptable delay between when you play a note on your keyboard and when the sound emerges from the speakers.

I was reading a forum comment about a camera store recently.  The commenter had returned a defective item and was complaining that it took too long for him to receive a replacement.  The store's representative explained that the only way they could afford to process the volume of packages that come in and out of the place every day is by having each package go through a series of stages, in each of which someone did something to them such as verifying their contents against the enclosed invoices.  As a result, returning anything to them did indeed take a few days to process, and they could not afford to shorten that interval.

What do these two stories have in common?  What they share is the notion that it is possible--and usually necessary--to trade turnaround time against throughput.  This kind of tradeoff occurs whenever it is possible to combine data into batches, and when there is a substantial overhead involved in processing a batch.  In such cases, the batch size has a profound effect on system behavior.  If you make the batches small, the system responds rapidly to new data but spends resources on batch overhead.  If you make batches large, you can typically push a lot more data through the system, at a cost of having each individual piece of data spend longer waiting to be processed.

Seeing a few such tradeoffs makes one realize how often they appear.  For example, using a large block size in a file system reduces the number of disk accesses, but does so at the cost of increasing the amount of space lost to breakage along with increasing the risk of data loss in the event of a crash.  Building a larger theater can allow more people to see the plays presented there, but also makes it a bigger risk to put on a play there.  Airlines spend a lot of time, effort, and money deciding how large the airplanes should be on each of their routes.

Sometimes it is possible to find compromises that give you some of the advantages of both extremes.  For example, I once wrote a memory allocator that greatly increased the speed of many applications that used it.  Its strategy was simple:  For memory blocks less than a given size, it would never return those blocks to the operating system.  Instead, it would maintain its own list of free blocks, one list for each distinct size, and only go to the operating system for memory if the list of blocks of the requested size was empty.

When I wrote this allocator, I realized an important subsidiary principle:  Sometimes it makes sense to treat blocks of different size differently.  In the case of a memory allocator, it is usually safe to assume that someone who allocates a block of memory intends to use that memory for something.  Moreover, using memory involves looking at all of its contents.  Therefore, someone who allocates a large block of memory is apt to spend a lot of time using that block.  From these facts, I drew the conclusion that I should care only about how long it takes to allocate small blocks of memory, because it would take significant time to use a large block anyway.

I have seen techniques used in other circumstances that have a similar feel to them.  For example, one might have a large buffer for a file, but arrange things so that if nothing happens to the buffer for a significant period of time, such as a few milliseconds, the buffer is automatically flushed to disk.  Such a hybrid strategy ensures that when lots of data are being generated, there isn't much time eaten up by multiple trips through the operating system; but when data are coming in a trickle, no one needs to spend much time waiting for data that might be sitting in a buffer.

Of course, such techniques have a disadvantage of their own: They add complexity.  Indeed, people who talk about trading between response and overhead do not always notice that there can be a third item to trade.  Instead of talking about trading between response and overhead, perhaps we should talk about trading between response, overhead, and complexity.  My personal bias is to try to avoid the complexity side of such tradeoffs, but sometimes its advantages are too compelling to ignore.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video