Colorizing the big bright green state machine

I've been busily optimizing OSLEC for the blackfin, X86, and X86_64 architectures.

It took a long period of thinking about how the algorithm really worked and how it interacted with the x86 hardware to figure out how to speed x86 up (My subconcious has labored on it since I hung out with David Rowe in February, watching an IP08 kind of fall over under the workload). I'm still not entirely sure how OSLEC works, actually, the inner mystery slips in and out of my head... David has been living inside it for far longer than I have and I keep referring back to his emails)

But: I had multiple eureka moments on the most mips eating loop on sunday night... I spent 2 days coding and testing... and (yea!)

I think I have achieved a major speedup for oslec on x86 and even more major on x86_64. I'm not going to say how much better it is until I finish checking to make sure it's bit exact with the original. (It's a lot faster. A virtual beer to the person that comes up with the closest guess. )

Flush with that success, creatively inspired, and wanting to defer writing a mind sucking tedious series of bitwalking tests for bit exactness for as long as possible, I took on the Blackfin.

I've spent about a month over the past quarter devouring manuals on the blackfin architecture and assembly language. It took reading some of them two or three times to really "get it". It is a cool processor!

So, for oslec, I came up with a parallel algorithm that I figured would be easily twice as fast as the original. (and with a little work, maybe more)

I had my eureka moment on wednesday I spent a day writing the code. 2 days cutting it down from 9 instructions to 7 in the inner loop. 3 days trying to get it to run. (you'll note how the math works out here, is that I didn't sleep very much)

It ran for the first time today. It's twice as fast as the original.

I think I have a major win there, but it is definitely NOT bit exact. !@#!@!!.

It's a rather big state machine to look at...

Worse.... I've got another major state machine that I'm debugging (alphatrack driver). I gave up on THAT last week, because it was just too tedious..... when programming stops being fun is when I start wanting a paycheck....

anyway, my whole life I have tended to look at enormous pictures of state that kind of look like this:

N0: 11000011111111000000000000000000
N1: 10000000000000000000000000000000
N2: 10000000000000000000100000000000
N3: 10000000000000000000100000000001
N4: 10000000000000000000100000000011
...

And I would let my eye pick out when it had gone wrong. Sometimes, when two parallel operations are going on, or I'm comparing a working piece of code with an optimized replacement, it makes sense to have BEFORE and AFTER on the same line:

BEFORE: 11000011111111000000000000000000 AFTER : 10000000000000000000000000000000
BEFORE: 11000011111111000000000000000000 AFTER : 10000000000000000000000000000000
BEFORE: 11000011111111000000000000000000 AFTER : 10000000000000000000000000000000
BEFORE: 11000011111111000000000000000000 AFTER : 10000000000000000000000000001000

Eyes are really good at seeing pictures in patterns like this, but when a state machine gets too big to fit on the screen, the patterns get harder to find. I would use smaller and smaller fonts until I could see as much as possible (sometimes hundreds of state changes on a screen - you don't have to actually be able to read the ones and zeros, font sizes of 2 are ok!)

You can take this to a real extreme if you have graphics available, and I've always kind of wanted to be able to zoom out of my session far enough to reduce each bit to a pixel...

It never occurred to me before now to use color for the *differences* between two machines.

It may be because I used to do this stuff on a huge monochrome Xterminal and it was simply easier to print out huge amounts of data and let my eyes due the work. I still miss that old Xterminal... and for that matter, green screens. So do my eyes.

My terminal windows are all green. The whole web has gone bright white and I find it, well, unsettling. Green is calming. it lets me think....

Anyway, I was looking for changes in new code vs old code in a 40 + 32 + 32 bit state machine and I decided that this was a better way to look at the differences:

10000000000000000000000000000000000000001000000000000000000000000000000011000011111111000000000000000000
10000000000000000000000000000000000000001100000000000000000000000000000001100100100100000000000000000000
00001011111000000000000000000000000000001000000000000000000000000000000010010110101100000000000000000000
10000000000000000000000000000000000000001000000000000000000000000000000011000011111111000000000000000000

And wrote an itty bitty little C program (that compiled the first time!) to generate both HTML and ansi character sequences. I like my cool green, and prefer cool colors, so on the green terminal this actually generates blue colors....

C++ has a nicer way of dealing with values larger than 64 bits (bitsets - LOVE EM), but this was good enough for my purposes....

I could turn this into a library but I gotta state machine to debug. Now that I've blogged I've run out of reasons to put it off... I sure hope a swell comes in soon....


/* Diffbits - released into the public domain 2008 by Michael Taht */

#include

// Some ansi standard strings

#ifdef HTML
#define REDON ""
#define REDOFF ""
#else
#define REDON "\033[01;34m"
#define REDOFF "\033[00m"
#endif

static int diffbits_64(long a,long b,int size) {
int color = 0;
int abit = 0;
int bbit = 0;
int status = 0;
int i;
for(i = 0; i < size; i++) {
abit = (a&1);
bbit = (b&1);
if(abit != bbit) {
status = 1;
if(color !=1) {
printf(REDON);
color = 1;
}
} else {
if(color ==1) {
printf(REDOFF);
color = 0;
}
}
printf("%d",abit);
a = a >> 1;
b = b >> 1;
}
if(color ==1) {
printf(REDOFF);
color = 0;
}
return (status);
}

int diffbits64(int a, int b) {
return diffbits_64(a,b,sizeof(long long)*8);
}

int diffbits32(int a, int b) {
return diffbits_64(a,b,sizeof(int)*8);
}

int diffbits16(int a, int b) {
return diffbits_64(a,b,sizeof(short)*8);
}

int diffbits8(char a, char b) {
return diffbits_64(a,b,sizeof(char)*8);
}

diffbits(long a, long b) {
diffbits_64(a,b,sizeof(int)*8);
}

#ifdef TEST

int main () {
diffbits(1,0); printf("\n");
diffbits(-1,1); printf("\n");
diffbits(555,225); printf("\n");
diffbits(16323,-12225); printf("\n");

diffbits8(1,-1); printf("\n");
diffbits16(1,-1); printf("\n");
diffbits16(16323,-12225); printf("\n");
diffbits32(1,-1); printf("\n");
diffbits32(1,2); printf("\n");
diffbits32(16323,-12225); printf("\n");
diffbits64(1,-1); printf("\n");
diffbits64(1,2); printf("\n");
diffbits64(16323,-12225); printf("\n");
}


Labels: ardour, computers, statistics

  ¶ 9:14 PM