4/22/2010
3:30pm-4:30pm
ECCR 265
|
Is it Computer Science, Software Engineering, or Hacking?
Bruce K. 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.
|
