lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nightowl...@apache.org
Subject [lucenenet] 07/07: Lucene.Net.Support.BitArrayExtensions::Cardinality(): Replaced implementation with one that benchmarked more than 3x faster, at the cost of a small amount of RAM
Date Sun, 15 Dec 2019 11:44:56 GMT
This is an automated email from the ASF dual-hosted git repository.

nightowl888 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucenenet.git

commit 85f824c6323d843af3d5136d4aaff3fdeafb439a
Author: Shad Storhaug <shad@shadstorhaug.com>
AuthorDate: Sat Dec 14 18:10:06 2019 +0700

    Lucene.Net.Support.BitArrayExtensions::Cardinality(): Replaced implementation with one
that benchmarked more than 3x faster, at the cost of a small amount of RAM
---
 src/Lucene.Net/Support/BitArrayExtensions.cs | 36 +++++++++++++++++++++++++---
 1 file changed, 33 insertions(+), 3 deletions(-)

diff --git a/src/Lucene.Net/Support/BitArrayExtensions.cs b/src/Lucene.Net/Support/BitArrayExtensions.cs
index 21e322d..e9c36c1 100644
--- a/src/Lucene.Net/Support/BitArrayExtensions.cs
+++ b/src/Lucene.Net/Support/BitArrayExtensions.cs
@@ -143,18 +143,48 @@ namespace Lucene.Net.Support
         }
 
         /// <summary>
-        /// Returns the number of bits set to true in this BitSet.
+        /// Returns the number of bits set to <c>true</c> in this <see cref="BitArray"/>.
         /// </summary>
-        /// <param name="bits">The BitArray object.</param>
-        /// <returns>The number of bits set to true in this BitSet.</returns>
+        /// <param name="bits">This <see cref="BitArray"/>.</param>
+        /// <returns>The number of bits set to true in this <see cref="BitArray"/>.</returns>
         public static int Cardinality(this BitArray bits)
         {
+            if (bits == null)
+                throw new ArgumentNullException(nameof(bits));
             int count = 0;
+
+#if NETSTANDARD1_6
             for (int i = 0; i < bits.Length; i++)
             {
                 if (bits[i])
                     count++;
             }
+#else
+            int bitsLength = bits.Length;
+            int[] ints = new int[(bitsLength >> 5) + 1];
+            int intsLength = ints.Length;
+            int c;
+
+            bits.CopyTo(ints, 0);
+
+            // fix for not truncated bits in last integer that may have been set to true
with SetAll()
+            ints[intsLength - 1] &= ~(-1 << (bitsLength % 32));
+
+            for (int i = 0; i < intsLength; i++)
+            {
+                c = ints[i];
+
+                // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
+                unchecked
+                {
+                    c -= (c >> 1) & 0x55555555;
+                    c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
+                    c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
+                }
+
+                count += c;
+            }
+#endif
             return count;
         }
 


Mime
View raw message