Monday, April 16, 2007

Childhood Memories

Today, Miguel asked me to take a look at fixing some of the System.Console 2.0 bugs. I managed to fix some of the ReadKey() and ReadLine() bugs, although the Backspace bug illustrated in Iron Python is still out there (it appears that the cursor X,Y position is not correctly kept track of in Mono).

Earlier today, when Miguel was explaining to me what sorts of problems existed in System.Console, one of the things he was hoping I could take a look at (although there was no bug # that I know of?) was optimizing Console.Write[Line]().

I didn't actually have time to look at that until tonight when I was sitting at my home computer waiting for my dinner to finish cooking. The solution was fairly simple (for those interested in seeing the patch, check out revision 75806).

An important part of optimizing a section of code is to compare actual running times of the old code vs the new code (and, obviously, to check that the results are correct), so I wrote a simple program that could be measured for performance improvements:

using System;

public class Program {
    static void Main () {
        Console.ForegroundColor = ConsoleColor.Cyan;
        string abc = new String ('a', 100000);
        Console.WriteLine (abc);
    }
}

Using the system `time' command, I got the following times:

pre optimization:

real 0m13.177s
user 0m0.308s
sys 0m0.232s

post optimization:

real 0m0.238s
user 0m0.124s
sys 0m0.004s

Wowzers!

Anyways, the reason the title of this blog is "Childhood Memories" is because after running this test program, I couldn't help but remember my first assembler program for the 6502 that I wrote back when I was 8 years old - it was a program which filled the screen with the character 'A' (which I then compared to a program written in BASIC that did the same thing). The difference in speed here was about the same as it was back then, too, funnily enough :)

Update: This morning I woke up realizing that I had a bug in my optimization patch last night, but I had a fix that lost no performance and then later today (in part thanks to Alan's prompting me to re-evaluate my need for a temporary buffer, which truly became unnecessary after my fix this morning) was able to optimize it even further (and eliminated the need for a temporary buffer) by blitting chunks of the input buffer between special escape sequences at a time (we have to handle certain escape sequences specially as they can relocate the cursor).

Oh, and the Iron Python bug is now solved... it was actually arguably a bug in Iron Python in that it goes behind Mono's back when writing to stdout so it was impossible for us to keep track of the cursor position. They do, however, use Console.In.ReadLine() (would be better if they simply used Console.ReadLine() but I digress), and so what I did was make ReadLine() query the terminal for the cursor position (rather than rely on our own state).

5 comments:

Unknown said...

Show us the 6510 assembly code :) And did you use any of the illegal opcodes back then? I remember using some of these opcodes to optimize a routine to set a single pixel to the screen. Iirc I was able to reduce the routine from 100 cycli to about 80 (on a 1.02 MHz machine).

Anonymous said...

Mr. Jeffrey Stedfast, I am really interested with your writing about Insertion sort and your optimizations.
I wonder if you allow me to use your writing as my reference due to my course assignment.
I am a third year student in University of Indonesia. My major is computer science.
I have an assignment to write a paper about any kind of algorithm(the course name is "Algorithm Analysis & Design") and i choose insertion sort as my topic.
After i googled, i found your blog and i found that your writing about insertion sort was very interesting.

If you don't mind, don't hesitate to contact me (iap40@ui.edu). Or, just by commenting via my blog.

I'll wait for your soonest reply.

Thanks.

Anonymous said...

I'm sorry, did i forget to show my blog url??

it's ilhamajipratomo.blogspot.com

AJ said...

Umm,i didn't find referance about method "memmove". Where can i find it, Jeff?

Jeffrey Stedfast said...

memmove() is part of POSIX I believe.

Code Snippet Licensing

All code posted to this blog is licensed under the MIT/X11 license unless otherwise stated in the post itself.