4 ms·

Sure thing. So did you ever issue a mea culpa regarding your statements in ACM Queue [1]: "The past 30 or 40 years of hardware and operating-systems developmen

Sure thing. So did you ever issue a mea culpa regarding your statements in ACM Queue [1]: "The past 30 or 40 years of hardware and operating-systems development seems to have only marginally impinged on the agenda in CS departments' algorithmic analysis sections, and as far as my anecdotal evidence, it has totally failed to register in the education they provide." Cache-Oblivious Algorithms and Data Structures - Erik Demaine http://erikdemaine.org/papers/BRICS2002/paper.pdf http://erikdemaine.org/papers/BRICS2002/paper.pdf Abstract: A recent direction in the design of cache-efficient and disk- efficient algorithms and data structures is the notion of cache obliviousness, introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999. Cache-oblivious algorithms perform well on a multilevel memory hierarchy without knowing any parameters of the hierarchy, only knowing the existence of a hierarchy. Equivalently, a single cache-oblivious algorithm is efficient on all memory hierarchies simultaneously. While such results might seem impossible, a recent body of work has developed cache-oblivious algorithms and data structures that perform as well or nearly as well as standard external-memory structures which require knowledge of the cache/memory size and block transfer size. Here we describe several of these results with the intent of elucidating the techniques behind their design. Perhaps the most exciting of these results are the data structures, which form general building blocks immediately leading to several algorithmic results. - Cache-Oblivious Algorithms - Thesis - Harald Prokop - 1999 http://supertech.csail.mit.edu/papers/Prokop99.pdf http://supertech.csail.mit.edu/papers/Prokop99.pdf [1]: https://queue.acm.org/detail.cfm?id=1814327 https://queue.acm.org/detail.cfm?id=1814327

phkamp 6y ago
No, and I dont think I owe anybody an apology for that. My main objection was that some of the algorithms praised in theoretical CS have near pessimal behaviour on actual hardware, and have had so for a quarter of a century, yet these "details of implementation" were deemed a waste of educational bandwidth. I've had a fair bit of communication with people in boths ends of CS education about that piece, and I think by and large most agree that I have a valid point there. But nobody wants "Algoritms %03d" to turn into "Optimizing your code for $CORPS microarchitecture %03d", and modern architectures are horribly complicated, in particular from a performance point of view, so sifting out the most representative and relevant phenomena and finding a way of presenting them in education is not easy. On CS TA told me that they hand out my article mid-semester, and ask the students to identify algorithms in their textbook which are robust or vulnerable to actual hardware performance. I'm torn between being flattered and thinking it is a bit of a cop-out. As far as cache-oblivious algorithms go: I'll consider them when they prove they are worth their often formidable complexity. Yes, it would be nice to never have to think about about page-sizes or cache-line widths and all that again, but if only people with a phd in those exact algorithms (many of which are patented) can debug programs which use them, the cost/benefit tilts.
- eternalban 6y ago
  Did you know about Cache-oblivious algorithms when you wrote that essay? My sense is that you did not, otherwise you would have mentioned them in passing and noted your (arguably reasonable) objections regarding their practicality. [p.s. I'll 'retract' /g that mea-culpa. Didn't mean it in a literal sense of "apology".]
  - phkamp 6y ago
    Yes, I did know about their existence, and I had even tried to implement one of them myself, but ditched once I realized that patents would preclude its use in FOSS. But I did not think then, and still do not think now, that they are core material in bread&butter CS algorithm courses, I consider them more of a research-curiosity, so I cant say I even thought about bringing them into the article.
    - eternalban 6y ago
      Fair disclosure that I studied EE so have second hand insight into what a CS education entails, but my thoughts on the oversight that you noted are that it may be too much to expect that level of knowledge sharing in a 4 year undergrad education. I am reminded of internship and post-doc of physicians working in a hospital. I’m sure you are aware of the prevalent mindset (from blogosphere to actual working environments) that heavily discount the value of experience in a software engineer. What are your thoughts on that?
      - phkamp 6y ago
        I think it is tricky. The claimed "time ~ experience" correlation certainly exists, and in a long established discipline, like plumbing, experience is almost unquestionably a virtue. In a young discipline, such as computers, there is a very concrete risk of confusing experience with not-moving-with-the-times, certainly on the party claiming experience. So it is probably very much a case-by-case judgement call ?
        6y ago

phkamp 6y ago

No, and I dont think I owe anybody an apology for that. My main objection was that some of the algorithms praised in theoretical CS have near pessimal behaviour on actual hardware, and have had so for a quarter of a century, yet these "details of implementation" were deemed a waste of educational bandwidth. I've had a fair bit of communication with people in boths ends of CS education about that piece, and I think by and large most agree that I have a valid point there. But nobody wants "Algoritms %03d" to turn into "Optimizing your code for $CORPS microarchitecture %03d", and modern architectures are horribly complicated, in particular from a performance point of view, so sifting out the most representative and relevant phenomena and finding a way of presenting them in education is not easy. On CS TA told me that they hand out my article mid-semester, and ask the students to identify algorithms in their textbook which are robust or vulnerable to actual hardware performance. I'm torn between being flattered and thinking it is a bit of a cop-out. As far as cache-oblivious algorithms go: I'll consider them when they prove they are worth their often formidable complexity. Yes, it would be nice to never have to think about about page-sizes or cache-line widths and all that again, but if only people with a phd in those exact algorithms (many of which are patented) can debug programs which use them, the cost/benefit tilts.

eternalban 6y ago
Did you know about Cache-oblivious algorithms when you wrote that essay? My sense is that you did not, otherwise you would have mentioned them in passing and noted your (arguably reasonable) objections regarding their practicality. [p.s. I'll 'retract' /g that mea-culpa. Didn't mean it in a literal sense of "apology".]
- phkamp 6y ago
  Yes, I did know about their existence, and I had even tried to implement one of them myself, but ditched once I realized that patents would preclude its use in FOSS. But I did not think then, and still do not think now, that they are core material in bread&butter CS algorithm courses, I consider them more of a research-curiosity, so I cant say I even thought about bringing them into the article.
  - eternalban 6y ago
    Fair disclosure that I studied EE so have second hand insight into what a CS education entails, but my thoughts on the oversight that you noted are that it may be too much to expect that level of knowledge sharing in a 4 year undergrad education. I am reminded of internship and post-doc of physicians working in a hospital. I’m sure you are aware of the prevalent mindset (from blogosphere to actual working environments) that heavily discount the value of experience in a software engineer. What are your thoughts on that?
    - phkamp 6y ago
      I think it is tricky. The claimed "time ~ experience" correlation certainly exists, and in a long established discipline, like plumbing, experience is almost unquestionably a virtue. In a young discipline, such as computers, there is a very concrete risk of confusing experience with not-moving-with-the-times, certainly on the party claiming experience. So it is probably very much a case-by-case judgement call ?
      - 6y ago