Recently I’ve had reason to go back over some data-structure theory, average times for insertion, deletion and search etc. I was reminded of a period around 1999 when I was implementing a Hyperchromatic Tree, a subtype of the basic red-black tree.
Hyperchromatic trees are lazily balanced i.e. balanced in the background rather than as part of the operation that changes the structure of the tree and they have some challenging locking disciplines to implement as well. They are designed to perform better under concurrent access than their ancestors.
Looking at my notes I was running a single test performing concurrent operations continuously for periods of 5 days against an instance containing 1 million entries on JDK 1.4. I suspect this period of my developer life taught me more about deadlocks and race conditions than any other.
Technorati Tags: concurrency, development, software
Comments Off
Entries (RSS)