1. 2

FYI the author is Jeffrey Ullman, very prolific researcher. If you’ve taken a course in compilers, automata theory, databases or introductory programming concepts, there’s a high likelihood you’ve used one of his textbooks.


  2. 1

    I think some of Ullman’s points are fair: purely incremental papers (like what we often see from the AI community) can get a bit exhausting. However when it comes to systems research I tend to disagree: the field of computer systems is where practice differs the most from theory.

    While balanced BSTs have much faster asymptotic lookup times than BTrees, in practice BTrees often provide better spatial locality and we are less prone to allocator fragmentation when using large allocations rather than the small ones used for BST nodes, which lead to Rust’s BTreeMap. In some cases, certain techniques are found to work better in practice with the theory following only later, such as the work of Hogwild! to give theoretical backing to why asynchronous SGD works well for machine learning tasks. These are the types of things you wouldn’t be able to see unless you tested your implementation on a real functioning computer.