Tricky simple comparison
How can you fool yourself and then QA out of the blue? Test not the code that is executed by the application!
This is a very simple moral, from a slightly more complex story that has been my overconfidence, my over-belief in tests, my lack of understanding of how BCL methods work. I had to deal with it. The actual story of this trial will follow below.
tie
Suppose we have the task of tracking changes in the account statement, which can be requested from the bank. The part of the statement we are interested in is a collection of account transactions, where each transaction has the following attributes:
-
ID of the recipient of the transaction (where the money actually went, may not be filled, i.e. null)
-
Transaction “number” is a deprecated field, it is guaranteed that the field is unique within one recipient. May be empty (for “new” transactions)
-
The unique transaction identifier is a globally unique string, and may also be left blank.
Of course, there are also various attributes, such as dates, amounts, etc., but for simplicity, we will not consider them. Next, we will work with the following transaction model:
public record Transaction(int? TargetId, string? Uid, string? Account);
The service in question should monitor the emergence of new transactions, and notify the user that a new transaction has been added, while taking into account some features:
-
A transaction cannot change the recipient.
-
The transaction may disappear from the statement
-
The transaction may appear “backdating” or change its date (so the date of the transaction is not taken into account as a key field)
-
There was a format change: some of the transactions have only a number, some have a number and ID, some have only ID.
-
At the same time, the assigned ID cannot be lost.
-
The assigned number may disappear, but only if it has been replaced with a uid
In the bottom line, the task looks quite simple: you need to “subtract” from the set of transactions of the current statement the set of transactions of the previous statement and report all new elements. In this case, the comparison of transactions is carried out according to some simple rules. And it seems that there is a method for this IEnumerable<T>.Except<T>() in linq, which takes a “comparator” as input: an object that implements the interface IEqualityComparer<T> answering the question of equality of two objects of type T.
We write the code
Let’s think of an uncomplicated comparison. Method Equals() looks pretty straight forward:
public bool Equals(Transaction? x, Transaction? y)
{
// null не обрабатываем, простите меня, Барбара Лисков
if (x == null || y == null) throw new ArgumentNullException();
// early exit: если получатель платежа заполнен для обоих транзакций и они не равны, то это явно разные транзакции.
if (x.TargetId.HasValue && y.TargetId.HasValue && x.TargetId != y.TargetId) return false;
// сравниваем уникальные идентификаторы, только если они оба заполнены
if (!string.IsNullOrEmpty(x.Uid) && !string.IsNullOrEmpty(y.Uid))
return string.Equals(x.Uid, y.Uid, StringComparison.OrdinalIgnoreCase);
// то же для номеров счетов
if (!string.IsNullOrEmpty(x.Account) && !string.IsNullOrEmpty(y.Account))
return string.Equals(x.Account, y.Account, StringComparison.OrdinalIgnoreCase);
return false; // ничего не сработало, значит это разные транзакции
}
Let’s also make getting the hashcode simple:
public int GetHashCode(Transaction obj) =>
HashCode.Combine(
obj.TargetId.GetHashCode(),
obj.Uid?.GetHashCode(),
obj.Account?.GetHashCode()
);
So far, everything looks valid and no problems are visible. But what is code without tests!
Let’s test it simply: we will prepare (possibly with domain experts) several test cases on which we will run the following test:
[Test, TestCaseSource(typeof(TestData))]
public void Equals_WhenCalled_ReturnsExpectedValue(Transaction x, Transaction y, bool expected)
{
//arrange
var sut = new TransactionComparer();
//act & assert
sut.Equals(x, y).Should().Be(expected);
sut.Equals(y, x).Should().Be(expected);
}
Let’s place the test cases side by side:
[ExcludeFromCodeCoverage]
public class TestData : IEnumerable
{
public IEnumerator GetEnumerator()
{
yield return new object[] { new Transaction(42, "uid", "account"), new Transaction(69, "uid", "account"), false };
yield return new object[] { new Transaction(42, "uid", null), new Transaction(42, "uid", null), true };
yield return new object[] { new Transaction(42, "uid", ""), new Transaction(42, "uid", null), true };
yield return new object[] { new Transaction(42, "uid", "account"), new Transaction(42, "uid", null), true };
yield return new object[] { new Transaction(42, "uid", "acc1"), new Transaction(42, "uid", "acc2"), true };
yield return new object[] { new Transaction(42, "uid", null), new Transaction(null, "uid", null), true };
yield return new object[] { new Transaction(42, "uid", ""), new Transaction(null, "uid", null), true };
yield return new object[] { new Transaction(42, "uid", "account"), new Transaction(null, "uid", null), true };
yield return new object[] { new Transaction(42, "uid", "acc1"), new Transaction(null, "uid", "acc2"), true };
yield return new object[] { new Transaction(42, "uid", null), new Transaction(42, "diu", null), false };
yield return new object[] { new Transaction(42, "uid", ""), new Transaction(42, "diu", null), false };
yield return new object[] { new Transaction(42, "uid", "account"), new Transaction(42, "diu", null), false };
yield return new object[] { new Transaction(42, "uid", "acc1"), new Transaction(42, "diu", "acc2"), false };
yield return new object[] { new Transaction(42, "uid", null), new Transaction(null, "olo", null), false };
yield return new object[] { new Transaction(42, "uid", ""), new Transaction(null, "olo", null), false };
yield return new object[] { new Transaction(42, "uid", "account"), new Transaction(null, "olo", null), false };
yield return new object[] { new Transaction(42, "uid", "acc1"), new Transaction(null, "olo", "acc2"), false };
yield return new object[] { new Transaction(42, null, "acc"), new Transaction(null, null, "acc"), true };
yield return new object[] { new Transaction(42, "", "acc"), new Transaction(null, null, "acc"), true };
yield return new object[] { new Transaction(42, "uid", "acc"), new Transaction(null, null, "caa"), false };
yield return new object[] { new Transaction(42, "uid", "acc1"), new Transaction(null, null, "acc1"), true };
yield return new object[] { new Transaction(42, "uid", null), new Transaction(42, null, "acc"), false };
yield return new object[] { new Transaction(42, "uid", null), new Transaction(null, null, "acc"), false };
}
}
Well, this test suite gives us almost full method coverage. Equals (we will not consider the degenerate case of comparison with null).
Now you can subtract from one collection another using .Except() and go drink tea. Or not? After all, testers bring examples when the code does not work as expected. Why?
And what did they test?
The real code that uses the comparator is slightly different from the test one and looks something like this:
var currentCollection = GetFromCurrentReport();
var previousCollection = _store.GetFromPreviousReport();
var diff = currentCollection.Except(previousCollection, sut);
This is slightly completely different from what we tested. But it seems that the method Equals() it’s still in use! What went wrong? Before uncovering the debugger, let’s write another test that works on the same data:
[Test, TestCaseSource(typeof(TestData))]
public void Except_WhenCalled_ReturnsEmptyCollection(Transaction x, Transaction y, bool isDiffEmpty)
{
//arrange
var sut = new TransactionComparer();
var currentCollection = new[]{x};
var previousCollection = new []{y};
//act
var diff = currentCollection.Except(previousCollection, sut).ToList();
//assert
if (isDiffEmpty)
diff.Should().BeEmpty();
else
diff.Should().NotBeEmpty();
}
This test checks the consistency of the behavior of a direct method call Equals() (it has already been tested and can be trusted!) with the observable effect of “subtracting” sets.
And… 10 out of 23 tests fail!
But something has changed, now there is a coating in the method TransactionComparer.GetHashCode(). The problem is localized, it’s time to look under the hood of the linq method Except()
How sets are subtracted
We uncover the decompiler or download debugging symbols and start falling into the implementation Except().
The method itself checks the input parameters and returns the generator from the private method:
private static IEnumerable<TSource> ExceptIterator<TSource>(
IEnumerable<TSource> first,
IEnumerable<TSource> second,
IEqualityComparer<TSource> comparer)
{
HashSet<TSource> set = new HashSet<TSource>(second, comparer);
foreach (TSource source in first)
{
if (set.Add(source))
yield return source;
}
}
What’s happening? From the subtracted sequence is created HashSet, into which the elements of the left (reduced) sequence are crammed in the loop. Those that were successfully stuffed are returned as elements of the resulting sequence (they were not in the subtracted sequence).
We need to go deeper! What happens in a call HashSet.Add()? How does a hashset determine new elements?
For the full code with various tricky hacks, you can go to runtime repositoryconsider the main execution paths:
private bool AddIfNotPresent(T value, out int location)
{
/* Код всякой подготовки */
if (comparer == null)
{
/* Не наш случай - comparer предоставляется */
}
else
{
hashCode = value != null ? comparer.GetHashCode(value) : 0;
bucket = ref GetBucketRef(hashCode);
int i = bucket - 1; // Value in _buckets is 1-based
while (i >= 0)
{
ref Entry entry = ref entries[i];
if (entry.HashCode == hashCode && comparer.Equals(entry.Value, value))
{
location = i;
return false; // <<== Выход в случае, если элемент не может быть добавлен
}
i = entry.Next;
collisionCount++;
/*Обаботка конкуретного обновления коллекции*/
}
}
/*
Бла бла бла, какой то сложный код, который обрабатывает добавление элемента в хэшсет
*/
return true; // <<== А это выход, если элемент таки удалось добавить
}
What conclusion can be drawn from what you see? There are only two possible exits in the method, so that a new element cannot be added to the hashset (because there is already an old element there), 2 conditions must be met:
Obviously the implementation GetHashCode() used earlier generates hashcodes inconsistently with the comparison function, which leads to the fact that some are “the same” (according to Equals()) elements can be added to one hashset.
Fixing a bug
Let’s rewrite the function GetHashCode()so that it always returns a constant, then the left side of the condition entry.HashCode == hashCode && comparer.Equals(entry.Value, value) will always be true and the condition will be identical comparer.Equals(entry.Value, value)that is, the result will be determined only by the method Equals().
public class PatchedTransactionComparer : TransactionComparer
{
public override int GetHashCode(Transaction obj) => 0;
}
And voila! All tests are green, the bug is fixed.
To confirm that the bug is defeated and now Equals() And Except() behave consistently add a property based test:
[FsCheck.NUnit.Property]
public void Except_Consistent_WithEquals()
{
var sut = new PatchedTransactionComparer();
Prop.ForAll<Transaction, Transaction>((l, r) =>
{
var equals = sut.Equals(l, r);
var diff = new[] { l }.Except(new[] { r }, sut).ToList();
diff.Any().Should().Be(!equals);
}).QuickCheckThrowOnFailure();
}
This test checks the following property of the comparator: for any pair of values, their equality through Equals() will provide an empty difference list obtained by calling Except(), sets consisting of one left and one right value, respectively; the reverse is also true – element inequality will produce a non-empty difference list.
The test is green, everything works. Job is done.
trade off
Here it is worth asking the question: so if with this GetHashCode() so many problems, why is it needed at all? If in comparators it is possible to implement complex and interesting logic in the method Equals()which will compare two records by different, possibly variable, keys, then what does the correct implementation of the hash code give?
Speed. HashSet he’s not just Set, but uses hashes to look up object comparisons. In the worst case, when GetHashCode() => const adding a set to itself is performed in quadratic time (each object must be compared with each), and in the optimal case, when the hashcode uniquely identifies each instance, the addition will be performed in linear time (each entry is added in O(1)).
Let’s demonstrate this with a benchmark with a slightly modified data model:
public record Data(int Group, string Key);
On which we compare two types of comparators:
public abstract class Comparer : IEqualityComparer<Data>
{
public bool Equals(Data? x, Data? y)
{
if (x == null || y == null) return false;
if (x.Group != y.Group)
{
return false;
}
return string.Equals(x.Key, y.Key, StringComparison.OrdinalIgnoreCase);
}
public abstract int GetHashCode(Data obj);
}
public class ConstHashComparer : Comparer
{
public override int GetHashCode(Data obj) => 0;
}
public class FullKeyComparer : Comparer
{
public override int GetHashCode(Data obj) =>
HashCode.Combine(obj.Group.GetHashCode(), obj.Key.GetHashCode(StringComparison.OrdinalIgnoreCase));
}
Actually the benchmark code is straightforward. Before starting the iteration, it will create 2 lists of random elements, then it will calculate the difference between these sets using one or the other comparator:
public class Bench
{
private Data BuildNewData(Random rng, int keyLen)
{
const string alphabet = "abcdefghijklmnopqrstuwxyz0123456789";
var sb = new StringBuilder(keyLen);
for (int i = 0; i < keyLen; ++i)
{
sb.Append(alphabet[rng.Next(0, alphabet.Length-1)]);
}
return new(rng.Next(0, 10), sb.ToString());
}
private List<Data> left;
private List<Data> right;
private readonly ConstHashComparer _constHashComparer = new();
private readonly FullKeyComparer _fullKeyComparer = new();
[Params(100, 10_000)]
public int LeftLen { get; set; }
[Params(100, 10_000)]
public int RightLen { get; set; }
[GlobalSetup]
public void Setup()
{
var rng = new Random();
left = new List<Data>(LeftLen);
for(int i = 0; i<LeftLen; ++i)
left.Add(BuildNewData(rng, 10));
right = new List<Data>(RightLen);
for(int i = 0; i<RightLen; ++i)
right.Add(BuildNewData(rng, 10));
}
[Benchmark]
public List<Data> ConstHashComparer() => left.Except(right, _constHashComparer).ToList();
[Benchmark]
public List<Data> FullKeyComparer() => left.Except(right, _fullKeyComparer).ToList();
}
Start, wait a bit and here they are the results:
// * Summary *
BenchmarkDotNet=v0.13.5, OS=ubuntu 23.04
AMD Ryzen 5 2400G with Radeon Vega Graphics, 1 CPU, 8 logical and 4 physical cores
.NET SDK=7.0.105
[Host] : .NET 7.0.5 (7.0.523.17801), X64 RyuJIT AVX2
DefaultJob : .NET 7.0.5 (7.0.523.17801), X64 RyuJIT AVX2
| Method | LeftLen | RightLen | Mean | Error | StdDev |
|------------------ |-------- |--------- |----------------:|--------------:|--------------:|
| ConstHashComparer | 100 | 100 | 239.67 us | 4.559 us | 5.067 us |
| FullKeyComparer | 100 | 100 | 12.05 us | 0.123 us | 0.109 us |
| ConstHashComparer | 100 | 10000 | 593,223.83 us | 11,283.344 us | 10,002.390 us |
| FullKeyComparer | 100 | 10000 | 621.23 us | 11.546 us | 11.339 us |
| ConstHashComparer | 10000 | 100 | 582,710.39 us | 3,615.278 us | 3,381.733 us |
| FullKeyComparer | 10000 | 100 | 902.72 us | 2.939 us | 2.606 us |
| ConstHashComparer | 10000 | 10000 | 2,389,666.31 us | 47,119.876 us | 56,092.861 us |
| FullKeyComparer | 10000 | 10000 | 1,794.25 us | 33.850 us | 49.618 us |
Clear win for FullKeyComparer!
All code is available in demo repositories
