In summary, the uncritical use of standard algorithms can miss implementation breakthroughs because of inappropriate measures (e.g., for packets filters such as BPF, the insertion of a new classifier can afford to take more time than search), inappropriate models (e.g., ignoring the effects of cache lines in software or parallelism in hardware), and inappropriate analysis (e.g., order-of-complexity results that hide constant factors crucial in ensuring wire speed forwarding).These words succinctly express feelings I commonly have. Standard algorithms theory often fails to live up to its promise in practice, untethered as it has become from applications. At the same time, a properly designed algorithm can yield immense breakthroughs in performance, so implementors cannot do without them. I believe we need more people willing to sit in the middle, but perhaps first we need more creative ways to bring theory and practice, or theorists and practitioners, together.
Thus another purpose of this book is to persuade implementors that insight into algorithms and the use of fundamental algorithmic techniques such as divide-and-conquer and randomization is important to master.
Friday, January 23, 2009
Algorithms and Implementation
I was leafing (again) through George Varghese's text, Network Algorithmics, and this caught my eye: