7
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Index out range if all bytes are zero. I'd give a chance to a simple if. How much performance matters? \$\endgroup\$ Commented May 18, 2017 at 17:03
  • \$\begingroup\$ I really need this method to pull as much performance as possible! I'll update my question to note that I do have a simple validation (starting byte equals zero) check before writing the stream into the empty byte[4096]. Thanks for pointing that out. \$\endgroup\$
    – Svek
    Commented May 18, 2017 at 17:34
  • 1
    \$\begingroup\$ If you need the last position often, and performance is important, may be the easier is to keep a lastIndexPosition variable with the info you need at hand \$\endgroup\$ Commented May 18, 2017 at 22:45
  • \$\begingroup\$ Array.IndexOf(myByteArray, 0) was not enough ? It gives you the index of the first empty byte, so the index+1 of the last not empty byte. (And -1 if array il totally empty) \$\endgroup\$ Commented May 22, 2017 at 12:35
  • \$\begingroup\$ @GuillaumeBeauvois - I can't guarantee that there will not be an empty byte in the middle of the array (ex: [+][+][+][+][ ][ ][ ][+][+][+][ ]...[ ] ). Although, I could not imagine why this would happen in 99.9% of the cases -- I just can't guarantee it. \$\endgroup\$
    – Svek
    Commented May 23, 2017 at 16:29

6 Answers 6

4
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ There might be zeroes (a.k.a. "empty bytes") in the byte array, so that's why I have to find it by getting the last byte with data only. \$\endgroup\$
    – Svek
    Commented May 18, 2017 at 17:30
  • \$\begingroup\$ Thats what my suggested solution will do. \$\endgroup\$
    – Heslacher
    Commented May 18, 2017 at 17:32
  • \$\begingroup\$ Svek, for counting to zero, not from zero. \$\endgroup\$ Commented May 18, 2017 at 17:32
  • \$\begingroup\$ No, as the question states most of the items are "empty" hence starting at 0 will be faster. \$\endgroup\$
    – Heslacher
    Commented May 18, 2017 at 17:34
  • \$\begingroup\$ @Heslacher - What I mean is [+][+][+][+][ ][ ][ ][+][+][+][ ]...[ ]. Does that illustrate the reason for going backwards? I've never seem this actually occur so far, this might be an impossible condition. \$\endgroup\$
    – Svek
    Commented May 18, 2017 at 17:36
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;       
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This won't work, because he mentioned there might be empty elements in between data, but he's only interested in the last element, where it's guaranteed to have no data after that. \$\endgroup\$ Commented May 19, 2017 at 0:02
  • \$\begingroup\$ There is no indicator of this in the Question. Just a comment posted at another answer. So how could I know? \$\endgroup\$
    – nidomiro
    Commented May 31, 2017 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.