Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Torvalds: More bitwise tricks

plus.google.com

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Torvalds: More bitwise tricks

#31

Post by diminish »

po wrote: post #30
diminish wrote: post #27

Earlier quoted context omitted.

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 worki…

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 comment…

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.

Re: Torvalds: More bitwise tricks

#32

Post by andrewcooke »

hansbo wrote: post #3
alexbell wrote: post #2

Login required on my iPhone's browser. Can someone post the contents please?

"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 kil…

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.

Re: Torvalds: More bitwise tricks

#33

Post by mvc »

henrikschroder wrote: post #23
gaving wrote: post #22

Earlier quoted context omitted.

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.

Re: Torvalds: More bitwise tricks

#34

Post by pbsd »

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;
  }

Re: Torvalds: More bitwise tricks

#35

Post by _sh »

pbsd wrote: post #34

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.

Re: Torvalds: More bitwise tricks

#36

Post by po »

diminish wrote: post #31
po wrote: post #30

Earlier quoted context omitted.

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 comment…

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.

Re: Torvalds: More bitwise tricks

#37

Post by acqq »

po wrote: post #20

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 t…

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

Post reply on HN