Precision Computing

In the last article, we talked about the theory behind a sampling profiler.  Let’s go over the code to implement one.  We’ll use this to guide our future optimizations.  You can also download the script here: profile-transcript.msh.

[Edit: Monad has now been renamed to Windows PowerShell. This script or discussion may require slight adjustments before it applies directly to newer builds.]

AKA: Welcome Don McGowan to the Party :)  Don works in the Law and Corporate Affairs organization at Microsoft, and has always been a bright and illuminating voice in our internal discussions.

Case in point -- a bunch of people internally are pretty upset that JC Penny is gouging customers by charging $800 for a vanilla Xbox  Premium system.  Where most people speculate, Don lays down this awesome summary of the situation:

There's plenty of people out there asking why Microsoft doesn't "do something about this".  Well, one reason is that we can't.

It’s great that he’s started blogging.  GrokLaw used to be a good source of information for non-lawyers, but they really rose to fame with their coverage of the SCO case.  Because of that, they’ve really started pandering pretty heavily to the OSDN audience.

[Edit: Fixed a typo]

We now have implemented a working fire effect in a form that’s extremely easy to read.  The intention of the code is clear, our functions are nice and modular, and the algorithms are clear.  However, we need to deal with some performance issues.  For that, we'll take a small digression.

At this point, if performance is of utmost importance, we might consider simply porting our script to a compiled C# cmdlet.  However, we’ll continue this in MSH, applying highly-targeted optimizations to bring the performance up to an acceptable level.

When tackling performance problems, the first rule is to measure the problem.  I can’t stress this highly enough.  It stuns (and saddens) me when I see people parade around on an optimization binge without ever enlisting the help of a profiler, or other measurement tool.  Unless you can guide your optimization efforts with hard performance data, you are almost certainly directing them to the wrong spots.  Random cute performance hacks will quickly turn your code to garbage, often with no appreciable performance gain.  I’ve done my fair share of micro-optimization, but it’s always been under the guidance of hard data to support it. 

Now, let’s investigate sources of our performance problems by measuring them.

The easiest way is to probably comment out function calls to see their effect on our refresh rate.  If we comment out the calls to both updateBuffer and updateScreen in our Main function, then we get about 8,000 frames per second.  If we comment out only the call to updateBuffer, we get about 3.7 frames per second.  If we comment out only the call to updateScreen, we get about 0.54 frames per second.  We can continue to comment out chunks of code, slowly determining what causes the most drastic effect on our script’s performance.

However, that’s not very elegant.  It’s slow, and inefficient.  We should really rely on a profiler to provide us the information we need.  But MSH doesn’t have a script profiler.

Is that going to stop us?  Not in the least.  In fact, it will barely slow us down.  With a surprisingly small amount of bubble gum and handy twine, we’ll write our own – in MSH, of course.

There are two approaches one can take when writing a profiler.  The first is an instrumenting profiler, and the second is a sampling profiler.

Instrumenting profilers inject code at the beginning and end of every call to measure the time spent in that call.  The idea is fairly straight-forward, but the technique is fairly invasive.  The instrumentation process itself can skew the performance profile of a program, so the profiler needs to calibrate itself to account for that.  In addition, robust code instrumentation is extremely difficult.  Binary instrumentation is much easier, so nearly all instrumenting profilers take this approach.

Sampling profilers semi-randomly peek into a program to see what statement it is currently executing.  If we see the program executing a certain statement half of the times we check, we can be fairly confident that our program is spending about 50% of its time executing that statement.  Likewise, if we see the program executing a certain statement 8 out of the 50 times we check, we can be fairly confident that our program is spending about 16% of its time executing that statement.  When we apply this idea to a much larger sample set, we can fairly accurately map the execution time of each individual statement.

We’re going to primarily implement a sampling profiler for several reasons:

• There is no concept of an MSH Script Binary.  If we implement an instrumenting profiler, we have only the very perilous path of mangling the script itself.
• Monad has several bits of infrastructure available that make a sampling profiler surprisingly easy to implement.

So how do we peek in on the MSH engine to see which line of script it’s currently executing?  Very indirectly. 

1. Turn on MSH script tracing (at level 1,) as outlined as part of Jon Newman’s excellent series of posts.
   MSH:116 C:\Temp >set-mshdebug –trace 1
2. Turn on file logging for our session:
   MSH:117 C:\Temp >start-transcript
3. Start our script

Once the script starts, we get entries similar to this in the transcript log for our session:

(…)
DEBUG:  113+             $colour = $screenBuffer[$baseOffset]
DEBUG:  114+             $colour += $screenBuffer[$baseOffset - 1]
DEBUG:  115+             $colour += $screenBuffer[$baseOffset + 1]
DEBUG:  116+             $colour += $screenBuffer[$baseOffset +
$windowWidth]
(…)

Now, we can see what line of script the engine is currently executing by looking at the last bit of output that made it to the log.

Here is an example of the output – we’ll go over the code next time:

Breakdown by line:
----------------------------
 15%: Line  123 -             if($colour -lt 20) { $colour -= 1 }
 14%: Line  122 -             if($colour -le 70) { $colour -= 3 }
 11%: Line  124 -             if($colour -lt 0) { $colour = 0 }
 10%: Line  128 -             $tempWorkingBuffer[$baseOffset -
  8%: Line  117 -             $colour /= 4.0
  7%: Line  121 -             if($colour -gt 70) { $colour -= 1 }
  6%: Line  154 -             $nextScreen[$row, $column] = `
  6%: Line  113 -             $colour = $screenBuffer[$baseOffset]
  6%: Line  115 -             $colour += $screenBuffer[$baseOffset + 1]
  6%: Line  116 -             $colour += $screenBuffer[$baseOffset +
  5%: Line  114 -             $colour += $screenBuffer[$baseOffset - 1]
  5%: Line  109 -             $baseOffset = ($windowWidth * $row) +
  0%: Line   90 -         if($random.NextDouble() -ge 0.20)
  0%: Line  152 -         for($column = 0; $column -lt $windowWidth;
  0%: Line   94 -             $screenBuffer[($windowHeight - 2) *

Breakdown by marked regions:
----------------------------
  6%: updateScreen
  0%: startFireLastRow
 93%: propigate
  0%: Unmarked
  0%: main

[Edit: Monad has now been renamed to Windows PowerShell. This script or discussion may require slight adjustments before it applies directly to newer builds.]

Now that we’ve generated the palette, the most complex part of the algorithm is actually behind us.  The remaining code implements the fire algorithm, and is fairly simple:

1. Generate fire on the bottom row of the screen.
2. Move the already existing fire upwards on the screen.  Rather than just move every cell of fire upwards, though, we take into account the fact that heat is always affected by nearby heat.  So the fire that we move upwards will actually be the average heat from its four neighboring cells.

Another technique that we implement is called “double buffering.”  If we were to update each cell on the screen as we compute it, the graceful effect of frame-by-frame animation would be destroyed.  It looks like the progressive text of a teleprompter, as compared to the subtle scrolling of credits at the end of a movie.  To combat this, we draw each new frame onto a pretend screen (which is one buffer.)  As soon as we’re finished our calculations, we bulk-update the real screen (which is the second buffer.)

The updated implementation is below, and also here: burn-console-1.working.msh.  The two new functions are updateBuffer and updateScreen, along with a little bit of new code in the main function.  The performance is atrocious, though.  I get about 0.4 frames per second on my computer, so we’ll work on improving that over the next two posts.  In fact, we’ll be in the mid 30s for frames per second by the time we’re done.

BTW – for a bit more visual realism, change your console font to either the 4x6 raster font, or the 5pt Lucida Console font.

[Edit: Monad has now been renamed to Windows PowerShell. This script or discussion may require slight adjustments before it applies directly to newer builds.]

This came up on SecurityFocus a few days ago, and it's extremely cool: cracking safes with thermal imaging.

The idea behind the attack is that your fingers transfer enough heat to the keypad to be visible for a significant amount of time afterwards.  The equipment costs around $10,000 -- but that may be a pittance compared to how much the safe has inside.

http://lcamtuf.coredump.cx/tsafe/

As a deeper example of interfacing with the MshHostRawUserInterface class, the next few articles will deal with implementing the classic “Fire Effect” seen in many of the demos that I so fondly remember.  As part of the journey, we’ll also explore some of the ways in which you can improve the performance of time-sensitive portions of your script.

[This GIF is animated.  Some Ad blocking software restricts animation]

What is the fire effect?  It’s a relatively simple algorithm to simulate fire – usually in a graphical buffer.  We’re going to do it in the console text buffer.  In the algorithm, you seed the bottom row randomly with hot pixels.  Then, you progress the fire upwards.  As you progress the fire upwards, you cool it off a little bit – and simulate heat dissipation by averaging the heat from nearby buffer cells.

You can find an excellent write-up of the concepts at http://freespace.virgin.net/hugo.elias/models/m_fire.htm

The first problem we run into is properly representing the shades of the fire.  The fire effect traditionally uses 256 shades of red as its palette.  Colour 255 is the hottest, while colour 0 is the coldest.  That’s difficult when your fire-like console palette is restricted to four fire-like colours from [System.Console]::ConsoleColor – Yellow, Red, DarkRed, and Black.  To get around this problem, we’ll dither our colours.  Newspapers use dithering with great success: by carefully controlling the density in which they place dots of ink, they can simulate a passable grayscale.

Similarly, we can generate many new colours using the high ASCII characters ░ (ALT+176), ▒ (ALT+177), ▓ (ALT+178), and █ (ALT+219) to mix foreground and background colours.  For example, a DarkRed foreground and Black background, applied to character ▒ produces a very dark red. 

Now, visual design isn’t my core competency.  I’d be hard pressed to mix these four colours, using only the ratios implicit in the dithering characters, to create a fire-like palette.  So I’ll cheat, and let the computer do it for me.  I’ll assign a number to each colour that represents its luminosity / intensity, let the computer generate all possible mixes of colours and characters, and then have it organize the resulting mixes it order of total visual intensity.

The code below accomplishes that.  You can also download the script: burn-console-1.palette.msh.

###############################################################################
## burn-console.msh
##
## Create a fire effect in MSH, using the Console text buffer as the rendering
## surface.
##
## Great overview of the fire effect algorithm here: 
## http://freespace.virgin.net/hugo.elias/models/m_fire.htm
##
###############################################################################

function main
{
    ## Rather than a simple red fire, we'll introduce oranges and yellows
    ## by including Yellow as one of the base colours
    $colours = "Yellow","Red","DarkRed","Black"
    
    ## The four characters that we use to dither with, along with the 
    ## percentage of the foreground colour that they show
    $dithering = "█","▓","▒","░"
    $ditherFactor = 1,0.75,0.5,0.25
    
    ## Hold the palette.  We actually store each entry as a BufferCell,
    ## since we need to retain a foreground colour, background colour,
    ## and dithering character.
    $palette = `
        @(new-object System.Management.Automation.Host.BufferCell) * 256
    
    ## Generate, then display, the palette
    clear-host
    generatePalette
    displayPalette

    ## Clean up and exit
    $host.UI.RawUI.ForegroundColor = "Gray"
    $host.UI.RawUI.BackgroundColor = "Black"
}

## Generates a palette of 256 colours.  We create every combination of 
## foreground colour, background colour, and dithering character, and then
## order them by their visual intensity.
##
## The visual intensity of a colour can be expressed by the NTSC luminance 
## formula.  That formula depicts the apparent brightness of a colour based on 
## our eyes' sensitivity to different wavelengths that compose that colour.
## http://en.wikipedia.org/wiki/Luminance_%28video%29
function generatePalette
{
    ## The apparent intensities of our four primary colours.
    ## However, the formula under-represents the intensity of our straight
    ## red colour, so we artificially inflate it.
    $luminances = 225.93,106.245,38.272,0
    $apparentBrightnesses = @{}

    ## Cycle through each foreground, background, and dither character
    ## combination.  For each combination, find the apparent intensity of the 
    ## foreground, and the apparent intensity of the background.  Finally,
    ## weight the contribution of each based on how much of each colour the
    ## dithering character shows.
    ## This provides an intensity range between zero and some maximum.
    ## For each apparent intensity, we store the colours and characters
    ## that create that intensity.
    $maxBrightness = 0
    for($fgColour = 0; $fgColour -lt $colours.Count; $fgColour++)
    {
        for($bgColour = 0; $bgColour -lt $colours.Count; $bgColour++)
        {
            for($ditherCharacter = 0; 
                $ditherCharacter -lt $dithering.Count; 
                $ditherCharacter++)
            {
                $apparentBrightness = `
                    $luminances[$fgColour] * $ditherFactor[$ditherCharacter] +`
                    $luminances[$bgColour] * 
                        (1 - $ditherFactor[$ditherCharacter])
                    
                if($apparentBrightness -gt $maxBrightness) 
                { 
                    $maxBrightness = $apparentBrightness 
                }
                    
                $apparentBrightnesses[$apparentBrightness] = `
                    "$fgColour$bgColour$ditherCharacter"
            }
       }
    }

    ## Finally, we normalize our computed intesities into a pallete of
    ## 0 to 255.  If a given intensity is 30% towards our maximum intensity,
    ## then it should be in the palette at 30% of index 255.
    $paletteIndex = 0
    foreach($key in ($apparentBrightnesses.Keys | sort))
    {
        $keyValue = $apparentBrightnesses[$key]
        do
        {
            $character = $dithering[[Int32]::Parse($keyValue[2])]
            $fgColour = $colours[[Int32]::Parse($keyValue[0])]
            $bgColour = $colours[[Int32]::Parse($keyValue[1])]
            
            $bufferCell = `
                new-object System.Management.Automation.Host.BufferCell `
                    $character, `
                    $fgColour, `
                    $bgColour, `
                    "Complete"
                    
            $palette[$paletteIndex] = $bufferCell
            $paletteIndex++
        } while(($paletteIndex / 256) -lt ($key / $maxBrightness));
    }
}

## Dump the palette to the screen.
function displayPalette
{
    for($paletteIndex = 254; $paletteIndex -ge 0; $paletteIndex--)
    {
        $bufferCell = $palette[$paletteIndex]
        $fgColor = $bufferCell.ForegroundColor
        $bgColor = $bufferCell.BackgroundColor
        $character = $bufferCell.Character

        $host.UI.RawUI.ForegroundColor = $fgColor
        $host.UI.RawUI.BackgroundColor = $bgColor
        write-host -noNewLine $character
    }
    
    write-host
}

. main

[Edit: Monad has now been renamed to Windows PowerShell. This script or discussion may require slight adjustments before it applies directly to newer builds.]

For those of you looking to slake your thirst for Monad on something other than Blogs and Newsgroups, Andy Oakley’s book will soon be available from Amazon: http://www.amazon.com/gp/product/0596100094

It’s called “Monad – Introducing the MSH Command Shell and Language.”  I read it (several times) as one of the technical editors, and it’s a good piece of work.

[Edit: Monad has now been renamed to Windows PowerShell. This script or discussion may require slight adjustments before it applies directly to newer builds.]

As your scripts become more complex, it’s possible that you will have to interact with the user in a manner more complex than write- and read-host.  For example, you might decide to implement a text-based menu system, or even a game of Aliens.

To support this low-level access to the console buffer, hosts (for example, ours,) extend the MshHostRawUserInterface class.  This class provides most of the common operations required by a console-mode raw user interface, including window management, blitting, scrolling, and colour control.

The following script demonstrates some of the ways in which you can work with Monad’s Raw UI.  It illustrates:

• Getting the coordinates of the viewport in relation to the window buffer
• Getting the current cursor location
• Obtaining direct access to the console’s buffer contents
• Scrolling the buffer’s contents
• Directly writing to the console’s buffer
• Working within the constraints of the console’s current width and height