Get the length of data within a buffer (by getting the position of the last byte with data)

Question

Background. I start out with a completely empty byte[4096]. As data streams into my application, the byte[4096] gets filled with data starting from first position.

This results in a byte array that is partially filled, but mostly empty, like so...

                0  1  2  3  4  5  6  7  8                       4096
byte[4096] --> [+][+][+][+][+][+][+][+][+][ ][ ][ ][ ][ ][ ] ... [ ]

[+] = Data
[ ] = Empty

I am trying to quickly obtain the position of the last byte with data.

---

My Question for Code Review

I'm looking for feedback for performance and possibly any correctness in unanticipated cases of this code block:

/// <summary>
/// Get the position of the last byte with data
/// </summary>
public static int GetPositionOfLastByteWithData(this byte[] array)
{
    int i = array.Length - 1;
    // find the end of the buffer by iterating backwards
    while (array[i] == 0) --i;

    return i;
}

Note: This method will throw an exception in the event that the byte[] passed in is totally blank/empty. In the actual use, I do validate that there is data in the byte array before it gets to this method. This method is aimed squarely for high performance.

Answer 1

If your array is completely "empty" your current method will throw an exeption because it will try to get array[-1].

Just use a for loop starting at 0 and if you find the first 0 return index-1. For the case that the whole buffer is filled return array.Length - 1.

Update:

As it seems it is possible that there are 0 values in between valid data like [+][+][+][+][ ][ ][ ][+][+][+][ ]...[ ]. Hence going from start to end of the array doesn't seem a reliable action.

Using a for loop instead of using the while loop enables your code to do the empty check as well like so

public const int NotFound = -1;
public static int GetPositionOfLastByteWithData(this byte[] array)
{
    for (int i = array.Length - 1; i > -1; i--)
    {
        if (array[i] > 0) { return i; }
    }
    return NotFound;
}  

---

As you are talking about streams in your question, wouldn't it be better to store the index of the last written byte ? This would be the easiest and the most safe variant because, assuming you are reading exactly 10 bytes from the stream and later on you need exactly these 10 bytes to restore the read data. If the last byte of that stream would be a 0 like
[+][+][+][+][+][+][+][+][+][ ][ ][ ][ ][ ]...[ ]

both methods, yours and mine, would return 8 but the really read byte count would be 9.

Answer 2

OK, only if you're really looking for performance (please profile, profile and then profile again) otherwise just go with Heslacher's review and keep your code easy to read (which is almost always the best thing to do).

Scanning byte by byte is slow because:

• You need to dereference a pointer for each read.
• You should check generated assembly code (at run-time) but if compiler can't safely remove bounds checking then it will hit performance.
• You need a comparison for each byte (and possibly a jump but branch prediction will work pretty well in this case then we can ignore this).

Given that any modern CPU is able to compare 32 bits as fast as 8 bits and that there are good chances that reading/comparing 4 bytes at a time is more efficient than reading 1 byte (especially assuming that memory is aligned, you might check how to align memory in C#, unfortunately it's not trivial and painless).

You need to use unsafe code then it may not be applicable in your case but it's a possible (untested!) proof of concept:

public unsafe static int GetPositionOfLastByteWithData(this byte[] array)
{
    fixed(byte* pArray = array)
    {
        for (int* ptr=(int*)pArray; ptr != pArray; --ptr)
        {
            if (*ptr != 0)
            {
                // Compare individual bytes, a simple
                // if ((*ptr & 0xff000000) != 0)
                // Repeated for each byte might be enough but
                // You may want to try searching for first set bit
                // Because it's much faster.
            }
        }
    }

    return array.Length - 1;
}

You might want to adjust the beginning of the search to start with an aligned address (and do a normal comparison for the bytes left off). On 64 bit machines you should compare 8 bytes at a time (long).

You may check real-world strlen() implementations for some more ideas to optimize your code here.

Answer 3

The only way to quickly get the last index is to store this index after each write operation. Other approaches will not, quote, "pull as much performance as possible".

I have a feeling that this problem you are having is a symptom of a much larger design issue. In general you should be able to just pick a correct data type, in this case it's MemoryStream, and work with that. You don't have to come up with your own ill-thought-out implementation.

var ms = new MemoryStream(new byte[4096]);
ms.Write(....);
ms.Write(....);
var lastIndex = ms.Length - 1;

For multi-threading scenarios you can segment your array using MemoryStream(byte[], int, int) constructor or ArraySegment<T> class. Both are cheap.

Answer 4

If performance wasn't an issue you could nicely solve it with LINQ and the new anonymous tuples in C# 7.

The first extension would give you the items backwards:

public static IEnumerable<(T Item, int Index)> Backwards<T>(this IList<T> values)
{
    for (int i = values.Count - 1; i >= 0; i--) yield return (Item: values[i], Index: i);
}

The second one would find the first non-zero item and return its index.

public static int LastDataBytePosition(this byte[] bytes)
{
    var firstNotZero = 
        bytes
            .Backwards()
            .SkipWhile(b => b.Item == 0)
            .Take(1)
            .ToList();

    return firstNotZero.Any() ? firstNotZero.Single().Index : -1;       
}

Answer 5

Since you're not changing any value, I would go with using multiple threads. Depending on how many cores your CPU has, break your array into smaller chunks and let each thread does the search.

For example, split into two. If the upper-hand thread finds the index, return the result, but if the lower-hand thread finds an index, wait for the other thread to finish because it has higher priority and make sure it didn't find anything, then return the result. In case upper-hand thread doesn't find anything, you already have the result for the rest of the array, so it's faster this way.

Answer 6

To increase performance you could use the concept of Binary search:

1. look at the length/2 index (= Split the array in two parts)
2. If this value contains data take the right array-part, if not the left and start at step 1 again.
3. if your remaning array has length 1 you found your index

I did not test my 'code' but you will get the idea, how it works. This code will only work if you have no empty indices between the data.