When Greedy Algorithms Can Be Faster [C++]
1–10 of 30 posts
Re: When Greedy Algorithms Can Be Faster [C++]
#2I suspect if you started using SIMD instructions, the analytical case would get better again (since it's branchless).
Re: When Greedy Algorithms Can Be Faster [C++]
#3I suspect if you started using SIMD instructions, the analytical case would get better again (since it's branchless).
Apropos of SIMD – I'm also surprised that the inner loop of the rejection-based algorithm optimized to MMX, but not the analytic algorithm!
I would like to think the rejection algorithm after -O3 is benefiting from branch prediction and all sorts of modern speculation optimizations. But I imagine the real test of that would be running these benchmarks would be running these benchmarks on a 5-10ish year old uarch.
Re: When Greedy Algorithms Can Be Faster [C++]
#4I don't know how numerics in hardware works, but would the use of functions like sin, cos, sqrt incur a penalty as well, even if only a slight one?
It's really fascinating to think about how all of this would work.
Re: When Greedy Algorithms Can Be Faster [C++]
#5I suspect if you started using SIMD instructions, the analytical case would get better again (since it's branchless).
Apropos of SIMD – I'm also surprised that the inner loop of the rejection-based algorithm optimized to MMX, but not the analytic algorithm! I would like to think the rejection algorithm after -O3 is benefiting from branch prediction and all sorts of modern speculation optimizations. But I imagine the real test of that would be running these benchmarks would be running these benchmarks on a 5-10ish year old uarch.
Ten years ago, you already have Skylake with pretty good indirect branch predictors...
Re: When Greedy Algorithms Can Be Faster [C++]
#6I don't know how numerics in hardware works, but would the use of functions like sin, cos, sqrt incur a penalty as well, even if only a slight one? It's really fascinating to think about how all of this would work.
Very early games had lookup tables for trig functions. The cpu instructions were too slow or missing. The tables were either generated at run time or statically defined in the code.
I think that’s one of those things Jai and Zig agree on - compile time functions have a place in preventing magic numbers that cannot be debugged.
Re: When Greedy Algorithms Can Be Faster [C++]
#7This isn't really what the article is about, but I don't think that the term "Greedy algorithm" means what the author thinks.
Greedy algorithms are about making locally optimal choices.
They are not "brute force" algorithms or inefficient ones.
In fact, greedy algorithms are almost always faster. They are faster because they consider only local information instead of the entire data set. In exchange for that, a greedy algorithm may produce non-optimal answers.
Re: When Greedy Algorithms Can Be Faster [C++]
#8I suspect if you started using SIMD instructions, the analytical case would get better again (since it's branchless).
On GPU, the rejection sampling approach wouldn't come close to analytical one.
Re: When Greedy Algorithms Can Be Faster [C++]
#9I don't know how numerics in hardware works, but would the use of functions like sin, cos, sqrt incur a penalty as well, even if only a slight one? It's really fascinating to think about how all of this would work.
yeah, that's very likely the explanation. All these functions are pretty high latency instructions, vs rejection sampling which only involves a multiplication. On Nvidia GPUs, mul has latency of 1-4 cycles while others are 16-32.
Re: When Greedy Algorithms Can Be Faster [C++]
#10This isn't really what the article is about, but I don't think that the term "Greedy algorithm" means what the author thinks. Greedy algorithms are about making locally optimal choices. They are not "brute force" algorithms or inefficient ones. In fact, greedy algorithms are almost always faster. They are faster because they consider only local information instead of the entire data set. In exchange for that, a greed…
Yeah, greedy is not what he thinks it is.
I think of change making algorithm when working retail. Greedy is you always use the largest coin you can, and then the next largest and so on. It works with sensible coin denominations but there are sets of coins where the greedy algorithm is not optimal.