Does UnsafeList.RemoveRange incorrectly use MemCpy instead of MemMove?

Unity Engine
, , , , ,
1

I was reading the implementation of UnsafeList.RemoveRange.

Here it is for reference:

  public unsafe void RemoveRange(int index, int count)
  {
    CheckIndexCount(index, count);
    index = CollectionHelper.AssumePositive(index);
    count = CollectionHelper.AssumePositive(count);
    if (count > 0)
    {
      int num = math.min(index + count, m_length);
      int num2 = sizeof(T);
      void* destination = (byte*)Ptr + index * num2;
      void* source = (byte*)Ptr + num * num2;
      UnsafeUtility.MemCpy(destination, source, (m_length - num) * num2);
      m_length -= count;
    }
  }

I was surprised to see the use of MemCpy, because the documentation of MemCpy contains this paragraph:

When the source and destination arrays overlap, the result isn’t guaranteed to be correct and you should use UnsafeUtility.MemMove instead.
Source: Unity - Scripting API: Unity.Collections.LowLevel.Unsafe.UnsafeUtility.MemCpy(void*,void*,ulong)

Questions:

  1. Aren’t destination and source overlapping if 2 * count < m_length - index?
  2. Does this mean that RemoveRange can lead to subtle bugs and should be avoided or is the documentation of MemCpy incomplete and the result is guaranteed in this case? For example it could be that MemCpy guarantees the result if the source pointer is greater than the destination pointer.
  3. Why does RemoveAt use a for loop instead of MemCpy/MemMove? Isn’t MemCpy/MemMove supposed to be faster?
    For reference here is the implementation of RemoveAt:
    public unsafe void RemoveAt(int index)
{
  CollectionHelper.CheckIndexInRange(index, m_length);
  index = CollectionHelper.AssumePositive(index);
  T* ptr = Ptr + index;
  T* ptr2 = ptr + 1;
  m_length--;
  for (int i = index; i < m_length; i++)
  {
    *(ptr++) = *(ptr2++);
  }
}
  4. Is my understanding correct that capping num to m_length is pretty useless because a) when collection checks are enabled this is already asserted by CheckIndexCount and b) when collection checks are disabled you can go out of bounds anyways by supplying a negative index?
2

Why not make a few test cases to confirm your hypothesis? It couldn’t have taken more time than to create this post. :wink:

How do you get to that calculation? There’s no 2*count in the code.
I didn’t check the code but I assume that any memcpy that were to overlap already fails the bounds checks respectively gets clamped.

3

Well, this is not supposed to be code. It’s just the condition for count, index and m_length to have an overlap in the source and destination memory. Maybe the condition makes more sense as

count < m_length - index - count

which is essentially the same but makes more sense. m_length-index is essentially all the space behind index which includes the number of removed elements (count) as well as the remaining elements that actually need to be moved down to index. By subracting count from that we get the number of elements that need to be moved down. If this amount is greater than count, we have an overlap


   index = 2
   count = 3
   m_length=10

0123456789
  |-||+++|
  56789
//-------
0156789xxx

Here we have a two element overlap. The 8 and 9 overlap with the original 5 and 6

This should be fine when the copy starts at the bottom and moves upwards. However when memcpy does too large steps or some strange optimisations it could potentially overwrite the overlap area before it’s copied. I think that is unlikely, especially since we move elements down. You generally have issues when moving memory upwards since you would need to start with the last element when you have overlap.

In the end memcpy also does loop over the memory. Though it may apply certain optimisations

2 Likes