GetEntityBatchFixed | C# Online Compiler

GetEntityBatchFixed by maca88

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
	public static void Main()
	{
		var list = new List<int>{2,3,4,5,6};
		var ids = new int[]{1};
		var batchSizes = new int[] {3};
		
		Console.WriteLine("OLD ALGORITHM START");
		foreach(var batchSize in batchSizes)
		{
			Test(list, ids, batchSize, o => false);
			Test(list, ids, batchSize, o => o % 2 == 0);
			Test(list, ids, batchSize, o => o % 2 != 0);
		}
		Console.WriteLine("OLD ALGORITHM END");
		
		Console.WriteLine("");
		Console.WriteLine("");
		
		// This result can be compared with the old algorithm to see the differences
		Console.WriteLine("NEW ALGORITHM NO BATCH CACHE START");
		foreach(var batchSize in batchSizes)
		{
			TestBatch(list, ids, batchSize, o => false, true, false);
			TestBatch(list, ids, batchSize, o => o % 2 == 0, true, false);
			TestBatch(list, ids, batchSize, o => o % 2 != 0, true, false);
		}
		Console.WriteLine("NEW ALGORITHM NO BATCH CACHE END");
		
		Console.WriteLine("");
		Console.WriteLine("");
		
		Console.WriteLine("NEW ALGORITHM BATCH CACHE START");
		foreach(var batchSize in batchSizes)
		{
			TestBatch(list, ids, batchSize, o => false);
			TestBatch(list, ids, batchSize, o => o % 2 == 0);
			TestBatch(list, ids, batchSize, o => o % 2 != 0);
			
			Console.WriteLine("");
			Console.WriteLine("");
		
			TestBatch(list, ids, batchSize, o => false, false);
		}
		Console.WriteLine("NEW ALGORITHM BATCH CACHE END");
	}
	
	
	private static void TestBatch(List<int> set, IEnumerable<int> ids, int batchSize, Func<int, bool> isCachedFn, bool checkCache = true, bool batchableCache = true)
	{
		Console.WriteLine("-----START------");
		var cacheCalls = 0;
		Func<int[], bool[]> areCachedFn = keys => {
			Console.WriteLine($"Checking cache keys: {string.Join(",", keys)}");
			cacheCalls++;
			var result = new bool[keys.Length];
			for(var i = 0; i < keys.Length; i++)
			{
				result[i] = isCachedFn(keys[i]);
			}
			Console.WriteLine($"Cache result: {string.Join(",", result)}");
			return result;
		};
		Func<int, bool> isCachedLogFn = key => {
			Console.WriteLine($"Checking cache key: {key}");
			cacheCalls++;
			var result = isCachedFn(key);
			Console.WriteLine($"Cache result: {result}");
			return result;
		};
		foreach(var id in ids)
		{
			Console.WriteLine(string.Format("Id: {0}", id));
			Console.WriteLine(string.Format("BatchSize: {0}", batchSize));
			var result = GetEntityBatch(id, batchSize, set, checkCache, batchableCache, isCachedLogFn, areCachedFn);
			Console.WriteLine("Result: " + string.Join(",", result));
			Console.WriteLine("----------------");
		}
		Console.WriteLine($"Total cache calls: {cacheCalls}");
		Console.WriteLine("------END-------");
		Console.WriteLine("");
	}
	
	private static void Test(List<int> set, IEnumerable<int> ids, int batchSize, Func<int, bool> isCachedFn)
	{
		Console.WriteLine("-----START------");
		var cacheCalls = 0;
		Func<int, bool> isCachedLogFn = key => {
			Console.WriteLine($"Checking cache key: {key}");
			cacheCalls++;
			var result = isCachedFn(key);
			Console.WriteLine($"Cache result: {result}");
			return result;
		};
		foreach(var id in ids)
		{
			Console.WriteLine(string.Format("Id: {0}", id));
			Console.WriteLine(string.Format("BatchSize: {0}", batchSize));
			var result = GetEntityBatch(id, batchSize, set, isCachedLogFn);
			Console.WriteLine("Result: " + string.Join(",", result));
			Console.WriteLine("----------------");
		}
		Console.WriteLine($"Total cache calls: {cacheCalls}");
		Console.WriteLine("------END-------");
		Console.WriteLine("");
	}

	// Old algorithm
	public static int[] GetEntityBatch(int id, int batchSize, List<int> set, Func<int, bool> isCachedFn)
	{
		int[] ids = new int[batchSize];
		ids[0] = id; //first element of array is reserved for the actual instance we are loading!
		int i = 1;
		int end = -1;
		bool checkForEnd = false;
		
		foreach (var key in set)
		{
			//TODO: this needn't exclude subclasses...
			if (checkForEnd && i == end)
			{
				//the first id found after the given id
				return ids;
			}
			if (id == key)
			{
				end = i;
			}
			else
			{
				if (!isCachedFn(key))
				{
					ids[i++] = key;
				}
			}
			if (i == batchSize)
			{
				i = 1; //end of array, start filling again from start
				if (end != -1)
					checkForEnd = true;
			}
		}
		return ids; //we ran out of ids to try
	}
	
	// New algorithm
	internal static int[] GetEntityBatch(int id, int batchSize, List<int> set, bool checkCache, bool batchableCache, Func<int, bool> isCachedFn, Func<int[], bool[]> areCachedFn)
	{
		int[] ids = new int[batchSize];
		ids[0] = id; //first element of array is reserved for the actual instance we are loading!
		int i = 1;
		int? idIndex = null;
		bool checkForEnd = false;
		
		int index = 0;
		var entityKeys = new List<KeyValuePair<int, int>>(batchSize);

		foreach (var key in set)
		{
			if (ProcessKey(key))
			{
				return ids;
			}
			index++;
		}
		//Console.WriteLine("Set iteration ended. Remaining cache keys: " + string.Join(",", entityKeys));
		
		while (i != batchSize && entityKeys.Count > 0)
		{
			if (CheckCacheAndProcessResult())
			{
				return ids;
			}
			//Console.WriteLine($"Cache keys {entityKeys.Count}, i: {i}");
		}
		
		//Console.WriteLine("Remaining cache keys: " + string.Join(",", entityKeys));
		return ids;
		
		bool CheckCacheAndProcessResult()
		{
			var fromIndex = batchableCache
				? entityKeys.Count - Math.Min(batchSize, entityKeys.Count)
				: 0;
			var toIndex = entityKeys.Count - 1;
			var indexes = GetSortedKeyIndexes(entityKeys, idIndex, fromIndex, toIndex);
			if (!batchableCache)
			{
				for (var j = 0; j < entityKeys.Count; j++)
				{
					if (ProcessKey(entityKeys[indexes[j]].Key))
					{
						return true;
					}
				}
			}
			else
			{
				var results = AreCached(entityKeys, indexes, areCachedFn, checkCache);
				for (var j = 0; j < results.Length; j++)
				{
					if (!results[j] && ProcessKey(entityKeys[indexes[j]].Key, true))
					{
						return true;
					}
				}
			}
			for (var j = toIndex; j >= fromIndex; j--)
			{
				entityKeys.RemoveAt(j);
			}
			return false;
		}
		
		bool ProcessKey(int key, bool ignoreCache = false)
		{
			//Console.WriteLine($"ProcessKey({index}, {key}, {ignoreCache})");
			//TODO: this needn't exclude subclasses...
			if (checkForEnd && (index == set.Count || index >= idIndex.Value + batchSize))
			{
				return true;
			}
			if (id == key)
			{
				idIndex = index;
				//Console.WriteLine($"idIndex {idIndex}");
			}
			else if (!checkCache || !batchableCache)
			{
				if (index < set.Count && (!idIndex.HasValue || index < idIndex.Value))
				{
					entityKeys.Add(new KeyValuePair<int, int>(key, index));
					return false;
				}
				if (!checkCache || !isCachedFn(key))
				{
					ids[i++] = key;
				}
			}
			else if (ignoreCache)
			{
				ids[i++] = key;
			}
			else
			{
				entityKeys.Add(new KeyValuePair<int, int>(key, index));
				
				// Check the cache only when we have collected as many keys as are needed to fill the batch,
				// that are after the currently demanded key.
				if (!idIndex.HasValue || index < idIndex.Value + batchSize)
				{
					return false;
				}
				return CheckCacheAndProcessResult();
			}
			if (i == batchSize)
			{
				i = 1; //end of array, start filling again from start
				if (idIndex.HasValue || index == set.Count)
				{
					checkForEnd = true;
					return index == set.Count || index >= idIndex.Value + batchSize;
				}
			}
			return false;
		}
	}

	private static int[] GetSortedKeyIndexes(List<KeyValuePair<int, int>> entityKeys, int? idIndex, int fromIndex, int toIndex)
	{
		var result = new int[Math.Abs(toIndex - fromIndex) + 1];
		var lowerIndexes = new List<int>();
		var i = 0;
		for (var j = fromIndex; j <= toIndex; j++)
		{
			if (!idIndex.HasValue || entityKeys[j].Value < idIndex.Value)
			{
				lowerIndexes.Add(j);
			}
			else
			{
				result[i++] = j;
			}
		}
		for (var j = lowerIndexes.Count - 1; j >= 0; j--)
		{
			result[i++] = lowerIndexes[j];
		}
		return result;
	}
	
	private static bool[] AreCached(List<KeyValuePair<int, int>> entityKeys, int[] keyIndexes, Func<int[], bool[]> areCachedFn, bool checkCache = true)
	{
		var result = new bool[keyIndexes.Length];
		if (!checkCache)
		{
			return result;
		}
		var cacheKeys = new int[keyIndexes.Length];
		var i = 0;
		foreach(var index in keyIndexes)
		{
			cacheKeys[i++] = entityKeys[index].Key;
		}
		var cacheResult = areCachedFn(cacheKeys);
		for (var j = 0; j < result.Length; j++)
		{
			result[j] = cacheResult[j];
		}

		return result;
	}
}

​x
 
using System;
using System.Linq;
using System.Collections.Generic;
​
public class Program
{
    public static void Main()
    {
        var list = new List<int>{2,3,4,5,6};
        var ids = new int[]{1};
        var batchSizes = new int[] {3};
        
        Console.WriteLine("OLD ALGORITHM START");
        foreach(var batchSize in batchSizes)
        {
            Test(list, ids, batchSize, o => false);
            Test(list, ids, batchSize, o => o % 2 == 0);
            Test(list, ids, batchSize, o => o % 2 != 0);
        }
        Console.WriteLine("OLD ALGORITHM END");
        
        Console.WriteLine("");
        Console.WriteLine("");
        
        // This result can be compared with the old algorithm to see the differences
        Console.WriteLine("NEW ALGORITHM NO BATCH CACHE START");
        foreach(var batchSize in batchSizes)
        {
            TestBatch(list, ids, batchSize, o => false, true, false);
            TestBatch(list, ids, batchSize, o => o % 2 == 0, true, false);
            TestBatch(list, ids, batchSize, o => o % 2 != 0, true, false);
        }
        Console.WriteLine("NEW ALGORITHM NO BATCH CACHE END");
        
        Console.WriteLine("");
        Console.WriteLine("");
        
        Console.WriteLine("NEW ALGORITHM BATCH CACHE START");
        foreach(var batchSize in batchSizes)
        {
            TestBatch(list, ids, batchSize, o => false);
            TestBatch(list, ids, batchSize, o => o % 2 == 0);
            TestBatch(list, ids, batchSize, o => o % 2 != 0);
            
            Console.WriteLine("");
            Console.WriteLine("");
        
            TestBatch(list, ids, batchSize, o => false, false);
        }
        Console.WriteLine("NEW ALGORITHM BATCH CACHE END");
    }
    
    
    private static void TestBatch(List<int> set, IEnumerable<int> ids, int batchSize, Func<int, bool> isCachedFn, bool checkCache = true, bool batchableCache = true)
    {
        Console.WriteLine("-----START------");
        var cacheCalls = 0;
        Func<int[], bool[]> areCachedFn = keys => {
            Console.WriteLine($"Checking cache keys: {string.Join(",", keys)}");
            cacheCalls++;
            var result = new bool[keys.Length];
            for(var i = 0; i < keys.Length; i++)
            {
                result[i] = isCachedFn(keys[i]);
            }
            Console.WriteLine($"Cache result: {string.Join(",", result)}");
            return result;
        };
        Func<int, bool> isCachedLogFn = key => {
            Console.WriteLine($"Checking cache key: {key}");
            cacheCalls++;
            var result = isCachedFn(key);
            Console.WriteLine($"Cache result: {result}");
            return result;
        };
        foreach(var id in ids)
        {
            Console.WriteLine(string.Format("Id: {0}", id));
            Console.WriteLine(string.Format("BatchSize: {0}", batchSize));
            var result = GetEntityBatch(id, batchSize, set, checkCache, batchableCache, isCachedLogFn, areCachedFn);
            Console.WriteLine("Result: " + string.Join(",", result));
            Console.WriteLine("----------------");
        }
        Console.WriteLine($"Total cache calls: {cacheCalls}");
        Console.WriteLine("------END-------");
        Console.WriteLine("");
    }
    
    private static void Test(List<int> set, IEnumerable<int> ids, int batchSize, Func<int, bool> isCachedFn)
    {
        Console.WriteLine("-----START------");
        var cacheCalls = 0;
        Func<int, bool> isCachedLogFn = key => {
            Console.WriteLine($"Checking cache key: {key}");
            cacheCalls++;
            var result = isCachedFn(key);
            Console.WriteLine($"Cache result: {result}");
            return result;
        };
        foreach(var id in ids)
        {
            Console.WriteLine(string.Format("Id: {0}", id));
            Console.WriteLine(string.Format("BatchSize: {0}", batchSize));
            var result = GetEntityBatch(id, batchSize, set, isCachedLogFn);
            Console.WriteLine("Result: " + string.Join(",", result));
            Console.WriteLine("----------------");
        }
        Console.WriteLine($"Total cache calls: {cacheCalls}");
        Console.WriteLine("------END-------");
        Console.WriteLine("");
    }
​
    // Old algorithm
    public static int[] GetEntityBatch(int id, int batchSize, List<int> set, Func<int, bool> isCachedFn)
    {
        int[] ids = new int[batchSize];
        ids[0] = id; //first element of array is reserved for the actual instance we are loading!
        int i = 1;
        int end = -1;
        bool checkForEnd = false;
        
        foreach (var key in set)
        {
            //TODO: this needn't exclude subclasses...
            if (checkForEnd && i == end)
            {
                //the first id found after the given id
                return ids;
            }
            if (id == key)
            {
                end = i;
            }
            else
            {
                if (!isCachedFn(key))
                {
                    ids[i++] = key;
                }
            }
            if (i == batchSize)
            {
                i = 1; //end of array, start filling again from start
                if (end != -1)
                    checkForEnd = true;
            }
        }
        return ids; //we ran out of ids to try
    }
    
    // New algorithm
    internal static int[] GetEntityBatch(int id, int batchSize, List<int> set, bool checkCache, bool batchableCache, Func<int, bool> isCachedFn, Func<int[], bool[]> areCachedFn)
    {
        int[] ids = new int[batchSize];
        ids[0] = id; //first element of array is reserved for the actual instance we are loading!
        int i = 1;
        int? idIndex = null;
        bool checkForEnd = false;
        
        int index = 0;
        var entityKeys = new List<KeyValuePair<int, int>>(batchSize);
​
        foreach (var key in set)
        {
            if (ProcessKey(key))
            {
                return ids;
            }
            index++;
        }
        //Console.WriteLine("Set iteration ended. Remaining cache keys: " + string.Join(",", entityKeys));
        
        while (i != batchSize && entityKeys.Count > 0)
        {
            if (CheckCacheAndProcessResult())
            {
                return ids;
            }
            //Console.WriteLine($"Cache keys {entityKeys.Count}, i: {i}");
        }
        
        //Console.WriteLine("Remaining cache keys: " + string.Join(",", entityKeys));
        return ids;
        
        bool CheckCacheAndProcessResult()
        {
            var fromIndex = batchableCache
                ? entityKeys.Count - Math.Min(batchSize, entityKeys.Count)
                : 0;
            var toIndex = entityKeys.Count - 1;
            var indexes = GetSortedKeyIndexes(entityKeys, idIndex, fromIndex, toIndex);
            if (!batchableCache)
            {
                for (var j = 0; j < entityKeys.Count; j++)
                {
                    if (ProcessKey(entityKeys[indexes[j]].Key))
                    {
                        return true;
                    }
                }
            }
            else
            {
                var results = AreCached(entityKeys, indexes, areCachedFn, checkCache);
                for (var j = 0; j < results.Length; j++)
                {
                    if (!results[j] && ProcessKey(entityKeys[indexes[j]].Key, true))
                    {
                        return true;
                    }
                }
            }
            for (var j = toIndex; j >= fromIndex; j--)
            {
                entityKeys.RemoveAt(j);
            }
            return false;
        }
        
        bool ProcessKey(int key, bool ignoreCache = false)
        {
            //Console.WriteLine($"ProcessKey({index}, {key}, {ignoreCache})");
            //TODO: this needn't exclude subclasses...
            if (checkForEnd && (index == set.Count || index >= idIndex.Value + batchSize))
            {
                return true;
            }
            if (id == key)
            {
                idIndex = index;
                //Console.WriteLine($"idIndex {idIndex}");
            }
            else if (!checkCache || !batchableCache)
            {
                if (index < set.Count && (!idIndex.HasValue || index < idIndex.Value))
                {
                    entityKeys.Add(new KeyValuePair<int, int>(key, index));
                    return false;
                }
                if (!checkCache || !isCachedFn(key))
                {
                    ids[i++] = key;
                }
            }
            else if (ignoreCache)
            {
                ids[i++] = key;
            }
            else
            {
                entityKeys.Add(new KeyValuePair<int, int>(key, index));
                
                // Check the cache only when we have collected as many keys as are needed to fill the batch,
                // that are after the currently demanded key.
                if (!idIndex.HasValue || index < idIndex.Value + batchSize)
                {
                    return false;
                }
                return CheckCacheAndProcessResult();
            }
            if (i == batchSize)
            {
                i = 1; //end of array, start filling again from start
                if (idIndex.HasValue || index == set.Count)
                {
                    checkForEnd = true;
                    return index == set.Count || index >= idIndex.Value + batchSize;
                }
            }
            return false;
        }
    }
​
    private static int[] GetSortedKeyIndexes(List<KeyValuePair<int, int>> entityKeys, int? idIndex, int fromIndex, int toIndex)
    {
        var result = new int[Math.Abs(toIndex - fromIndex) + 1];
        var lowerIndexes = new List<int>();
        var i = 0;
        for (var j = fromIndex; j <= toIndex; j++)
        {
            if (!idIndex.HasValue || entityKeys[j].Value < idIndex.Value)
            {
                lowerIndexes.Add(j);
            }
            else
            {
                result[i++] = j;
            }
        }
        for (var j = lowerIndexes.Count - 1; j >= 0; j--)
        {
            result[i++] = lowerIndexes[j];
        }
        return result;
    }
    
    private static bool[] AreCached(List<KeyValuePair<int, int>> entityKeys, int[] keyIndexes, Func<int[], bool[]> areCachedFn, bool checkCache = true)
    {
        var result = new bool[keyIndexes.Length];
        if (!checkCache)
        {
            return result;
        }
        var cacheKeys = new int[keyIndexes.Length];
        var i = 0;
        foreach(var index in keyIndexes)
        {
            cacheKeys[i++] = entityKeys[index].Key;
        }
        var cacheResult = areCachedFn(cacheKeys);
        for (var j = 0; j < result.Length; j++)
        {
            result[j] = cacheResult[j];
        }
​
        return result;
    }
}

View IL Code