Search data from one array in another

Question

What I'm trying to do is simple but it's just slooow. Basically I'm looping through data (byte array), converting some parts to a INT and then comparing it to RamCache with is also a byte array. The reason why I'm converting it to a INT is because it's 4 bytes so if 4 bytes are equal in some part of the RamCache array I know it's already 4 length equal. And then from there I can see how many bytes are equal.

In short what this code must do:

Loop through the data array and take 4 bytes ,then look if it contains in the RamCache array. Currently the code below is slow when the data array and RamCache array contains 65535 bytes.

    private unsafe SmartCacheInfo[] FindInCache(byte[] data, Action<SmartCacheInfo> callback)
    {
        List<SmartCacheInfo> ret = new List<SmartCacheInfo>();

        fixed (byte* x = &(data[0]), XcachePtr = &(RamCache[0]))
        {
            Int32 Loops = data.Length >> 2;
            int* cachePtr = (int*)XcachePtr;
            int* dataPtr = (int*)x;

            if (IndexWritten == 0)
                return new SmartCacheInfo[0];

            //this part is just horrible slow
            for (int i = 0; i < data.Length; i++)
            {
                if (((data.Length - i) >> 2) == 0)
                    break;

                int index = -1;
                dataPtr = (int*)(x + i);

                //get the index, alot faster then List.IndexOf
                for (int j = 0; ; j++)
                {
                    if (((IndexWritten - j) >> 2) == 0)
                        break;

                    if (dataPtr[0] == ((int*)(XcachePtr + j))[0])
                    {
                        index = j;
                        break;
                    }
                }

                if (index == -1)
                {
                    //int not found, lets see how 
                    SmartCacheInfo inf = new SmartCacheInfo(-1, i, 4, false);
                    inf.instruction = Instruction.NEWDATA;
                    i += inf.Length - 1; //-1... loop does +1
                    callback(inf);
                }
                else
                {
                    SmartCacheInfo inf = new SmartCacheInfo(index, i, 0, true); //0 index for now just see what the length is of the MemCmp
                    inf.Length = MemCmp(data, i, RamCache, index);
                    ret.Add(inf);
                    i += inf.Length - 1; //-1... loop does +1
                }
            }
        }
        return ret.ToArray();
    }

Double looping is what's making it so slow. The data array contains 65535 bytes and so goes for the RamCache array. This code is btw some part of the Cache system I'm working at it's for my SSP project.

Answer 1

Sort the RamCache array or a copy of the array and use a Array.BinarySearch. If you cannot sort it, create a HashSet of the RamCache.