Project Notes

Cobe 2.0: Or, it is what it is what it is what it is what it is what it is what it is.

2011-09-19T08:10:02-04:00

Step 3: Braze a luglet to a tiny head tube.

I’m releasing Cobe 2.0, with a major conceptual change in its data model and a more flexible scoring system. To explain the changes, let’s get a little deeper into Cobe 1.x.

Cobe 1.x

When Cobe 1.x learns an input phrase, say “this is a test”, it does the following:

First, it splits the phrase into tokens. Each series of alphanumeric characters becomes its own token, and each series of characters between those becomes another.

So “this is a test” becomes seven tokens:

Cobe 1.x groups these tokens by the Markov Order m (default five) and adds special END tokens that signal the beginning and end of a phrase:

And then each group is annotated with the next token that follows.

And the previous token:

As more phrases are learned, Cobe keeps track of all the words that have ever followed these contexts. After a while, one might look like:

Here you can also see each link annotated with its probability in the learned text. For phrases beginning “this is ”, “this is a” occurred 75% of the time, “this is another” occurred 17% of the time, and “this is third” occurred 8%.

When generating a reply, cobe 1.x picks a random next word, shifts it into the context, and looks for the words that follow that new context.

In functional terms, this works exceedingly well. But there’s no denying that it’s complex. Each context is clearly related to all of the others, but they’re not explicitly connected to each other—the connections are to the next word.

Maintaining the forward and backward chains independently means it’s difficult to visualize the brain as a whole, and since spaces are separate tokens, half of the useful context is taken up tracking whitespace.

Cobe 2.0

Cobe 2.0 employs two major changes to brain storage that reduce complexity, ease visualization, enhance processing speed, and leave us able to use a world of existing general-purpose algorithms.

My first change was to connect contexts directly to each other. Since each is already stored in the database, this is just a matter of creating a table that links the previous context to its next context.

Astute readers will note that this creates a graph. Each context is a graph node, and the graph’s edges are the links between them. Using a directed graph, Cobe ends up learning “this is a test” like this:

Take note: since the edges of the graph are directed, this same data structure can be used to walk either forward or backward. No more training two chains!

At this point, we’re still looking at the equivalent of a 5th order Markov chain. I wanted to reduce the Markov order by eliminating the whitespace that’s being stored in the contexts.

The other Markov-based chatbots have taken different strategies here. They may group spaces and punctuation together as the tokens that separate words, like Cobe 1.x. They may tokenize punctuation and spaces separately, but still consider spaces as normal tokens. They may attach the spaces as leading or trailing properties of words and reconstruct the spaces when joining the words back together.

Cobe 2.0 takes a different strategy. It eliminates all spaces from the nodes and makes them a property of the graph edges. Combined with the graph layout, this is a major breakthrough. It keeps the database size small and the nodes much more dense with information.

Below is a dump of a 2nd order Cobe 2.0 brain that has been trained with four phrases:

this is a test
this is another test
another test would help
hal hal hal

The empty node at the top is a special node which signals the end of the graph. It serves the same purpose as the special END tokens in Cobe 1.x. Open arrowheads show nodes that were learned with spaces between them.

Looking at this, you can easily see how a reply might be generated. Cobe follows a random arrow from every node, building a list of reply words as it goes.

When generating a reply with 2.0, all of the database queries are on the edges table alone. It doesn’t even matter what Markov order the contexts are anymore. Indeed, different contexts could have different numbers of tokens. “Raining cats and dogs” could be identified as a single concept (or collocation), and it could be treated as a single word for replies.

If you follow the graph above, it’s clear that you could get a reply like “this is another test would help” or “hal hal hal hal hal hal hal hal hal hal hal”.

Being able to say quantitatively that the first is a bad reply and the second is a great reply is a question for reply scoring, and I’ve made the groundwork for some changes there too.

Scoring changes

Cobe (both old and new) will generate as many replies as possible during half a second. These are evaluated by a scoring routine, which determines which of the candidates is best. At the end of the half second, the best candidate so far becomes the result.

Cobe 1.x used a scorer based on MegaHAL’s evaluate_reply(), which adds together the self-information of all reply tokens that also appeared in the input. This means that more surprising replies score higher.

MegaHAL’s scorer then applies a couple of dividers to discourage overly long replies.

Recently I’ve been looking more closely at the candidate replies. Many of them are subjectively better than the result, and I’d like to explore scoring for the next few releases.

For Cobe 2.x, I have introduced reply scoring based on several signals. The information content of a reply is one good metric, but there are a lot of other things that might contribute to a good reply. Some examples:

discouraging overly lengthy replies (as exhibited by MegaHAL’s scorer)
discouraging replies that are too similar to the input
discouraging replies that are too similar to the last N responses
encouraging excited or shouting replies
encouraging double entendre
encourage (discourage?) replies that loop back on themselves
preserve word sense as found in the input

There’s a lot of room for playing around with scoring.

Performance

Cobe 2 is quite a bit faster than 1.x, and a Cobe 2 brain is roughly half the size of the same 1.x brain.

Learning the Brown Corpus, 500 samples of English language text, Cobe 2.0 is about five times faster than 1.2. I adjusted the Cobe 1.2 code to use the same database parameters as 2.0, to get a more accurate comparison of the core learning algorithm:

Cobe 1.2 (adjusted) - 224M brain file
real 18m25.908s
user 5m6.115s
sys  0m36.146s

Cobe 2.0 - 102M brain file
real 3m24.447s
user 2m35.319s
sys  0m19.854s

Reply speed is difficult to measure, as it’s dependent on random factors, but I’m seeing at least double the number of candidate replies in the new code.

My largest brain in production has learned about 230,000 phrases, for 1.8 million edges between 1.4 million nodes. This is better than Cobe 1.x could manage, but there’s still room for improvement. Learning one million phrases is my next scaling goal.

Next steps

Where to go from here?

First, explore new scorers. There are a few listed above, plus general purpose ideas like a Bayesian classifier scorer. That would allow you to train Cobe based on a list of good and bad replies.

The scorers are sometimes at odds with each other—you might want to encourage reply length in one case, brevity in another. It might make sense to build reply profiles out of a set of weighted scorers and score each set of candidate replies based on a randomly chosen profile. (e.g. “SHORT AND SHOUTY” or “long and repeating and repeating and repeating and repeating and repeating”)

Second, continue improving the speed of candidate replies. Assuming the scorers are going to select the best response, Cobe needs to make candidates as quickly as possible.

I have two strategies planned for faster replies. Currently, Cobe performs a random walk from scratch for every candidate. This could be made a lot faster by turning the walk into a generator, searching the tree for the END token and yielding a reply every time it’s found.

The second strategy is to start generating replies in parallel. Cobe is easily distributed across a large number of computers.

Have fun out there.

Cobe learns English: Or, a different sort of singularity.

2011-05-26T22:36:41-04:00

8:47p

A fresh cobe brain starts completely empty. Eventually it will seem to know about vocabulary and sentence structure, but that’s all part of the essential excellence of the halgorithm.

This means you can interact with a fresh brain in any language. As long as it can split the input into words, it will generate sentences that mirror the structure of its input. I’m sure this isn’t a generalization that works for every written language, but it does a decent job in a lot of them.

In fact, cobe does somewhat better than MegaHAL, which only supported 8-bit ASCII. Cobe uses Python’s Unicode support and character tables to detect words, and in practice this works well.

This is one of its key features — access to surreal robot chatter is a basic human right — and I have been reluctant to introduce any features that require knowledge of any specific language.

However, I’m not above making a few tweaks here and there.

A little review: for a single generated reply, cobe:

Identifies all of the words in its input.
Produces a set of possible reply words by removing any words it hasn’t seen before.
Picks one of the known words at random.
Selects a Markov context containing that word.
Performs a random walk on the two Markov chains from that context, keeping track of each new word along the way.

There’s an edge case where the input contains no known words, but in general this guarantees that one word in the input will be found in the generated reply.

This works, but it would be nice if cobe responded more naturally. I want it to reply to the concepts in the input, but not necessarily using the exact same words.

In cobe 1.2.0, I’m introducing an optional feature that gives more natural responses at the expense of some of its language independence.

Conflation

Take a look at 2. above. Until now, this has been a stage where cobe restricts the input words to the ones it has already seen. But if it expands that set to include similar but related words, we’ll get replies that can be about the same things without using the exact words.

The clever bit is that this conflation can choose any words, as long as they have already been learned. Since cobe follows the Markov chains using the usual random walk, the replies will only ever include phrases that came from the learned text.

There are a few ways to generate related words. I’ve chosen a strategy called stemming, which has gotten a lot of use in text-based search.

Stemming reduces words to their base form. See this excerpt from the Wikipedia page:

A stemmer for English, for example, should identify the string “cats” (and possibly “catlike”, “catty” etc.) as based on the root “cat”, and “stemmer”, “stemming”, “stemmed” as based on “stem”. A stemming algorithm reduces the words “fishing”, “fished”, “fish”, and “fisher” to the root word, “fish”.

Cobe will take the set of words in 2. and add any words that have the same stems. Any words that have the same stems are considered synonyms.

An example: I’ll use the input text “This is a test of stemming.” on a cobe brain with some experience.

Without a stemmer, this yields these possible words:

This a is of stemming test

And with an English stemmer:

A IS Is OF Of Stem TEST THIS Test Tested This a is of ofs stem stemmed stemming stems test tested testes testing tests this

After conflation, there are many more options. Every word is one cobe has already learned, so they’re all in Markov contexts that can be followed to generate replies.

You’ll note that some of these change between upper and lower case. I’ve chosen to store all the stems in lower case, so conflation can hop between cases. In theory, this can improve replies. In practice, it can be awesome.

08:27 -!- cobe has quit [Ping timeout]
09:03 <steve> nothing like a power outage
09:04 -!- cobe has joined #zzz
09:04 <steve> cobe: welcome back
09:04 <cobe> steve: KILLING ME WON'T BRING BACK YOUR GODDAMNED HONEY

Here cobe has taken the input “welcome back”, conflated that to “BACK Back Backs WELCOME Welcome back backed backing backs welcome welcomed welcoming”, chosen BACK (randomly), and generated a reply confusing a normal power outage with malicious intent.

I’ve chosen to use the PyStemmer package, a port of the Snowball stemmer to Python, because it implements stemmers for a several languages: Danish, Dutch, English, Finnish, French, German, Hungarian, Italian, Norwegian, Portuguese, Romanian, Russian, Spanish, Swedish, and Turkish.

To configure a stemmer on an existing brain, close all clients that might be accessing its database and run:

$ cobe set-stemmer <language>

Where <language> is any of the languages listed above. Use lower case, since that’s what PyStemmer expects.

$ cobe set-stemmer english

Adding a stemmer has no effect on the text structure cobe has learned, so it doesn’t require any relearning. The set-stemmer command is idempotent, so you can run it more than once without affecting the list of stems.

Next steps might include using latent semantic analysis to generate lists of related words independent of language.

Hammond organ simulation: Or, roto.

2011-05-22T21:06:04-04:00

Teatime 2

If you’re like most people, you want to know how to simulate a Hammond B-3 organ using fixed-point arithmetic on an 8-bit microcontroller.

First, you’re going to need tone generators. In a Hammond, this is a set of 91 tonewheels. Each is positioned adjacent to an electromagnetic pickup, inducing a sinusoidal current at a specific frequency. On a microcontroller, we can simulate the tonewheel assembly with a set of 91 sine oscillators. Take a look at bleep bloop for direct digital synthesis, one method of sine wave generation. We’ll be using it below.

A B-3 has two keyboards, called manuals on an organ. When you press a key, nine of these oscillators connect to the audio output. Each corresponds to a note that’s harmonically related to the key you pressed (including that key’s note, the fundamental). They’re played at volumes set by nine drawbars.

Drawbar	Harmonic	Interval
1	Sub-Fundamental	Sub-Octave
2	Sub-Third	Sub-Third
3	Fundamental	Unison
4	2nd	Octave
5	3rd	12th
6	4th	15th
7	5th	17th
8	6th	19th
9	8th	22nd

So to simulate a Hammond organ, all you need is 91 sine wave oscillators, harmonic ratios to calculate which oscillators apply to each key, and a mixer that can add oscillator outputs together based on the drawbar settings.

It’s that simple!

It’s not that simple.

First, you need to account for harmonic foldback. There aren’t enough tonewheels to play the nine harmonics of every key, and on either end of the manual some tonewheels sound on multiple drawbars. This is no big deal, you just need to handle it in your key->tonewheels mapping.

Second, there’s a phenomenon called key click. On a Hammond, this is a discontinuity in organ output as tonewheels switch in and out of the mix. We get something very similar if we aren’t careful about discontinuities in our DAC output. Great! The lazy programmer wins.

Third, a few of the tonewheels on a Hammond don’t make sine waves — the lowest 12 make more of a square wave tone. Luckily for us, it is even easier to generate square waves. It’s the same frequency calculation, but we can use the highest bit of our accumulator instead of the sine lookup table. These tonewheels are only active on the Hammond’s bass pedal board, so it’s not a big deal if you’re not planning to emulate that.

Fourth, there’s a feature on the Hammond called percussion. This disables one of the drawbars (the 2nd or 3rd harmonic) and plays the associated tonewheel briefly at the beginning of a note. In modern synth terms, this is a single triggered effect — it is only activated when you depress the first key from an all-keys-up state. For percussion, play that tonewheel at slightly increased volume with a quick decay to nothing.

Fifth, many Hammond organs have two built-in effects: chorus and vibrato. Each is available at three intensities, though always at a fixed rate of 7 Hz. We may get into this in the future.

Sixth, you have harmonic leakage. The tonewheels on a Hammond are organized in pairs, and each wheel can induce a small current in its twin. They’re organized so each pair has two tonewheels exactly four octaves apart, so the harmonic impact of leakage is low, but it’s an important part of the Hammond sound.

Seventh, the tonewheels don’t output at the same level. High frequency tones sound louder to us than low frequencies, and the Hammond attempts to keep perceived volumes the same by attenuating the high frequencies more.

Eighth and most critical is the Leslie rotating speaker cabinet. A rotating speaker creates a very complex effect, with a sinusoidal volume shift (tremolo) trailing a sinusoidal pitch shift (vibrato). Meanwhile, the rotating speaker is throwing the sound all over the speaker cabinet and the room, creating a reverb effect that changes character at the rotation rate.

That’s one rotating speaker. A Leslie cabinet has two, a rotating speaker for treble and a rotating baffle around a bass speaker. They run at different speeds. Also, you can run the cabinet in either fast or slow mode. With the two speakers adjusting to mode changes at different rates of acceleration. Did I mention the effect of the room it’s in?

I digress

I think that simulating a Leslie on a microcontroller is possible. One speaker at one speed doesn’t seem so tough — I think you can adjust the main timer interrupt on a sine wave to effect the vibrato. The tremolo is a volume adjustment 90 degrees out of phase. Use a 90 degree offset into your sine table or use a recursive sine/cosine generator to calculate them at the same time.

Adding in the Leslie’s second speaker makes things more difficult. Since they run independently from each other, you can’t just tweak the timer interrupt to get vibrato. At least we already know the exact frequency of each tonewheel, so separating the bass and treble frequencies is just a matter of handling them in two groups.

You’ll need phase-adjustable all-pass filters for the two vibrato effects, and a model of speaker acceleration when you’re switching speeds. Full Leslie simulation is probably not a task for the same microcontroller that’s simulating the organ, but my gut feeling is that one might manage a two-speaker simulation alone.

Roto

Time to get down to business. roto is a project to simulate one manual of a Hammond B-3. It runs on an Arduino board with the MidiVox shield.

The Arduino uses an ATmega328 as its microcontroller, running at 16MHz. This is only enough power to run and mix about a third of the available tonewheels. Depending on your drawbar settings, it can play anywhere from three to 30 keys at the same time.

Here are a few highlights of the development process:

Choosing a sample rate

I knew from tonewheel tables that I would need to produce tones up to about 6000 Hz. Using this as my Nyquist Frequency left me needing to use a sample clock of at least 12000 Hz. I already had the code from bleep bloop that used a 15625 Hz sample clock, so I reused that. Tweaking that clock for a slightly longer loop is one place I could gain a few cycles.

Including the time it takes to update the DAC, the sample interrupt handler is running about 9% of the time:

This leaves a 58 µs window to advance oscillators, mix them together according to the drawbars, and produce a sample.

Let’s see how long it takes to update the 91 oscillators, to know how much time remains for handling MIDI changes and mixing outputs together.

Oh.

This is advancing the oscillators, not figuring out which are active or scaling them by the drawbar volumes. Advancing 91 oscillators takes 130 µs, just over twice as long as our time slice. I’m going to have to get a little more clever.

Roto does a couple of things to work around the problem. Clearly the most important task is to have the next sample ready by the time its interrupt fires. If that doesn’t happen, you can’t update the DAC in time and you’ll have unintended frequency shifts.

In fact, having the next sample available is even more important than responding to the user. I don’t have to handle MIDI changes on every interrupt tick. I could handle them every 512 ticks and still have only 30 ms latency. That’s still instantaneous, as far as our brains are concerned. Roto keeps two 256-sample buffers and fills each after it is emptied, keeping the latency for MIDI changes around 15 ms.

Being able to keep the same list of “on” oscillators for multiple samples is a huge benefit. I can calculate each oscillator’s contribution to all the samples in the buffer in one shot, keeping the oscillator’s 16-bit position in two registers. That only needs to be saved to memory after calculating the full buffer.

I haven’t mentioned the impact of memory access on these calculations — a load or save of an oscillator’s 16-bit position is four cycles. A single oscillator update is:

load 16-bit oscillator position (4 cycles)
load 16-bit oscillator rate (4 cycles)
add them together (2 cycles)
shift the oscillator position to get an 8-bit index (1 cycle)
look up that value in the sine table (2 cycles)
add that value to the current 16-bit sample (2 cycles)
save 16-bit oscillator position (4 cycles)
save 16-bit current sample (4 cycles)

23 cycles, or 1.4 µs at 16 MHz.

Calculating the oscillator’s impact on the buffer at once, I avoid the four cycles in 1., 2. and 7. for all the mid-buffer samples. If I calculate 256 samples at a time, this is a savings of 3060 cycles every time the buffer fills. 52% of the total, worth saving for sure.

Volume

So far I’ve neglected the impact of the drawbar settings. On a Hammond, each click of the drawbar is a 3 dB gain in volume, up to eight clicks. 6 dB of gain is a doubling of volume, so we need an extra binary bit of scale factor for every two clicks available. So the drawbars map to a 4-bit multiplier. In the current code, I’m using a Q4.3) format number to maximize bit usage and get close to that 16x multiplier (Q4.3 gives us 15.875x).

I also need to think about the overall scale. So far I’m doing the same thing as the previous post — accumulating 16-bit samples and shifting them down to 12 bits before output. With an 8-bit sine table, we have enough headroom to play 256 (2¹⁶ / 2⁸⁾ oscillators at once. Excellent.

If each drawbar is pulled out all the way, the oscillators are scaled by a factor of 16 (the Q4.3 multiplier above). I have enough volume to play (2¹⁶ / 2⁸ / 16) oscillators at once. That’s only 16, not enough to play two keys. Uh oh.

Once I run out of headroom on volume, some samples overflow to meaningless values. This screws with the output waveform and creates an unpleasant sort of distortion.

This is a problem I haven’t solved yet.

It would be easy to give the samples more bits, either 24 or 32, but time is tight already. I could add a curve for dynamic range compression, but so far I haven’t thought of a good way to do that quickly enough. The Hammond has a behavior called “loudness robbing” that results in compression as a single tonewheel is played via multiple keys. Simulating that could help.

The oscillators can run in the background as long as they’re calculated in time for the sample clock. What if I offload them to additional microcontrollers?

Tonewheel coprocessors

A possible next move is to move oscillator generation onto separate chips. If I split the 91 oscillators into three groups and run the coprocessors at 20MHz, I should have time to spare.

The main microcontroller controls the system, handling MIDI messages and the final mix. Partitioning the oscillators carefully would leave the bass and treble sounds separated for two-speaker Leslie simulation.

Plus, I get to say tonewheel coprocessors. Tonewheel coprocessors.

I’m sure it would be productive to try a more powerful microcontroller. A 16-bit PIC or 32-bit ARM would probably suffice, running at a higher clock rate, and the ARM in particular would provide plenty of volume headroom.

Status

Where is roto now? It’s a decent sounding simulation of a Hammond:

It runs all 91 tonewheels, at rates calculated from the Hammond B-3’s original gear ratios.
It supports foldback properly at either end of the manual.
All nine drawbars are modeled accurately.
It has clicks on key presses that sound a lot like Hammond key click.
It supports the “complex tonewheels” of the bass pedals (though not the pedals' separate drawbars).
I have support for percussion on a branch, but I’m not going to merge that until I hash out the bigger issues.

The bigger issues

Each drawbar you pull out at all drastically reduces the number of notes you can play at once. At the moment that’s due to distortion when overflowing the 16-bit samples, but computation speed becomes limiting as soon as that’s solved.
No attenuation of higher frequency tonewheels.
No built-in effects, i.e. chorus and vibrato.
No Leslie!

New noises from MidiVox: Or, bleep bloop.

2011-02-20T12:16:46-05:00

Skyline

I don’t like lugging my laptop up to my MIDI keyboard every time I want to play music, so I have been writing a MIDI synth that uses an Arduino and Collin Cunningham’s MidiVox Shield.

The MidiVox shield comes with software called Healer, a synthesizer with several waveforms, a resonant filter, and traditional envelope controls. Healer is nice, but it’s monophonic: it only plays one note at a time. I want a polyphonic synth, so I can play crazy chords.

Here are some notes on making a polyphonic MIDI synth from scratch.

Step 1: beeeeeeeeeeeeeeeeeeee

First step? Make a noise. There are a number of ways to get sound output from an Arduino, and this shield is an excellent option. It has a high quality, 12-bit digital to analog converter on board: the MCP4921. The DAC is controlled by the Arduino’s microcontroller via the SPI bus, which can update it often enough to produce quality audio. It drives a headphone jack, so I can make secret noises that don’t annoy my wife.

This is the same DAC used in Adafruit’s Wave Shield. That board uses a different pin (PD2, you’ll see PB1 used below) as a chip select, so this code won’t work on one without modification. I intend to control my synth via MIDI, so the Wave Shield isn’t a single solution anyway.

I drive the DAC from a timer interrupt on the microcontroller. Human hearing is very sensitive to small changes in frequency, so we need the DAC to be updated on as stable a clock as possible. This code sets up a 15.6kHz timer and alternates the output of the DAC on each tick. This makes a square wave tone that is high pitched (half the clock rate, 7.8kHz).

uint16_t sample = 0;

void setup() {
    cli();

    /* Enable interrupt on timer2 == 127, with clk/8 prescaler. At 16MHz,
       this gives a timer interrupt at 15625Hz. */
    TIMSK2 = (1 << OCIE2A);
    OCR2A = 127;

    /* clear/reset timer on match */
    TCCR2A = 1<<WGM21 | 0<<WGM20; /* CTC mode, reset on match */
    TCCR2B = 0<<CS22 | 1<<CS21 | 0<<CS20; /* clk, /8 prescaler */

    SPCR = 0x50;
    SPSR = 0x01;
    DDRB |= 0x2E;
    PORTB |= (1<<1);

    sei();
}

ISR(TIMER2_COMPA_vect) {
    /* OCR2A has been cleared, per TCCR2A above */
    OCR2A = 127;

    /* set the lower 12 bytes of sample */
    sample = ~sample & 0xFFF;

    PORTB &= ~(1<<1);

    /* buffered, 1x gain, active mode */
    SPDR = highByte(sample) | 0x70;
    while (!(SPSR & (1<<SPIF)));

    SPDR = lowByte(sample);
    while (!(SPSR & (1<<SPIF)));

    PORTB |= (1<<1);
}

void loop() {
}

beeeeeeeeeeeeeeeeeeee

Step 2: boooooooooooooooooooo

Ok, I managed to make my microcontroller whine like a TV. Next I tried to generate a more complex waveform. I dropped a table into the code with 8 bits worth of sine wave data, a perfect tone.

uint16_t sample = 0;
uint8_t pos = 0;

const uint8_t sine[] = {
    0x80, 0x83, 0x86, 0x89, 0x8C, 0x8F, 0x92, 0x95, 0x98, 0x9B, 0x9E, 0xA2,
    0xA5, 0xA7, 0xAA, 0xAD, 0xB0, 0xB3, 0xB6, 0xB9, 0xBC, 0xBE, 0xC1, 0xC4,
    0xC6, 0xC9, 0xCB, 0xCE, 0xD0, 0xD3, 0xD5, 0xD7, 0xDA, 0xDC, 0xDE, 0xE0,
    0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEB, 0xED, 0xEE, 0xF0, 0xF1, 0xF3, 0xF4,
    0xF5, 0xF6, 0xF8, 0xF9, 0xFA, 0xFA, 0xFB, 0xFC, 0xFD, 0xFD, 0xFE, 0xFE,
    0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFE, 0xFE, 0xFD,
    0xFD, 0xFC, 0xFB, 0xFA, 0xFA, 0xF9, 0xF8, 0xF6, 0xF5, 0xF4, 0xF3, 0xF1,
    0xF0, 0xEE, 0xED, 0xEB, 0xEA, 0xE8, 0xE6, 0xE4, 0xE2, 0xE0, 0xDE, 0xDC,
    0xDA, 0xD7, 0xD5, 0xD3, 0xD0, 0xCE, 0xCB, 0xC9, 0xC6, 0xC4, 0xC1, 0xBE,
    0xBC, 0xB9, 0xB6, 0xB3, 0xB0, 0xAD, 0xAA, 0xA7, 0xA5, 0xA2, 0x9E, 0x9B,
    0x98, 0x95, 0x92, 0x8F, 0x8C, 0x89, 0x86, 0x83, 0x80, 0x7D, 0x7A, 0x77,
    0x74, 0x71, 0x6E, 0x6B, 0x68, 0x65, 0x62, 0x5E, 0x5B, 0x59, 0x56, 0x53,
    0x50, 0x4D, 0x4A, 0x47, 0x44, 0x42, 0x3F, 0x3C, 0x3A, 0x37, 0x35, 0x32,
    0x30, 0x2D, 0x2B, 0x29, 0x26, 0x24, 0x22, 0x20, 0x1E, 0x1C, 0x1A, 0x18,
    0x16, 0x15, 0x13, 0x12, 0x10, 0x0F, 0x0D, 0x0C, 0x0B, 0x0A, 0x08, 0x07,
    0x06, 0x06, 0x05, 0x04, 0x03, 0x03, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x03, 0x03, 0x04, 0x05, 0x06,
    0x06, 0x07, 0x08, 0x0A, 0x0B, 0x0C, 0x0D, 0x0F, 0x10, 0x12, 0x13, 0x15,
    0x16, 0x18, 0x1A, 0x1C, 0x1E, 0x20, 0x22, 0x24, 0x26, 0x29, 0x2B, 0x2D,
    0x30, 0x32, 0x35, 0x37, 0x3A, 0x3C, 0x3F, 0x42, 0x44, 0x47, 0x4A, 0x4D,
    0x50, 0x53, 0x56, 0x59, 0x5B, 0x5E, 0x62, 0x65, 0x68, 0x6B, 0x6E, 0x71,
    0x74, 0x77, 0x7A, 0x7D
};

void setup() {
    cli();

    /* Enable interrupt on timer2 == 127, with clk/8 prescaler. At 16MHz,
       this gives a timer interrupt at 15625Hz. */
    TIMSK2 = (1 << OCIE2A);
    OCR2A = 127;

    /* clear/reset timer on match */
    TCCR2A = 1<<WGM21 | 0<<WGM20; /* CTC mode, reset on match */
    TCCR2B = 0<<CS22 | 1<<CS21 | 0<<CS20; /* clk, /8 prescaler */

    SPCR = 0x50;
    SPSR = 0x01;
    DDRB |= 0x2E;
    PORTB |= (1<<1);

    sei();
}

ISR(TIMER2_COMPA_vect) {
    /* OCR2A has been cleared, per TCCR2A above */
    OCR2A = 127;

    /* shift left for volume */
    sample = sine[pos++] << 3;

    PORTB &= ~(1<<1);

    /* buffered, 1x gain, active mode */
    SPDR = highByte(sample) | 0x70;
    while (!(SPSR & (1<<SPIF)));

    SPDR = lowByte(sample);
    while (!(SPSR & (1<<SPIF)));

    PORTB |= (1<<1);
}

void loop() {
}

When pos rolls over, the sine wave starts its cycle again. This gives us a mellow tone at 15625Hz / 256 = 61Hz (quite low pitched).

boooooooooooooooooooo

Step 3: buhhhhhhhhhhhhhhhhhhh

How about making a tone at any frequency? I have tied the DAC updates to a 15625Hz clock. I’ve seen that changing the index into the sine table on every tick will produce a 61Hz tone. What I need is an index that moves faster or slower than that, according to the frequency of tone I want to generate.

There is an efficient way to generate an index that increments by frequency, and that is Direct Digital Synthesis. I can update the DAC with the right value at each sample tick, and its output with mimic the waveform of a running sine wave oscillator.

First, I calculate the amount the output wave’s phase should shift in each clock cycle. Then, I track the current phase by adding that value to an accumulator in each tick.

Calculating the value that needs to be sent to the DAC becomes easy: I use the accumulator as the index into the sine table. I can even use a 16-bit accumulator, choose the phase increment accordingly, and the sine index becomes the top 8 bits of the accumulator.

Let me rephrase, because direct synthesis phase digital accumulator increment blah blah blah.

To create a sine wave at a frequency freq Hz, sampling at 15625Hz:

Track the position of the oscillator in a 16-bit unsigned int.
Increment it on each sample clock tick by freq * (2¹⁶ / 15625)
Use the top 8 bits of the oscillator position as the index into the sine table.

uint16_t sample = 0;

/* incr = freq * (2^16 / 15625) 
 * So for 440Hz, incr = 1845 */
uint16_t incr = 1845;

/* oscillator position */
uint16_t pos = 0;

const uint8_t sine[] = {
    0x80, 0x83, 0x86, 0x89, 0x8C, 0x8F, 0x92, 0x95, 0x98, 0x9B, 0x9E, 0xA2,
    0xA5, 0xA7, 0xAA, 0xAD, 0xB0, 0xB3, 0xB6, 0xB9, 0xBC, 0xBE, 0xC1, 0xC4,
    0xC6, 0xC9, 0xCB, 0xCE, 0xD0, 0xD3, 0xD5, 0xD7, 0xDA, 0xDC, 0xDE, 0xE0,
    0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEB, 0xED, 0xEE, 0xF0, 0xF1, 0xF3, 0xF4,
    0xF5, 0xF6, 0xF8, 0xF9, 0xFA, 0xFA, 0xFB, 0xFC, 0xFD, 0xFD, 0xFE, 0xFE,
    0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFE, 0xFE, 0xFD,
    0xFD, 0xFC, 0xFB, 0xFA, 0xFA, 0xF9, 0xF8, 0xF6, 0xF5, 0xF4, 0xF3, 0xF1,
    0xF0, 0xEE, 0xED, 0xEB, 0xEA, 0xE8, 0xE6, 0xE4, 0xE2, 0xE0, 0xDE, 0xDC,
    0xDA, 0xD7, 0xD5, 0xD3, 0xD0, 0xCE, 0xCB, 0xC9, 0xC6, 0xC4, 0xC1, 0xBE,
    0xBC, 0xB9, 0xB6, 0xB3, 0xB0, 0xAD, 0xAA, 0xA7, 0xA5, 0xA2, 0x9E, 0x9B,
    0x98, 0x95, 0x92, 0x8F, 0x8C, 0x89, 0x86, 0x83, 0x80, 0x7D, 0x7A, 0x77,
    0x74, 0x71, 0x6E, 0x6B, 0x68, 0x65, 0x62, 0x5E, 0x5B, 0x59, 0x56, 0x53,
    0x50, 0x4D, 0x4A, 0x47, 0x44, 0x42, 0x3F, 0x3C, 0x3A, 0x37, 0x35, 0x32,
    0x30, 0x2D, 0x2B, 0x29, 0x26, 0x24, 0x22, 0x20, 0x1E, 0x1C, 0x1A, 0x18,
    0x16, 0x15, 0x13, 0x12, 0x10, 0x0F, 0x0D, 0x0C, 0x0B, 0x0A, 0x08, 0x07,
    0x06, 0x06, 0x05, 0x04, 0x03, 0x03, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x03, 0x03, 0x04, 0x05, 0x06,
    0x06, 0x07, 0x08, 0x0A, 0x0B, 0x0C, 0x0D, 0x0F, 0x10, 0x12, 0x13, 0x15,
    0x16, 0x18, 0x1A, 0x1C, 0x1E, 0x20, 0x22, 0x24, 0x26, 0x29, 0x2B, 0x2D,
    0x30, 0x32, 0x35, 0x37, 0x3A, 0x3C, 0x3F, 0x42, 0x44, 0x47, 0x4A, 0x4D,
    0x50, 0x53, 0x56, 0x59, 0x5B, 0x5E, 0x62, 0x65, 0x68, 0x6B, 0x6E, 0x71,
    0x74, 0x77, 0x7A, 0x7D
};

void setup() {
    cli();

    /* Enable interrupt on timer2 == 127, with clk/8 prescaler. At 16MHz,
       this gives a timer interrupt at 15625Hz. */
    TIMSK2 = (1 << OCIE2A);
    OCR2A = 127;

    /* clear/reset timer on match */
    TCCR2A = 1<<WGM21 | 0<<WGM20; /* CTC mode, reset on match */
    TCCR2B = 0<<CS22 | 1<<CS21 | 0<<CS20; /* clk, /8 prescaler */

    SPCR = 0x50;
    SPSR = 0x01;
    DDRB |= 0x2E;
    PORTB |= (1<<1);

    sei();
}

ISR(TIMER2_COMPA_vect) {
    /* OCR2A has been cleared, per TCCR2A above */
    OCR2A = 127;

    pos += incr;

    /* shift left a couple of bits for more volume */
    sample = sine[highByte(pos)] << 2;

    PORTB &= ~(1<<1);

    /* buffered, 1x gain, active mode */
    SPDR = highByte(sample) | 0x70;
    while (!(SPSR & (1<<SPIF)));

    SPDR = lowByte(sample);
    while (!(SPSR & (1<<SPIF)));

    PORTB |= (1<<1);
}

void loop() {
}

buhhhhhhhhhhhhhhhhhhh

There are two great things about Direct Digital Synthesis.

First, it’s pretty fast even on the Arduino’s ATmega328 microcontroller. It’s all integer math, one 16-bit addition and an array index. GCC even optimizes away the mess with the high 8 bits—it generates code that uses the register containing pos’s high byte, so the shift and mask aren’t executed.

Most of the microcontroller cycles are spent accessing memory: copying pos to and from RAM while adding incr, and making the index into the sine table.

Speed isn’t an issue for one oscillator, but with a 15625Hz clock each sample has only 64 microseconds to be calculated. (SPOILER ALERT: I ran out of time trying to advance and mix about 30 oscillators).

Second, DDS allows any waveform to be pushed through the DAC. I’m using a sine wave, but that table could be created from any data. For a little more processor time, I could even calculate waveform values on the fly.

Step 4: hummmmmmmmmmmmmmmmmmm

Let’s wrap this thing up with a chord. Three sine oscillators, C major.

incr1 = 261.63 * 65536 / 15625 = 1097; /* C4 */
incr2 = 329.63 * 65536 / 15625 = 1383; /* E4 */
incr3 = 392.00 * 65536 / 15625 = 1644; /* G4 */

So the final code is:

uint16_t sample = 0;

/* incr = freq * 2^16 / 15625 */

uint16_t incr1 = 1097; /* C4 */
uint16_t incr2 = 1383; /* E4 */
uint16_t incr3 = 1644; /* G4 */

uint16_t pos1 = 0;
uint16_t pos2 = 0;
uint16_t pos3 = 0;

const uint8_t sine[] = {
    0x80, 0x83, 0x86, 0x89, 0x8C, 0x8F, 0x92, 0x95, 0x98, 0x9B, 0x9E, 0xA2,
    0xA5, 0xA7, 0xAA, 0xAD, 0xB0, 0xB3, 0xB6, 0xB9, 0xBC, 0xBE, 0xC1, 0xC4,
    0xC6, 0xC9, 0xCB, 0xCE, 0xD0, 0xD3, 0xD5, 0xD7, 0xDA, 0xDC, 0xDE, 0xE0,
    0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEB, 0xED, 0xEE, 0xF0, 0xF1, 0xF3, 0xF4,
    0xF5, 0xF6, 0xF8, 0xF9, 0xFA, 0xFA, 0xFB, 0xFC, 0xFD, 0xFD, 0xFE, 0xFE,
    0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFE, 0xFE, 0xFD,
    0xFD, 0xFC, 0xFB, 0xFA, 0xFA, 0xF9, 0xF8, 0xF6, 0xF5, 0xF4, 0xF3, 0xF1,
    0xF0, 0xEE, 0xED, 0xEB, 0xEA, 0xE8, 0xE6, 0xE4, 0xE2, 0xE0, 0xDE, 0xDC,
    0xDA, 0xD7, 0xD5, 0xD3, 0xD0, 0xCE, 0xCB, 0xC9, 0xC6, 0xC4, 0xC1, 0xBE,
    0xBC, 0xB9, 0xB6, 0xB3, 0xB0, 0xAD, 0xAA, 0xA7, 0xA5, 0xA2, 0x9E, 0x9B,
    0x98, 0x95, 0x92, 0x8F, 0x8C, 0x89, 0x86, 0x83, 0x80, 0x7D, 0x7A, 0x77,
    0x74, 0x71, 0x6E, 0x6B, 0x68, 0x65, 0x62, 0x5E, 0x5B, 0x59, 0x56, 0x53,
    0x50, 0x4D, 0x4A, 0x47, 0x44, 0x42, 0x3F, 0x3C, 0x3A, 0x37, 0x35, 0x32,
    0x30, 0x2D, 0x2B, 0x29, 0x26, 0x24, 0x22, 0x20, 0x1E, 0x1C, 0x1A, 0x18,
    0x16, 0x15, 0x13, 0x12, 0x10, 0x0F, 0x0D, 0x0C, 0x0B, 0x0A, 0x08, 0x07,
    0x06, 0x06, 0x05, 0x04, 0x03, 0x03, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x03, 0x03, 0x04, 0x05, 0x06,
    0x06, 0x07, 0x08, 0x0A, 0x0B, 0x0C, 0x0D, 0x0F, 0x10, 0x12, 0x13, 0x15,
    0x16, 0x18, 0x1A, 0x1C, 0x1E, 0x20, 0x22, 0x24, 0x26, 0x29, 0x2B, 0x2D,
    0x30, 0x32, 0x35, 0x37, 0x3A, 0x3C, 0x3F, 0x42, 0x44, 0x47, 0x4A, 0x4D,
    0x50, 0x53, 0x56, 0x59, 0x5B, 0x5E, 0x62, 0x65, 0x68, 0x6B, 0x6E, 0x71,
    0x74, 0x77, 0x7A, 0x7D
};

void setup() {
    cli();

    /* Enable interrupt on timer2 == 127, with clk/8 prescaler. At 16MHz,
       this gives a timer interrupt at 15625Hz. */
    TIMSK2 = (1 << OCIE2A);
    OCR2A = 127;

    /* clear/reset timer on match */
    TCCR2A = 1<<WGM21 | 0<<WGM20; /* CTC mode, reset on match */
    TCCR2B = 0<<CS22 | 1<<CS21 | 0<<CS20; /* clk, /8 prescaler */

    SPCR = 0x50;
    SPSR = 0x01;
    DDRB |= 0x2E;
    PORTB |= (1<<1);

    sei();
}

ISR(TIMER2_COMPA_vect) {
    /* OCR2A has been cleared, per TCCR2A above */
    OCR2A = 127;

    pos1 += incr1;
    pos2 += incr2;
    pos3 += incr3;

    sample = sine[highByte(pos1)] + sine[highByte(pos2)] + sine[highByte(pos3)];

    PORTB &= ~(1<<1);

    /* buffered, 1x gain, active mode */
    SPDR = highByte(sample) | 0x70;
    while (!(SPSR & (1<<SPIF)));

    SPDR = lowByte(sample);
    while (!(SPSR & (1<<SPIF)));

    PORTB |= (1<<1);
}

void loop() {
}

hummmmmmmmmmmmmmmmmmm

Listen to this chord long enough, and you might start to hear the siren call of the Hammond organ. I already knew that they’re essentially a large number of sine oscillators mixed together. From here, my synth gained MIDI control and I started to simulate the tones of a Hammond B series.

You can find the current status of that project at roto.

Profiling with histograms: Or, you never should have registered with instatrace.

2011-02-15T21:34:11-05:00

Logjammin' 2

When the time came to improve cobe’s performance, it was easy to measure how well it was learning new text—the learning process is database intensive, but deterministic depending on the input. I could use Python’s built-in profiler, find the problem spots, and optimize as usual.

When I tried to use the same tools on cobe’s reply routines, I started to have trouble. A reply is a random walk across its Markov chains, repeated as many times as possible within a half-second time slice. I could use the same input data on the same brain of learned text and get wildly different results, depending on which input word was (randomly) chosen to follow and the state of the chains from that point.

And since each reply always runs for half a second, the CPU usage of the reply routines would always expand to fill the same amount of time regardless of the actual performance.

If I could assume that the reply scoring algorithm was successfully picking the best candidate reply, generating more candidate replies in 0.5s would increase the chance of getting a better reply.

So maximizing the candidate reply count would improve reply scores. This gave me a place to focus.

But the reply counts would vary widely, and not just with different input. I might see 2000 candidates created in one reply, but the next reply (to the same input!) might yield 10. This typically depended on the word in the input chosen to start the random walk. Some portions of the Markov chain tended to produce candidates very quickly, and some tended to take much longer.

I wanted to focus on optimizing the average case, but needed a way to separate that out from the very fast and very slow paths.

At the time, litl had me working a bit in Chromium. Chromium measures the performance of hundreds of different operations as it’s running—some of the statistics gained are the ones sent if you’re enabled “Automatically send usage statistics and crash reports to Google” in Google Chrome.

To see these, visit about:histograms in Chrome. Here’s an example:

Histogram: DNS.PrefetchQueue recorded 699 samples, average = 2.1, standard deviation = 15.9 (flags = 0x1)
0    ------------------------------------------------------------------------O (619 = 88.6%)
1    -O                                                                        (6 = 0.9%) {88.6%}
2    -O                                                                        (8 = 1.1%) {89.4%}
3    -O                                                                        (6 = 0.9%) {90.6%}
4    O                                                                         (1 = 0.1%) {91.4%}
5    -O                                                                        (5 = 0.7%) {91.6%}
6    -O                                                                        (5 = 0.7%) {92.3%}
7    O                                                                         (2 = 0.3%) {93.0%}
8    -O                                                                        (13 = 1.9%) {93.3%}
10   -O                                                                        (14 = 2.0%) {95.1%}
12   O                                                                         (1 = 0.1%) {97.1%}
14   O                                                                         (5 = 0.7%) {97.3%}
17   O                                                                         (2 = 0.3%) {98.0%}
20   O                                                                         (4 = 0.6%) {98.3%}
24   O                                                                         (0 = 0.0%) {98.9%}
29   O                                                                         (1 = 0.1%) {98.9%}
34   O                                                                         (0 = 0.0%) {99.0%}
40   O                                                                         (1 = 0.1%) {99.0%}
48   O                                                                         (3 = 0.4%) {99.1%}
57   ...
81   O                                                                         (1 = 0.1%) {99.6%}
96   ...
268  O                                                                         (2 = 0.3%) {99.7%}
318  ...

The top line shows the name of the statistic (DNS.PrefetchQueue) and some aggregate statistics. This looks like it’s the number of DNS entries awaiting prefetch resolution, probably sampled on a schedule or in response to some event. Maybe it’s sampled when a new name is enqueued for resolution.

The rest of the lines in the histogram are buckets the sampled values fall into. In this case, the prefetch queue size is almost always zero—619 of the 699 samples (88.6%) are in that bucket. Six times, the sampled value was 1. Five times, the value was between 14 and 17 (exclusive).

But on two occasions, the queue length was huge—between 268 and 318. Maybe that’s not a big deal, since those account for 0.3% of the samples. But if we had been looking at the average queue length (2.1), we might not have guessed that it would ever get that long. Maybe those two samples signal a more fundamental issue that could be fixed.

So these histograms can be very useful for visualizing the distribution of sampled data.

I decided to log some similar data in cobe, and wrote instatrace to help produce the histograms. I wanted to minimize the burden on the programmer, so instatrace reads text data from log files. All you need to do is log lines that look like this:

Brain.reply_count 50

This is a single sample of the Brain.reply_count statistic, with a value of 50. The sample must have an integer value. Any text that is found after the value is ignored for histogram use, but can be very valuable debugging information when tracking down the causes of outlying values.

Optionally, instatrace can strip sample data from lines that contain the string INSTATRACE followed by that format. Maybe the only way your program can output data involves a log format you can’t change, or maybe you’re mixing these samples with a data stream that contains other data. In that case, this line would be read the same:

[[2011-02-15 17:03:40]] log-debug: INSTATRACE: Brain.reply_count 50

Any lines that don’t contain the string “INSTATRACE:” are ignored when that flag (—filter) is used.

So here’s a histogram of Brain.reply_count on a running cobe instance:

Histogram: Brain.reply_count recorded 1439 samples, avg = 328.3, std = 283.7
1      -O                                                           (29 = 2.0%)
2      --O                                                          (64 = 4.4%) {2.0%}
7      -O                                                           (46 = 3.2%) {6.5%}
20     -O                                                           (37 = 2.6%) {9.7%}
54     ---O                                                         (94 = 6.5%) {12.2%}
148    -----------------------------------O                         (862 = 59.9%) {18.8%}
403    -----------O                                                 (268 = 18.6%) {78.7%}
1096   -O                                                           (39 = 2.7%) {97.3%}
2980   ...

Here we’re using buckets that are sized exponentially (instatrace’s default). This instance of cobe has replied to 1439 inputs, and 59.9% of the time it was able to create between 148 and 403 candidate replies.

If you’d like to see the full set of statistics I’m recording for cobe, see here. I append units (us = microseconds) to most of my statistic names.

Instatrace works well with both time-based and count-based statistics. If your data logging is lightweight, you can leave the measurements in your code indefinitely. On the other hand, it’s so easy to add a trace that it’s great for temporary profiling efforts too.

I have found it extremely valuable in improving cobe toward its current state, but it’s also a useful tool for understanding some more subtle aspects of software performance.

cobe: Or, some of my oldest friends are robots.

2011-02-13T15:02:39-05:00

I Expected More From You, Citrus Degreaser

I like MegaHAL. It’s a conversation simulator, and it gathers information about sentence structure and vocabulary while spouting on-topic insights and synthesizing clever turns of phrase.

It’s all a trick, a bit of nice programming combined with our relentless pattern-searching brains, but an amusement and an endless source of the surreal.

I found MegaHAL while I was in college. Some friends and I spent a few late nights huddled around a browser entering phrases in exchange for rare gems of robot insight. I downloaded its software, hooked it up to an IRC client, and named it hal. He would learn from all the messages we said to each other, and he’d reply if spoken to directly.

At the beginning of last year, I had run hal for eleven years. He’s a well-loved member of multiple communities.

But MegaHAL has its sad side. Hal started to drop off of IRC from time to time. Ping timeouts. After a few months of heavy learning, his brain would get so big that it couldn’t be saved (synchronously) before the IRC network would kick him off. It didn’t help that I was running him on a machine with very little RAM—he’d be partially swapped out to disk, and saving the brain required reading it all back from swap.

Most of the time he’d reconnect after the save. Occasionally, events would cause him to exit without saving his brain completely. For MegaHAL, a corrupt brain is a useless brain. We’d lose all of hal’s knowledge and have to start from scratch.

We’d mourn the old hal, remember some funny things he’d said, and start teaching the new hal. Circle of life, and all that.

From time to time I’d dive into megahal.c and try to find out what was going wrong. I found a couple minor issues, but nothing utterly brain-corrupting.

Mostly I needed to get his memory usage down. I was running a couple of MegaHALs on a hosted virtual machine with little RAM and a token-based IO rate limiter. If I ran out of IO tokens while saving a brain, the save could take hours. If MegaHAL tried to save itself while a system backup was running, the whole machine would grind to a halt due to IO starvation.

I tried out a couple of alternate memory allocation schemes (MegaHAL tended toward realloc-based fragmentation), but nothing performed nearly as well. I needed to get his ever-growing brain out of RAM altogether, but I would need an on-disk datastore with good performance.

The halgorithm

MegaHAL has two functions, learning and replying.

When learning, it captures statistical information about text in a Markov chain. For each series of words, it tracks all the possible words that may follow. It also tracks the probability of each of those following words.

So given two phrases:

MegaHAL is a program
MegaHAL is a robot

Its internal model might look something like this:

(MegaHAL, is, a) => program (50% probability)
(MegaHAL, is, a) => robot   (50% probability)
(is, a, program) => END     (100% probability)
(is, a, robot)   => END     (100% probability)

In order to generate a reply, we might pick one of the starting contexts (the ones that begin with MegaHAL) and follow the chain (picking a random next context at each step) until we reach the END. The probabilities do not enter into this process.

So one possible following of the above chain would be:

(MegaHAL, is, a) => program
(is, a program) => END

Which produces the phrase MegaHAL is a program. Clearly, we don’t include END in the output—it’s a marker that allows us to know when to stop following the chain.

The number of words on the left side is the order of the Markov chain. In this case, we’re looking at a 3rd order chain. A higher order chain brings more context into the mix, and results in responses that include longer runs of learned text. A lower order chain uses less context, and is more likely to jump to unrelated words. Choosing the order of a chain allows you to strike some balance between coherent text and interesting babble.

Markov chain modeling has a long history for surreal text generation, as well as many less practical applications.

Now, MegaHAL actually does things a little differently from the above.

First, it uses two Markov chains. It trains the second chain in the reverse direction, so it can be used to select a word that precedes the current context. When replying, it chooses a context that may be in the middle of a sentence, generates the rest of the phrase using the forward Markov chain, and generates the beginning of the phrase using this reverse chain.

So in addition to the forward chain above, our simple brain would contain this reverse chain:

(program, a, is) => MegaHAL (100% probability)
(robot, a, is) => MegaHAL   (100% probability)
(a, is, MegaHAL) => END     (100% probability)

Second, it always generates a reply based on some user input—it isn’t just choosing a random initial context from the chain. It selects a word from the input, finds a context containing that word, and generates a reply from that context. In this way, its reply always has something in common with the input.

Third, it does this many, many times for one reply. Internally it may generate thousands of possible replies to your input, each time choosing a random input word, selecting a context, and following the two chains to produce a phrase. This is where the probabilities above come into play. MegaHAL gives you back the reply with the most surprise, essentially the least probable reply of the thousands it generates, evaluated word by word.

Fourth, it doesn’t split input word-by-word. It tracks punctuation, spacing, and numbers each as separate tokens on par with words. And everything is upper-cased internally, so the user’s capitalization doesn’t matter.

So this phrase:

This isn't a test, but it might be a good one.

Turns into these 22 tokens (split with slashes):

THIS/ /ISN'T/ /A/ /TEST/, /BUT/ /IT/ /MIGHT/ /BE/ /A/ /GOOD/ /ONE/.

Because of this, MegaHAL tends to learn the punctuation conventions of its users and obey those conventions when replying.

cobe

I made a couple of stabs at a database backend for MegaHAL about five years ago, but never really got anywhere. I used Berkeley DB and tried to be a little too clever with database access. I misunderstood some of How MegaHAL Works and ended up with poor quality replies.

So we kept at the circle of life, creating, teaching, and mourning our robot friend. Over time, I got better at recognizing how to coddle a running MegaHAL. He would last for months on a single brain, but that still wasn’t enough.

About a year ago, I decided to try again. I started a Python codebase with a SQLite backend. I found the MegaHAL Perl port called Hailo, which showed that a SQL database was a viable option.

So now we have cobe (coh-bee). It’s named after a former employer’s Code of Business Ethics. It’s usually in violation.

cobe’s datastore uses SQLite and resides entirely on disk. I used to be able to run a MegaHAL brain until its process was about 130M (resident – shared). With cobe, a brain with the same learned content results in a process taking 4M. That MegaHAL would have been nearing the end of its life, but cobe is just getting started.

It uses a similar process to generate replies as MegaHAL. It generates as many replies as possible in half a second, and chooses the least probable reply based on surprise. Since its datastore is on disk instead of RAM, it can generate far fewer replies than MegaHAL in this time. cobe will generate a few hundred to MegaHAL’s thousands, and once a cobe brain is very large this may drop to dozens of replies on average.

In theory, this results in poorer quality replies because it has fewer chances to maximize surprise. In practice, reply quality appears to be about the same.

There are two main differences from MegaHAL’s behavior that end up improving reply quality further.

The first is in capitalization. cobe is case preserving, so “foo”, “Foo”, and “FOO” are all different tokens. MegaHAL would have called all of those “FOO”. This reduces some overlap between contexts, so some tangents can’t be followed, but makes up for all of that when the robot starts shouting (SHOUTY HAL).

The second is in the way it splits up input phrases into tokens. Hyphenated words are kept together as one token. Multiple spaces between words are collapsed together to one space. URLs are kept together as one token. It was always cute when MegaHAL attempted to make up its own URLs based on portions of learned links, but in practice the constant 404s made it annoying.

cobe also has some tweaks to the surprise calculations and initial context selection that improve reply scores by a measurable amount.

cobe has a transactional datastore and is resistant to brain corruption. A brain can be accessed concurrently by several processes—one can be serving replies, while another crawls the internet for text to learn.

While optimizing cobe, I had to come up with some techniques for comparing the performance of random processes. Every potential reply is a random walk across the Markov chain, and depending on chance the performance of two replies could be wildly different for the same input. The surprise of potential replies also varies based on random factors, and average scores change quite a bit over the lifetime of a brain. All of these made CPU profiling by average execution time less useful.

I developed a tool called instatrace for visualizing performance characteristics of random processes, based somewhat on Google Chrome’s Histograms. It proved very effective for helping to optimize cobe, but I’ll write about that some other time.

As of this writing, cobe is nearing a year in production use. Happy birthday, little guy.

Many thanks to Jason Hutchens, the author of MegaHAL, for years of entertainment. And check out his plans for MegaHAL.10.

Screen and ssh-agent

2006-02-23T09:40:59-05:00

My Biggest

I started using Screen on a daily basis, and quickly desired an ssh-agent tied to a long-lived screen session.

The obvious solution (running "ssh-agent screen") doesn't work—as soon as you log out, screen drops into the background and you lose the agent.

People have solved this problem in various ways—a quick search shows some of them. I didn't like them. They all rely on scripts external to screen for running the agent and maintaining its environment variables.

I spent a little time last night on a solution. It's completely contained in your .screenrc, and produces an ssh-agent tied to screen's life cycle.

It's just two lines:

setenv SSH_AUTH_SOCK $HOME/.screen-ssh-agent
screen 10 ssh-agent -a $SSH_AUTH_SOCK $SHELL

This creates a screen (number 10) that holds your ssh agent. If you don't like 10, you can start the agent on any screen. Things still work properly. The agent will be available to all the screens in that session. It also persists if you close the screen it was started on.

Make sure you run the setenv line early enough in your .screenrc that it will take effect before you open new screens.

The only problem I have with this setup is that all my screen sessions share the same agent—the one listening on $HOME/.screen-ssh-agent. I'd like to make that one agent per screen session, using something like $HOME/.screen-ssh-agent.$$. Unfortunately $$ is empty from within .screenrc—I can't find a real environment variable that uniquely identifies the current process.

Persecution Complex

2005-12-16T15:11:21-05:00

LA 8-BALL!

If you are offended by discussion about Emacs, please stop reading now.

Over the last few years, Dan Mills and I have been improving an Emacs configuration style we both enjoy using. There has recently been some interest in this setup internally, so I thought I'd pull some notes together and send it out into the world.

There were two original goals for this design:

A good, clean configuration—none of the mess that usually clutters .emacs files.
Easy deployment of new elisp packages.

The configuration comes down to three things.

First, all the elisp files I own, either packages I've downloaded or things I've written myself, should exist under one tree. This eases maintenance, and allows me to keep everything in Subversion.

Second, all the relevant directories in that tree should be automatically added to the Emacs load-path, so I don't ever have to add anything manually when I want to try out something new.

Third, configuration files should be loaded automatically—I want to be able to drop settings in and not have to edit a file to get them to load.

Here is the result:

All directories under ~/elisp that contain elisp files are added to my load path.
All *-settings.el files under ~/elisp/settings are loaded automatically on start.
Customized variables (M-x customize, that is) are saved in ~/elisp/custom.el.

Whenever I download something new and nifty, I put it in ~/elisp/packages. If it's a single file, I'll put it there directly. If it comes as several files (or even a deep tree), I'll put it in its own subdirectory. I add a settings file that loads that package, and off I go.

These settings files are often extremely short—all I want to do there is set the configuration variables I need to use the package.

I keep my .emacs file itself as simple as possible—it's not in the version controlled tree, and I tend to forget changes when I make them. At the moment, it has one line—hopefully it's simple enough for me to remember if I lose it:

(load-file "~/elisp/init.el")

A sample elisp tree containing that init.el file can be found here. There's a fair amount of documentation in the comments of init.el.