BitOperations.PopCount 是在 .NET 中计算 BitArray 基数的最佳方式吗?

Question

.NET 中的Numerics.BitOperations.PopCount是我所知道的计算组成 int 的位数的最快方法。但是，我还没有看到有人使用它来计算System.Collections.BitArray对象中设置的位数(例如：计算 .Net BitArray 类中设置的位数)。

使用以下C++代码为例：

#include <iostream>
#include <bitset>
using namespace std;
int main() {
bitset<500000000> visited;
long limit = 500000000;
for (long x=0; x < limit; x++) {
visited[x] = true;
}
cout << visited.count() << endl;
}

运行时间： 0.36 真实 0.34 用户 0.02 系统

这是我在 F# 中的最佳尝试：

open System
open System.Numerics
let limit = 500000000
let visited = Collections.BitArray(limit)
for x in 0..limit-1 do
visited.[x] <- true
let ints = Array.create ((visited.Count >>> 5) + 1) 0u
visited.CopyTo(ints, 0)
ints
|> Array.map BitOperations.PopCount
|> Array.reduce Operators.(+) 
|> printfn "%d"

运行时间： 1.53 真实 1.47 用户 0.06 系统

是否可以改进 .NET 版本以更好地匹配C++实现？

更新

仅与计数部分进行比较并使用for循环更改高级功能，将差距从C++快 4 倍增加到快 5 倍。

open System
open System.Numerics
let limit = 500000000
let visited = Collections.BitArray(limit)
visited.[9999999] <- true
let ints = Array.create ((visited.Count >>> 5) + 1) 0u
visited.CopyTo(ints, 0)
let mutable total = 0
for i in ints do
total <- Operators.(+) total (BitOperations.PopCount(i)) 
printfn "%d" total

运行时间： 0.21 真实 0.15 用户 0.06 系统

#include <iostream>
#include <bitset>
using namespace std;
int main() {
bitset<500000000> visited;
visited[9999999] = true;
cout << visited.count() << endl;
}

运行时间： 0.04 真实 0.02 用户 0.02 系统

更新 2

将BitArray替换为uint32 array可将性能从比位集慢 5 倍提高到 4 倍C++：

open System.Numerics
let limit = 500000000 >>> 5
let visited = Array.create (limit + 1) 0u
visited.[9999999] <- uint 0b00100000
let mutable total = 0
for i in visited do
total <- Operators.(+) total (BitOperations.PopCount(i)) 
printfn "%d" total

运行时间： 0.15 真实 0.12 用户 0.03 系统

Answer 1

在必须使用BitArray的限制下，BitOperations.PopCount似乎是最好的选择：

open System
open System.Numerics
let limit = 500000000
let bitArray = Collections.BitArray(limit)
bitArray.[9999999] <- true
let ints = Array.create ((bitArray.Count >>> 5) + 1) 0u
bitArray.CopyTo(ints, 0)
ints
|> Array.sumBy BitOperations.PopCount
|> printfn "%d"

运行时间： 0.20 真实 0.15 用户 0.05 系统

从那里开始，下一步是将BitArray替换为uint[]如@nicomp所示。