From 5fdc262c0f657e6e27935fd7179d78c73e12be2a Mon Sep 17 00:00:00 2001 From: Ganbarukamo41 Date: Thu, 7 Nov 2019 14:58:11 +0900 Subject: [PATCH] Vectorise BitArray (dotnet/corefx#41896) * Speed up BitArray 1. Use AVX2, if available, for And/Or/Xor 2. Vectorize Not 3. Use Span.Fill() for SetAll() 4. Add more test sizes to account for And/Or/Xor/Not loop unrolling cases * Vectorise BitArray(bool[]) * Vectorise BitArray further * Vectorise CopyTo(Array, int) when copying to a bool[] * Use Vector128/256.Create and store it in static readonly field instead of loading from PE header * Add some random test data for BitArray Commit migrated from https://github.com/dotnet/corefx/commit/a4f04476ea74c61a52168cf0b31c0281822ecad3 --- .../src/System/Collections/BitArray.cs | 235 +++++++++++++++++++-- .../tests/BitArray/BitArray_CtorTests.cs | 12 +- .../tests/BitArray/BitArray_GetSetTests.cs | 81 +++---- .../tests/BitArray/BitArray_OperatorsTests.cs | 8 +- 4 files changed, 275 insertions(+), 61 deletions(-) diff --git a/src/libraries/System.Collections/src/System/Collections/BitArray.cs b/src/libraries/System.Collections/src/System/Collections/BitArray.cs index e3d48d9..35a7477 100644 --- a/src/libraries/System.Collections/src/System/Collections/BitArray.cs +++ b/src/libraries/System.Collections/src/System/Collections/BitArray.cs @@ -113,7 +113,7 @@ namespace System.Collections _version = 0; } - public BitArray(bool[] values) + public unsafe BitArray(bool[] values) { if (values == null) { @@ -123,7 +123,51 @@ namespace System.Collections m_array = new int[GetInt32ArrayLengthFromBitLength(values.Length)]; m_length = values.Length; - for (int i = 0; i < values.Length; i++) + int i = 0; + + if (values.Length < Vector256.Count) + { + goto LessThan32; + } + + // Comparing with 1s would get rid of the final negation, however this would not work for some CLR bools + // (true for any non-zero values, false for 0) - any values between 2-255 will be interpreted as false. + // Instead, We compare with zeroes (== false) then negate the result to ensure compatibility. + + if (Avx2.IsSupported) + { + fixed (bool* ptr = values) + { + for (; (i + Vector256.Count) <= values.Length; i += Vector256.Count) + { + Vector256 vector = Avx.LoadVector256((byte*)ptr + i); + Vector256 isFalse = Avx2.CompareEqual(vector, Vector256.Zero); + int result = Avx2.MoveMask(isFalse); + m_array[i / 32] = ~result; + } + } + } + else if (Sse2.IsSupported) + { + fixed (bool* ptr = values) + { + for (; (i + Vector128.Count * 2) <= values.Length; i += Vector128.Count * 2) + { + Vector128 lowerVector = Sse2.LoadVector128((byte*)ptr + i); + Vector128 lowerIsFalse = Sse2.CompareEqual(lowerVector, Vector128.Zero); + int lowerPackedIsFalse = Sse2.MoveMask(lowerIsFalse); + + Vector128 upperVector = Sse2.LoadVector128((byte*)ptr + i + Vector128.Count); + Vector128 upperIsFalse = Sse2.CompareEqual(upperVector, Vector128.Zero); + int upperPackedIsFalse = Sse2.MoveMask(upperIsFalse); + + m_array[i / 32] = ~((upperPackedIsFalse << 16) | lowerPackedIsFalse); + } + } + } + + LessThan32: + for (; i < values.Length; i++) { if (values[i]) { @@ -241,13 +285,8 @@ namespace System.Collections public void SetAll(bool value) { int fillValue = value ? -1 : 0; - int[] array = m_array; - - for (int i = 0; i < array.Length; i++) - { - array[i] = fillValue; - } - + int arrayLength = GetInt32ArrayLengthFromBitLength(Length); + m_array.AsSpan(0, arrayLength).Fill(fillValue); _version++; } @@ -275,8 +314,13 @@ namespace System.Collections if (Length != value.Length || (uint)count > (uint)thisArray.Length || (uint)count > (uint)valueArray.Length) throw new ArgumentException(SR.Arg_ArrayLengthsDiffer); + // Unroll loop for count less than Vector256 size. switch (count) { + case 7: thisArray[6] &= valueArray[6]; goto case 6; + case 6: thisArray[5] &= valueArray[5]; goto case 5; + case 5: thisArray[4] &= valueArray[4]; goto case 4; + case 4: thisArray[3] &= valueArray[3]; goto case 3; case 3: thisArray[2] &= valueArray[2]; goto case 2; case 2: thisArray[1] &= valueArray[1]; goto case 1; case 1: thisArray[0] &= valueArray[0]; goto Done; @@ -284,7 +328,20 @@ namespace System.Collections } int i = 0; - if (Sse2.IsSupported) + if (Avx2.IsSupported) + { + fixed (int* leftPtr = thisArray) + fixed (int* rightPtr = valueArray) + { + for (; i < count - (Vector256.Count - 1); i += Vector256.Count) + { + Vector256 leftVec = Avx.LoadVector256(leftPtr + i); + Vector256 rightVec = Avx.LoadVector256(rightPtr + i); + Avx.Store(leftPtr + i, Avx2.And(leftVec, rightVec)); + } + } + } + else if (Sse2.IsSupported) { fixed (int* leftPtr = thisArray) fixed (int* rightPtr = valueArray) @@ -330,8 +387,13 @@ namespace System.Collections if (Length != value.Length || (uint)count > (uint)thisArray.Length || (uint)count > (uint)valueArray.Length) throw new ArgumentException(SR.Arg_ArrayLengthsDiffer); + // Unroll loop for count less than Vector256 size. switch (count) { + case 7: thisArray[6] |= valueArray[6]; goto case 6; + case 6: thisArray[5] |= valueArray[5]; goto case 5; + case 5: thisArray[4] |= valueArray[4]; goto case 4; + case 4: thisArray[3] |= valueArray[3]; goto case 3; case 3: thisArray[2] |= valueArray[2]; goto case 2; case 2: thisArray[1] |= valueArray[1]; goto case 1; case 1: thisArray[0] |= valueArray[0]; goto Done; @@ -339,7 +401,20 @@ namespace System.Collections } int i = 0; - if (Sse2.IsSupported) + if (Avx2.IsSupported) + { + fixed (int* leftPtr = thisArray) + fixed (int* rightPtr = valueArray) + { + for (; i < count - (Vector256.Count - 1); i += Vector256.Count) + { + Vector256 leftVec = Avx.LoadVector256(leftPtr + i); + Vector256 rightVec = Avx.LoadVector256(rightPtr + i); + Avx.Store(leftPtr + i, Avx2.Or(leftVec, rightVec)); + } + } + } + else if (Sse2.IsSupported) { fixed (int* leftPtr = thisArray) fixed (int* rightPtr = valueArray) @@ -385,8 +460,13 @@ namespace System.Collections if (Length != value.Length || (uint)count > (uint)thisArray.Length || (uint)count > (uint)valueArray.Length) throw new ArgumentException(SR.Arg_ArrayLengthsDiffer); + // Unroll loop for count less than Vector256 size. switch (count) { + case 7: thisArray[6] ^= valueArray[6]; goto case 6; + case 6: thisArray[5] ^= valueArray[5]; goto case 5; + case 5: thisArray[4] ^= valueArray[4]; goto case 4; + case 4: thisArray[3] ^= valueArray[3]; goto case 3; case 3: thisArray[2] ^= valueArray[2]; goto case 2; case 2: thisArray[1] ^= valueArray[1]; goto case 1; case 1: thisArray[0] ^= valueArray[0]; goto Done; @@ -394,7 +474,20 @@ namespace System.Collections } int i = 0; - if (Sse2.IsSupported) + if (Avx2.IsSupported) + { + fixed (int* leftPtr = m_array) + fixed (int* rightPtr = value.m_array) + { + for (; i < count - (Vector256.Count - 1); i += Vector256.Count) + { + Vector256 leftVec = Avx.LoadVector256(leftPtr + i); + Vector256 rightVec = Avx.LoadVector256(rightPtr + i); + Avx.Store(leftPtr + i, Avx2.Xor(leftVec, rightVec)); + } + } + } + else if (Sse2.IsSupported) { fixed (int* leftPtr = thisArray) fixed (int* rightPtr = valueArray) @@ -421,15 +514,60 @@ namespace System.Collections ** off/false. Off/false bit values are turned on/true. The current instance ** is updated and returned. =========================================================================*/ - public BitArray Not() + public unsafe BitArray Not() { - int[] array = m_array; + // This method uses unsafe code to manipulate data in the BitArray. To avoid issues with + // buggy code concurrently mutating this instance in a way that could cause memory corruption, + // we snapshot the array then operate only on this snapshot. We don't care about such code + // corrupting the BitArray data in a way that produces incorrect answers, since BitArray is not meant + // to be thread-safe; we only care about avoiding buffer overruns. + int[] thisArray = m_array; + + int count = GetInt32ArrayLengthFromBitLength(Length); - for (int i = 0; i < array.Length; i++) + // Unroll loop for count less than Vector256 size. + switch (count) { - array[i] = ~array[i]; + case 7: thisArray[6] = ~thisArray[6]; goto case 6; + case 6: thisArray[5] = ~thisArray[5]; goto case 5; + case 5: thisArray[4] = ~thisArray[4]; goto case 4; + case 4: thisArray[3] = ~thisArray[3]; goto case 3; + case 3: thisArray[2] = ~thisArray[2]; goto case 2; + case 2: thisArray[1] = ~thisArray[1]; goto case 1; + case 1: thisArray[0] = ~thisArray[0]; goto Done; + case 0: goto Done; } + int i = 0; + if (Avx2.IsSupported) + { + Vector256 ones = Vector256.Create(-1); + fixed (int* ptr = thisArray) + { + for (; i < count - (Vector256.Count - 1); i += Vector256.Count) + { + Vector256 vec = Avx.LoadVector256(ptr + i); + Avx.Store(ptr + i, Avx2.Xor(vec, ones)); + } + } + } + else if (Sse2.IsSupported) + { + Vector128 ones = Vector128.Create(-1); + fixed (int* ptr = thisArray) + { + for (; i < count - (Vector128.Count - 1); i += Vector128.Count) + { + Vector128 vec = Sse2.LoadVector128(ptr + i); + Sse2.Store(ptr + i, Sse2.Xor(vec, ones)); + } + } + } + + for (; i < count; i++) + thisArray[i] = ~thisArray[i]; + + Done: _version++; return this; } @@ -597,7 +735,13 @@ namespace System.Collections } } - public void CopyTo(Array array, int index) + // The mask used when shuffling a single int into Vector128/256. + // On little endian machines, the lower 8 bits of int belong in the first byte, next lower 8 in the second and so on. + // We place the bytes that contain the bits to its respective byte so that we can mask out only the relevant bits later. + private static readonly Vector128 s_lowerShuffleMask_CopyToBoolArray = Vector128.Create(0, 0x01010101_01010101).AsByte(); + private static readonly Vector128 s_upperShuffleMask_CopyToBoolArray = Vector128.Create(0x_02020202_02020202, 0x03030303_03030303).AsByte(); + + public unsafe void CopyTo(Array array, int index) { if (array == null) throw new ArgumentNullException(nameof(array)); @@ -682,7 +826,62 @@ namespace System.Collections throw new ArgumentException(SR.Argument_InvalidOffLen); } - for (int i = 0; i < m_length; i++) + int i = 0; + + if (m_length < BitsPerInt32) + goto LessThan32; + + if (Avx2.IsSupported) + { + Vector256 shuffleMask = Vector256.Create(s_lowerShuffleMask_CopyToBoolArray, s_upperShuffleMask_CopyToBoolArray); + Vector256 bitMask = Vector256.Create(0x80402010_08040201).AsByte(); + Vector256 ones = Vector256.Create((byte)1); + + fixed (bool* destination = &boolArray[index]) + { + for (; (i + Vector256.Count) <= m_length; i += Vector256.Count) + { + int bits = m_array[i / BitsPerInt32]; + Vector256 scalar = Vector256.Create(bits); + Vector256 shuffled = Avx2.Shuffle(scalar.AsByte(), shuffleMask); + Vector256 extracted = Avx2.And(shuffled, bitMask); + + // The extracted bits can be anywhere between 0 and 255, so we normalise the value to either 0 or 1 + // to ensure compatibility with "C# bool" (0 for false, 1 for true, rest undefined) + Vector256 normalized = Avx2.Min(extracted, ones); + Avx.Store((byte*)destination + i, normalized); + } + } + } + else if (Ssse3.IsSupported) + { + Vector128 lowerShuffleMask = s_lowerShuffleMask_CopyToBoolArray; + Vector128 upperShuffleMask = s_upperShuffleMask_CopyToBoolArray; + Vector128 bitMask = Vector128.Create(0x80402010_08040201).AsByte(); ; + Vector128 ones = Vector128.Create((byte)1); + + fixed (bool* destination = &boolArray[index]) + { + for (; (i + Vector128.Count * 2) <= m_length; i += Vector128.Count * 2) + { + int bits = m_array[i / BitsPerInt32]; + Vector128 scalar = Vector128.CreateScalarUnsafe(bits); + + Vector128 shuffledLower = Ssse3.Shuffle(scalar.AsByte(), lowerShuffleMask); + Vector128 extractedLower = Sse2.And(shuffledLower, bitMask); + Vector128 normalizedLower = Sse2.Min(extractedLower, ones); + Sse2.Store((byte*)destination + i, normalizedLower); + + Vector128 shuffledHigher = Ssse3.Shuffle(scalar.AsByte(), upperShuffleMask); + Vector128 extractedHigher = Sse2.And(shuffledHigher, bitMask); + Vector128 normalizedHigher = Sse2.Min(extractedHigher, ones); + Sse2.Store((byte*)destination + i + Vector128.Count, normalizedHigher); + } + } + } + + LessThan32: + for (; i < m_length; i++) { int elementIndex = Div32Rem(i, out int extraBits); boolArray[index + i] = ((m_array[elementIndex] >> extraBits) & 0x00000001) != 0; diff --git a/src/libraries/System.Collections/tests/BitArray/BitArray_CtorTests.cs b/src/libraries/System.Collections/tests/BitArray/BitArray_CtorTests.cs index 738d592..723d688 100644 --- a/src/libraries/System.Collections/tests/BitArray/BitArray_CtorTests.cs +++ b/src/libraries/System.Collections/tests/BitArray/BitArray_CtorTests.cs @@ -76,12 +76,22 @@ namespace System.Collections.Tests public static IEnumerable Ctor_BoolArray_TestData() { + Random rnd = new Random(0); + yield return new object[] { new bool[0] }; - foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2 }) + foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, BitsPerInt32 * 4, BitsPerInt32 * 8, BitsPerInt32 * 16}) { yield return new object[] { Enumerable.Repeat(true, size).ToArray() }; yield return new object[] { Enumerable.Repeat(false, size).ToArray() }; yield return new object[] { Enumerable.Range(0, size).Select(x => x % 2 == 0).ToArray() }; + + bool[] random = new bool[size]; + for (int i = 0; i < random.Length; i++) + { + random[i] = rnd.Next(0, 2) == 0; + } + + yield return new object[] { random }; } } diff --git a/src/libraries/System.Collections/tests/BitArray/BitArray_GetSetTests.cs b/src/libraries/System.Collections/tests/BitArray/BitArray_GetSetTests.cs index 18b58ef..96fbf05 100644 --- a/src/libraries/System.Collections/tests/BitArray/BitArray_GetSetTests.cs +++ b/src/libraries/System.Collections/tests/BitArray/BitArray_GetSetTests.cs @@ -233,59 +233,64 @@ namespace System.Collections.Tests yield return new object[] { new BitArray(0), 0, 0, new byte[0], default(byte) }; yield return new object[] { new BitArray(0), 0, 0, new int[0], default(int) }; - foreach (int bitArraySize in new[] { 0, 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2 }) + foreach (int bitArraySize in new[] { 0, 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, BitsPerInt32 * 4, BitsPerInt32 * 8, BitsPerInt32 * 16 }) { - BitArray allTrue = new BitArray(Enumerable.Repeat(true, bitArraySize).ToArray()); - BitArray allFalse = new BitArray(Enumerable.Repeat(false, bitArraySize).ToArray()); + BitArray allTrue = new BitArray(bitArraySize, true); + BitArray allFalse = new BitArray(bitArraySize, false); BitArray alternating = new BitArray(Enumerable.Range(0, bitArraySize).Select(i => i % 2 == 1).ToArray()); - foreach (Tuple d in new[] { Tuple.Create(bitArraySize, 0), - Tuple.Create(bitArraySize * 2 + 1, 0), - Tuple.Create(bitArraySize * 2 + 1, bitArraySize + 1), - Tuple.Create(bitArraySize * 2 + 1, bitArraySize / 2 + 1) }) + Random rnd = new Random(0); + + foreach ((int arraySize, int startIndex) in new[] { (bitArraySize, 0), + (bitArraySize * 2 + 1, 0), + (bitArraySize * 2 + 1, bitArraySize + 1), + (bitArraySize * 2 + 1, bitArraySize / 2 + 1) }) { - int arraySize = d.Item1; - int index = d.Item2; + yield return new object[] { allTrue, arraySize, startIndex, Enumerable.Repeat(true, bitArraySize).ToArray(), default(bool) }; + yield return new object[] { allFalse, arraySize, startIndex, Enumerable.Repeat(false, bitArraySize).ToArray(), default(bool) }; + yield return new object[] { alternating, arraySize, startIndex, Enumerable.Range(0, bitArraySize).Select(i => i % 2 == 1).ToArray(), default(bool) }; - yield return new object[] { allTrue, arraySize, index, Enumerable.Repeat(true, bitArraySize).ToArray(), default(bool) }; - yield return new object[] { allFalse, arraySize, index, Enumerable.Repeat(false, bitArraySize).ToArray(), default(bool) }; - yield return new object[] { alternating, arraySize, index, Enumerable.Range(0, bitArraySize).Select(i => i % 2 == 1).ToArray(), default(bool) }; + bool[] randomBools = new bool[bitArraySize]; + for (int i = 0; i < bitArraySize; i++) + { + randomBools[i] = rnd.Next(0, 2) == 0; + } + BitArray random = new BitArray(randomBools); + + yield return new object[] { random, arraySize, startIndex, randomBools, default(bool) }; if (bitArraySize >= BitsPerByte) { - yield return new object[] { allTrue, arraySize / BitsPerByte, index / BitsPerByte, Enumerable.Repeat((byte)0xff, bitArraySize / BitsPerByte).ToArray(), default(byte) }; - yield return new object[] { allFalse, arraySize / BitsPerByte, index / BitsPerByte, Enumerable.Repeat((byte)0x00, bitArraySize / BitsPerByte).ToArray(), default(byte) }; - yield return new object[] { alternating, arraySize / BitsPerByte, index / BitsPerByte, Enumerable.Repeat((byte)0xaa, bitArraySize / BitsPerByte).ToArray(), default(byte) }; + yield return new object[] { allTrue, arraySize / BitsPerByte, startIndex / BitsPerByte, Enumerable.Repeat((byte)0xff, bitArraySize / BitsPerByte).ToArray(), default(byte) }; + yield return new object[] { allFalse, arraySize / BitsPerByte, startIndex / BitsPerByte, Enumerable.Repeat((byte)0x00, bitArraySize / BitsPerByte).ToArray(), default(byte) }; + yield return new object[] { alternating, arraySize / BitsPerByte, startIndex / BitsPerByte, Enumerable.Repeat((byte)0xaa, bitArraySize / BitsPerByte).ToArray(), default(byte) }; } if (bitArraySize >= BitsPerInt32) { - yield return new object[] { allTrue, arraySize / BitsPerInt32, index / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xffffffff), bitArraySize / BitsPerInt32).ToArray(), default(int) }; - yield return new object[] { allFalse, arraySize / BitsPerInt32, index / BitsPerInt32, Enumerable.Repeat(0x00000000, bitArraySize / BitsPerInt32).ToArray(), default(int) }; - yield return new object[] { alternating, arraySize / BitsPerInt32, index / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xaaaaaaaa), bitArraySize / BitsPerInt32).ToArray(), default(int) }; + yield return new object[] { allTrue, arraySize / BitsPerInt32, startIndex / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xffffffff), bitArraySize / BitsPerInt32).ToArray(), default(int) }; + yield return new object[] { allFalse, arraySize / BitsPerInt32, startIndex / BitsPerInt32, Enumerable.Repeat(0x00000000, bitArraySize / BitsPerInt32).ToArray(), default(int) }; + yield return new object[] { alternating, arraySize / BitsPerInt32, startIndex / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xaaaaaaaa), bitArraySize / BitsPerInt32).ToArray(), default(int) }; } } } foreach (int bitArraySize in new[] { BitsPerInt32 - 1, BitsPerInt32 * 2 - 1 }) { - BitArray allTrue = new BitArray(Enumerable.Repeat(true, bitArraySize).ToArray()); - BitArray allFalse = new BitArray(Enumerable.Repeat(false, bitArraySize).ToArray()); + BitArray allTrue = new BitArray(bitArraySize, true); + BitArray allFalse = new BitArray(bitArraySize, false); BitArray alternating = new BitArray(Enumerable.Range(0, bitArraySize).Select(i => i % 2 == 1).ToArray()); - - foreach (Tuple d in new[] { Tuple.Create(bitArraySize, 0), - Tuple.Create(bitArraySize * 2 + 1, 0), - Tuple.Create(bitArraySize * 2 + 1, bitArraySize + 1), - Tuple.Create(bitArraySize * 2 + 1, bitArraySize / 2 + 1)}) + foreach ((int arraySize, int startIndex) in new[] { (bitArraySize, 0), + (bitArraySize * 2 + 1, 0), + (bitArraySize * 2 + 1, bitArraySize + 1), + (bitArraySize * 2 + 1, bitArraySize / 2 + 1) }) { - int arraySize = d.Item1; - int index = d.Item2; if (bitArraySize >= BitsPerInt32) { - yield return new object[] { allTrue, (arraySize - 1) / BitsPerInt32 + 1, index / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xffffffff), bitArraySize / BitsPerInt32).Concat(new[] { unchecked((int)(0xffffffffu >> 1)) }).ToArray(), default(int) }; - yield return new object[] { allFalse, (arraySize - 1) / BitsPerInt32 + 1, index / BitsPerInt32, Enumerable.Repeat(0x00000000, bitArraySize / BitsPerInt32 + 1).ToArray(), default(int) }; - yield return new object[] { alternating, (arraySize - 1) / BitsPerInt32 + 1, index / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xaaaaaaaa), bitArraySize / BitsPerInt32).Concat(new[] { unchecked((int)(0xaaaaaaaau >> 2)) }).ToArray(), default(int) }; + yield return new object[] { allTrue, (arraySize - 1) / BitsPerInt32 + 1, startIndex / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xffffffff), bitArraySize / BitsPerInt32).Concat(new[] { unchecked((int)(0xffffffffu >> 1)) }).ToArray(), default(int) }; + yield return new object[] { allFalse, (arraySize - 1) / BitsPerInt32 + 1, startIndex / BitsPerInt32, Enumerable.Repeat(0x00000000, bitArraySize / BitsPerInt32 + 1).ToArray(), default(int) }; + yield return new object[] { alternating, (arraySize - 1) / BitsPerInt32 + 1, startIndex / BitsPerInt32, Enumerable.Repeat(unchecked((int)0xaaaaaaaa), bitArraySize / BitsPerInt32).Concat(new[] { unchecked((int)(0xaaaaaaaau >> 2)) }).ToArray(), default(int) }; } } } @@ -293,22 +298,22 @@ namespace System.Collections.Tests [Theory] [MemberData(nameof(CopyTo_Array_TestData))] - public static void CopyTo(BitArray bitArray, int length, int index, T[] expected, T def) + public static void CopyTo(BitArray bitArray, int destinationLength, int startIndex, T[] expected, T def) { - T[] array = (T[])Array.CreateInstance(typeof(T), length); + T[] array = new T[destinationLength]; ICollection collection = bitArray; - collection.CopyTo(array, index); - for (int i = 0; i < index; i++) + collection.CopyTo(array, startIndex); + for (int i = 0; i < startIndex; i++) { - Assert.Equal(def, array[i]); + Assert.True(def.Equals(array[i]), $"Elements before the start index have been modified. Expected {def} at index {i}, actual {array[i]}"); } for (int i = 0; i < expected.Length; i++) { - Assert.Equal(expected[i], array[i + index]); + Assert.True(expected[i].Equals(array[i + startIndex]), $"Elements that are copied over does not match the expected value. Expected {expected[i]} at index {i + startIndex}, actual {array[i]}"); } - for (int i = index + expected.Length; i < array.Length; i++) + for (int i = startIndex + expected.Length; i < array.Length; i++) { - Assert.Equal(def, array[i]); + Assert.True(def.Equals(array[i]), $"Elements after the copied area have been modified. Expected {def} at index {i}, actual {array[i]}"); } } diff --git a/src/libraries/System.Collections/tests/BitArray/BitArray_OperatorsTests.cs b/src/libraries/System.Collections/tests/BitArray/BitArray_OperatorsTests.cs index 3b288ea..cfe6697 100644 --- a/src/libraries/System.Collections/tests/BitArray/BitArray_OperatorsTests.cs +++ b/src/libraries/System.Collections/tests/BitArray/BitArray_OperatorsTests.cs @@ -15,7 +15,7 @@ namespace System.Collections.Tests public static IEnumerable Not_Operator_Data() { - foreach (int size in new[] { 0, 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, short.MaxValue }) + foreach (int size in new[] { 0, 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, BitsPerInt32 * 3, BitsPerInt32 * 4, BitsPerInt32 * 5, BitsPerInt32 * 6, BitsPerInt32 * 7, BitsPerInt32 * 8, BitsPerInt32 * 8 + BitsPerInt32 - 1, short.MaxValue }) { yield return new object[] { Enumerable.Repeat(true, size).ToArray() }; yield return new object[] { Enumerable.Repeat(false, size).ToArray() }; @@ -41,7 +41,7 @@ namespace System.Collections.Tests public static IEnumerable And_Operator_Data() { yield return new object[] { new bool[0], new bool[0], new bool[0] }; - foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, short.MaxValue }) + foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, BitsPerInt32 * 3, BitsPerInt32 * 4, BitsPerInt32 * 5, BitsPerInt32 * 6, BitsPerInt32 * 7, BitsPerInt32 * 8, BitsPerInt32 * 8 + BitsPerInt32 - 1, short.MaxValue }) { bool[] allTrue = Enumerable.Repeat(true, size).ToArray(); bool[] allFalse = Enumerable.Repeat(false, size).ToArray(); @@ -77,7 +77,7 @@ namespace System.Collections.Tests public static IEnumerable Or_Operator_Data() { yield return new object[] { new bool[0], new bool[0], new bool[0] }; - foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, short.MaxValue }) + foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, BitsPerInt32 * 3, BitsPerInt32 * 4, BitsPerInt32 * 5, BitsPerInt32 * 6, BitsPerInt32 * 7, BitsPerInt32 * 8, BitsPerInt32 * 8 + BitsPerInt32 - 1, short.MaxValue }) { bool[] allTrue = Enumerable.Repeat(true, size).ToArray(); bool[] allFalse = Enumerable.Repeat(false, size).ToArray(); @@ -113,7 +113,7 @@ namespace System.Collections.Tests public static IEnumerable Xor_Operator_Data() { yield return new object[] { new bool[0], new bool[0], new bool[0] }; - foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, short.MaxValue }) + foreach (int size in new[] { 1, BitsPerByte, BitsPerByte * 2, BitsPerInt32, BitsPerInt32 * 2, BitsPerInt32 * 3, BitsPerInt32 * 4, BitsPerInt32 * 5, BitsPerInt32 * 6, BitsPerInt32 * 7, BitsPerInt32 * 8, BitsPerInt32 * 8 + BitsPerInt32 - 1, short.MaxValue }) { bool[] allTrue = Enumerable.Repeat(true, size).ToArray(); bool[] allFalse = Enumerable.Repeat(false, size).ToArray(); -- 2.7.4