-
Notifications
You must be signed in to change notification settings - Fork 30
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Lzct SSE instruction when available #42
Comments
Couldn't that class be written like this: internal static class Bitwise {
private static readonly int[] Lookup;
static Bitwise()
{
Lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
Lookup[i] = (int)(Math.Log(i) / Math.Log(2));
}
}
public static int NumberOfLeadingZeros(ulong value)
{
if (value < uint.MaxValue)
return 63 - Log2((uint)value);
return 31 - Log2((uint)(value>>32));
}
private static int Log2(uint i)
{
if (i >= 0x1000000) { return Lookup[i >> 24] + 24; }
if (i >= 0x10000) { return Lookup[i >> 16] + 16; }
if (i >= 0x100) { return Lookup[i >> 8] + 8; }
return Lookup[i];
}
} or inlined: internal static class Bitwise
{
private static readonly int[] Lookup;
static Bitwise()
{
Lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
Lookup[i] = (int)(Math.Log(i) / Math.Log(2));
}
}
public static int NumberOfLeadingZeros(ulong value)
{
if (value >= 0x100000000000000) { return 7 - Lookup[value >> 56]; }
if (value >= 0x1000000000000) { return 15 - Lookup[value >> 48]; }
if (value >= 0x10000000000) { return 23 - Lookup[value >> 40]; }
if (value >= 0x100000000) { return 31 - Lookup[value >> 32]; }
if (value >= 0x1000000) { return 39 - Lookup[value >> 24]; }
if (value >= 0x10000) { return 47 - Lookup[value >> 16]; }
if (value >= 0x100) { return 56 - Lookup[value >> 8]; }
return 63 - Lookup[value];
}
} I don't have any profiling (or for that matter any stake in this project at all, I was searching for this particular function) but it seems odd that these functions are operating on signed values and that the impl for |
Thanks for the interest and contribution @bbarry . Personally I am not a bit-fiddler magician, I am just leaning on the contributions from Gil and people like yourself. |
Some quick feedback. Updating the proposed code to use For 64bit values:
Note that on LegacyJit it sneaks ahead of the current implementation (but still comes 3rd to some other implementations). For predominantly 32 bit values (which in this libraries case are the more performance sensitive values):
Again we see that it is 5%, 38% and 90% slower than the current implementation. I hope you find this valuable. |
It appears that this functionality has been merged to |
We currently have at the heart of the hot path a manual method for find the leading zero count.
This is used to identify the correct bucket to assign a recorded value.
Frustratingly, this is supported as an intrinsic instruction on most modern CPU architectures.
The code is found in
Bitwise.NumberOfLeadingZeros
, and has been isolated with the intent that it can be a single place to refactor/optimize if the opportunity arises.Follow this .NET core issue for progress/resolution
The text was updated successfully, but these errors were encountered: