Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Abstraction Quality Is Important

May 31, 2010

Does it take ten times as long to create 1,000 files in a file folder than it takes to create 100 files? This question has a surprisingly deep effect on system design--deep enough that it is worth understanding both why the question matters and what design lessons we can learn from it.For many years, I used operating systems that stored directories (also known as file folders) as unordered lists of names. This strategy came about for two reasons. First, the system automatically cached frequently used disk blocks in main memory, so if a directory was used more than occasionally, searching it was much faster than the disk speed would suggest. Second, the strategy meant that once the name of a file was written to disk as part of a directory, it would never be moved again. Therefore, if the machine were to crash in the process of writing a directory, the directory's data structure would still be valid.

The only way to search a completely unordered container is to look at every entry. This fact implied that putting a large number of files in a single directory would take an amount of cpu time that was quadratic in the number of files, so that creating 1,000 files would take 100 times as long as creating 100 files. Of course, because the same directory was involved with all of these files, the operating system's caching would assure that this overhead would still be much less than the overhead of writing all those files' contents to disk.

Despite the extra speed gained by caching, there were always some applications that would create directories with too many files for comfort, such as message spoolers. What would happen is that as the number of messages built up, the sheer amount of time needed to store and retrieve those messages would slow down message processing until the machine could no longer keep up. After that, the message queue would grow without bound until incoming messages were shut down for long enough for the queue to clear.

Authors of such applications would typically adopt a strategy of scattering their queues among multiple directories. If you have 1,000 files, and put them in ten directories with 100 files each, the resulting software runs much faster than if you put them all in a single directory.

I believe that this phenomenon is an example of something that happens fairly often but goes unobserved:

1) Someone defines a widely useful abstraction.

2) That abstraction is implemented in a way that is less good than it could be.

3) Users of that abstraction must then individually find workarounds for the abstraction's shortcoming.

Whoever provided the abstraction in the first place has an easier time of it this way, but only at the cost of shifting some of the implementation work to all of its users, who must then repeat it.

I was reminded of this phenomenon a few days ago when I was reading a discussion group for some software I was using. Another user commented that the number 29.97 displayed as 29.969999, and wondered whether there was anything to be done about it. The reply was that this kind of behavior was typical of programs that used 32-bit floating-point numbers, and there was nothing to be done.

The response was wrong. In fact, this is a problem that Guy Steele and Jon White solved more than 20 years ago, and for which both algorithms and (free) source code have been published. The real difficulty is that the solution is not exactly easy to understand or test, and so many library implementers don't want to take the trouble. As a result, people who use this particular software must decide whether they want to limit the precision of the numbers they display, or to regale their users with extra digits that add no extra precision.

There is nothing wrong with implementing useful abstractions in simple ways, especially if the alternative is not to implement them at all. However, part of the effort that should go into making software ready for widespread use should be to reimplement those abstractions to remove as many of their shortcomings as possible. That way, each individual user will not have to discover those shortcomings and figure out how to work around them.Whoever provided the abstraction in the first place has an easier time of it this way, but only at the cost of shifting some of the implementation work to all of its users, who must then repeat it.

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.