Hacker News Reader

lambda_cubeon Ten Ways to Check if an Integer Is a Power Of Two in C

Nice to see some experimentation. :)

I tested all 2^31 non-negative integers, which is 2147483648 values. If I remember correctly, the value that was wrong was large, probably between 2^30 and 2^31. Java is pretty fast and I think this took tens of minutes. Python is about 20 times slower so it may take hours for you.

lambda_cubeon Ten Ways to Check if an Integer Is a Power Of Two in C

> I was doing a linear scan, and I know that that is artificial.

May be artificial :). Don't forget that your application is the best benchmark. If it uses linear access you can take advantage of that. Let's just say that linear access is a special case and random access is a worst case result. The behavior of the random access is the one to remember, IMO.

> Shrinking the lookup table by 1/8, I don't know how to do that fast.

Here is how I do bit vectors. I'm not suggesting that anyone should use a lookup table for this problem since there are very fast solutions that uses O(1) memory, but let's use this as an example since we're all familiar with it.

Since you mention a 2GiB table I guess you use a byte vector. The article uses an unsigned int as the type for the argument which would need 4GiB for all values, I guess you used int instead. We want to use every bit of memory in an array to store boolean flags. It's probably faster to use the native word size of the machine than to use byte size elements, so let's use unsigned int. I assume that we use a 32-bit machine, just like in the article. If you have a 64-bit machine it will be obvious what to change.

We need 2^31 bits (1 << 31 in C), unsigned int is 32 bits and 32 is 2^5 so we need 2^31/2^5 = 2^26 elements.

When looking up things in a bit vector we need to find the right element in the array and the right bit in the array element that holds the boolean flag. To find the right element we divide the input by the number of bits in each element. To find the right bit we do mod (%) by the number of bits in each element and then shift a bit flag by that amount and AND (&) with the array element.

  unsigned table[1 << 26];
  unsigned is_power_of_two(int x)
  {
      if (x > 0) {
          return table[x / 32] & (1 << (x % 32));
      } else {
          return 0;
      }
  }

Since the constant 32 is a power of two, a good C compiler will change the divide and modulo operations to shift and AND. If you use some other language and/or your compiler doesn't optimize that you may want to do that optimization by hand. x / 32 == x >> 5, if x >= 0. x % 32 == x & 31, if x >= 0. NB: It's not that simple for negative numbers!

The lookup table must be populated before use of course, that is left as an exercise for the reader ;-).

(imurray, if you think I explained things you already know, I did it for other readers.)

> The annoying thing about lookup tables is that they are hard to benchmark properly.

If you want some general rule: If you can get the table small, lookup tables are fast, sometimes the fastest solution. But maybe you're application (not an artificial benchmark) doesn't use the function very often and the table won't be in the cache. Then the computation have to slower than fetching memory with a cache miss for the lookup table to be worth it. Also, memory bandwith has been a bottleneck for a long time and it will get even worse. This diminishes the value of lookup tables and trading memory for computation time. As always when it comes to performance and optimizations: benchmark your application with your data. General results may or may not apply in your context.

Edit: If you want the answer to always come out as 0 for false and 1 for true, you can do this instead:

  return (table[x / 32] >> (x % 32)) & 1;

lambda_cubeon Ten Ways to Check if an Integer Is a Power Of Two in C

Thank you for that little trick. Even if it doesn't matter for this case I will remember it for later. I know I've read stuff like that before, but I haven't learned enough of that part of discrete math to really understand why (but it seems kind of intuitive).

As a coincidence I got "A Concrete Introduction to Higher Algebra" by Lindsay Childs in the mail today. The concrete part of the book is that he uses properties about integers to introduce and teach concepts about algebra (and then he goes on to polynomials and other stuff). So now I got no excuse to not know that stuff any longer :-).

lambda_cubeon Ten Ways to Check if an Integer Is a Power Of Two in C

Yes, but the two best solutions don't. The other solutions are mostly for educational purposes, I guess. One of #9 or #10 is the one that should be in some utility library.

lambda_cubeon Ten Ways to Check if an Integer Is a Power Of Two in C

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 use random access. Do you agree? (Special applications could use a linear access pattern, of course.)

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

lambda_cubeon Ten Ways to Check if an Integer Is a Power Of Two in C

This will probably give the wrong answer for some integer. I have tried something similar in Java. Since it was three years ago my memory is a little hazy. I was working on a parallelizing compiler written in Java (but not for Java) and I saw that the other programmers had used a method similar to yours, it used log anyway. I knew about #9 and #10 and worried that their method was potentially wrong (and also inefficient). To check if it was wrong I coded up something that compared the log-floating point method against #10 for all non-negative integers and the log-floating point method gave the wrong answer for one value (out of 2 billion).

That was Java and your example is in Python, there could be some difference. If you try and compare in Python, please tell us the result.

lambda_cubeon Last.fm web site primary and failover down

> if I didn't read Hacker News I'd be sitting there hitting refresh a bunch of times

Then I know some things that may help you in the future. At the bottom of almost every page at Last.fm there four columns of links. In the column named "Get Help" there is a link that says "System Status" which goes to: http://status.last.fm/ where you can see how different parts of the site are running and a short explanation if there is a problem. I've never seen the system status page go down, even when there are problems on other parts of the site.

One time when Last.fm had some problem the links at the bottom of the page went away. Since then I find it handy to have a bookmark to the system status page.

Another thing to check are the forums (I wanna say fora :-), especially the Web Site Support forum: http://www.last.fm/forum/21713 . Usually the users of the site notice problems before explanations go up at the system status page and someone asks a question what is going on. The staff usually answers, explain what is going on and sometimes say an estimate of when the problem will be solved. In short, there are more details in the web site support forum than on the system status page.

Hope this helps. :-)

lambda_cubeon Bored People Quit

Sure, all managers answer to another manager, except the CEO. But it's also normal to delegate responsibility when it comes to hiring and working assignments in projects. If you're sufficiently high up in the manager hierarchy (which shouldn't be that high up IMO), you should have the power to make decisions like that.

lambda_cubeon Why perl has separate arrays and hashes: It's as if they thought it through

I thought that was deprecated a long time ago. When I learned Perl in 2000 I remember I read not to use that "feature". Apparently it was just not recommended, for a very long time.

lambda_cubeon Why perl has separate arrays and hashes: It's as if they thought it through

The point of preserving insertion order is not to be able to treat hashes as arrays. It's to get deterministic and repeatable iteration order between different runs. Java has LinkedHashMap and LinkedHashSet if you care about iteration order and HashMap and HashSet if you don't.

With the repeatability it's easier to write automatic tests.

I worked at a company making a compiler in Java and we got different binaries when compiling without changing the source code. After we changed to LinkedHashMap and LinkedHashSet that problem was gone. That's an example where we wanted the deterministic aspect of the Linked versions.

Another way to get the same behavior in Java is to use TreeMap and TreeSet, but that only works if the things you put in are comparable, and you get different time complexities as well.

lambda_cubeon Mozilla VP Mike Shaver responds to Microsoft's WebGL security concerns

ATI and NVidia surely cares about driver stability. Who would buy their graphics cards if the games kept crashing all the time?

ATI and NVidia didn't have to care about security before, since the only applications that could access the drivers and graphics cards were trusted applications. Now we have a new situation where they they have to start to care about security. I don't think AMD or NVidia want to be blacklisted in WebGL implementations because their driver isn't secure enough.