Torvalds: More bitwise tricks | Hacker News Reader

Torvalds: More bitwise tricks

plus.google.com

183 pointsSkyMarshal35 comments

Google Plus is still a very strange place.

Here you have an exceedingly technical thread with some of OSS brightest minds working on a little puzzle and it's interspersed with litter. You have the sincere (yet misplaced) thank you for working on OSS, the clueless guy, and the isn't it cool we're talking about such hardcore topics guy. Every one of those comments makes me cringe a little.

This is why geeks have yet to give up mailing lists. The hurdle they put up is actually an effective barrier for the unmotivated. Some conversations are meant to be had in a quiet place amongst people who are similarly inclined. Google misleads you into thinking that Plus is that place, but it just isn't. Perhaps if there was a way for the community to sort the relevant from the irrelevant, it's just too tempting of a megaphone for people to jump in front of. Sometimes adding a little friction to the 'Post' button is a good thing.

meanwhile everybody awkwardly +1'ing each other

"Its things like this that make me realize how little I really know.." +8

The people who +1 stuff aren't the ones that understand the discussion, and the ones that do understand it don't +1, because why would they, it's obvious by reading the comments which ones are good and which ones are bad... It's a fantastic culture clash.

I don't know because I don't have the same problems (I make few posts on Google+ and receive even fewer comments when I do), but presumably, all the smart guys and girls already have each other circled and just ignore all the spam. I can't imagine Linus would even use Google+ if there wasn't an easy method of filtering the wheat from the chaff.

Linus knows exactly what kind of comments it will get.

So either he doesn't care about the comments at all, or he is fishing for these exact pats on the back.

Or he naively thought the signal to noise ratio would be higher.

An open discussion on a very low level technical implementation with a heterogeneous crowd on Google+ seems to be the dawn of a new era; open source programming becomes public in full sunlight the same way books or mathematics became public after the invention of the printing. Compare it to mailing lists or earlier forms of engineering discussions behind closed doors. Many outsiders all around the world are now working hard on sunday learning C or with their gcc compilers trying to solve Linus's bitwise calculation optimisation problem and they previously had nothing to do with kernel programming. Their results may go into the next Linux kernel release and that is exciting for a puzzle.

and as opposed to you I find this to be a nice thing for everyone++ to be invited to think Linus's question on Google+ (which is better than facebook or linked in or pinterest for this purpose)

'...so it's not a generic "count number of bits" (or even a generic "count number of bytes"). So I was hoping somebody would come up with something simple like (x & mask1) + (x&mask2)>>shift that just got the four possibilities right.'

I love that Linus does his thinking out in the public, but that's nothing new. Google Plus isn't enabling anything that he didn't do before, it's just being exposed to a new audience. Frankly, I love that this new audience is seeing his writing. I love being able to watch smart people doing their thing and I hope they inspire others.

But, I'm afraid you you've totally missed my point. What I don't love is the commentary being mixed in with the game. This is why when you have a panel discussion, you don't hand a microphone to everyone in the auditorium. When you go to a concert, you don't hand everyone an instrument. People have varying levels of contextual awareness and/or self control: it's not really their fault for throwing in their $0.02. I'm just pointing out that Google Plus is a type of forum and I'm still not sure what kind of conversation is supposed to go on there. This kind of discussion feels unnatural to me.

yes i agree about g+, though i feel the same about facebook, linked in and disqus about any type of discussion. only on HN; i mostly feel "these are the right people here answering"

what linus does is more like an experiment, not on what g+ is but on what it can become. i pray the experiment will be successful, but i think i wont.

Nobody tries to have these kinds of discussions on Facebook because it's obviously the wrong place (my mom doesn't care what I think of bit-shifting). Disqus is fine because it's in the context of the blog post. People have to seek it out. Twitter is fine because conversations are not globally visible, they are filtered by @replies to relevant parties.

Google Plus was seeded with Google employees and they are the most enthusiastic users so it is filled with these kinds of discussions.

He was aware of the "other" public: his post with the picture of his cat got more "upvotes" than anything before:

https://plus.google.com/102150693225130002912/posts/Uk1YxfFD...

If you like this sort of bit-level puzzles, this is a nice book: http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201... -- probably the only book at such a low level I remember buying in many years.

Can someone explain the problem he is trying to solve with this piece of code ? I don't understand.

    no bytes: 00000000 -> 0
    one byte: 000000ff -> 1
    two bytes: 0000ffff -> 2
    three bytes: 00ffffff -> 3

I think that is what he is trying to accomplish.

"More bitwise tricks..

So my quest to calculate the hash and the length of a pathname component efficiently continues. I'm pretty happy with where I am now (some changes to the code have happened, it you actually want to see the current situation you need to check out the kernel mailing list post), but finding the number of bytes in the final mask bothers me.

Using an explicit loop is out - the branch mispredicts kill it. And while at least modern Intel CPU's do quite well with just using the bit scan instructions ("bsf") to find where the first NUL or '/' was in the word, that sucks on some older CPU's.

So I came up with the following trick to count the number of bytes set in the byte mask:

  /* Low bits set in each byte we used as a mask */
  mask &= ONEBYTES;
  /* Add up "mask + (mask<<8) + (mask<<16) +... ":
  same as a multiply */
  mask *= ONEBYTES;
  /* High byte now contains count of bits set */
  len += mask >> 8*(sizeof(unsigned long)-1);

and I'm wondering if anybody can come up with something that avoids the need for that multiply (and again - conditionals don't work, the mispredict costs kill you).

Because that multiply isn't free either."

EDIT: Thanks for the tips, I'm new here

And

#define ONEBYTES 0x0101010101010101ul

And the most important part of the post is actually wrong... it should be mask *= ONEBYTES; instead of mask = ONEBYTES;

The * have gone away (HN is treating it as markdown for italics). You can put spaces around it to prevent this (e.g. the first * in the first comment is treated literally; the last * in that comment isn't).

The easiest solution is to indent the code by two spaces (HN renders it literally then).

also, for the original asker - most of the interesting part is in the technical discussion (and the culture clash described elsewhere) that is in the answers.

It requires a log in to see?

Quickest way (without multiplication) is divide and conquer, just like the usual bit popcount:

  static inline int f(const u64 m)
  {
    const u64 ones = 0x0101010101010101ULL;
    const u64 b64 = m & ones;
    const u32 b32 = b64 + (b64>>32);
    const u16 b16 = b32 + (b32>>16);
    const  u8  b8 = b16 + (b16>> 8);
    return b8;
  }

But this is slower than with multiplication, as Linus explains:

  the simple shift+add version is all totally serialized
  and nothing can be done before the previous operation
  ends: as a result the three adds and three shifts will
  inevitably take 6 cycles (the original P4 had that 
  double-pumped ALU, but not for shifts). That's already
  slower than almost any multiply.

Edit: oops, I forgot your '(without multiplication)' qualifier. Yes, your way is likely the quickest without multiplication.

I'm not sure if I understand the problem. Without a loop, is he only counting a fixed number of bytes (ie, 4 or 8 maximum)?

why does this guy always behave himself like a god

I am aware that Linus has that reputation, but glancing over the post and comments, it seemed like a good, factual discussion in this case. Did I miss something?

Wrong question. Why does everyone else elevate the most mundane aspects of his daily musings into the words of God?

I dont think he asked for this post to be put on the front page of HN, and he is probably laughing about it right now.

Why? I'd say we find optimisation tricks quiet interesting here. I barely saw any sucking up or worshipping in the thread, it was mostly on topic.

Gods behave in many ways. Some are jealous and quick to anger, and others are inhumanly patient. Some forbid alcohol to their followers, and others get drunk and beat up giants. Some descent to earth in the form of a bull to conduct illicit sexual liaisons with mortals, and others lack reproductive organs altogether. However, without exception, one thing they all have in common is that they never conduct polite discussions of bitwise arithmetic tricks. And yet that is exactly what I see here.

Next time you decide to #include <linus/stdflame.h>, please check to make sure it actually applies to the situation.

> "Next time you decide to #include <linus/stdflame.h>"

... give me a break.

What is annoying about this comment is that it compels me to go back and read every other comment you've written. Please write less gracefully next time.

Nice illustration of the problems associated with naive Bayesian classifiers.

So in which verse in the bible they talk about bitwise tricks?

Mathew 5:37

Because there exist fools who bow to every word they say.

Reply on news.ycombinator.com