ASCII Strings and Zero-Allocation

Question

Over the weekend this article inspired me to write an ASCII string implementation that avoids memory allocation during basic operations like Substring and Trim. It's still a work-in-progress but I think this is a solid foundation to build off of and wanted some help checking my logic/maths.

The main method of interest is the overload of Substring that accepts an offset and a count since most other methods are implemented by calling it.

using System;
using System.Text;

namespace ByteTerrace.CSharp.Data
{
    /// <summary>
    /// Represents text as a series of ASCII characters.
    /// </summary>
    /// <remarks>
    /// Inspired by Christopher Wright's FastString work: https://github.com/dhasenan/FastString.
    /// </remarks>
    public struct AsciiString : IEquatable<AsciiString>
    {
        private readonly ArraySegment<byte> m_bytes;

        /// <summary>
        /// Gets the <see cref="char"/> object at a specified position in this <see cref="AsciiString"/> instance.
        /// </summary>
        /// <param name="index">A position in the current string.</param>
        public char this[int index] {
            get {
                if ((index < 0) || ((m_bytes.Offset + index) > (m_bytes.Offset + Length))) {
                    throw new ArgumentOutOfRangeException(nameof(index));
                }

                return (char)m_bytes.Array[m_bytes.Offset + index];
            }
        }
        /// <summary>
        /// Indicates whether this <see cref="AsciiString"/> instance is empty.
        /// </summary>
        public bool IsEmpty {
            get {
                return m_bytes.Count == 0;
            }
        }
        /// <summary>
        /// Indicates whether this <see cref="AsciiString"/> instance is empty or consists of only whitespace characters.
        /// </summary>
        public bool IsEmptyOrWhitespace {
            get {
                return Trim().IsEmpty;
            }
        }
        /// <summary>
        /// The number of characters in this <see cref="AsciiString"/> instance.
        /// </summary>
        public int Length {
            get {
                return m_bytes.Count;
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by an <see cref="Array"/> of ASCII bytes.
        /// </summary>
        /// <param name="bytes">An <see cref="Array"/> of ASCII bytes.</param>
        public AsciiString(ArraySegment<byte> bytes) { m_bytes = bytes; }
        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by an <see cref="ArraySegment{T}"/> of ASCII bytes.
        /// </summary>
        /// <param name="bytes">An <see cref="ArraySegment{T}"/> of ASCII bytes.</param>
        public AsciiString(byte[] bytes) : this(new ArraySegment<byte>(bytes ?? new byte[0])) { }
        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by an <see cref="Array"/> of ASCII bytes,
        /// a starting position within that array, and a length.
        /// </summary>
        /// <param name="bytes">An array of ASCII bytes.</param>
        /// <param name="offset">The zero-based starting character position of a substring in bytes.</param>
        /// <param name="count">The number of characters in the substring.</param>
        public AsciiString(byte[] bytes, int offset, int count) : this(new ArraySegment<byte>(bytes, offset, count)) { }
        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by a <see cref="string"/>.
        /// </summary>
        /// <param name="value">A string value that will be transcoded to ASCII.</param>
        public AsciiString(string value) : this(Encoding.ASCII.GetBytes(value ?? string.Empty)) { }

        /// <summary>
        /// Create a new copy of this <see cref="AsciiString"/> instance.
        /// </summary>
        public unsafe AsciiString Copy() {
            var buffer = new byte[Length];
            var count = m_bytes.Offset + Length;

            fixed (byte* leftPointer = &buffer[0])
            fixed (byte* rightPointer = &m_bytes.Array[m_bytes.Offset]) {
                byte* left = leftPointer;
                byte* right = rightPointer;

                while (31 < count) {
                    (*(long*)(left + 0)) = (*(long*)(right + 0));
                    (*(long*)(left + 8)) = (*(long*)(right + 8));
                    (*(long*)(left + 16)) = (*(long*)(right + 16));
                    (*(long*)(left + 24)) = (*(long*)(right + 24));

                    count -= 32;
                    left += 32;
                    right += 32;
                }

                if (15 < count) {
                    (*(long*)(left + 0)) = (*(long*)(right + 0));
                    (*(long*)(left + 8)) = (*(long*)(right + 8));

                    count -= 16;
                    left += 16;
                    right += 16;
                }


                while (0 < count) {
                    *left = *right;

                    count--;
                    left++;
                    right++;
                }
            }

            return new AsciiString(buffer);
        }
        /// <summary>
        /// Determines whether this instance and another specified <see cref="AsciiString"/> object have the same value.
        /// </summary>
        /// <param name="other">The <see cref="AsciiString"/> to compare to this instance.</param>
        public unsafe bool Equals(AsciiString other) {
            var count = Length;

            if (count != other.Length) {
                return false;
            }
            else { // shamelessly adapted from http://referencesource.microsoft.com/#mscorlib/system/string.cs,11648d2d83718c5e
                fixed (byte* leftPointer = &m_bytes.Array[m_bytes.Offset])
                fixed (byte* rightPointer = &other.m_bytes.Array[other.m_bytes.Offset]) {
                    byte* left = leftPointer;
                    byte* right = rightPointer;

                    while (31 < count) {
                        if ((*(long*)(left + 0) != *(long*)(right + 0))
                         || (*(long*)(left + 8) != *(long*)(right + 8))
                         || (*(long*)(left + 16) != *(long*)(right + 16))
                         || (*(long*)(left + 24) != *(long*)(right + 24))
                        ) { return false; }

                        count -= 32;
                        left += 32;
                        right += 32;
                    }

                    if (15 < count) {
                        if ((*(long*)(left + 0) != *(long*)(right + 0))
                         || (*(long*)(left + 8) != *(long*)(right + 8))
                        ) { return false; }

                        count -= 16;
                        left += 16;
                        right += 16;
                    }

                    while (0 < count) {
                        if (*left != *right) {
                            return false;
                        }

                        count--;
                        left++;
                        right++;
                    }

                    return true;
                }
            }
        }
        /// <summary>
        /// Determines whether this instance and another specified <see cref="object"/>, which also must be a <see cref="AsciiString"/>, have the same value.
        /// </summary>
        /// <param name="other">The <see cref="object"/> to compare to this instance.</param>
        public override bool Equals(object other) {
            var asciiString = other as AsciiString?;

            if (asciiString.HasValue) {
                return Equals(asciiString.Value);
            }
            else {
                return false;
            }
        }
        /// <summary>
        /// Returns the hash code for the underlying <see cref="ArraySegment{T}"/> of this <see cref="AsciiString"/> instance.
        /// </summary>
        public override int GetHashCode() {
            return m_bytes.GetHashCode();
        }
        /// <summary>
        /// Retrieves a substring from this <see cref="AsciiString"/> instance. The slice will be performed left to right and has a specified length.
        /// </summary>
        /// <param name="count">The number of characters in the substring.</param>
        public AsciiString SliceLeft(int count) {
            return Substring(0, count);
        }
        /// <summary>
        /// Retrieves a substring from this <see cref="AsciiString"/> instance. The slice will be performed right to left and has a specified length.
        /// </summary>
        /// <param name="count">The number of characters in the substring.</param>
        public AsciiString SliceRight(int count) {
            return Substring(Length - count, count);
        }
        /// <summary>
        /// Retrieves a substring from this <see cref="AsciiString"/> instance. The substring starts at a specified character position and has a specified length.
        /// </summary>
        /// <param name="offset">The zero-based starting character position of a substring in this instance.</param>
        /// <param name="count">The number of characters in the substring.</param>
        public AsciiString Substring(int offset, int count) {
            if ((offset < 0) || ((m_bytes.Offset + offset + count) > (m_bytes.Offset + Length))) {
                throw new ArgumentOutOfRangeException(nameof(offset));
            }
            if (count > m_bytes.Count) {
                throw new ArgumentOutOfRangeException(nameof(count));
            }

            return new AsciiString(m_bytes.Array, m_bytes.Offset + offset, count);
        }
        /// <summary>
        /// Retrieves a substring from this <see cref="AsciiString"/> instance. The substring starts at a specified character position and continues to the end of the string.
        /// </summary>
        /// <param name="offset">The zero-based starting character position of a substring in this instance.</param>
        public AsciiString Substring(int offset) {
            return Substring(offset, Length - offset);
        }
        /// <summary>
        /// Converts this <see cref="AsciiString"/> value to its equivalent <see cref="string"/> representation.
        /// </summary>
        public override string ToString() {
            return Encoding.ASCII.GetString(m_bytes.Array, m_bytes.Offset, m_bytes.Count);
        }
        /// <summary>
        /// Removes all leading whitespace characters from this <see cref="AsciiString"/> instance.
        /// </summary>
        public AsciiString TrimLeft() {
            var index = m_bytes.Offset;
            var count = Length;

            while (0 < count--) {
                if (!IsWhitespaceCharacter(m_bytes, index++)) {
                    break;
                }
            }

            return SliceRight(++count);
        }
        /// <summary>
        /// Removes all trailing whitespace characters from this <see cref="AsciiString"/> instance.
        /// </summary>
        public AsciiString TrimRight() {
            var index = Length - 1;
            var count = Length;

            while (0 < count--) {
                if (!IsWhitespaceCharacter(m_bytes, index--)) {
                    break;
                }
            }

            return SliceLeft(++count);
        }
        /// <summary>
        /// Removes all leading and trailing whitespace characters from this <see cref="AsciiString"/> instance.
        /// </summary>
        public AsciiString Trim() {
            return TrimLeft().TrimRight();
        }

        /// <summary>
        /// Determines whether two <see cref="AsciiString"/> objects have the same value.
        /// </summary>
        public static bool operator ==(AsciiString left, AsciiString right) {
            return left.Equals(right);
        }
        /// <summary>
        /// Determines whether two <see cref="AsciiString"/> objects have different values.
        /// </summary>
        public static bool operator !=(AsciiString left, AsciiString right) {
            return !left.Equals(right);
        }
        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by an <see cref="Array"/> of ASCII bytes.
        /// </summary>
        /// <param name="bytes">An <see cref="Array"/> of ASCII bytes.</param>
        public static implicit operator AsciiString(byte[] bytes) {
            return new AsciiString(bytes);
        }
        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by an <see cref="ArraySegment{T}"/> of ASCII bytes.
        /// </summary>
        /// <param name="bytes">An <see cref="ArraySegment{T}"/> of ASCII bytes.</param>
        public static implicit operator AsciiString(ArraySegment<byte> bytes) {
            return new AsciiString(bytes);
        }
        /// <summary>
        /// Initializes a new instance of the <see cref="AsciiString"/> structure to the value indicated by a <see cref="string"/>.
        /// </summary>
        /// <param name="value">A string value that will be transcoded to ASCII.</param>
        public static implicit operator AsciiString(string value) {
            return new AsciiString(value);
        }

        private static bool IsWhitespaceCharacter(ArraySegment<byte> bytes, int index) {
            var c = bytes.Array[bytes.Offset + index];

            if ((c == 0x20) || ((c > 0x08) && (c < 0x0E))) {
                return true;
            }
            else {
                return false;
            }
        }
    }
}

I must say I like this solution much better then the original one with its weird Splitter, Slicer and what not. — t3chb0t, Apr 17, 2017 at 16:28

Heslacher · Accepted Answer · 2017-04-18 08:09:46Z

public AsciiString Substring(int offset, int count) {
    if ((offset < 0) || ((m_bytes.Offset + offset + count) > (m_bytes.Offset + Length))) {
        throw new ArgumentOutOfRangeException(nameof(offset));
    }
    if (count > m_bytes.Count) {
        throw new ArgumentOutOfRangeException(nameof(count));
    }

    return new AsciiString(m_bytes.Array, m_bytes.Offset + offset, count);
}

If we take a look at the first if statement we can simplify ((m_bytes.Offset + offset + count) > (m_bytes.Offset + Length)) to ((offset + count) > Length).

If we assume Length == 10 and we call

public AsciiString Substring(int offset) {
    return Substring(offset, Length - offset);
}

with offset == 11 the overloaded Substring(int, int) will be called like Substring(11, -1) which just passes the if conditions but will throw an ArgumentOutOfRangeException at calling the constructor of the ArraySegment which means you are exposing implementation details.

Another edge case is if offset == Length, using the above example with Length == 10, which would result in Substring(10, 0) which shouldn't be valid either.

If you change the second if to

if (count < 1 || count > m_bytes.Count) {
    throw new ArgumentOutOfRangeException(nameof(count));
}

this should be fixed.

For the constructors the points about validation and exposing implementation details apply as well. Although the overloaded constructors are looking nice, some validation should take place.

At least for public AsciiString(byte[] bytes, int offset, int count) the passed arguments should be validated.

The IsWhitespaceCharacter() method could be simplified by just returning the condition of the if. Although I don't know how the compiler will optimize it I would suggest to switch the conditions on the right hand side of the || operator. This is because more characters will be > 0x08 than < 0x0E.

private static bool IsWhitespaceCharacter(ArraySegment<byte> bytes, int index) {
    var c = bytes.Array[bytes.Offset + index];
    return (c == 0x20) || ((c < 0x0E) && (c > 0x08);
}

The IsEmptyOrWhiteSpace() method could be improved some more by first checking for IsEmpty and introducing a IsWhytespace() method which simply checks for whitespace characters.

public bool IsEmptyOrWhitespace
{
    get
    {
        return IsEmpty || IsWhitespace();
    }
}
private bool IsWhitespace()
{
    byte[] current = new byte[m_bytes.Count - m_bytes.Offset];
    Array.Copy(m_bytes.Array, current, current.Length);

   return current.All(c => (c == 0x20) || ((c < 0x0E) && (c > 0x08));
 }

t3chb0t · Accepted Answer · 2017-04-18 07:55:14Z

1

public AsciiString(byte[] bytes) : this(new ArraySegment<byte>(bytes ?? new byte[0])) { }

I find you shouldn't allow nulls but if you do, then it's better to provide a default constructor (or in a case of a sctruct it already has one) then doing as everything was fine. This might not crash because of this but it might hide a bug that is hard to find because the user might have done something wrong where his bytes are null but actually shouldn't. He expects a new AsciiString is created from his buffer but in reality it just did some weird initialization from an empty one.

public AsciiString(string value) : this(Encoding.ASCII.GetBytes(value ?? string.Empty)) { }

The same here. I'd be really surprised if I passed an invalid string and it actually worked.

public struct AsciiString

I think it should be a class rather then a struct. What happens to the buffers when you pass an AsciiString via a parameter? Are they copied too? I think this kills the whole fast-string idea.

edited Apr 18, 2017 at 7:55

answered Apr 18, 2017 at 7:46

t3chb0t

44.1k9 gold badges78 silver badges180 bronze badges

\$\begingroup\$ Am experimenting with the idea that null and the empty string are equivalent; one can opt out of this decision by wrapping an AsciiString in a Nullable<> to intercept the constructors. As for the copying, no. The current design is intended for maximum performance and doesn't protect the programmer outside of simple bounds checking. The Copy method allocates an entirely new array if one needs a buffer that no one can manipulate without resorting to naughty things. \$\endgroup\$
– Kittoes0124
Apr 18, 2017 at 12:23
\$\begingroup\$ AsciiStrings take up half the size of standard .NET strings which inherently makes them faster during most operations (unless I personally failed to optimize a function well enough). Even if I choose to give up the zero allocation feature they'd still be half the size and thus allocating them is twice as fast. I have confirmed this in testing with Copy and Equals. \$\endgroup\$
– Kittoes0124
Apr 18, 2017 at 12:34

Add a comment |

Stack Exchange Network

ASCII Strings and Zero-Allocation

2 Answers 2

Your Answer

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

Hot Network Questions

ASCII Strings and Zero-Allocation

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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