From 92f2d6880204666b2e4c786108eaf8a7432a4279 Mon Sep 17 00:00:00 2001 From: Brent Pedersen Date: Mon, 9 Sep 2019 14:04:28 -0600 Subject: count 64 bits at a time --- lib/system/sets.nim | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) (limited to 'lib/system/sets.nim') diff --git a/lib/system/sets.nim b/lib/system/sets.nim index e48484da7..fe7df053d 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,10 @@ 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.. Date: Mon, 9 Sep 2019 20:20:35 -0600 Subject: spacing --- lib/system/sets.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/system/sets.nim') diff --git a/lib/system/sets.nim b/lib/system/sets.nim index fe7df053d..ea92c3ca3 100644 --- a/lib/system/sets.nim +++ b/lib/system/sets.nim @@ -35,5 +35,5 @@ proc cardSet(s: NimSet, len: int): int {.compilerproc, inline.} = inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) j = i + 7 - for i in (j+1).. Date: Wed, 11 Sep 2019 08:35:44 -0600 Subject: only do 64bts on x86 --- lib/system/sets.nim | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'lib/system/sets.nim') diff --git a/lib/system/sets.nim b/lib/system/sets.nim index ea92c3ca3..4835bef1e 100644 --- a/lib/system/sets.nim +++ b/lib/system/sets.nim @@ -31,9 +31,10 @@ proc countBits64(n: uint64): int {.compilerproc, inline.} = proc cardSet(s: NimSet, len: int): int {.compilerproc, inline.} = var j = -1 - for i in countup(0, len - 8, 8): - inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) - j = i + 7 + when defined(x86): + for i in countup(0, len - 8, 8): + inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) + j = i + 7 for i in (j + 1) ..< len: inc(result, countBits32(uint32(s[i]))) -- cgit 1.4.1-2-gfad0 From 944bab4c3c19ffd45eb5cb7c49f87a853c0cdcac Mon Sep 17 00:00:00 2001 From: Brent Pedersen Date: Wed, 11 Sep 2019 08:39:33 -0600 Subject: add amd64 --- lib/system/sets.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/system/sets.nim') diff --git a/lib/system/sets.nim b/lib/system/sets.nim index 4835bef1e..83d18e546 100644 --- a/lib/system/sets.nim +++ b/lib/system/sets.nim @@ -31,7 +31,7 @@ proc countBits64(n: uint64): int {.compilerproc, inline.} = proc cardSet(s: NimSet, len: int): int {.compilerproc, inline.} = var j = -1 - when defined(x86): + when defined(x86) or defined(amd64): for i in countup(0, len - 8, 8): inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) j = i + 7 -- cgit 1.4.1-2-gfad0 From 5b923cd149607bc91c94ac0b9191f02792de5395 Mon Sep 17 00:00:00 2001 From: Brent Pedersen Date: Wed, 11 Sep 2019 15:40:34 -0600 Subject: use while --- lib/system/sets.nim | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'lib/system/sets.nim') diff --git a/lib/system/sets.nim b/lib/system/sets.nim index 83d18e546..39f7d474f 100644 --- a/lib/system/sets.nim +++ b/lib/system/sets.nim @@ -30,11 +30,12 @@ proc countBits64(n: uint64): int {.compilerproc, inline.} = result = ((v * 0x0101010101010101'u64) shr 56'u64).int proc cardSet(s: NimSet, len: int): int {.compilerproc, inline.} = - var j = -1 + var i = 0 when defined(x86) or defined(amd64): - for i in countup(0, len - 8, 8): + while i < len - 8: inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) - j = i + 7 + inc(i, 8) - for i in (j + 1) ..< len: + while i < len: inc(result, countBits32(uint32(s[i]))) + inc(i, 1) -- cgit 1.4.1-2-gfad0