Another Lesson on Performance

Just another story you can tell someone who fears that "XYZ might be too slow":

I'm toying with the idea to write a new text editor. I mean, I've written my own OS, my own XML parser and I once maintained XDME, an editor written originally by Matthew Dillon. XDME has a couple of bugs and major design flaws that I always wanted to fix but never really got to it. Anyway.

So what is the best data structure for a text editor in 2008? List of lines? Gap-Buffer? Multi-Gap-Buffer?

XDME would keep the text in a list of lines and each line would point to a character array with the actual data. When editing, the characters would be copied into an edit buffer, the changes made and after the edit, the changed characters would be copied back, allocation a new character array if necessary.

This worked, it was a simple design but it had a flaw: it didn't scale. The length of a line was limited to the max size of the edit buffer and loading a huge file took ages because each line was read, analyzed, memory was allocated ... you get the idea.

So I wanted to make it better. Much better. I'd start with reading the file into a big buffer, chopped into evenly sized chunks to make reading both fast and memory efficient (imagine loading a 46MB file into a single memory chunk - after a couple of changes, I'd need to allocate a second 46MB chunk, copy the whole stuff over, etc, needing twice the amount of RAM for a short time).

During the weekend, I mulled the various ideas over, planned, started with a complex red-black tree structure for markers (positions in the text that move when you insert before them). It's huge, complex. It screams "wrong way!"

So today, I sat back and did what I should have done first: Get some figures. How much does it really cost to copy 4MB of RAM? Make a guess. Here is the code to check:

    public static void main (String[] args)
    {
        long start = System.currentTimeMillis ();
        
        int N = 10000;
        for (int i=0; i<N; i++)
        {
            int[] buffer = new int[1024*1024];
            System.arraycopy (buffer, 0, buffer, 1, buffer.length-1);
        }
        
        long duration = System.currentTimeMillis () - start;
        System.out.println (duration);
        System.out.println (duration / N);
    }

On my machine, this prints "135223" and "13". That's thirteen milliseconds to copy 4MB of RAM. Okay. It's obviously not worth to spend a second to think about the cost of moving data around in a big block of bytes.

That leaves the memory issue. I would really like to be able to load and edit a 40MB file in a VM which has 64MB heap. Also, I would like to be effective loading a file with 40MB worth of line-feeds as well as a file which contains just a single line with 40MB data in it.

But this simple test has solved one problem for me: I can keep the lines in an ArrayList for fast access and need not worry too much about performance. The actual character data needs to go into a chunked memory structure, though.

Morale: There is no way to tell the performance of a piece of code by looking at it.