I'm writing a Roslyn-driven C# editor. Roslyn syntax verification requires me to submit the entire edit buffer of a C# source file for analysis every time a keystroke is pressed. The buffer has to be a snapshot, so I can't wrap the actual live edit buffers.

The current algorithm, waiting for the "Never Optimize" rule to expire: Allocate a fresh char[] array every keystroke, and serialize the editor text into the array, pay no attention to what the actual operation was. 

Surprisingly, the performance isn't terrible. But I'm worried about thrashing the garbage collector with large allocations in large projects. Imagine allocating a 2MB buffer every keystroke while editing a large C# file. That can't be good in the long term. 

I know from an inside source that Visual Studio uses some sort of "binary tree" data structure to submit incremental updates. But the sources for that part of Visual Studio aren't available. 

I imagine an algorithm something along the lines of: split the entire edit buffer up into manageably small pieces. A change to the document will either insert, delete or replace one or more characters every time a key is pressed. So instead of allocating a fresh buffer, use a strategy that splits and patches in changes; then wrap the entire data structure with a an interfaces that presents the fragments as a contiguous sequential block. Instead of allocating massive large-object structures, that are going to force a Gen2 CG, allocate little tiny blocks to effect the patch. 

And presumably some strategy for coalescing, maybe on a lowest-priority thread.

I could go at it adhoc, but I can't help thinking there must be some formal algorithm to deal with this problem. 

Anyone? (A pair of swapped buffers, I suppose. But still...)