[HN Gopher] When Greedy Algorithms Can Be Faster [C++]
___________________________________________________________________
When Greedy Algorithms Can Be Faster [C++]
Author : def-pri-pub
Score : 44 points
Date : 2025-01-28 16:06 UTC (3 days ago)
(HTM) web link (16bpp.net)
(TXT) w3m dump (16bpp.net)
| cozzyd wrote:
| I suspect if you started using SIMD instructions, the analytical
| case would get better again (since it's branchless).
| nxobject wrote:
| 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.
| Sesse__ wrote:
| Ten years ago, you already have Skylake with pretty good
| indirect branch predictors...
| shihab wrote:
| On GPU, the rejection sampling approach wouldn't come close to
| analytical one.
| nxobject wrote:
| I 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.
| hinkley wrote:
| 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.
| shihab wrote:
| 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.
| akoboldfrying wrote:
| Yes, and at least for sqrt(), internally it's likely
| implemented as a heuristic guess followed by a fixed number of
| iterations of Newton's Method. (In software, you'd normally
| iterate Newton's Method until the change in the result is less
| than some threshold; in hardware, I'm guessing that it might be
| simpler to figure out the maximum number of iterations that
| would ever be needed for any input, and always run that many,
| but I don't know.)
| Const-me wrote:
| > at least for sqrt(), internally it's likely implemented as
| a heuristic guess
|
| Square roots are implemented in hardware:
| https://www.felixcloutier.com/x86/sqrtsd
|
| > In software, you'd normally iterate Newton's Method
|
| Software normally computes trigonometric functions (and other
| complicated ones like exponents and std::erf) with a high-
| degree polynomial approximation.
| adgjlsfhk1 wrote:
| sqrt is the one exception to this. the newton series is
| really good and the polynomials aren't great (and the
| newton based approach prevents you from having to do range
| reduction)
| Negitivefrags wrote:
| This 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.
| adamgordonbell wrote:
| 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.
| o11c wrote:
| Relevant link: https://en.wikipedia.org/wiki/Change-
| making_problem
|
| Looking at cases where greedy isn't optimal, I see two
| patterns. Either:
|
| * there are two coins close in value (ratio of less than 2),
| e.g. both 20C/ and 25C/; or
|
| * there is a "missing" coin at the GCD of two larger coins.
|
| I'm pretty sure you can precompute extra "virtual coins"
| (e.g. 40C/) to make greedy optimal again, but you have to
| place restrictions on how many of them you're allowed to use.
| Labo333 wrote:
| To accelerate the analytical solution, there are more obvious
| techniques, like replacing trigonometric opetations with series.
| This is a 10x improvement in
| https://ashvardanian.com/posts/google-benchmark/#slow-trigon...
| emtel wrote:
| I'm surprised they didn't mention the reason that the rejection
| sampling method is surprisingly fast: the probability of needing
| to resample N times decreases exponentially with N. So even for
| the 3D case, where 50% of your samples get rejected, the EV for
| number of samples required is about 2.
|
| This is also a good case study on the difference between
| throughput sensitive vs latency sensitive applications. The
| rejection sampling is fast on average, but the analytical
| solution likely has a much tighter upper bound on how long it can
| take. In a throughput application you care about EV. But if you
| need to minimize latency, then you care about the upper bound.
___________________________________________________________________
(page generated 2025-02-01 08:01 UTC)