Repository navigation
Optimize System.Numerics.BitOperations using arm64 intrinsics #33495
Description
Activity
- changed the title
[-]Optimize System.Numerics.BitOperations[/-][+]Optimize System.Numerics.BitOperations using arm64 intrinsics[/+]on Mar 11, 2020 I was trying to convert
BitOperations.PopCount()method to use Arm64 Intrinsics.PopCountinstruction “cnt” is only available for vector registers and not for scalar registers. Even for vector registers, the argument can only be a vector holding elements of type byte or sbyte. SinceBitOperations.PopCount()APIs takes uint/ulong as argument, here is what we could do:- Move the value of scalar register into a vector register.
- Perform cnt on vector register.
- Move back the result from vector into scalar register.
However since “cnt” only operates on byte/sbyte, I need to use
AddAcrossto accumulate the result of popcount across all lanes. I wrote 2 versions of this logic and both are 6-9X slower than the software fallback we have in place today.
The code, corresponding assembly code and result are present at https://gist.github.com/kunalspathak/398a14edae6367033a6656a8a62c6486Any other suggestion that I can try to optimize PopCount() using arm64 intrinsic or should we stick to software fallback for now?
@TamarChristinaArm @tannergooding @echesakovMSFT
Hm.. here is what clang emits for
__builtin_popcounthttps://godbolt.org/z/JydBtp@kunalspathak yeah unfortunately we do only have popcount on vector registers, but your sequence is correct and should be much faster than the software fallbacks. It looks like the reason it's not is the surrounding code to create and extract the element.
Your second example
Custom2_PopCountseems to be the closest to doing it right butVector64<uint> input = Vector64.CreateScalar(value);should have been converted into a simple
fmovwhere currently you get
D2933D80 movz x0, #0x99ec F2B657E0 movk x0, #0xb2bf LSL #16 F2CFFEE0 movk x0, #0x7ff7 LSL #32 B9400000 ldr w0, [x0] 0E040FE0 dup v0.2s, wzr FD000FA0 str d0, [fp,#24] B9001BA0 str w0, [fp,#24] FD400FA0 ldr d0, [fp,#24] FD0017A0 str d0, [fp,#40] FD4017A0 ldr d0, [fp,#40]That alone looks like it's more expensive than the software fallback. It looks like the JIT doesn't know how to move values between register files if not through memory.
52800000 mov w0, #0 97FFAE89 bl System.Runtime.Intrinsics.Vector64:GetElement(System.Runtime.Intrinsics.Vector64`1[Byte],int):ubyte ;; bbWeight=1 PerfScore 18.00This should have been an
fmovas well. If these are fixed your change should be faster than the fallback. I suspectGetElementis also emitting the same move through memory operations.Perhaps instead of
result = (int)Vector64.GetElement<byte>(added, 0);this works better for the final bits
result = (int)added.ToScalar();Vector64 input = Vector64.CreateScalar(value);
should have been converted into a simple fmovThis is tracked by #33496 and should likely be resolved before moving forward on the other items so we don't accidentally skew benchmark numbers due to inefficient create methods.
Reacted by Tamar ChristinaThanks @TamarChristinaArm for the insights. Yes,
CreateScalaris something to be done as part of #33496 but I was not sure how much perf gain it would give. I will work on that API first to see gains forPopCount. Also, didn't noticeToScalar(). The code looks simpler but it doesn't make much perf impact. I will get back to it after convertingCreateScalar().Hm.. here is what clang emits for
__builtin_popcounthttps://godbolt.org/z/JydBtpThanks for reminding me of godbolt @EgorBo . I keep forgetting that I can verify the code generated by others. :)
- ghost locked as resolved and limited conversation to collaborators
on Dec 10, 2020
This item tracks the conversion of the System.Numerics.BitOperations class to use arm64 intrinsics.
Related: #33308