Provide StringBuilder.ForeachChunk for efficient access to characters in a StringBuilder

[vancem]

Today, StringBuilder has problem in that the only way to read the characters out of the StringBuilder is to do it a character at a time [] or call the ToString APIs to convert it to a string (and then index it). Both of these are slow.

Typically what people actually do is call ToString, which forces the creation of a large string. Often the very next thing that happens is that the String is written to a file, leaving behind a large, dead string on the GC heap.

With the advent of Span there is now an efficient, safe mechanism for extracting the data in the StringBuilder.

The proposed API is

        /// <summary>
        /// ForEachChunk is an efficient way of accessing all the characters in the StringBuilder.
        /// It is an alternative to calling ToString() on the StringBuilder.   
        /// 
        /// The 'callback' delegate is called 0 or more times, each time being passed a chunk of
        /// the string as a ReadOnlySpan of characters (in order).  This is repeated until all
        /// the characters in the span have been passed back through 'callback'.  
        /// </summary>
        /// <param name="callback">A method that is called repeatedly, being passed a chunk 
        /// of the Strinbuilder with each call.  If 'false' is returned by the callback
        /// then ForEachChunk terminates immediately.  </param>
        public void ForEachChunk(Func<ReadOnlySpan<char>, bool> callback)

The actual implmentation is simple:

        public void ForEachChunk(Func<ReadOnlySpan<char>, bool> callback)
        {
            VerifyClassInvariant();
            ForEachChunk(callback, this);
        }

        private bool ForEachChunk(Func<ReadOnlySpan<char>, bool> callback, StringBuilder chunk)
        {
            // The chunks are last written first, so we need to output the others first.  
            var next = chunk.m_ChunkPrevious;
            if (next != null && !ForEachChunk(callback, next))
                return false;

            // The fields here might be changing and inaccurate if threads are racing, but the validation that Span does on 
            // construction insures that the values, even if inaccurate, are 'in bounds'.   
            return callback(new Span<char>(chunk.m_ChunkChars, chunk.m_ChunkOffset, chunk.m_ChunkLength));
        }

The intent is that this new API can be a building block to provide extension methods on Stream (or other APIs that act like streams) that operate on StringBuilders directly (so an intermediate strings need not be formed)

Question: A variation of this is to have an explicit context parameter that is passed to the callback.

       public void ForEachChunk<T>(Func<ReadOnlySpan<char>, T, bool> callback, T context = null) where T : class

While this is not as convenient to use, it allows the user to avoid creating closures (which force the allocation of a Func), which is faster (and the goal of this API is is all about being faster)

@stephentoub @jkotas @alexperovich @AlexGhiondea @davidfowl

[stephentoub]

This looks like a reasonable thing to add. Note that I'll be opening one or more issues in the coming days with a list of APIs based on Span/Buffer I believe we should be adding, and I can put these on the list; others on StringBuilder include overloads for methods like Append/Insert for working with spans.

If we add such a ForEachChunk method, we should definitely include the generic context argument; otherwise we force the closure and delegate allocations, and the most common uses of this method will be in transferring the data to something else, so invariably there's going to need to be some context, and we should enable and encourage using it efficiently.

As a nit, isn't Span as ref-like type prohibited from being used as a generic type argument? Assuming yes, we'll also need a custom delegate type. It'll be interesting to see if a few common shapes for such delegates emerge such that we can create more generically named ones, or whether we should create them for each API named to correspond to that API.

[omariom]

Or StringBuilder can return the mathematical opposite of callbacks - enumerator :)

[stephentoub]

Vance, how do you see this behaving if the callback mutates the StringBuilder in ways that change/invalidate the chunks?

[ahsonkhan]

Regarding:

public void ForEachChunk(Func<ReadOnlySpan<char>, bool> callback)

As a nit, isn't Span as ref-like type prohibited from being used as a generic type argument?

Yes, it is prohibited. Span cannot be used as a type argument since it is a stack only type.

cc @VSadov

Edit: Added response to @stephentoub's comment.

[davidfowl]

I'm not a fan of callback methods like this for a couple of reasons:

• You need the state callback which doesn't work well for locals (you still need to allocate)
• You might need an async version in case the thing you're trying to do in the callback is async.

Is there any way we can revisit the ISpanEnumerable<T> pattern that @jaredpar suggested way back when.

[svick]

I would also prefer enumerable, because:

• The API is easier to understand and use. (An enumerable type instead of a callback, a context and a custom delegate type.)
• Using it does not have to involve any virtual calls and involves less allocations than ForEachChunk.

How come enumerable allocates less, considering that the proposed implementation of ForEachChunk uses stack-based recursion and enumerable can't do that?

Because ForEachChunk can't do it either: for large StringBuilders, it would cause StackOverflowException. For example, the following code does that for me:

var sb = new StringBuilder();

for (int i = 0; i < 20_000; i++)
    sb.Append(new string('a', 8000));

sb.ForEachChunk(c => true);

So, how could chunk enumerable or ForEachChunk be implemented instead? I can see four options:

1. Use Stack<StringBuilder> as an explicit stack that's not limited by the size of the thread stack. This requires an allocation, potentially a large one.
2. Use a trick where you reverse the linked list on the way to the front and then reverse it back on the way back. This is probably the most efficient solution, but would require some form of "locking" to ensure no other operation (read or write) operates on the StringBuilder at the same time.
3. After every chunk, iterate from the start of the linked list to find the next chunk. This approach is O(n²) (all the others are O(n)), but it does not not allocate and is also not otherwise invasive.
4. Turn StringBuilder from a singly-linked list to a doubly-linked list. This would require adding a pointer-sized field to every StringBuilder for a niche use case.

So, all the implementations I could think of have pretty serious drawbacks. Did I miss some? Does one of these stand out as the best option?

[stephentoub]

but would require some form of "locking" to ensure no other operation (read or write) operates on the StringBuilder at the same time.

StringBuilder currently isn't safe to be used concurrently... why would this operation need to be? Or maybe you just meant what I asked about earlier, the callback itself accessing the builder?

[svick]

@stephentoub Yeah, I didn't mean making StringBuilder thread-safe. But with that option, even reading the StringBuilder from the same thread while iterating the chunks would not be safe.

For example, consider code like this (using enumerable for cleaner code, but ForEachChunk would have the same issue):

foreach (var chunk in sb.EnumerateChunks())
{
    Console.WriteLine($"{sb} {chunk}");
}

This code would have to be disallowed, because it's reading the StringBuilder, while it's being iterated. The implicit call to StringBuilder.ToString() couldn't give the correct result, because all the m_ChunkPrevious references might currently point the wrong way.

So, while the StringBuilder's chunks are being iterated, the StringBuilder has to be "locked", even from access from the same thread, if my option 2 was chosen.

[stephentoub]

But with that option, even reading the StringBuilder from the same thread while iterating the chunks would not be safe.

Yes, this is actually why I personally prefer the callback in this situation; it makes the scoping very clear, and, at least in my eyes (though little technically different about it), discourages accessing the StringBuilder directly.

Regardless, in any of these approaches, whether callback or enumerables, unless a copy of the data is made (which defeats the purpose of the method), StringBuilder would need to detect and prevent usage while the callback/enumerables was still outstanding, which at the very least would add checks to most other operations on the StringBuilder; not pay-for-play, though I've not measured to see if it would actually show up.

I'm also not personally concerned about the reading/writing difference you mention... it's rare in my experience to read from a StringBuilder (other than ToString, which this would be used in place of in certain situations), and when you do, it's usually to check whether to write something (e.g. checking whether it ends with a slash to know whether to add one).

[davidfowl]

We do have prior art in this space https://msdn.microsoft.com/en-us/library/bwabdf9z(v=vs.110).aspx but this pattern isn't pervasive in the BCL. This method doesn't take a state parameter so it's pretty much impossible to use without allocating.

The benefit of a push model like this is that we can do 0 allocations (using the string builder's memory directly without allocating the string). If we're going to do this I suggest we do it across the board on things that allocate internally. We need a sync and async version as well:

sb.CopyTo(callback, state);
await sb.CopyToAsync(callback, state);

[davidfowl]

More generally, maybe StringBuilder should be a TextWriter and there should have been a CopyTo and CopyToAsync on TextWriter that took a TextReader similar to Stream.CopyToAsync.

[stephentoub]

We need a sync and async version as well

Can you share examples from ASP.NET where these would be used?

[stephentoub]

there should have been a CopyTo and CopyToAsync on TextWriter that took a TextReader

I'm not following. Did you mean CopyTo{Async} on TextReader that took a TextWriter? And that StringBuilder should have been a TextReader(which would be counterintuitive)?

[vancem]

I suspected that this API would solicit lively feedback and that certainly seems to be the case. Lets write down some principles that hopefully will help in deciding more details of the design.

1. StringBuilder is not thread-safe (this is true today). Thus we don't care if it values are not well defined on concurrent access, however we would strongly prefer that even in the presence of concurrency that we don't break type/memory safety (e.g. you don't access things beyond the bounds of the array that holds them).

2. This new API is not essential (after all we have lived without it for > 10 years), and the primary motivation for it is efficiency. Thus we should be catering to a more advanced user who is willing to sacrifice some ease of use to get that efficiency.

3. Implementations should be biased toward small strings (e.g. likely statistics are 90% < 1K (1 chunk), 99% of strings are < 1M), but of course should handle strings of any size up to 2GB characters (the limit).

4. This API is meant to NOT mutate. We may not be able to enforce that completely, but the intent is for it to be non-mutating. I would also argue that doing mutation in a non-mutating call (e.g. reversing pointers and unreversing them), is not a good idea.

5. It is likely that a common scenario for this API is to perform I/O on the string (write it out to a stream) and these APIs are likely to be Async (they may block). This argues that the proposed API above not sufficient (we need to work through that scenario).

For what it is worth, issues about reversing the chunks that were brought up is definitely solvable. Most likely by having a stack-based structure that works for cases < some number of chunks, and it bails to either an N*N or heap allocated case for very large number of chunks. Thus I would not worry about this. The big issue in my mind is the Enumerable vs Callback (which).

We should explore the Enumerable design, but it is not clear to me, how this interacts with Span and async. I need to think about it a bit...