" /> A Programmer's Apology: November 2006 Archives

« October 2006 | Main | December 2006 »

November 14, 2006

Intel launches quad-core Kentsfield CPU

Intel takes Quad Core to the desktop

Intel Corp has officially launched its first desktop quad-core processor, codenamed Kentsfield.... a 2.66GHz chip with a 1066MHz front-side bus.

November 10, 2006

Lissajous sculpture


Fielding Brown sent me this.

The rim realizes in 3-D a particular Lissajous, and is made by laminating thin wood strips with aluminum around a form. The strings are dacron kite string fixed to the rim with small eyelets. The piece was just recently part of a solo show of my work at Cape Cod Museum of Art.

November 08, 2006

Efficient thread safe static initialization

Dave MacLachlan, a Mac programmer at Google, discusses thread safe initialization of statics here and here on the Official Google Mac blog offering an interesting peak under the hood of Objective-C and avoiding the pitfalls of the dreaded DCLP.

Bill Bumgarner offered a clever approach: the Objective-C method which initialzes the static uses an expensive lock to ensure that only one thread performs the initialization, but then calls ReplaceMethodImplementationWithSelector so that later calls to that method call an alternate version of the function without the lock. This provides a general solution to the complications of the DCLP, by using a function pointer which initially calls a function with a lock to guard initialization, then replaces the function pointer. This doesn't actually require a function pointer. One just needs a separate global saying, in essence, don't bother with the expensive lock any more. Modifying the objective C method pointer is quite elegant.

I wonder what subtleties I'm missing behind all this.

In the presence of CPU write-reordering, might another threads see the new method or function pointer but the old uninitialized static variable? A lock acts as a write barrier, but both are set between acquiring and releasing the lock, and the faster version of the function has no lock, so there needs to be an additional memory barrier between the initialization and ReplaceMethodImplementationWithSelector, unless one is implicit in the call to ReplaceMethodImplementationWithSelector.

On reflection, this is just the DCLP in disguise. In essence, DCLP is an attempt to avoid an expensive lock by doing a check first to see if its needed. Using a method or function-pointer for dispatch implements that check without an "if" statement, but doesn't eliminate the problems of DCLP in the presence of relaxed consistency when CPUs can reorder memory reads and writes.

Big screens

The visual interface to GC is designed to focus attention on the math with a minimum of distracting window dressing. The graph and equations are in the same window to keep them tightly coupled in the users mind, that they are both just different representations of the same underlying objects. Now that wide monitors are common for viewing DVDs, I've added the option shown below to make better use of space with wide but short windows.


It needs a better descriptive name for the preference, though. Anyone have any suggestions?

November 07, 2006

Discontinuous functions and C++0x

On the Graphing Calculator Users List, David Craig pointed out an interesting bug.

"A formula for a conic section in polar coordinates is r=A/(1+Ecos&theta) where A and E are constants. E is the eccentricity. When E is increased past one so that the section is hyperbolic, GC 'crosses' the hyperbola. This is distracting."



The bug occurs because GC samples the function at discrete points and connects them with line segments. Where the denominator goes to zero, the function is not continuous, but GC does not notice and blithely connects points sampled on separate branches of the hyperbola.

To do this correctly, GC should check that the function is defined and continuous everywhere on the interval between the sampled points. One of the proposals to the C++ standard committee meeting last month in Portland, N2137: A Proposal to add Interval Arithmetic to the C++ Standard Library provides just such a mechanism for checking continuity, by using interval arithmetic and passing an additional flag with each calculation to check if the function is defined and continous everywhere on an interval.

Jeff Tupper's GrafEq software, for example, uses interval arithmetic and continuity-tracking to rigorously prove the existence of a solution to the given equations in any pixel it draws. The image below is from GrafEq:


For now, the simplest way to work around the problem in GC is to explicitly tell it in the equation to ignore points too close to where the denominator is zero, by graphing the following instead:


November 05, 2006


After finishing the implementation phase of threading GC, I took a week off to rest from a cold. I expect some interesting debugging sessions, and look forward to benchmarking, profiling, and optimizing GC on multicore systems, but for now I'm moving on to other issues on my todo list.

I started this blog intending to write mostly about user interface design and the evolution of GC. Diving into threading occupied my full attention for several months, but now that that is done, it fades into the background. From the users perspective, it changes nothing in the interface. Some things are faster on newer machines, but new machines get faster all the time. That is expected. Eventually, I will be able to explore new kinds of visualization which would not have previously been possible without the speed benefits of parallel machines, enabling new functionality. But for now, the threading is just an implementation detail, transparent to the user.

Today, I'm looking at adding an option to the preferences dialog for GC4. In homage to A Short History of DragThing....

Graphing Calculator 1.0 (1993)

In designing Graphing Calculator 1.0, we would have preferred fewer preferences. Many options in the preferences dialog represent our failure as designers: we were throwing our hands up and saying 'We can't do the right thing, so we're forcing the user to make a choice." Taking the items one by one: Font Family, Font Size, and Significant Digits are reasonable items. Users know what they mean, different folks will have different preferences for these, and they are given default values so that users need not even be aware of the preferences.

3D Graph "Resolution" represents a programming failure exposing an implementation detail in the user interface. When GC graphs the function z=sin(x*y) as a 3D surface, it approximates the function by evaluating it on a square grid, 30 x 30 points by default. Ideally, GC would choose the grid automatically, making it fine enough to capture all the features of the function accurately, and coarse enough to do so quickly. However, choosing that automatically was too difficult to get right in all cases, so we made it a preference. This allows the user to explicitly trade off speed versus quality, but exposes an implementation detail which has little to do with the math being visualized.

Super/Subscript Font Size and Second Super/Subscript Size are the sizes of exponents, and exponents to exponents. At the time in 1994 some sizes of fonts were more readable than others, so this degree of control was necessary, though more complicated than we would have liked.

Assistance: Messages Below Equations. This option was simply an incorrect judgement call on Greg and my part. After our usability study in 1993, we added several messages which automatically appeared below the equation being typed in circumstances we could programmatically detect which we had observed from behind the two-way mirror watching people trying to use our software for the first time. We feared those assistance messages might become distracting and annoying, so we write them in grey on white to reduce their contrast, positioned them in the users peripheral vision, and provided a preference option to inhibit them entirely. No one ever complained about them, and in retrospect the option was unnecessary clutter.

Graphing Calculator 2.0 (1998)

In Graphing Calculator 2.0, we removed the "Assistance" preferences option. No one ever complained, or even seemed to notice. The "3D Graph: Resolution" preferences left the preferences dialog and become the resolution slider in the main window. This was necessary as GC2 allowed multiple equations, so the user needed to be able to choose the tradeoff between quality and speed separately for each equation. Net result: the prefs dialog is simpler by two items.

Graphing Calculator 3.5 (2004)

In Graphing Calculator 3.5, the Preferences Dialog became a Mac OS X Document Settings sheet. It also added the "3D Background" menu to control the backdrop for 3D views, and a help button. Sheets represent a significant UI improvement by closely tying the options to the document they affect, and distinguishing between global application preferences and document settings.

Graphing Calculator 4

In Graphing Calculator 4 (so far), I've removed the Superscript and Second Superscript options by computing them automatically as fractions of the main Font Size setting. It is tempting to reduce this even further by using the Text Menu to change the equation Font and Size.