Corefxlab: Resolve un-contiguous memory into contiguous memory

[msedi]

I'm often having the problem that I have to deal with large image volumes. Currently to run quickly over a volume and do image operations on the data, I need to copy the whole volume into one large block of memory. Assume that I have a volume with a matrix size of 512x512 and around 1000 images stored in float, I have doubled the amount of memory in my system only because I need the data contiguously in memory.

I don't know how to resolve this, but it would be convenient to a structure that merges all data into one let's say Span.

I'm "dreaming" of something that can be done like this:

float[] A = new float[1000];
float[] B = new float[1000];

Span<float> C = Span<T>.Merge(A, B);

where Span.Merge is defined as

static Span<T> Merge(params Span<T>[] spans)

In the end, only the internal indexer needs to take care of going into the right span when doing something like this (example from above)

float[] A = new float[1000];
float[] B = new float[1000];

Span<float> C = Span<T>.Merge(A, B);
for (int i=0; i<C.Length; i++) C[i] += 10;

Of course this can be managed by myself, but since Span is a struct, I'm not able to do it myself.

That would be awesome.

[ahsonkhan]

Have you tried looking into ReadOnlySequence? It supports discontiguous memory and obfuscates that away. https://github.com/dotnet/corefx/blob/master/src/System.Memory/ref/System.Memory.cs#L310-L346

cc @pakrym, @KrzysztofCwalina

[ahsonkhan]

cc @JeremyKuhne

[ahsonkhan]

Sample use:

```C#
var bufferSegment1 = new BufferSegment(new float[1000]);
BufferSegment bufferSegment2 = bufferSegment1.Append(new float[1000]);
var sequence = new ReadOnlySequence(bufferSegment1, 0, bufferSegment2, 1000);

foreach (ReadOnlyMemory segment in sequence)
{
ReadOnlySpan span = segment.Span;
for (int i = 0; i < span.Length; i++)
Console.Write(span[i] + ", ");
}
```

If that is not sufficient for your scenario, can you please file an issue in the corefx repo, as that is where Span and System.Memory live now (https://github.com/dotnet/corefx)? Thanks.

[msedi]

@ahsonkhan: Thank you for the comment. This is really nice. I did some performance tests on it and it seems that using the BufferSegment is equivalent, if not even faster than my original "copy into one block" solution. The benefit of your method is also that is not so memory hungry than my solution. Thanks a lot for pointing this out.

My only question is, why is the BufferSegment not "official" but only in the test methods?

[davidfowl]

We didn't ship an official "buffer linked list node" type outside of these test implementations and the implementation in pipelines. File an issue on corefx as a feature request if you'd like to see it.

[msedi]

@davidfowl: Thanks's, I will do.
@ahsonkhan: I made a mistake on my tests, so I have to redo some things, because I was also mistakenly assuming that I can run with one continuous index over the array. So in the end it's currently not really what I need, but I will an request. Do you think it makes sense to copy this post here into the corefx repo?

[davidfowl]

@msedi can you post the code you want to write and the code you wrote.

[ahsonkhan]

can you post the code you want to write and the code you wrote.

@msedi, any updates?

[msedi]

Hello, sorry for the late reply,

This is maybe going to be a larger text. Just to clarify a few terms in advance.
When I'm talking about an image volume, I mean a 3D volume that consists of a stack of individual slices.

To wrap the individual slices I have created a container called VoxelVolume. The VoxelVolumehas an indexer VoxelVolume[int sliceIndex] that returns a VolumeSliceclass. Each VolumeSlice has a method where I can get access to the data:

• float[] GetData(AreaDescriptor ad = null)
  That returns the internal data of the slice either completely, or only from a certain area in the full slice.

• void SetData(float[] data, AreaDescriptor = null)
  That sets the full data of to the slice or only a portion.

Also to clarify a few things, why it's not possible to access the data of the slice directly is first, because there are additional parameter on the slice, like orientation, etc. Another thing is that the slice can unload itself if the memory consumption of the whole system is getting low.

There are now occasions where I need to filter the data. One pretty easy thing would be to create a mean value for each pixel of the image in the surrounding area, first, of course in plane (x/y-direction), but also out of the plane (z-direction). To be fast I'm using pointers, but for the sake of brevity I leave this one out in the example below. Assuming a few simplifications that the volume is divisible by 10 and I don't care about the edges, although this would produce an error.

        VoxelVolume Filter(VoxelVolume volume, int filterSize)
        {
            VoxelVolume result = volume.Clone() as VoxelVolume;


            float[] aBuffer = new float[(filterSize * 2 + 1) * volume.NxNy];
            float[] aResult = new float[volume.NxNy];

            // Run over the slices.
            for (int SliceNo = 0; SliceNo < volume.Length; SliceNo++)
            {
                // Copy the data in a block
                int aTargetIndex = 0;
                for (int aSourceNo = SliceNo - filterSize; aSourceNo < SliceNo + filterSize; aSourceNo++)
                {
                    Array.Copy(volume[aSourceNo].GetData(), 0, aBuffer, aTargetIndex, volume.NxNy);
                    aTargetIndex += volume.NxNy;
                }

                double aSum = 0;

                for (int X = 0; X < volume.Nx; X++)
                for (int Y = 0; Y < volume.Ny; Y++)
                {
                    for (int z = 0; z < (filterSize * 2) + 1; z++)
                    for (int x = X - (filterSize * 2) + 1; x < X + (filterSize * 2) + 1; x++)
                    for (int y = Y - (filterSize * 2) + 1; y < Y + (filterSize * 2) + 1; y++)
                    {
                        aSum += aBuffer[(z * volume.NxNy) + (y * volume.Nx) + x];
                    }

                    aResult[(Y * volume.Nx) + X] = aSum / (double) ((filterSize * 2 + 1));
                }

                result[aSliceNo].SetData(aResult);
            }
        }

If course this works this way, but the final solution is that for performance reasons I also put this into a Parallel.For which consumes a lot of memory. I was hoping there would be a solution that abstracts the memory in a way I don't have to copy but also has the performance of the example above. BufferSegment would be interesting, but I still have to deal with the inidividual segments. Something like the code below would be good:

        VoxelVolume Filter(VoxelVolume volume, int filterSize)
        {
            VoxelVolume result = volume.Clone() as VoxelVolume;


            float[] aResult = new float[volume.NxNy];

            // Run over the slices.
            for (int SliceNo = 0; SliceNo < volume.Length; SliceNo++)
            {
                BufferSegment<float> aBufferSegment = new BufferSegment<>();

                // Copy the data in a block
                int aTargetIndex = 0;
                for (int aSourceNo = SliceNo - filterSize; aSourceNo < SliceNo + filterSize; aSourceNo++)
                {
                    aBufferSegment.Add(volume[aSourceNo].GetData());
                    aTargetIndex += volume.NxNy;
                }

                Span<float> aMemoryBlock = aBufferSegment.Span;

                double aSum = 0;

                for (int X = 0; X < volume.Nx; X++)
                for (int Y = 0; Y < volume.Ny; Y++)
                {
                    for (int z = 0; z < (filterSize * 2) + 1; z++)
                    for (int x = X - (filterSize * 2) + 1; x < X + (filterSize * 2) + 1; x++)
                    for (int y = Y - (filterSize * 2) + 1; y < Y + (filterSize * 2) + 1; y++)
                    {
                        aSum += aMemoryBlock[(z * volume.NxNy) + (y * volume.Nx) + x];
                    }

                    aResult[(Y * volume.Nx) + X] = aSum / (double) ((filterSize * 2 + 1));
                }

                result[aSliceNo].SetData(aResult);
            }

Does this makes sense?