Jagged array, copy with offset

Question

I am trying to copy one jagged array into another jagged array with given offset. I came up with the following:

private void CopyWithOffset(char[][] buffer, (int row, int col) offset)
{
    if (buffer == null) throw new ArgumentNullException(nameof(buffer));

    for (var row = 0; row < buffer.Length; row++)
    {
        try
        {
            for (var col = 0; col < buffer[row].Length; col++)
            {
                try
                {
                    _buffer[row + offset.row][col + offset.col] = buffer[row][col];
                }
                catch (IndexOutOfRangeException){}
            }
        } catch(IndexOutOfRangeException){}
    }
}

Unfortunately it is very slow. Is there any way to do it faster?

It is slow because you hit the IndexOutOfRange exception and this is very costly in terms of performance. You should try to avoid going out of index — Steve, Jul 29 '17 at 20:33
Apart from the anti-pattern that you catch exceptions in planned way if you need to gain more performance, before using Parralel.For, try to use SIMD instructions which are implemented via Vector. http://instil.co/2016/03/21/parallelism-on-a-single-core-simd-with-c/ — Eduard Lepner, Jul 29 '17 at 20:40

score 0 · Answer 1 · answered Jul 30 '17 at 05:28

0

As noted in this comment, exception handling is very expensive, and if you use it as a normal control-flow mechanism in your code, it will make that code very slow.

You can easily avoid exceptions by just writing the code so that it doesn't use out-of-range index values in the first place:

private void CopyWithOffset(char[][] buffer, (int row, int col) offset)
{
    if (buffer == null) throw new ArgumentNullException(nameof(buffer));

    for (var row = 0; row < buffer.Length; row++)
    {
        for (var col = 0; col < buffer[row].Length ; col++)
        {
            int i = row + offset.row;

            if (i < _buffer.Length)
            {
                int j = col + offset.col;

                if (j < _buffer[i].Length)
                {
                    _buffer[i][j] = buffer[row][col];
                }
            }
        }
    }
}

answered Jul 30 '17 at 05:28

Peter Duniho

68,759
7
102
136

It is still slow. Basically it is doing lot more work than it should be doing. Just imagine that you have array 50x50 and you want coppy an array also 50x50 with offset [30,30]. Your algo would do 50 squared operations but to copy the array with offset [30,30] you should need only 20 squared operations. So you can imagine how slow it is when you copy arrays like 3000x3000 :). – Jan Tajovsky Jul 31 '17 at 01:03
_"So you can imagine how slow it is when you copy arrays like 3000x3000"_ -- no, I can't. It depends all on context, but _one_ copy of data 3000x3000 is only 9 million elements, which on a modern computer is a cake walk. In any case, the code _you_ posted is _greatly_ slowed by the use of exceptions for bounds-checking. The above _will_ be _much_ faster than your original code. If you have some _specific_ performance goal, you need to post a good **[mcve]** that demonstrates your current performance and state in precise terms what your goal is and why you think it's achievable. – Peter Duniho Jul 31 '17 at 01:08
(Naturally, the actual cost of the exception-based bounds checking depends on how often you actually throw an exception. Again, without a good **[mcve]**, it's impossible to know. I mean, it's possible your code _never_ throws an exception. But you haven't shared enough information for anyone here to know whether that's the case.) – Peter Duniho Jul 31 '17 at 01:09
" If you have some specific performance goal" -- Yes, I have specific performance goal. Generality. It should run fastest as possible for any kind of input data. Therefore, it should be general. The method signature should be enough. – Jan Tajovsky Jul 31 '17 at 01:46
"run fastest as possible" is not a specific performance goal. Put another way, how do you know you have not already achieved that goal? – Peter Duniho Jul 31 '17 at 01:49

score 0 · Accepted Answer · answered Jul 31 '17 at 03:46

As suggested by @Steve avoiding going out of index and iterating over necessary part of an array instead of iterating over the entire array pays of greatly.

Combine it with Parallel.For and Array.Copy (it should make use of SIMD extension more info here) and one pretty much have lighting fast array copy function.

public static void CopyWithOffset(char[][] buffer, int x, int y)
{
    var rowStart = Math.Max(Math.Min(y, _buffer.Length), 0);
    var rowLenght = _buffer.Length + Math.Min(y, 0);

    Parallel.For(rowStart, rowLenght, row =>
    {
        var colStart = Math.Max(Math.Min(x, _buffer[row].Length), 0);
        var colLength = _buffer[row].Length + Math.Min(x, -1);

        Array.Copy(buffer[row - y], colStart - x, _buffer[row], colStart, colLength);
    });
}

Jagged array, copy with offset

2 Answers2