C#•2y ago

✅ Which of these for-loops is more performant? How can I improve

public class Solution {
    public int[] DecodeOne(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;
        
        for (int i = 1; i < arr.Length; i++)
        {
            arr[i] = encoded[i-1]^arr[i-1];
        }

        return arr;
    }

    public int[] DecodeTwo(int[] encoded, int first)
    {
        var intSize = sizeof(int);
        var arr = new int[encoded.Length + 1];
        arr[0] = first;
        System.Buffer.BlockCopy(encoded, 0, arr, intSize, intSize * encoded.Length);
        
        for (int i = 1; i < arr.Length; i++)
        {
            arr[i] ^= arr[i-1];
        }

        return arr;
    }
}

public class Solution {
    public int[] DecodeOne(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;
        
        for (int i = 1; i < arr.Length; i++)
        {
            arr[i] = encoded[i-1]^arr[i-1];
        }

        return arr;
    }

    public int[] DecodeTwo(int[] encoded, int first)
    {
        var intSize = sizeof(int);
        var arr = new int[encoded.Length + 1];
        arr[0] = first;
        System.Buffer.BlockCopy(encoded, 0, arr, intSize, intSize * encoded.Length);
        
        for (int i = 1; i < arr.Length; i++)
        {
            arr[i] ^= arr[i-1];
        }

        return arr;
    }
}

Not sure if I'm thinking about this correctly or not. Would love to be pointed to resources regarding optimization if you have them. ~skr

23 Replies

Jimmacle•2y ago

benchmark them and find out?

Jimmacle•2y ago

https://github.com/dotnet/BenchmarkDotNet

GitHub

GitHub - dotnet/BenchmarkDotNet: Powerful .NET library for benchmar...

Powerful .NET library for benchmarking. Contribute to dotnet/BenchmarkDotNet development by creating an account on GitHub.

rabbit (she/he) <plural>OP•2y ago

I will try that later yes just trying to understand from a theoretical standpoint rn i.e. System.Buffer.BlockCopy versus multiple array indexes in loop also, it's not represented in my examples, but is previous element value cached with compiler optimization / can I output the IL code

rabbit (she/he) <plural>OP•2y ago

Aaron•2y ago

the first is marginally faster, at least on my machine the reason why is fairly simple, the second version does more work

rabbit (she/he) <plural>OP•2y ago

this is my final submission:

public class Solution {
    public int[] Decode(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;
        
        for (int i = 1; i < arr.Length; i++)
        {
            first = arr[i] = encoded[i-1] ^ first;
        }

        return arr;
    }
}

public class Solution {
    public int[] Decode(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;
        
        for (int i = 1; i < arr.Length; i++)
        {
            first = arr[i] = encoded[i-1] ^ first;
        }

        return arr;
    }
}

i suppose copying is more expensive than having multiple indexes i loop hoist myself instead of relying on the compiler to do it thx all

DaVinki•2y ago

Don't forget spans

rabbit (she/he) <plural>OP•2y ago

|          Method |     N |       Mean |    Error |   StdDev |
|---------------- |------ |-----------:|---------:|---------:|
|          Decode |  1000 |   859.4 ns |  1.70 ns |  1.59 ns |
| DecodeWithSpans |  1000 |   843.9 ns |  2.06 ns |  1.72 ns |
|          Decode | 10000 | 8,013.4 ns | 31.75 ns | 26.52 ns |
| DecodeWithSpans | 10000 | 7,857.6 ns | 13.34 ns | 10.41 ns |

|          Method |     N |       Mean |    Error |   StdDev |
|---------------- |------ |-----------:|---------:|---------:|
|          Decode |  1000 |   859.4 ns |  1.70 ns |  1.59 ns |
| DecodeWithSpans |  1000 |   843.9 ns |  2.06 ns |  1.72 ns |
|          Decode | 10000 | 8,013.4 ns | 31.75 ns | 26.52 ns |
| DecodeWithSpans | 10000 | 7,857.6 ns | 13.34 ns | 10.41 ns |

namespace Xor;

public static class Xor
{
    public static int[] Decode(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;

        for (int i = 1; i < arr.Length; i++)
        {
            first = arr[i] = encoded[i - 1] ^ first;
        }

        return arr;
    }

    public static int[] DecodeWithSpans(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;

        var encodedSpan = encoded.AsSpan();
        var arrSpan = arr.AsSpan(1);
        for (int i = 0; i < arrSpan.Length; i++)
        {
            first = arrSpan[i] = encodedSpan[i] ^ first;
        }

        return arr;
    }
}

namespace Xor;

public static class Xor
{
    public static int[] Decode(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;

        for (int i = 1; i < arr.Length; i++)
        {
            first = arr[i] = encoded[i - 1] ^ first;
        }

        return arr;
    }

    public static int[] DecodeWithSpans(int[] encoded, int first)
    {
        var arr = new int[encoded.Length + 1];
        arr[0] = first;

        var encodedSpan = encoded.AsSpan();
        var arrSpan = arr.AsSpan(1);
        for (int i = 0; i < arrSpan.Length; i++)
        {
            first = arrSpan[i] = encodedSpan[i] ^ first;
        }

        return arr;
    }
}

DaVinki•2y ago

Honestly if you really want to prematurely optimize, you can even go as far as making your decoded array uninitialized as long as you can guarantee you are setting all elements before using any of them Might score you some nanoseconds lol

cap5lut•2y ago

but then also Unsafe.Add and Unsafe.IsAddressLessThan and get rid of bound checks ;p

Aaron•2y ago

there's this thing called restraint practice it

DaVinki•2y ago

100% this

cap5lut•2y ago

but then it depends on the size again iirc, as u would have to pin it or have it on the stack i thought of going that way and vectorization for my raytracer, but then i simply threw it on the graphics card via opencl xD

DaVinki•2y ago

Honestly just throw it on the stack like you said You’re right

cap5lut•2y ago

that depends on the actual context, the stack is after all more limited than the heap there are alternatives after all, simply pre-pinned buffers or unmanaged memory allocation to throw the data into while "generating" it

Aaron•2y ago

no? you don't need to pin to have a ref that's the entire point of having a ref instead of a pointer

cap5lut•2y ago

but its about having 2 refs and comparing them hmmm, wait, i think i dont know enough about that

Aaron•2y ago

Unsafe.AreEqual? or Unsafe.IsAddrLessThan

cap5lut•2y ago

its about using these methods

Aaron•2y ago

both are fine without pinning thats, again, the point of using references instead of pointers for this if you had to pin, you could just use a pointer instead

cap5lut•2y ago

ah okay, good to know ;p never had such hot paths where it was an issue 😂

Aaron•2y ago

(it pretty much never is)

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

✅ Which of these for-loops is more performant? How can I improve