[HN Gopher] When Greedy Algorithms Can Be Faster [C++]
       ___________________________________________________________________
        
       When Greedy Algorithms Can Be Faster [C++]
        
       Author : def-pri-pub
       Score  : 20 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...
        
       | 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.
        
       ___________________________________________________________________
       (page generated 2025-01-31 23:00 UTC)