4 ms·

This is very long for something that's quite simple: If your input space is small enough that it fits into an 8- or 16-bit LUT, try it. If it's faster, use the

This is very long for something that's quite simple: If your input space is small enough that it fits into an 8- or 16-bit LUT, try it. If it's faster, use the LUT; if it's not, don't use it. Really, that's all that needs to be said. The cases where LUTs this small crop up are so rare that you lose nothing by trying. There's no use in trying to predict the performance when you can just measure it.

remram 3y ago
I agree. Do a benchmark end-to-end. Measuring the lookup alone and theorizing is worth nothing.
nullc 3y ago
One challenge is that the table cutoff size in a microbenchmark will be higher than in an application that has other cache pressure. So for example, you may have a bit of code that is rarely very hot unless you're being DOS attacked. If you are it's performance is limiting for the system, so very important. Otherwise it just runs intermittently. A large table may win in a microbenchmark or under the dos load, but trash the application performance outside of attacks due to flushing out the cache relative to a slower implementation with a smaller table or no table. It's often difficult to measure the overall application performance difference between changes to components (as effects from alignment may dominate). And even if you do know that you have a situation like I described the correct choice isn't always obvious.
- fluoridation 3y ago
  Don't do a microbenchmark, test the entire application under expected usage with and without the LUT. If it's supposed to tolerate a DoS, test that as well. A LUT is a drop-in replacement; there's no need to rely on some synthetic benchmark that may not be representative when you can test on the real thing.
  - Brian_K_White 3y ago
    You can even have the code detect a usage/abusage pattern and switch implementations on the fly.
Brian_K_White 3y ago
Another comment says bit shifting 128 bits, constructed ftom 2 64 bit lut results, still won over a simple division. It's still a simple rule to find out by testing, but the simple rule is not so limited.

remram 3y ago

I agree. Do a benchmark end-to-end. Measuring the lookup alone and theorizing is worth nothing.

nullc 3y ago

One challenge is that the table cutoff size in a microbenchmark will be higher than in an application that has other cache pressure. So for example, you may have a bit of code that is rarely very hot unless you're being DOS attacked. If you are it's performance is limiting for the system, so very important. Otherwise it just runs intermittently. A large table may win in a microbenchmark or under the dos load, but trash the application performance outside of attacks due to flushing out the cache relative to a slower implementation with a smaller table or no table. It's often difficult to measure the overall application performance difference between changes to components (as effects from alignment may dominate). And even if you do know that you have a situation like I described the correct choice isn't always obvious.

fluoridation 3y ago
Don't do a microbenchmark, test the entire application under expected usage with and without the LUT. If it's supposed to tolerate a DoS, test that as well. A LUT is a drop-in replacement; there's no need to rely on some synthetic benchmark that may not be representative when you can test on the real thing.
- Brian_K_White 3y ago
  You can even have the code detect a usage/abusage pattern and switch implementations on the fly.

Brian_K_White 3y ago

Another comment says bit shifting 128 bits, constructed ftom 2 64 bit lut results, still won over a simple division. It's still a simple rule to find out by testing, but the simple rule is not so limited.