51–60 of 82 posts
Earlier quoted context omitted.
But they aren't in base 10. The constant mentioned might as well have been put into the code in hex or octal and nothing would have changed. (I don't know whether C support binary constants.)
I didn't write the article; I'm just giving the rationale. You don't need to take it out on me.
Earlier quoted context omitted.
math.log uses floating point arithmetic. That will lead to trouble on large numbers. The article addresses the issue.
I'm not doing power == int(power) though which is what he warns against. I haven't done a lot of testing however as far I can tell it's working. >>> is_power_of_two(2 ** 31 - 1) False >>> is_power_of_two(2 ** 31) True >>> is_power_of_two(2 ** 31 + 1) False >>> is_power_of_two(2 ** 548 - 1) False >>> is_power_of_two(2 ** 548) True >>> is_power_of_two(2 ** 548 + 1) False
For interest rather than practical use: Creating a 2GiB lookup table is ~10% faster on my machine than method #10. That is, faster on the benchmark in the blog post. A 2GiB lookup table is horrible, has a little setup cost dominated by calloc-ing the array, and would trash caches with real code. A also made a solution using a union to split x into two shorts and a 64kiB lookup table that was ~15% slower. For more exp…
(Also, you can shrink the size to 1/8 by just using 1 bit instead of one byte, but that would need some more code of course.)
Edit: You can simulate random access by using a stride great enough to avoid the cache. I guess that would be slightly worse than random, but close enough.
return ((x != 0) && !(x & (x - 1))); This is beautiful.
Most of the solutions explicitly assume 32 bit integers. These days most of us have 64 bit integers available.
For interest rather than practical use: Creating a 2GiB lookup table is ~10% faster on my machine than method #10. That is, faster on the benchmark in the blog post. A 2GiB lookup table is horrible, has a little setup cost dominated by calloc-ing the array, and would trash caches with real code. A also made a solution using a union to split x into two shorts and a 64kiB lookup table that was ~15% slower. For more exp…
On modern-day systems main memory access is much slower than the processor, and on multi-core systems (which are the norm these days, though not all cores are always in use, of course) the memory bus can easily become a bottleneck. Benchmarks tend to hide that fact because they are often run on a single core on an otherwise idle system, so they usually have all memory bandwidth and cache memory to themselves, which isn't really representative of real-world systems.
For that reason, I believe that algorithms that do not depend on fast memory access to work efficiently are preferable to those that make use of large memory caches, at least if the performance difference isn't too great.
For interest rather than practical use: Creating a 2GiB lookup table is ~10% faster on my machine than method #10. That is, faster on the benchmark in the blog post. A 2GiB lookup table is horrible, has a little setup cost dominated by calloc-ing the array, and would trash caches with real code. A also made a solution using a union to split x into two shorts and a 64kiB lookup table that was ~15% slower. For more exp…
How were you accessing the lookup table? In a linear or random way? If you did it in a linear way, locality and prefetching will help performance for your lookup table. The great thing about #9 and #10 is that they are just as fast when the sequence of numbers is random. I know you weren't serious about the 2GiB lookup table, but if a lookup table in general should be used as a baseline, the benchmark should probably…
(Shrinking the lookup table by 1/8, I don't know how to do that fast.)
The annoying thing about lookup tables is that they are hard to benchmark properly. But superficially they often look like a good idea. (Here faster than the fastest reported result, when tested naively.)
(x & (x - 1)) == 0
For interest rather than practical use: Creating a 2GiB lookup table is ~10% faster on my machine than method #10. That is, faster on the benchmark in the blog post. A 2GiB lookup table is horrible, has a little setup cost dominated by calloc-ing the array, and would trash caches with real code. A also made a solution using a union to split x into two shorts and a 64kiB lookup table that was ~15% slower. For more exp…
How were you accessing the lookup table? In a linear or random way? If you did it in a linear way, locality and prefetching will help performance for your lookup table. The great thing about #9 and #10 is that they are just as fast when the sequence of numbers is random. I know you weren't serious about the 2GiB lookup table, but if a lookup table in general should be used as a baseline, the benchmark should probably…
I think a good pattern is to add a large number co-prime to 2^32 on every iteration. That guarantees you actually hit all cache entries, while picking a "round" number like 1024 underutilizes the cache severely, which is unfair if you were trying to simulate random performance.
edit: Actually, in this case it doesn't really matter since your values aren't expected to be in-cache anyway.