9
\$\begingroup\$

I've written some utilities to read text from streams. One of these, the ReadTo method, is to read text from a specified stream until a given text is encountered, behaving like string.IndexOf, but with streams.
Really, it's quite fast. But I'd like to know if anyone knows any way to make it even faster, as it's used in a very performance-critical part of a program I'm developing.

/// <summary>
/// Provides utilities to manage streams.
/// </summary>
public static class StreamUtils
{

    private const int DefaultBufferSize = 1024;

    /// <summary>
    /// Enumerate buffers from a specified stream.
    /// </summary>
    /// <param name="stream">The stream to read.</param>
    /// <param name="bufferSize">The size of each buffer.</param>
    /// <param name="count">How many bytes to read. Negative values mean read to end.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static IEnumerable<byte[]> EnumerateBuffers(this Stream stream, int bufferSize = DefaultBufferSize, long count = -1)
    {
        byte[] buffer = new byte[bufferSize];
        do
        {
            long read = stream.Read(buffer, 0, bufferSize);
            if (read < 1)
                break;
            if (count > -1)
            {
                count -= read;
                if (count < 0)
                    read += count;
            }
            if (read == bufferSize)
                yield return buffer;
            else
            {
                byte[] newBuffer = new byte[read];
                Buffer.BlockCopy(buffer, 0, newBuffer, 0, (int)read);
                yield return newBuffer;
                break;
            }
        } while (true);
    }

    /// <summary>
    /// Enumerate substrings from a specified stream.
    /// </summary>
    /// <param name="stream">The stream to read.</param>
    /// <param name="bufferSize">The length of each substring.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static IEnumerable<string> EnumerateSubstrings(this Stream stream, int bufferSize = DefaultBufferSize) => stream.EnumerateSubstrings(Encoding.Default, bufferSize);

    /// <summary>
    /// Enumerate substrings from a specified stream.
    /// </summary>
    /// <param name="stream">The stream to read.</param>
    /// <param name="encoding">The encoding to use.</param>
    /// <param name="bufferSize">The length of each substring.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static IEnumerable<string> EnumerateSubstrings(this Stream stream, Encoding encoding, int bufferSize = DefaultBufferSize) => from byte[] buffer in stream.EnumerateBuffers(bufferSize) select encoding.GetString(buffer);

    /// <summary>
    /// Read the current stream until a specified string is encountered.
    /// </summary>
    /// <param name="stream">The source stream.</param>
    /// <param name="separator">The string that marks the end.</param>
    /// <param name="bufferSize">The size of the buffers.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static string ReadTo(this Stream stream, string separator, int bufferSize = DefaultBufferSize) => stream.ReadTo(separator, Encoding.Default, bufferSize);

    /// <summary>
    /// Read the current stream until a specified string is encountered.
    /// </summary>
    /// <param name="stream">The source stream.</param>
    /// <param name="separator">The string that marks the end.</param>
    /// <param name="encoding">The encoding to use.</param>
    /// <param name="bufferSize">The size of the buffers.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static string ReadTo(this Stream stream, string separator, Encoding encoding, int bufferSize = DefaultBufferSize)
    {
        // This method requires seeking, so ensure that the specified stream supports it.
        if (!stream.CanSeek)
            throw new NotSupportedException();
        // This StringBuilder will build the resulting text. Using this to avoid too many string reallocations.
        StringBuilder text = new StringBuilder();
        bool hasSuffix = false;
        string endingSeparator = null;
        // Retrieve how many bytes is the specified separator long. This will be necessary to handle some seekings on the stream.
        int separatorByteLength = encoding.GetByteCount(separator);
        // Iterate through each substring in the stream. Each one is a buffer converted to a string using a specified encoding.
        foreach (string substring in stream.EnumerateSubstrings(encoding, bufferSize))
        {
            // Retrieve how many bytes is the current substring long. Again, useful for seekings.
            int substringByteLength = encoding.GetByteCount(substring);
            // Check out whether the previous substring had a suffix.
            if (hasSuffix)
            {
                // If it had, then verify whether the current substring starts with the remaining part of the separator.
                if (substring.StartsWith(separator.Substring(endingSeparator.Length)))
                {
                    // In that case, seek till before the separator and break the loop.
                    stream.Seek(substringByteLength - encoding.GetByteCount(endingSeparator), SeekOrigin.Current);
                    break;
                }
                // If the code reached here, then the previous suffix were not part of a separator, as the whole of the separator cannot be found.
                hasSuffix = false;
                text.Append(endingSeparator);
            }
            // If the current substring starts with the separator, just skip it and break the loop, so the StringBuilder will only contain previous substrings.
            if (substring.StartsWith(separator))
                break;
            {
                // Check out whether the current substring contains the separator.
                int separatorIndex = substring.IndexOf(separator);
                if (separatorIndex != -1)
                {
                    // If that's the case, take this substring till the previously found index, ...
                    string newSubstring = substring.Remove(separatorIndex);
                    // ...then seek the current stream before the separator, ...
                    stream.Seek(encoding.GetByteCount(newSubstring) - substringByteLength, SeekOrigin.Current);
                    /// ...and finally append the new substring (the one before the separator) to the StringBuilder.
                    text.Append(newSubstring);
                    break;
                }
            }
            // Check out whether the current substring ends with the specified separator.
            if (substring.EndsWith(separator))
            {
                // If it does, go back as many bytes as the separator is long within the stream.
                stream.Seek(-separatorByteLength, SeekOrigin.Current);
                // Then, append this substring till before the specified separator to the StringBuilder.
                text.Append(substring.Remove(substring.Length - separator.Length));
                break;
            }
            // Sometimes, it might happen that the separator is divided between the current substring and the next one.
            // So, see whether the current substring ends with just one part (even one only character) of the separator.
            endingSeparator = separator;
            do
                // Remove the last character from the 'ending separator'.
                endingSeparator = endingSeparator.Remove(endingSeparator.Length - 1);
                // If the ending separator isn't empty yet and the current substring doesn't end with it,
                // continue the loop.
            while (!(endingSeparator.Length == 0 || substring.EndsWith(endingSeparator)));
            // At this time, the ending separator will be an initial part of the specified separator,
            // which is a 'suffix' of the current substring.
            // Push the length of the suffix on the stack, so I'll avoid to call the Length getter accessor multiple times.
            int suffixLength = endingSeparator.Length;
            // If the suffix is empty, that means the current string doesn't end with even just a part of the separator.
            // Therefore, just append the current string to the StringBuilder.
            if (suffixLength == 0)
                text.Append(substring);
            else
            {
                // If rather the suffix isn't empty, then mark this with the boolean hasSuffix and
                // append the current substring only till before the suffix.
                hasSuffix = true;
                text.Append(substring.Remove(substring.Length - suffixLength));
            }
        }
        return text.ToString();
    }
}

Usage sample:

string text = "Hello world, this is a test";
Encoding encoding = Encoding.UTF8;
using (Stream stream = new MemoryStream(encoding.GetBytes(text)))
{
    string substring = stream.ReadTo(", this", encoding);
    // substring == "Hello world"
}
\$\endgroup\$
  • \$\begingroup\$ You must not edit the code when answers have been posted. It can and usually does invalidate them. I rolled back your last couple of edits. \$\endgroup\$ – t3chb0t Sep 3 at 15:10
  • \$\begingroup\$ Ok, I didn't know. Thanks \$\endgroup\$ – Davide Cannizzo Sep 3 at 15:12
3
\$\begingroup\$

By altering/ specifying the string comparer from the default StringComparison.CurrentCulture to StringComparison.Ordinal you can win a lot.

Also note that sometimes Buffer.BlockCopy(buffer, 0, newBuffer, 0, (int)read) is slower than Array.Copy(buffer, 0, newBuffer, 0, (int)read).

I ran your code with a Stopwatch, added these small changes and ran it as few times again and again and averaged on. original 401986 ticks updated 101224 ticks

If you like to really know if you gain something instrument it with BenchmarkDotNet, cool nuget package that shows where "it hurts"

This is by no means all you could do, I would start to look at removing things that cause "newing up classes" as that takes a lot of time and work with span or even ReadOnlySpan. The linq method you use is such class that generates a class in memory that needs to be taken to the GC, over time this starts to slow things down.

Here is your code with the small tweeks

public static class StreamUtils
{

    private const int DefaultBufferSize = 1024;

    /// <summary>
    /// Enumerate buffers from a specified stream.
    /// </summary>
    /// <param name="stream">The stream to read.</param>
    /// <param name="bufferSize">The size of each buffer.</param>
    /// <param name="count">How many bytes to read. Negative values mean read to end.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static IEnumerable<byte[]> EnumerateBuffers(this Stream stream, int bufferSize = DefaultBufferSize, long count = -1)
    {
        byte[] buffer = new byte[bufferSize];
        do
        {
            long read = stream.Read(buffer, 0, bufferSize);
            if (read < 1)
                break;
            if (count > -1)
            {
                count -= read;
                if (count < 0)
                    read += count;
            }
            if (read == bufferSize)
                yield return buffer;
            else
            {
                byte[] newBuffer = new byte[read];
                Array.Copy(buffer, 0, newBuffer, 0, (int)read);
                //Buffer.BlockCopy(buffer, 0, newBuffer, 0, (int)read);
                yield return newBuffer;
                break;
            }
        } while (true);
    }

        // A very simple and efficient memmove that assumes all of the
        // parameter validation has already been done.  The count and offset
        // parameters here are in bytes.  If you want to use traditional
        // array element indices and counts, use Array.Copy.
        [System.Security.SecuritySafeCritical]  // auto-generated
        [ResourceExposure(ResourceScope.None)]
        [MethodImplAttribute(MethodImplOptions.InternalCall)]
        internal static extern void InternalBlockCopy(Array src, int srcOffsetBytes,
            Array dst, int dstOffsetBytes, int byteCount);


        /// <summary>
        /// Enumerate substrings from a specified stream.
        /// </summary>
        /// <param name="stream">The stream to read.</param>
        /// <param name="bufferSize">The length of each substring.</param>
        /// <returns></returns>
        /// <exception cref="ArgumentException"></exception>
        /// <exception cref="ArgumentNullException"></exception>
        /// <exception cref="IOException"></exception>
        /// <exception cref="DecoderFallbackException"></exception>
        /// <exception cref="NotSupportedException"></exception>
        /// <exception cref="ObjectDisposedException"></exception>
        public static IEnumerable<string> EnumerateSubstrings(this Stream stream, int bufferSize = DefaultBufferSize) 
            => stream.EnumerateSubstrings(Encoding.Default, bufferSize);

    /// <summary>
    /// Enumerate substrings from a specified stream.
    /// </summary>
    /// <param name="stream">The stream to read.</param>
    /// <param name="encoding">The encoding to use.</param>
    /// <param name="bufferSize">The length of each substring.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static IEnumerable<string> EnumerateSubstrings(this Stream stream, Encoding encoding, int bufferSize = DefaultBufferSize) 
            => from byte[] buffer in stream.EnumerateBuffers(bufferSize) select encoding.GetString(buffer);



    /// <summary>
    /// Read the current stream until a specified string is encountered.
    /// </summary>
    /// <param name="stream">The source stream.</param>
    /// <param name="separator">The string that marks the end.</param>
    /// <param name="bufferSize">The size of the buffers.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static string ReadTo(this Stream stream, string separator, int bufferSize = DefaultBufferSize) => stream.ReadTo(separator, Encoding.Default, bufferSize);

    /// <summary>
    /// Read the current stream until a specified string is encountered.
    /// </summary>
    /// <param name="stream">The source stream.</param>
    /// <param name="separator">The string that marks the end.</param>
    /// <param name="encoding">The encoding to use.</param>
    /// <param name="bufferSize">The size of the buffers.</param>
    /// <returns></returns>
    /// <exception cref="ArgumentException"></exception>
    /// <exception cref="ArgumentNullException"></exception>
    /// <exception cref="IOException"></exception>
    /// <exception cref="DecoderFallbackException"></exception>
    /// <exception cref="NotSupportedException"></exception>
    /// <exception cref="ObjectDisposedException"></exception>
    public static string ReadTo(this Stream stream, string separator, Encoding encoding, int bufferSize = DefaultBufferSize)
    {
        // This method requires seeking, so ensure that the specified stream supports it.
        if (!stream.CanSeek)
            throw new NotSupportedException();
        // This StringBuilder will build the resulting text. Using this to avoid too many string reallocations.
        StringBuilder text = new StringBuilder();
        bool hasSuffix = false;
        string endingSeparator = null;
        // Retrieve how many bytes is the specified separator long. This will be necessary to handle some seekings on the stream.
        int separatorByteLength = encoding.GetByteCount(separator);
        // Iterate through each substring in the stream. Each one is a buffer converted to a string using a specified encoding.
        foreach (string substring in stream.EnumerateSubstrings(encoding, bufferSize))
        {
            // Retrieve how many bytes is the current substring long. Again, useful for seekings.
            int substringByteLength = encoding.GetByteCount(substring);
            // Check out whether the previous substring had a suffix.
            if (hasSuffix)
            {
                // If it had, then verify whether the current substring starts with the remaining part of the separator.
                if (substring.StartsWith(separator.Substring(endingSeparator.Length),StringComparison.Ordinal))
                {
                    // In that case, seek till before the separator and break the loop.
                    stream.Seek(substringByteLength - encoding.GetByteCount(endingSeparator), SeekOrigin.Current);
                    break;
                }
                // If the code reached here, then the previous suffix were not part of a separator, as the whole of the separator cannot be found.
                hasSuffix = false;
                text.Append(endingSeparator);
            }
            // If the current substring starts with the separator, just skip it and break the loop, so the StringBuilder will only contain previous substrings.
            if (substring.StartsWith(separator,StringComparison.Ordinal))
                break;
            {
                // Check out whether the current substring contains the separator.
                int separatorIndex = substring.IndexOf(separator,StringComparison.Ordinal);
                if (separatorIndex != -1)
                {
                    // If that's the case, take this substring till the previously found index, ...
                    string newSubstring = substring.Remove(separatorIndex);
                    // ...then seek the current stream before the separator, ...
                    stream.Seek(encoding.GetByteCount(newSubstring) - substringByteLength, SeekOrigin.Current);
                    /// ...and finally append the new substring (the one before the separator) to the StringBuilder.
                    text.Append(newSubstring);
                    break;
                }
            }
            // Check out whether the current substring ends with the specified separator.
            if (substring.EndsWith(separator,StringComparison.Ordinal))
            {
                // If it does, go back as many bytes as the separator is long within the stream.
                stream.Seek(-separatorByteLength, SeekOrigin.Current);
                // Then, append this substring till before the specified separator to the StringBuilder.
                text.Append(substring.Remove(substring.Length - separator.Length));
                break;
            }
            // Sometimes, it might happen that the separator is divided between the current substring and the next one.
            // So, see whether the current substring ends with just one part (even one only character) of the separator.
            endingSeparator = separator;
            do
                // Remove the last character from the 'ending separator'.
                endingSeparator = endingSeparator.Remove(endingSeparator.Length - 1);
                // If the ending separator isn't empty yet and the current substring doesn't end with it,
                // continue the loop.
            while (!(endingSeparator.Length == 0 || substring.EndsWith(endingSeparator,StringComparison.Ordinal)));
            // At this time, the ending separator will be an initial part of the specified separator,
            // which is a 'suffix' of the current substring.
            // Push the length of the suffix on the stack, so I'll avoid to call the Length getter accessor multiple times.
            int suffixLength = endingSeparator.Length;
            // If the suffix is empty, that means the current string doesn't end with even just a part of the separator.
            // Therefore, just append the current string to the StringBuilder.
            if (suffixLength == 0)
                text.Append(substring);
            else
            {
                // If rather the suffix isn't empty, then mark this with the boolean hasSuffix and
                // append the current substring only till before the suffix.
                hasSuffix = true;
                text.Append(substring, 0, substring.Length - suffixLength);
            }
        }
        return text.ToString();
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ sometimes Buffer.BlockCopy is slower than Array.Copy - can you provide some information to support this so far theory? OP should use ReadOnlySpan in place of what exactly? \$\endgroup\$ – t3chb0t Sep 2 at 16:57
  • 1
    \$\begingroup\$ BenchmarkDotNet, cool nuget package that shows where "it hurts" - by doing what? Is it better than a profiler? \$\endgroup\$ – t3chb0t Sep 2 at 17:02
  • \$\begingroup\$ @t3chb01, Well it's a different tool, shows different information. I like it when I tune code have a look at the documentation benchmarkdotnet.org/articles/overview.html \$\endgroup\$ – PPann Sep 2 at 19:09
4
\$\begingroup\$

Problems:

  • EnumerateSubstrings and ReadTo do not work correctly with variable-width encodings, multi-byte encodings and surrogate pairs, because they do not take into account that characters can be split across buffer boundaries. This can cause a variety of problems.
  • In some cases, ReadTo fails to find the separator if it's longer than the buffer size (this always happens if the separator is more than twice as long).
  • ReadTo also fails to detect matches across buffer boundaries when separator contains a prefix of itself and there's both a partial and a full match across the boundary. For example, try reading up to "aab" in "..aaab.." with a buffer size of 4.

Performance:

  • As has been pointed out already, StringComparison.Ordinal is a lot faster - because it just compares code point values without taking culture-specific rules into account. For example, a culture-aware comparison will see that "\u00E9" and "e\u0301" both represent an é, but an ordinal comparison will treat them as unequal. Which one to choose first and foremost depends on the behavior you need.
  • The StartsWith and EndsWith checks are useless - substring.IndexOf(separator) already takes care of those situations.
  • For long separators, the do-while loop that checks if the buffer ends with a prefix of the given separator involves a fair amount of string allocations. If you need culture-specific string comparisons then it might be faster to combine the end of the last buffer with the current buffer so you can keep using IndexOf. If ordinal comparisons are fine for your purposes, then a modified Knuth-Morris-Pratt algorithm could be useful here. Both of these should also help with solving the cross-boundary partial matches problem.
  • Using an 8KB buffer is roughly 25% faster on my system. I'd recommend testing different sizes before deciding on a good (default) size.
  • Instead of first creating a substring with string.Remove, use the StringBuilder.Append(string, int, int) overload.

Other notes:

  • The encoding returned by Encoding.Default depends on system settings, which means you can get different results on different systems. Encoding.UTF8 would be a safer default.
  • It would be nice if the NotSupportedException exception contained a message that said what exactly it doesn't support.
  • If you're going to guard against invalid parameters, then also be sure to check that the separator isn't null or empty. I'd also set the encoding and buffer size to some sane default value if they're null or too low, respectively.
  • ReadTo contains a lot of superfluous comments. For example, the first check already makes it obvious that the method requires seeking, and the whole purpose of a StringBuilder is to build up strings efficiently. Repeating that in comments is just adding clutter.
  • I'd recommend using var to cut down on typename repetition.
  • Add some empty lines to break up long parts of code and to make it easier to distinguish between different 'blocks' of code (such as unrelated if statements).
  • Inconsistent use of braces makes it more difficult to see control flow, which makes it easier to make mistakes.
  • It's good to see methods being documented. A few minor things: 'the length of each substring' sounds like it's measured in characters, but it's actually the number of bytes. 'The size of the buffers' suggests that the methods use multiple buffers internally, so I'd make that singular instead.
\$\endgroup\$
  • \$\begingroup\$ I updated the code in my question as per some of your and other's suggestions. However, I cannot figure out how could some of your points be true: I've just noticed, as you pointed out, that my method would fail on if the specified separator is twice of more longer than the specified buffer size, but how could it fail on with separators just longer than the buffer size (less long than twice the buffer size). \$\endgroup\$ – Davide Cannizzo Sep 3 at 15:11
  • \$\begingroup\$ The user @t3chb0t just rolled out my last changes. He was right, indeed. I was unaware of edits invalidating answers. Anyway, I don't understand how my method could fail on with separators that are longer than the buffer size and less long than twice it. Can you please explain me? \$\endgroup\$ – Davide Cannizzo Sep 3 at 15:14
  • 1
    \$\begingroup\$ It happens when a match stretches across 3 buffers, which can be achieved with a separator that's bufferSize + 2 long. Try finding "abbbbc" in "aaaabbbbcccc", with a buffer size of 4. \$\endgroup\$ – Pieter Witvoet Sep 3 at 15:18
  • \$\begingroup\$ I got that. I was referring to the case where the separator is longer than the buffer size, but shorter than twice as long. \$\endgroup\$ – Davide Cannizzo Sep 3 at 15:25
  • 1
    \$\begingroup\$ "abbbbc" is longer than 4, but shorter than 8. \$\endgroup\$ – Pieter Witvoet Sep 3 at 15:30
3
\$\begingroup\$
    if (read == bufferSize)
      yield return buffer;
    else

Be aware that repeatedly yield return the same buffer is rather risky. Imagine the following use case where all returned buffers are cached for later use for some reason:

  List<byte[]> buffers = new List<byte[]>();
  using (FileStream stream = File.OpenRead(path))
  {
    foreach (byte[] buffer in stream.EnumerateBuffers(1024))
    {
      buffers.Add(buffer);
    }
  }

The result is that all items in buffers are references to the same buffer, hence they all have the same (the last returned with full length) set of bytes.

I think you should go with a much simpler approach:

public static IEnumerable<byte[]> EnumerateBuffers(this Stream stream, int bufferSize = DefaultBufferSize, long count = -1)
{
  long read;
  while (true)
  {
    byte[] buffer = new byte[bufferSize];
    read = stream.Read(buffer, 0, bufferSize);
    if (read > 0)
      yield return buffer;
    else
      break;
  } 
}

Update

Have you tested performance against reading char-by-char using a StreamReaderlike:

public static string ReadTo(this Stream stream, string separator, Encoding encoding)
{
  if (!stream.CanSeek)
    throw new NotSupportedException("The stream must be seekable");

  StringBuilder text = new StringBuilder();
  int index = 0;
  bool searching = false;
  int sepIndex = 0;
  char cur;

  using (StreamReader reader = new StreamReader(stream, encoding, false, 1024, true))
  {
    int res;
    while ((res = reader.Read()) != -1)
    {
      cur = (char)res;
      if (!searching && cur == separator[0])
      {
        searching = true;
        sepIndex = 1;
      }
      else if (searching && sepIndex < separator.Length && cur == separator[sepIndex])
      {
        sepIndex++;
      }
      else
      {
        if (sepIndex == separator.Length)
        {
          break;
        }

        searching = false;
        sepIndex = 0;
      }

      text.Append(cur);

      index++;
    }
  }

  if (sepIndex == separator.Length && text.Length >= sepIndex)
    text.Length -= sepIndex;

  return text.ToString();
}

This is more than ten times faster than the original for a data set of 7600 kb and finding the last four chars as the separator.

\$\endgroup\$
  • \$\begingroup\$ I know that it is risky, but I need extreme performances, and re-allocating as many buffers as chunks would be even more risky when it comes to performances. My method is not meant to cache buffers, but to immediately read from a stream. Indeed, the right way to cache a stream is to copy it to a MemoryStream, not adding buffers to a list. It would be a bad practice, and if bad practices don't work, it's not my issue! \$\endgroup\$ – Davide Cannizzo Sep 2 at 15:45
  • 2
    \$\begingroup\$ @DavideCannizzo: OK, it's your code, but maybe you should document the behavior then. \$\endgroup\$ – Henrik Hansen Sep 2 at 15:52
  • \$\begingroup\$ Right, @Henrik Hansen. I'll do as soon as possible \$\endgroup\$ – Davide Cannizzo Sep 2 at 16:15
  • 1
    \$\begingroup\$ a much simpler approach - could you explain what is so special about this approach? \$\endgroup\$ – t3chb0t Sep 2 at 16:58
  • 1
    \$\begingroup\$ @t3chb0t: It's you, that use the word "special" - not I. I call it simpler (than the original). But it is - according to Davides comment - irrelevant as he wants to keep his own version :-) \$\endgroup\$ – Henrik Hansen Sep 2 at 17:03
3
\$\begingroup\$

If you're not scared of a little bit of unsafe code then you can get rid of the copying of the buffer entirely as there is a GetString overlaod that accepts a length of the buffer. Or another overload that doesn't require unsafe code

The loop in ReadTo could begin like this:

    foreach (var (buffer, length) in stream.EnumerateBuffers(bufferSize))
    {
        var substring = default(string);
        unsafe
        {
            fixed (byte* p_buffer = buffer)
            {
                substring = encoding.GetString(p_buffer, length);
            }
        }   

        // or

        substring = encoding.GetString(buffer, 0, length);

where EnumerateBuffers now returns tuples with the buffer and its length:

public static IEnumerable<(byte[] Buffer, int Length)> EnumerateBuffers(this Stream stream, int bufferSize = DefaultBufferSize, long count = -1)
{
    byte[] buffer = new byte[bufferSize];
    do
    {
        long read = stream.Read(buffer, 0, bufferSize);
        if (read < 1)
        {
            break;
        }
        if (count > -1)
        {
            count -= read;
            if (count < 0)
                read += count;
        }

        yield return (buffer, (int)read);

    } while (true);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, @t3chb0t for your solution. However, I won't apply it because of the disorder of returning tuples (I'm not scared of unsafety). \$\endgroup\$ – Davide Cannizzo Sep 3 at 16:08
  • 1
    \$\begingroup\$ @DavideCannizzo sure, there is no must apply ;-] I just thought it's good to know there is one more overload that makes it more convenient in certain situations - might be useful someone else. But could you expand what kind of disorder you mean? \$\endgroup\$ – t3chb0t Sep 3 at 16:10
  • \$\begingroup\$ @DavideCannizzo I now noticed your edit. disorder of returning tuples? I might still need help understanding this one. \$\endgroup\$ – t3chb0t Sep 3 at 16:12
  • \$\begingroup\$ I'm happy to know about the overload you were pointing out (indeed, I upvoted your answer the same). However, I feel your code a bit messy. EnumerateSubstring, as per its name, should enumerate some substrings (each one per buffer), so it'll be strange if it returned tuples. Moreover, I made it to make things simple, and if it gave the responsibility to cut the buffers, it would be uncomfortable to use it. \$\endgroup\$ – Davide Cannizzo Sep 3 at 16:13
  • 1
    \$\begingroup\$ @DavideCannizzo as a matter of fact I started this with the pointers and only later noticed there was the second overload. The reason it looks the way it is, is because enumerators didn't like unsafe code :-P Had I started with the safe one, it'd probably turned out differently hehe. \$\endgroup\$ – t3chb0t Sep 3 at 16:21
2
\$\begingroup\$

Looking at those many answers and comments suggesting several ways to solve some issues, along with speeding this up, I mixed up some ideas and I came out with the following edits:

The EnumerateSubstrings method:

/// <summary>
/// Enumerate substrings from a specified stream.
/// </summary>
/// <param name="stream">The stream to read.</param>
/// <param name="encoding">The encoding to use.</param>
/// <param name="bufferSize">The length of each substring.</param>
/// <returns></returns>
/// <exception cref="ArgumentException"></exception>
/// <exception cref="ArgumentNullException"></exception>
/// <exception cref="IOException"></exception>
/// <exception cref="DecoderFallbackException"></exception>
/// <exception cref="NotSupportedException"></exception>
/// <exception cref="ObjectDisposedException"></exception>
public static IEnumerable<string> EnumerateSubstrings(this Stream stream, Encoding encoding, int bufferSize = DefaultBufferSize)
{
    // Ensure that stream is not a null pointer.
    if (stream is null)
        throw new ArgumentNullException(nameof(stream));
    // Ensure that stream is readable.
    if (!stream.CanRead)
        throw new NotSupportedException("The stream must be readable.");
    Contract.EndContractBlock();
    char[] buffer = new char[bufferSize];
    using (StreamReader reader = new StreamReader(stream, encoding, false, bufferSize, true))
        for (int position = 0, read; (read = reader.ReadBlock(buffer, 0, bufferSize)) > 0; position += read)
        if (read == bufferSize)
            yield return new string(buffer);
        else
            yield return new string(buffer, 0, read);
}

The ReadTo method:

/// <summary>
/// Read the current stream until a specified string is encountered.
/// </summary>
/// <param name="stream">The source stream.</param>
/// <param name="separator">The string that marks the end.</param>
/// <param name="encoding">The encoding to use.</param>
/// <param name="bufferSize">The size of the buffers.</param>
/// <returns></returns>
/// <exception cref="ArgumentException"></exception>
/// <exception cref="ArgumentNullException"></exception>
/// <exception cref="IOException"></exception>
/// <exception cref="DecoderFallbackException"></exception>
/// <exception cref="NotSupportedException"></exception>
/// <exception cref="ObjectDisposedException"></exception>
public static string ReadTo(this Stream stream, in string separator, in Encoding encoding, in int bufferSize = DefaultBufferSize)
{
    // Ensure that some parameters are not null pointers.
    if (stream is null)
        throw new ArgumentNullException(nameof(stream));
    if (separator is null)
        throw new ArgumentNullException(nameof(separator));
    if (encoding is null)
        throw new ArgumentNullException(nameof(encoding));
    // This method requires seeking and reading, so ensure that the specified stream supports those features.
    if (!stream.CanSeek)
        throw new NotSupportedException("The stream must be seekable.");
    if (!stream.CanRead)
        throw new NotSupportedException("The stream must be readable.");
    Contract.EndContractBlock();

    long initialPosition = stream.Position;

    // This StringBuilder will build the resulting text. Using this to avoid too many string reallocations.
    StringBuilder text = new StringBuilder();

    bool hasSuffix = false;
    StringBuilder endingSeparator = new StringBuilder();

    // Iterate through each substring in the stream. Each one is a buffer converted to a string using a specified encoding.
    foreach (string _substring in stream.EnumerateSubstrings(encoding, bufferSize))
    {
        string substring = _substring;
        // Retrieve how many bytes is the current substring long. This will be necessary to handle some seekings on the stream.
        int substringByteLength = encoding.GetByteCount(substring);
        // Check out whether the previous substring had a suffix.
        if (hasSuffix)
        {
            // If it had, then verify whether the current substring starts with the remaining part of the separator.
            string newEndingSeparator = separator.Substring(endingSeparator.Length);
            bool separatorChanged = false;
            while (newEndingSeparator.Length != 0 && !substring.StartsWith(newEndingSeparator, StringComparison.Ordinal))
            {
                newEndingSeparator = newEndingSeparator.Remove(newEndingSeparator.Length - 1);
                separatorChanged = true;
            }
            if (newEndingSeparator.Length == 0)
            {
                // If the code reached here, then the previous suffix were not part of a separator, as the whole of the separator cannot be found.
                hasSuffix = false;
                //text.Append(endingSeparator);
                //text.Append(substring);
                substring = endingSeparator + substring;
            }
            else
            {
                if (!separatorChanged)
                {
                    string result = text.ToString();
                    // Seek till before the separator and break the loop.
                    stream.Position = initialPosition + encoding.GetByteCount(result);
                    return result;
                }
                endingSeparator.Append(newEndingSeparator);
                continue;
            }
        }

        {
            // Check out whether the current substring contains the separator.
            int separatorIndex = substring.IndexOf(separator, StringComparison.Ordinal);
            // If the current substring starts with the separator, just skip it and break the loop, so the StringBuilder will only contain previous substrings.
            if (separatorIndex == 0)
                break;
            if (separatorIndex != -1)
            {
                // If that's the case, take this substring till the previously found index, ...
                string newSubstring = substring.Remove(separatorIndex);
                // ...then append the new substring (the one before the separator) to the StringBuilder, ...
                text.Append(newSubstring);
                string result = text.ToString();
                // ...and finally seek the current stream before the separator-
                stream.Position = initialPosition + encoding.GetByteCount(result);
                return result;
            }
        }

        // Sometimes, it might happen that the separator is divided between the current substring and the next one.
        // So, see whether the current substring ends with just one part (even one only character) of the separator.
        endingSeparator.Clear();
        endingSeparator.Append(separator);

        do
            // Remove the last character from the 'ending separator'.
            endingSeparator = endingSeparator.Remove(endingSeparator.Length - 1, 1);
        // If the ending separator isn't empty yet and the current substring doesn't end with it,
        // continue the loop.
        while (!(endingSeparator.Length == 0 || substring.EndsWith(endingSeparator.ToString(), StringComparison.Ordinal)));

        // At this time, the ending separator will be an initial part of the specified separator,
        // which is a 'suffix' of the current substring.
        // Push the length of the suffix on the stack, so I'll avoid to call the Length getter accessor multiple times.
        int suffixLength = endingSeparator.Length;

        // If the suffix is empty, that means the current string doesn't end with even just a part of the separator.
        // Therefore, just append the current string to the StringBuilder.
        if (suffixLength == 0)
            text.Append(substring);
        else
        {
            // If rather the suffix isn't empty, then mark this with the boolean hasSuffix and
            // append the current substring only till before the suffix.
            hasSuffix = true;
            text.Append(substring, 0, substring.Length - suffixLength);
        }
    }

    if (hasSuffix)
        text.Append(endingSeparator);

    return text.ToString();
}

Now, I apparently fixed all the bugs people pointed out and as per some suggestion I was able to make it a bit faster. If anyone should find out other issues or any way to speed this up even more, it'll be happily accepted and regarded.

Thanks to everyone who participated to this question, who helped me a lot.

EDIT: I just came out with a brand new algorithm (even if there might be still some similarities), which I think works, and it's also way simpler, notwithstanding the concepts are still the same.

The necessary changes only regard the ReadTo method. Here is it:

/// <summary>
/// Read the current stream until a specified string is encountered.
/// </summary>
/// <param name="stream">The source stream.</param>
/// <param name="separator">The string that marks the end.</param>
/// <param name="encoding">The encoding to use.</param>
/// <param name="bufferSize">The size of the buffers.</param>
/// <param name="comparisonType">The rules of comparison for the current search.</param>
/// <returns></returns>
/// <exception cref="ArgumentException"></exception>
/// <exception cref="ArgumentNullException"></exception>
/// <exception cref="IOException"></exception>
/// <exception cref="DecoderFallbackException"></exception>
/// <exception cref="NotSupportedException"></exception>
/// <exception cref="ObjectDisposedException"></exception>
public static string ReadTo(this Stream stream, in string separator, in Encoding encoding, in int bufferSize = DefaultBufferSize, in StringComparison comparisonType = StringComparison.Ordinal)
{
    // Ensure that some parameters are not null pointers.
    if (stream is null)
        throw new ArgumentNullException(nameof(stream));
    if (separator is null)
        throw new ArgumentNullException(nameof(separator));
    if (encoding is null)
        throw new ArgumentNullException(nameof(encoding));
    // This method requires seeking and reading, so ensure that the specified stream supports those features.
    if (!stream.CanSeek)
        throw new NotSupportedException("The stream must be seekable.");
    if (!stream.CanRead)
        throw new NotSupportedException("The stream must be readable.");
    Contract.EndContractBlock();

    long initialPosition = stream.Position;

    StringBuilder text = new StringBuilder();

    string endingSeparator = null;

    foreach (string chunk in stream.EnumerateSubstrings(encoding, bufferSize))
    {

        // If there was an ending separator, try to find a match.
        if (endingSeparator != null)
        {
            // Retrieve the remaining separator (i.e., the part of the separator after the ending one).
            string remainingSeparator = separator.Substring(endingSeparator.Length);

            // Remove characters from the end of the remaining separator until it is found at the beginning of the
            // current chunk, unless it gets empty first.
            // The newly-cut remaining separator will be named starting separator.
            string startingSeparator = remainingSeparator;
            while (!chunk.StartsWith(startingSeparator, comparisonType))
            {
                startingSeparator = startingSeparator.RemoveLast(1);
                if (startingSeparator.Length == 0)
                    break;
            }

            // If the starting separator is empty, it means that the ending separator was only a partial match.
            // Therefore, append the ending separator to the text. Otherwise, break the loop, as the separator was found.
            if (startingSeparator.Length == 0)
            {
                text.Append(endingSeparator);
                endingSeparator = null;
            }
            else
                break;
        }

        // Try to search the separator in the current chunk.
        if (chunk.TrySearch(separator, out int match, comparisonType))
        {
            // If it was found, break the loop here and append the current chunk till before the match.
            text.Append(chunk, 0, match);
            break;
        }

        // Remove characters from the end of the separator until the separator is found at the end of the current chunk,
        // unless it gets empty first. The newly-cut separator will be named ending separator.
        endingSeparator = separator;
        do
            endingSeparator = endingSeparator.RemoveLast();
        while (endingSeparator.Length != 0 && !chunk.EndsWith(endingSeparator, comparisonType));

        {
            // If an ending separator was found, append the current chunk till before the ending separator.
            // If the ending separator will be only a partial match, then the it will be further appended to
            // the text again.
            int endingSeparatorLength = endingSeparator.Length;
            if (endingSeparatorLength == 0)
                endingSeparator = null;
            else
            {
                text.Append(chunk, 0, chunk.Length - endingSeparatorLength);
                continue;
            }
        }

        // The current chunk doesn't contains the separator nor ends with part of it, so append it.
        text.Append(chunk);
    }

    // Store the result of this method.
    string result = text.ToString();

    // Seek the current stream just after the result.
    stream.Position = initialPosition + result.Length;

    // Return the result.
    return result;
}

The above method requires the following two ones:

/// <summary>
/// Try to search a specified substring in the current string.
/// </summary>
/// <param name="source">The source string.</param>
/// <param name="search">The substring to search.</param>
/// <param name="match">When this method returns, contains the index at which the substring was found, if it was; otherwise, -1.</param>
/// <param name="comparisonType">The rules of comparison for the current search.</param>
/// <returns>Whether the specified substring was found or not.</returns>
/// <exception cref="ArgumentNullException"></exception>
public static bool TrySearch(this string source, in string search, out int match, in StringComparison comparisonType = StringComparison.CurrentCulture)
{
    if (source is null)
        throw new ArgumentNullException(nameof(source));
    if (search is null)
        throw new ArgumentNullException(nameof(search));
    Contract.EndContractBlock();
    if (search.Length > source.Length)
    {
        match = -1;
        return false;
    }
    match = source.IndexOf(search, comparisonType);
    return match != -1;
}

/// <summary>
/// Remove the last <paramref name="count"/> characters from the current string.
/// </summary>
/// <param name="str">The source string.</param>
/// <param name="count">The number of characters to remove from the end of the current string.</param>
/// <returns></returns>
public static string RemoveLast(this string str, in int count = 1)
{
    if (str is null)
        throw new ArgumentNullException(nameof(str));
    Contract.EndContractBlock();
    return str.Remove(str.Length - count);
}

EDIT: Again, here is another brand new implementation (which will require the above TrySearch method):

/// <summary>
/// Read the current stream until a specified string is encountered.
/// </summary>
/// <param name="stream">The source stream.</param>
/// <param name="separator">The string that marks the end.</param>
/// <param name="encoding">The encoding to use.</param>
/// <param name="bufferSize">The size of the buffers.</param>
/// <param name="comparisonType">The rules of comparison for the current search.</param>
/// <returns></returns>
/// <exception cref="ArgumentException"></exception>
/// <exception cref="ArgumentNullException"></exception>
/// <exception cref="IOException"></exception>
/// <exception cref="DecoderFallbackException"></exception>
/// <exception cref="NotSupportedException"></exception>
/// <exception cref="ObjectDisposedException"></exception>
public static string ReadTo(this Stream stream, in string separator, in Encoding encoding, in int bufferSize = DefaultBufferSize, in StringComparison comparisonType = StringComparison.Ordinal)
{
    if (stream is null)
        throw new ArgumentNullException(nameof(stream));
    if (separator is null)
        throw new ArgumentNullException(nameof(separator));
    if (encoding is null)
        throw new ArgumentNullException(nameof(encoding));
    if (!stream.CanSeek)
        throw new NotSupportedException("The stream must be seekable.");
    if (!stream.CanRead)
        throw new NotSupportedException("The stream must be readable.");
    Contract.EndContractBlock();
    long initialPosition = stream.Position;
    string text = string.Empty;
    foreach (string chunk in stream.EnumerateSubstrings(encoding, bufferSize))
    {
        text += chunk;
        if (text.TrySearch(separator, out int match, comparisonType))
        {
            text = text.Remove(match);
            break;
        }
    }
    stream.Position = initialPosition + text.Length;
    return text;
}

I also thought about another quite simple algorithm, which would work only if the buffer size is greater than or equal to the length of the separator. But this would be faster, as it will mainly use a StringBuilder and will end up finding separators concatenating a string for just two buffers each one). Therefore, I first check for the buffer size and the length of the separator, and then choose what implementation is being used:

/// <summary>
/// Read the current stream until a specified string is encountered.
/// </summary>
/// <param name="stream">The source stream.</param>
/// <param name="separator">The string that marks the end.</param>
/// <param name="encoding">The encoding to use.</param>
/// <param name="bufferSize">The size of the buffers.</param>
/// <param name="comparisonType">The rules of comparison for the current search.</param>
/// <returns></returns>
/// <exception cref="ArgumentException"></exception>
/// <exception cref="ArgumentNullException"></exception>
/// <exception cref="IOException"></exception>
/// <exception cref="DecoderFallbackException"></exception>
/// <exception cref="NotSupportedException"></exception>
/// <exception cref="ObjectDisposedException"></exception>
public static string ReadTo(this Stream stream, in string separator, in Encoding encoding, in int bufferSize = DefaultBufferSize, in StringComparison comparisonType = StringComparison.Ordinal)
{
    if (stream is null)
        throw new ArgumentNullException(nameof(stream));
    if (separator is null)
        throw new ArgumentNullException(nameof(separator));
    if (encoding is null)
        throw new ArgumentNullException(nameof(encoding));
    if (!stream.CanSeek)
        throw new NotSupportedException("The stream must be seekable.");
    if (!stream.CanRead)
        throw new NotSupportedException("The stream must be readable.");
    Contract.EndContractBlock();
    long initialPosition = stream.Position;
    string text;
    if (bufferSize < separator.Length)
    {
        text = string.Empty;
        foreach (string chunk in stream.EnumerateSubstrings(encoding, bufferSize))
        {
            text += chunk;
            if (text.TrySearch(separator, out int match, comparisonType))
            {
                text = text.Remove(match);
                break;
            }
        }
    }
    else
    {
        StringBuilder builder = new StringBuilder();
        string chunk = null;
        bool flag = false;
        foreach (string substring in stream.EnumerateSubstrings(encoding, bufferSize))
        {
            if (flag)
                chunk += substring;
            else
                chunk = substring;
            if (chunk.TrySearch(separator, out int match, comparisonType))
            {
                int diff = match - chunk.Length + substring.Length;
                if (diff != 0)
                    if (diff < 0)
                        builder.Remove(builder.Length + diff, -diff);
                    else
                        builder.Append(substring, 0, diff);
                break;
            }
            chunk = substring;
            flag = true;
            builder.Append(substring);
        }
        text = builder.ToString();
    }
    stream.Position = initialPosition + text.Length;
    return text;
}

I hope this works. Please, tell me if I'm wrong :)

\$\endgroup\$
  • 1
    \$\begingroup\$ It's better, but there are still edge-cases. Try reading up to "abb" in "aaaabbbbcccc", with a buffer size of 4. That do-while loop is also still quite sensitive to large separators - for ordinal comparisons, a simple loop can be (much) faster. \$\endgroup\$ – Pieter Witvoet Sep 4 at 13:30
  • 1
    \$\begingroup\$ That's still not all, though - the 3rd problem in my review is not solved yet (a partial match overlapping a real match on a buffer boundary). \$\endgroup\$ – Pieter Witvoet Sep 4 at 14:08
  • 1
    \$\begingroup\$ It looks like the problem you just found has not been fixed properly - try reading up to "aab" in "aa". The problem I meant however is the 3rd point in my review. \$\endgroup\$ – Pieter Witvoet Sep 4 at 14:36
  • 1
    \$\begingroup\$ Nope - 3rd problem has not been solved yet. \$\endgroup\$ – Pieter Witvoet Sep 4 at 14:53
  • 1
    \$\begingroup\$ The 3rd point in my review already contains a test case... The problem is that a partial match can 'hide' a full match, when both the partial and full match occur on a buffer boundary. When looking for "aab" in "aaab", with buffer size 2, that first buffer ("aa") is a partial match - but the second buffer starts with an a, so the match fails. However, there is a full match that also starts in the first buffer (at the last a). \$\endgroup\$ – Pieter Witvoet Sep 4 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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