When Greedy Algorithms Can Be Faster [C++]

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.

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.

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.

I think I would call it naive algorithm rather than greedy.

It looked like an interesting problem so I spent some time this morning exploring if there would be any performance improvement by pregenerating an array of X items (where X around 1M to 16M items) and then randomly returning one of them at a time. I explored the project and copied the functions to be as faithful as the original implementation as possible.

Generating 10M unit sphere (best of 3 runs, g++ 13, linux, Intel i7-8565U, one core for tests):

  - naive/rejection: ~574ms
  - analytical: ~1122ms
  - pregen 1M elements: ~96ms

After looking at those results I decided to try on the project itself, so I downloaded, compiled and applied similar optimizations in the project, only updating circle and sphere random generators (with 16M unit vectors that are only created once on app lifetime) but got almost no noticeable benefits (marginal at most). Hard to tell because of the random nature of the raytracing implementation. On the bright side the image quality was on par. Honestly I was afraid this method would generate poor visuals.

Just for the record, I'm talking about something as simple as:

  std::vector<Vec3> g_unitSpherePregen;
  uint32_t g_unitSpherePregenIndex = 0;

  void setupUnitSpherePregen(uint32_t nElements) {
    g_unitSpherePregen.resize(nElements);
    for (auto i = 0; i < nElements; i++) {
      g_unitSpherePregen[i] = unitSphereNaive();  // call the original naive or analytical method
    }
  }

  Vec3 unitSpherePregen() {
    g_unitSpherePregenIndex = (g_unitSpherePregenIndex + 1) % g_unitSpherePregen.size();
    return g_unitSpherePregen[g_unitSpherePregenIndex];
  }
 

Next step would be profiling, but I don't think I will invest more time on this.

Edit: fix formatting

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...

I suspect if you started using SIMD instructions, the analytical case would get better again (since it's branchless).

Isn't there a likely faster analytical solution? At least I think sqrt, sin, and cos are generally considered to be slow.

Maybe this:

1. Generate random X [-1 to 1]

2. Based on X you can calculate a range of legal Y that will still fall within the circle. Try to use a lookup table+interpolation with desired resolution to make this really fast if there's not some sufficiently fast hardware instructions we can abuse.

3. Generate random Y in that range.