Cfrgtkky

In C#, 64bit Windows, .NET 4.5 (or later), and enabling gcAllowVeryLargeObjects in the App.config file allows for objects larger than two gigabyte. That's cool, but unfortunately, the maximum number of elements that C# allows in an array is still limited to about 2^31 = 2.15 billion. Testing confirmed this.

To overcome this, Microsoft recommends in Option B creating the arrays natively. Problem is we need to use unsafe code, and as far as I know, unicode won't be supported, at least not easily.

So I ended up creating my own BigStringBuilder function in the end. It's a list where each list element (or page) is a char array (type List<char>).

Providing you're using 64 bit Windows, you can now easily surpass the 2 billion character element limit. I managed to test creating a giant string around 32 gigabytes large (needed to increase virtual memory in the OS first, otherwise I could only get around 7GB on my 8GB RAM PC). I'm sure it handles more than 32GB easily. In theory, it should be able to handle around 1,000,000,000 * 1,000,000,000 chars or one quintillion characters, which should be enough for anyone!

I also added some common functions to provide some functionality such as fileSave(), length(), substring(), replace(), etc. Like the StringBuilder, in-place character writing (mutability), and instant truncation are possible.

Speed-wise, some quick tests show that it's not significantly slower than a StringBuilder when appending (found it was 33% slower in one test). I got similar performance if I went for a 2D jagged char array (char) instead of List<char>, but Lists are simpler to work with, so I stuck with that.

I'm looking for advice to potentially speed up performance, particularly for the append function, and to access or write faster via the indexer (public char this[long n] {...} )

// A simplified version specially for StackOverflow / Codereview

public class BigStringBuilder

{

    List<char> c = new List<char>();

    private int pagedepth;

    private long pagesize;

    private long mpagesize;         // https://stackoverflow.com/questions/11040646/faster-modulus-in-c-c

    private int currentPage = 0;

    private int currentPosInPage = 0;



    public BigStringBuilder(int pagedepth = 12) {   // pagesize is 2^pagedepth (since must be a power of 2 for a fast indexer)

        this.pagedepth = pagedepth;

        pagesize = (long)Math.Pow(2, pagedepth);

        mpagesize = pagesize - 1;

        c.Add(new char[pagesize]);

    }



    // Indexer for this class, so you can use convenient square bracket indexing to address char elements within the array!!

    public char this[long n]    {

        get { return c[(int)(n >> pagedepth)][n & mpagesize]; }

        set { c[(int)(n >> pagedepth)][n & mpagesize] = value; }

    }



    public string returnPagesForTestingPurposes() {

        string s = new string[currentPage + 1];

        for (int i = 0; i < currentPage + 1; i++) s[i] = new string(c[i]);

        return s;

    }

    public void clear() {

        c = new List<char>();

        c.Add(new char[pagesize]);

        currentPage = 0;

        currentPosInPage = 0;

    }



    // See: https://stackoverflow.com/questions/373365/how-do-i-write-out-a-text-file-in-c-sharp-with-a-code-page-other-than-utf-8/373372

    public void fileSave(string path)   {

        StreamWriter sw = File.CreateText(path);

        for (int i = 0; i < currentPage; i++) sw.Write(new string(c[i]));

        sw.Write(new string(c[currentPage], 0, currentPosInPage));

        sw.Close();

    }



    public void fileOpen(string path)   {

        clear();

        StreamReader sw = new StreamReader(path);

        int len = 0;

        while ((len = sw.ReadBlock(c[currentPage], 0, (int)pagesize)) != 0){

            if (!sw.EndOfStream)    {

                currentPage++;

                if (currentPage == c.Count) c.Add(new char[pagesize]);

            }

            else    {

                currentPosInPage = len;

                break;

            }

        }

        sw.Close();

    }



    public long length()    {

        return (long)currentPage * (long)pagesize + (long)currentPosInPage;

    }



    public string ToString(long max = 2000000000)   {

        if (length() < max) return substring(0, length());

        else return substring(0, max);

    }



    public string substring(long x, long y) {

        StringBuilder sb = new StringBuilder();

        for (long n = x; n < y; n++) sb.Append(c[(int)(n >> pagedepth)][n & mpagesize]);    //8s

        return sb.ToString();

    }



    public bool match(string find, long start = 0)  {

        //if (s.Length > length()) return false;

        for (int i = 0; i < find.Length; i++) if (i + start == find.Length || this[start + i] != find[i]) return false;

        return true;

    }

    public void replace(string s, long pos) {

        for (int i = 0; i < s.Length; i++)  {

            c[(int)(pos >> pagedepth)][pos & mpagesize] = s[i];

            pos++;

        }

    }



    // Simple implementation of an append() function. Testing shows this to be about

    // as fast or faster than the more sophisticated Append2() function further below

    // despite its simplicity:

    public void Append(string s)

    {

        for (int i = 0; i < s.Length; i++)

        {

            c[currentPage][currentPosInPage] = s[i];

            currentPosInPage++;

            if (currentPosInPage == pagesize)

            {

                currentPosInPage = 0;

                currentPage++;

                if (currentPage == c.Count) c.Add(new char[pagesize]);

            }

        }

    }



    // This method is a more sophisticated version of the Append() function above.

    // Surprisingly, in real-world testing, it doesn't seem to be any faster. 

    public void Append2(string s)

    {

        if (currentPosInPage + s.Length <= pagesize)

        {

            // append s entirely to current page

            for (int i = 0; i < s.Length; i++)

            {

                c[currentPage][currentPosInPage] = s[i];

                currentPosInPage++;

            }

        }

        else

        {

            int stringpos;

            int topup = (int)pagesize - currentPosInPage;

            // Finish off current page with substring of s

            for (int i = 0; i < topup; i++)

            {

                c[currentPage][currentPosInPage] = s[i];

                currentPosInPage++;

            }

            currentPage++;

            currentPosInPage = 0;

            stringpos = topup;

            int remainingPagesToFill = (s.Length - topup) >> pagedepth; // We want the floor here

            // fill up complete pages if necessary:

            if (remainingPagesToFill > 0)

            {

                for (int i = 0; i < remainingPagesToFill; i++)

                {

                    if (currentPage == c.Count) c.Add(new char[pagesize]);

                    for (int j = 0; j < pagesize; j++)

                    {

                        c[currentPage][j] = s[stringpos];

                        stringpos++;

                    }

                    currentPage++;

                }

            }

            // finish off remainder of string s on new page:

            if (currentPage == c.Count) c.Add(new char[pagesize]);

            for (int i = stringpos; i < s.Length; i++)

            {

                c[currentPage][currentPosInPage] = s[i];

                currentPosInPage++;

            }

        }

    }

}

    List<char> c = new List<char>();

    private int pagedepth;

    private long pagesize;

    private long mpagesize;         // https://stackoverflow.com/questions/11040646/faster-modulus-in-c-c

    private int currentPage = 0;

    private int currentPosInPage = 0;

Some of these names are rather cryptic. I'm not sure why c isn't private. And surely some of the fields should be readonly?

        pagesize = (long)Math.Pow(2, pagedepth);

IMO it's better style to use 1L << pagedepth.

    public char this[long n]    {

        get { return c[(int)(n >> pagedepth)][n & mpagesize]; }

        set { c[(int)(n >> pagedepth)][n & mpagesize] = value; }

    }

Shouldn't this have bounds checks?

    public string returnPagesForTestingPurposes() {

        string s = new string[currentPage + 1];

        for (int i = 0; i < currentPage + 1; i++) s[i] = new string(c[i]);

        return s;

    }

There's no need for this to be public: you can make it internal and give your unit test project access with [assembly:InternalsVisibleTo]. Also, since it's for testing purposes, it could probably be marked [System.Diagnostics.Conditional("DEBUG")].

    public void clear() {

        c = new List<char>();

        c.Add(new char[pagesize]);

In C# it's conventional for method names to start with an upper case letter.

There's no need to throw quite as much to the garbage collector. Consider as an alternative:

var page0 = c[0];

c.Clear();

c.Add(page0);

    // See: https://stackoverflow.com/questions/373365/how-do-i-write-out-a-text-file-in-c-sharp-with-a-code-page-other-than-utf-8/373372

Why? I don't think it sheds any light on the following method.

    public void fileSave(string path)   {

        StreamWriter sw = File.CreateText(path);

        for (int i = 0; i < currentPage; i++) sw.Write(new string(c[i]));

        sw.Write(new string(c[currentPage], 0, currentPosInPage));

        sw.Close();

    }

Missing some disposal: I'd use a using statement.

new string(char) copies the entire array to ensure that the string is immutable. That's completely unnecessary here: StreamWriter has a method Write(char, int, int).

    public void fileOpen(string path)   {

        clear();

Yikes! That should be mentioned in the method documentation.

        StreamReader sw = new StreamReader(path);

        int len = 0;

        while ((len = sw.ReadBlock(c[currentPage], 0, (int)pagesize)) != 0){

            if (!sw.EndOfStream)    {

                currentPage++;

                if (currentPage == c.Count) c.Add(new char[pagesize]);

            }

            else    {

                currentPosInPage = len;

                break;

I think this can give rise to inconsistencies. Other methods seem to assume that if the length of the BigStringBuilder is an exact multiple of pagesize then currentPosInPage == 0 and c[currentPage] is empty, but this can give you currentPosInPage == pagesize and c[currentPage] is full.

This method is also missing disposal.

    public long length()    {

        return (long)currentPage * (long)pagesize + (long)currentPosInPage;

    }

Why is this a method rather than a property? Why use multiplication rather than <<?

    public string substring(long x, long y) {

        StringBuilder sb = new StringBuilder();

        for (long n = x; n < y; n++) sb.Append(c[(int)(n >> pagedepth)][n & mpagesize]);    //8s

What is 8s? Why append one character at a time? StringBuilder also has a method which takes (char, int, int).

    public bool match(string find, long start = 0)  {

        //if (s.Length > length()) return false;

        for (int i = 0; i < find.Length; i++) if (i + start == find.Length || this[start + i] != find[i]) return false;

        return true;

    }

What does this method do? The name implies something regexy, but there's no regex in sight. The implementation looks like StartsWith (by default - the offset complicates it).

    public void replace(string s, long pos) {

        for (int i = 0; i < s.Length; i++)  {

            c[(int)(pos >> pagedepth)][pos & mpagesize] = s[i];

            pos++;

        }

    }

Bounds checks?

    // This method is a more sophisticated version of the Append() function above.

    // Surprisingly, in real-world testing, it doesn't seem to be any faster. 

I'm not surprised. It's still copying character by character. It's almost certainly faster to use string.CopyTo (thanks to Pieter Witvoet for mentioning this method) or ReadOnlySpan.CopyTo.

Design considerations

In the comments you mentioned that you're going to analyze and manipulate this string? If so, that could be a problem, because replacing, inserting and removing text requires moving all subsequent characters to make room or to fill the gap. With this much data, you can expect that to have a major impact on performance. That is why I mentioned data structures like ropes, gap buffers and piece tables: those are often used in text editors to efficiently support these kind of operations.

But I think that would be solving the wrong problem. From what I understand so far, the rest of your code is built around a 2D array of strings - a table, essentially - that can be converted to a variety of formats. Because it's an array, you need to know the number of columns and rows up-front, so you need to parse the input before you can allocate the array, and then parse it again to fill the array. This BigStringBuilder class allows you to read the whole file into memory, so you don't have to read it from disk twice.

Why not use dynamically resizable arrays (List<T>) instead? That would allow you to read the data directly into your final data structure with only a single parsing pass. If that requires a lot of work, then you're probably suffering from a lack of abstraction. Instead of passing a raw string[,] around, wrap it in a class. That allows you to swap the internal 2D array for a more suitable data structure without having to modify all the code that uses this table.

For example, a List<List<string>> as internal data structure lets you add variable-length rows on-the-fly, so you only need a single parsing pass. That also allows you to read the input file in a streaming fashion instead of having to read it fully into memory first.

If modifying existing code that relies in a 2D string array sounds like a lot of work, consider emulating the 'interface' of a 2D array. With a class that provides a string this[int row, int column] indexer and a GetLength(int dimension) method, chances are that you only need to change the type of a bunch of parameters and variables.

Other notes

• Putting if and for bodies on the same line makes control flow difficult to follow.


• 
  fileSave and fileOpen are not very flexible. Letting the caller pass in a Stream or TextReader/TextWriter would make them more reusable. That also gives callers control over things like encoding and buffer size. Additionally, overloads like CopyToStream(Stream toStream, long offset, long count) and CopyFromStream(Stream fromStream, long count) are probably also a good idea.


• 
  c[(int)(n >> pagedepth)][n & mpagesize] is duplicated several times in the code. Use this[n] instead.


• There's very little documentation, especially for infrastructure-level code like this. I don't know about you, but I tend to forget things about code I wrote a while ago, so documentation that explains why something works the way it does, or how something is intended to be used, is quite useful.


• I'd recommend using more self-descriptive names, and aiming for consistency with the standard types you're 'emulating':
  
  
  
  
  • 
    this[n] -> this[index]
    
  
  
  • 
    substring(x, y) -> Substring(startIndex, length)
    
  
  
  • 
    replace(s, pos) -> Overwrite(value, startIndex) (I find replace confusing because it's so different from what string.Replace does)
  
  
  
  


• Regarding camelCase vs PascalCase, I don't see why it's important to distinguish between standard library code and your own, but to each their own I guess. But why the inconsistency in ToString and Append?


• I'd argue that correctness is more important than performance. Leaving out bounds checks should be a last resort, and only when profiling shows that they're actually a bottleneck. Chances are that it's possible to improve the API so you don't need to access individual characters so often.


• I agree with Peter that fileOpen clearing the string-builder is unexpected behavior, in a negative way.
  Certainly the caller can call clear before fileOpen if that's the behavior they want? Otherwise, I would clearly document this.


• 
  length being a method is inconsistent with StringBuilder and other collection types. A little bit of calculation in a property should be fine.


• If you're using returnPagesForTestingPurposes for automated testing then you're testing implementation details, which is a bad idea. If you're using it for debugging, then why not inspect the data with a debugger instead, or use tracepoints?