3 ms·

Well yeah, for many problems, there are solutions that have wonderful running time in the RAM model, like van Emde Boas trees or Fibonacci heaps, but are approx

Well yeah, for many problems, there are solutions that have wonderful running time in the RAM model, like van Emde Boas trees or Fibonacci heaps, but are approximately 100% useless in practice because of the constants involved. I guess this is where I pitch what we call "Algorithm Engineering", which considers both theoretical guarantees and practical performance, including properties of real-world hardware such as the ones you mentioned :) https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering

Const-me 7y ago
> including properties of real-world hardware such as the ones you mentioned :) https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering Are you sure about that? The most recent source of that article is from 2000. Half of the stuff I have mentioned didn’t exist back then. As far as I’m aware, there’re very few people in academia who study modern hardware while focused on software performance. I only know about Agner Fog, from technical university of Denmark.
- lorenzhs 7y ago
  It's a meta-article, it doesn't contain all the results of the field. But the field is alive and well. Just look at the proceedings of SEA and ALENEX (there was no SEA this year for stupid reasons that have nothing to do with the field). Agner Fog does some cool stuff (and I've used his RNG libraries many times) but as you said he studies modern hardware with a focus on software performance. Algorithm engineering is about finding algorithms that have nice theoretical guarantees (e.g., proving correctness or that there aren't any inputs which would result in substantially worse running time) while keeping in mind that the result would be quite useless if it couldn't be implemented efficiently on the machines we have, so the goal is to come up with algorithms that are also really fast in practice.

Const-me 7y ago

> including properties of real-world hardware such as the ones you mentioned :) https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering Are you sure about that? The most recent source of that article is from 2000. Half of the stuff I have mentioned didn’t exist back then. As far as I’m aware, there’re very few people in academia who study modern hardware while focused on software performance. I only know about Agner Fog, from technical university of Denmark.

lorenzhs 7y ago
It's a meta-article, it doesn't contain all the results of the field. But the field is alive and well. Just look at the proceedings of SEA and ALENEX (there was no SEA this year for stupid reasons that have nothing to do with the field). Agner Fog does some cool stuff (and I've used his RNG libraries many times) but as you said he studies modern hardware with a focus on software performance. Algorithm engineering is about finding algorithms that have nice theoretical guarantees (e.g., proving correctness or that there aren't any inputs which would result in substantially worse running time) while keeping in mind that the result would be quite useless if it couldn't be implemented efficiently on the machines we have, so the goal is to come up with algorithms that are also really fast in practice.