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

1–10 of 37 posts

Re: Torvalds: More bitwise tricks

#3

Post by hansbo »

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

Re: Torvalds: More bitwise tricks

#4

Post by hornd »

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…

And

#define ONEBYTES 0x0101010101010101ul

Re: Torvalds: More bitwise tricks

#5

Post by Jyaif »

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…

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

Re: Torvalds: More bitwise tricks

#6

Post by 6ren »

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…

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

Re: Torvalds: More bitwise tricks

#9

Post by zzz90210 »

Alind wrote: post #7

why does this guy always behave himself like a god

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.

Re: Torvalds: More bitwise tricks

#10

Post by pjscott »

Alind wrote: post #7

why does this guy always behave himself like a god

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 , please check to make sure it actually applies to the situation.

Post reply on HN