10 ms·

Torvalds: More bitwise tricks

183 points by SkyMarshal 15y ago

alexbell 15y ago
Login required on my iPhone's browser. Can someone post the contents please?
- hansbo 15y ago
  "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
  - hornd 15y ago
    And #define ONEBYTES 0x0101010101010101ul
  - Jyaif 15y ago
    And the most important part of the post is actually wrong... it should be mask *= ONEBYTES; instead of mask = ONEBYTES;
  - 6ren 15y ago
    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).
  - andrewcooke 15y ago
    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.
Alind 15y ago
why does this guy always behave himself like a god
- skystorm 15y ago
  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?
- zzz90210 15y ago
  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.
  - robryan 15y ago
    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.
    - zzz90210 15y ago
      Yes and I wonder just how interesting this post would have seemed if it was just some schmuck on G+ instead of His Greatness, hmm? The fact that so few comments on this post relate to the subject matter of optimization kind of disproves your point.
- pjscott 15y ago
  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.
chmike 15y ago
Can someone explain the problem he is trying to solve with this piece of code ? I don't understand.
- zokier 15y ago
  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.
Erwin 15y ago
If you like this sort of bit-level puzzles, this is a nice book: http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ 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.
po 15y ago
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.
- gaving 15y ago
  meanwhile everybody awkwardly +1'ing each other
  - henrikschroder 15y ago
    "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.
    - mvc 15y ago
      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.
- Peaker 15y ago
  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.
DiabloD3 15y ago
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)?
Tichy 15y ago
It requires a log in to see?
pbsd 15y ago
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; }
- _sh 15y ago
  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.

183 points by SkyMarshal 15y ago

alexbell 15y ago

hansbo 15y ago
"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
- hornd 15y ago
  And #define ONEBYTES 0x0101010101010101ul
- Jyaif 15y ago
  And the most important part of the post is actually wrong... it should be mask *= ONEBYTES; instead of mask = ONEBYTES;
- 6ren 15y ago
  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).
- andrewcooke 15y ago
  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.

Alind 15y ago

why does this guy always behave himself like a god

skystorm 15y ago
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?
zzz90210 15y ago
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.
- robryan 15y ago
  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.
  - zzz90210 15y ago
    Yes and I wonder just how interesting this post would have seemed if it was just some schmuck on G+ instead of His Greatness, hmm? The fact that so few comments on this post relate to the subject matter of optimization kind of disproves your point.
pjscott 15y ago
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.

chmike 15y ago

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

zokier 15y ago
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.

Erwin 15y ago

If you like this sort of bit-level puzzles, this is a nice book: http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ 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.

po 15y ago

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.

gaving 15y ago
meanwhile everybody awkwardly +1'ing each other
- henrikschroder 15y ago
  "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.
  - mvc 15y ago
    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.
Peaker 15y ago
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.

DiabloD3 15y ago

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)?

Tichy 15y ago

It requires a log in to see?

pbsd 15y ago

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

_sh 15y ago
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.