diff options
| author | Andreas Rumpf <rumpf_a@web.de> | 2019-09-12 08:20:53 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2019-09-12 08:20:53 +0200 |
| commit | eb241f424134ff2174dc9b9e2a9e76ef9def7027 (patch) | |
| tree | 563f1dcc4d39f86b6ef59006fe94b4eb8ca64613 /lib/system/sets.nim | |
| parent | ca7bf3be8b5641716b9c9e75b0fdca9ca308c0e0 (diff) | |
| parent | 5b923cd149607bc91c94ac0b9191f02792de5395 (diff) | |
| download | Nim-eb241f424134ff2174dc9b9e2a9e76ef9def7027.tar.gz | |
count 64 bits at a time instead of 8 (#12159)
* count 64 bits at a time * spacing * only do 64bts on x86 * add amd64 * use while
Diffstat (limited to 'lib/system/sets.nim')
| -rw-r--r-- | lib/system/sets.nim | 12 |
1 files changed, 9 insertions, 3 deletions
diff --git a/lib/system/sets.nim b/lib/system/sets.nim index e48484da7..39f7d474f 100644 --- a/lib/system/sets.nim +++ b/lib/system/sets.nim @@ -21,7 +21,7 @@ proc countBits32(n: uint32): int {.compilerproc.} = v = (v and 0x33333333) + ((v shr 2) and 0x33333333) result = (((v + (v shr 4) and 0xF0F0F0F) * 0x1010101) shr 24).int -proc countBits64(n: uint64): int {.compilerproc.} = +proc countBits64(n: uint64): int {.compilerproc, inline.} = # generic formula is from: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel var v = uint64(n) v = v - ((v shr 1'u64) and 0x5555555555555555'u64) @@ -30,6 +30,12 @@ proc countBits64(n: uint64): int {.compilerproc.} = result = ((v * 0x0101010101010101'u64) shr 56'u64).int proc cardSet(s: NimSet, len: int): int {.compilerproc, inline.} = - for i in 0..<len: - if likely(s[i] == 0): continue + var i = 0 + when defined(x86) or defined(amd64): + while i < len - 8: + inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) + inc(i, 8) + + while i < len: inc(result, countBits32(uint32(s[i]))) + inc(i, 1) |