home · mobile · calendar · colloquia · 2009-2010 · 

Colloquium - Haddon

Is it Computer Science, Software Engineering, or Hacking?
Bruce Haddon
Paladin Software International

This talk presents the story of developing a class, SparseBitSet, intended for the Java JDK, based on the API for an existing class, BitSet. The motivation came from frequent complaints in the various discussion forums about the performance limitations of BitSet, particularly in large, but sparse, bit sets.

The talk will walk through the various evolutionary steps in bringing an implementation of SparseBitSet to fruition, starting from various published suggestions, to experimentation with alternative data structures, to the application of design patterns to obtain what appears to be an acceptable solution, that balances execution speed with storage requirements. The whole effort was something of a walk on the wild side!

The title of the talk refers to the fact that this kind of set maintenance has been studied as part of the theory of algorithms over a long period of time, that the software engineering involves real trade-offs with speed, storage and complexity, that design patterns are an effective approach to structuring code, and that up-front design involved too many unknowns to be effective. Even with all this background, there were many "on the spot" decisions to be made.

Finally, the ultimate structure used was obtained by successive refactoring on what appears to be simply an ad hoc basis. The talk demonstrates many of the tensions between the science of computing, the demands of software engineering, and the freedom of the hacker. The answer to the proposed question, which is the title of this talk, is left as an exercise for the listener.

Bruce has provided his slides, as well as the full source code of the class definition that is the subject of the talk.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)