DEV Community: Sungu, Hasan Emrah

How to compare two files using .NET, really really fast!

Sungu, Hasan Emrah — Tue, 21 Dec 2021 10:53:22 +0000

Optimization Problem

Last week, I finished my tasks at work early so I had some time at hand, which I used to optimize some tools at work!

Without any delay let us move onto what I did. SO, there is this in-company tool which is used to serialize files from "SOURCE" folder, to "TARGET" folder. If source file and target file are different, it also copies the source file to target directory. So far so good! However, when I looked at the source code, I noticed that the comparison is done by checking MD5 hashes of both files.

This is an optimization chance for the following reasons:
a) In order to calculate MD5hash, all the bytes of the file has to be read and then put through message-digest algorithm.
b) A matching MD5 hash does not 100% mean, files are the same

*Since MD5 is a 128bit hashing algorithm, Birthday problem predicts on average hashing 2⁶⁴ files will end up with a collision ← well, not much of a possibility anyways

Benchmark

※I used BenchmarkDotNet which is also supported by the .NET Foundation, to benchmark the code I wrote. I am comparing 128mB of same files!

Since I want to have a standardized interface, I started out by designing my FileComparer class. I think I commented good enough so it does not need any further explaining :)

MD5 Comparison

Now to implement our baseline, which is MD5 comparison.

After running BenchmarkDotNet, here we can see the result.

Method	Mean	Error	StdDev	Ratio
Md5Comparer	1.302 s	0.0090 s	0.0080 s	1.00

Compare Individual Bytes

Can we do better? Of course! We do not need to calculate the MD5 hash at all. We can do a byte-to-byte check and do an early return as soon as we find a not matching byte!

Wow! ReadWholeFileAtOnce is almost 7 times faster, but it is not memory efficient. It reads whole file into memory even before doing any comparison! But Can we do better? Of course!

Method	Mean	Error	StdDev	Ratio
Md5Comparer	1,296.4 ms	11.02 ms	10.31 ms	1.00
ReadWholeFileAtOnce	190.2 ms	2.66 ms	2.49 ms	0.15

LINQ is not that fast

But before doing better I would like to show "efficiency" of LINQ queries.

Method	Mean	Error	StdDev	Ratio
Md5Comparer	1,299.5 ms	6.09 ms	5.40 ms	1.00
CompareUsingLinq	830.0 ms	1.86 ms	1.45 ms	0.64
UseSequenceEquals	805.5 ms	7.62 ms	7.13 ms	0.62
ReadWholeFileAtOnce	190.4 ms	2.90 ms	2.71 ms	0.15

As can be seen from the results, simple for loop is 4 times faster than a LINQ query. Of course, it does not mean that this is always the case but for high performance code, it is wise to stay away from LINQ and stick to simple choices.

Read File in Chunks

Continuing on! ...But Can we do better? Of course!
Now is the time to up the optimization game! We will read the files in chunks of certain size and then compare the bytes. Here is the new base class which inherits from FileComparer.cs.

Next thing is to choose a suitable ChunkSize, which should yield a faster speed than reading the whole file at once and also must be better with memory efficiency as well. Here is a benchmark I run on the suitable BufferSize. I chose my candidates as
4096 * 1, 4096 * 2, 4096 * 4, 4096 * 8, 4096 * 16, 4096 * 32, 4096 * 64, 4096 * 128 bytes and turns out 4096 * 32 is a good choice.

So currently, reading files in chunks of 4096 * 32 and comparing them one byte at a time seems to be the fastest method, almost 8 times faster than MD5 comparison

Method	BufferSize	Mean	Ratio
Md5Comparer		1,298.1 ms	1.00
AllFile		190.6 ms	0.15
Chunks_One	131072	168.7 ms	0.13

Reading in Chunks comparing 8 bytes at a time

But Can we do better? Of course! There is a pretty neat trick which you can find in some implementations in glibc, about strlen or memcmp as well. It makes use of comparing word length of bytes at a time! Here is the source code!

So, it looks like comparing 8 bytes at a time is a reasonable trick and we end up with 10 times the speed of MD5 comparison!

Method	BufferSize	Mean	Ratio
Md5Comparer		1,298.1 ms	1.00
AllFile		190.6 ms	0.15
Chunks_One	131072	168.7 ms	0.13
Chunks_Eight	131072	126.9 ms	0.10

Using SIMD

But Can we do better? Of course! By vectorizing our problem at hand, we can use SIMD instructions as long as our hardware supports it. Here is a class using general purpose Vecotr class.

After Vectorizing, we are more than 15 times faster the MD5 comparison speed!

Method	BufferSize	Mean	Error	StdDev	Ratio
Md5	131072	1,293.05 ms	7.763 ms	6.882 ms	1.00
Vector	131072	81.92 ms	0.240 ms	0.188 ms	0.06

But can we do better? Of course!
I am currently using a CPU which supports AVX2 SIMD instructions. Instead general purpose Vector class, let us use hardware specific instrinsics.

※I guess almost any CPU released after the year 2013 should support it, but I am not sure.

After AVX2, we are more than 16 times faster the MD5 comparison speed!

Method	BufferSize	Mean	Error	StdDev	Ratio
Md5	131072	1,293.05 ms	7.763 ms	6.882 ms	1.00
AVX2	131072	81.92 ms	0.240 ms	0.188 ms	0.06

Singleton Pattern Implemented in C#

Sungu, Hasan Emrah — Mon, 14 Oct 2019 13:10:15 +0000

Singleton pattern is a very well known design pattern in software engineering. It is a very controversial topic and you can find many heated discussions about why Singleton pattern is the source of all the evil in the world or when it is acceptable to use it. However, if you are in game development like myself, you already know that it is a pretty commonly used design for Manager type classes such as CutSceneManager or InputManager and so on.

I will not go into details about what Singleton is or when to use it but to put it simply, a Singleton is a class which you expect to have only one instance of through out an application's life.

I have recently moved to a team whose members are mostly junior engineers as a senior engineer. I have been going through the source code to understand where I needed to apply some "fixing" before I actually started coding. I started with main game loop and went on to the initializations of the Manager type classes, which are expected to be Singleton. To my surprise all of them had public constructors and fixing these became my first task.

In its most simple every game looks like the following→



private readonly Managers[] _managers... 

static void main(string[] args){
    //Initialize XXXManager
    //Initialize YYYManager
    //Initialize ZZZManager

    while(true){
        foreach(var mgr in _managers){
            mgr.Update();
        }
        if(someCondition){
            break;
        }
    }

    //Reverse of creation order
    //Destroy ZZZManager
    //Destroy YYYManager
    //Destroy XXXManager
}

It is clear that each Manager class is a Singleton which implements an interface with methods Initialize, Update and Destroy. Moreover, it is a good idea to manage the creation of those Singleton instances so that Singletons are accessed through a single entry point (I will come to that in a bit). So here is the base class for each Singleton class to inherit from.



public abstract class SingletonBase<T> {

/// <summary>
/// Instance creator for this class. <see cref="Lazy{T}" /> guarantees
/// that <see cref="InstanceCreator" /> will only run once.
/// </summary>
private static readonly Lazy<T> LazyInstance = new Lazy<T>(InstanceCreator);

#if DEBUG

/// <summary>
/// Counter which holds how many instances this class has.
/// Since this is a Singleton implementation,
/// <see cref="_instanceCount" /> can at most be one (1).
/// </summary>
private static int _instanceCount;

#endif

 /// <summary>
 /// Every Singleton implementation is required to inherit this base class.
 /// </summary>
protected SingletonBase() {
#if DEBUG
    Interlocked.Increment(ref _instanceCount);
    if (_instanceCount > 1) {
        throw new Exception($"{nameof(T)} is Singleton but it has {_instanceCount} instances");
    }
#endif
}

/// <summary>
/// Access the instance of this Singleton. The first time you access
/// it is lazily instantiated.
/// </summary>
/// <remarks>This property must be thread-safe.</remarks>
public static T Instance => LazyInstance.Value;

/// <summary>
/// </summary>
/// <returns>An instance of <see cref="T" /></returns>
private static T InstanceCreator() {
#if DEBUG
    var ctors = typeof(T).GetConstructors(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);
    var publicCtors = ctors.Where(c => c.IsPublic);
    if (publicCtors.Any()) {
        throw new HasPublicConstructorException(typeof(T));
    }

    var ctorsWithParameters = ctors.Where(c => c.GetParameters().Length > 0);
    if (ctorsWithParameters.Any()) {
        throw new HasConstructorWithParametersException(typeof(T));
    }
#endif
    //Since this will be run only once during the application's life cycle it is acceptable to use.
    //If it would be called many times, it is better to CreateDelegate
    return (T) Activator.CreateInstance(typeof(T), true);
}

I tried to comment as detailed as possible so the code itself is self explanatory and #if DEBUG preprocessor is there on the assumption that by the time the release phase is reached, all the tests are passed and extra checks are already unnecessary. It may look like a micro optimization but every little bit helps :)

Now that the base singleton is created, it is pretty straight forward to create a base GameManager class, which all the game managers need to inherit from. As can be seen, it only has the bare minimum with a really clean interface.




    public interface IGameManager {

        void Initialize();

        void Update();

        void Destroy();
    }

    public abstract class GamaManagerBase<T> : SingletonBase<T>, IGameManager  {


        protected GamaManagerBase(){

        }

        public abstract void Initialize();

        public abstract void Update();

        public abstract void Destroy();
}

Finally, I would like mention about the single entry point for the Singleton instances as I do not want the users of this instances to be accessed erratically. I will create a SingletonManager class, which will handle all the access



public class SingletonManager : SingletonBase<SingletonManager> {

    /// <summary>
    /// Cache which holds Type and its lazily instantiated object.
    /// </summary>
    private readonly Dictionary<Type, Lazy<object>> _cache = new Dictionary<Type, Lazy<object>>();

    /// <summary>
    /// Classes implementing <see cref="SingletonBase{T}"/> can be registered at <see cref="SingletonManager"/>.
    /// </summary>
    private SingletonManager() {
    }

    /// <summary>
    /// Registers the given type to <see cref="SingletonManager"/>.
    /// </summary>
    /// <typeparam name="T">Type to register to <see cref="SingletonManager"/></typeparam>
    /// <exception cref="AlreadyRegisteredTypeException">Throws if the type being registered is already registered.</exception>
    public void Register<T>() where T : SingletonBase<T> {
        if (_cache.ContainsKey(typeof(T))) {
            throw new AlreadyRegisteredTypeException(typeof(T));
        }
        _cache[typeof(T)] = new Lazy<object>(() => SingletonBase<T>.Instance);
    }

    /// <summary>
    /// Gets the Instance of given type.
    /// </summary>
    /// <typeparam name="T">Type to get.</typeparam>
    /// <returns>The instance of T, implementing <see cref="SingletonBase{T}"/></returns>
    /// <exception cref="NotRegisteredTypeException">Throws if the type being registered is not registered.</exception>

    public T Get<T>() where T : SingletonBase<T> {
        if (_cache.TryGetValue(typeof(T), out var value)) {
            return (T)value.Value;
        }
        throw new NotRegisteredTypeException(typeof(T));
    }
}

Now, here is the expected usage of SingletonManager class→



private static void Main(string[] args) {
    var manager = SingletonManager.Instance;
    manager.Register<CutSceneManager>();
    manager.Get<CutSceneManager>().Initialize();
    manager.Get<CutSceneManager>().Update();
}

TL;DR

How to implement singleton pattern in c# and a working example