Channels ▼

Bil Lewis

Dr. Dobb's Bloggers

Self-Optimizing Data Structures

October 23, 2009

Why not?

Why should I have to spend my time thinking about how some data
structure will be used, just to select the best implementation? Why
can't the computer do that for me?

Let's say I want to have a list of stuff. In today's world, I have to
designate the implementation to be used:

List<Stuff> stuffs = new ArrayList<Stuff>();

But it may well be that a LinkedList would have been more
efficient. Or some other kind of list.

When I was building the Omniscient Debugger (See "Debugging
Backwards in Time" Dr Dobbs... 2005? Just Google "Omniscient"), I
found that I spent a massive amount of time creating lists and adding
things to them (almost never removing anything). I forget, but it was
90% of my CPU or more.

I studied the usage of lists and found a distinct pattern. 99.9% of
lists in situation 1 contained exactly 1 element, and 99% of lists in
situation 2 had 1 or 3 elements. I wrote two specialized list
implementations and my program ran 5x faster.

Why couldn't the computer have done that for me?

I can easily imagine a static optimizer. I'd write the program, run it
on a "representive" test case in "analysis" mode, and an analyzer
would post-process the results and cache suggestions for which list
implementations to use where. On the next run, my program would use
those suggestions and it would run faster.

[If we limit our choices to LinkedLists and ArrayLists, then the
decision is pretty simple. Allowing the machine to create new and
innovative implementions ala the Omniscient Debugger would be so much
more fun, however.]

But why do it statically?

Why not just let the program run and refine the data structures being
used dynamically?

The Sun Hot Spot dynamic complier does something pretty much like this
for compiling byte code to native instructions, including backing out
previously compiled code and recompiling, when required.

So it's definitely possible.

Would it be worth it?

-Bil

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