One Million Lines Per Minute: SPITBOL/386 times for tokenizing and code generation

I’m making good progress on producing a version of SPITBOL for Linux.

One sign I’m on the right track is the performance that PC-SPITBOL delivers when run on Linux using Wine.

The translation is done in two steps.

The first step tokenizes the input, puts the operations in a standard form and drops the comments. This takes about 0.8 seconds to scan 31,000+ lines of MINIMAL source for v3.7, and produces just over 12,000 lines of tokenized instructions. This corresponds to about 2,325,000 lines/minute.

The second step generates assembly code for 386 for the 12,000 instructions. This results in 14,000 386 instructions and takes about 1.4 seconds. The scales up to about 500,000 statements/minute for the code generation phase.

The combined phases take just over 2 seconds to translate 31,000 lines of MINIMAL to 14,000 386 instructions. This corresponds to about 930,000 source lines per minute.

Not bad for a program written over 25 years ago.

And that’s before doing any tuning…

Alaska’s Greatest Gift to the United States?

Alaska Lt. Governor Sean Parnell, who will succeed current Governor Sarah Palin, has stated that Ms. Palin is Alaska’s greatest gift to the United States.

While her resignation is certainly her greatest gift to Mr. Parnell, I attach higher value to the North Slope Oil Reserves. For example, according to the U.S. Energy Department:

Through 2050, the North Slope could yield up to 36 billion barrels of oil and 137 trillion cubic feet of natural gas under optimistic assumptions, the Energy Department said.

That would be enough to meet current U.S. oil demand for about five years and natural gas for a year and a half, but some major obstacles stand in the way of hitting those goals.

At a price of $50/barrel, 36 billion barrels are worth about $1.8 trillion dollars. While Ms. Palin is a source of constant amusement, I would value her contribution to the United States at far less than a trillion dollars.

That’s not even counting the value of the natural gas, though the gas coming from Ms. Palin and Mr. Parnell will continue to provide fodder for the media in their coverage of the willful destruction of the Republican Party by its current leadership.

Indeed, Mr. Parnell’s initial foray into the public arena suggests he may have an even more serious case of foot-in-mouth disease than Ms. Palin.

SQL No, Set Theory Yes

Slashdot just posted a story about a “nosql” conference, Enthusiasts Convene To Say No To SQL, Hash Out New DB Breed.

The “nosql” folks seem to agree with me that SQL is fundamentally wrong.

However, a quick look at some of the presentations to be found at NOSQL debrief suggests they are missing a key point.

The presentations lament the problems with SQL in today’s world, and make mention of some of the latest buzzwords such as “JSON,” “REST” and “Log-structured Merge Trees.”

I suggest the answer is not be found in a mashup of hot new technologies but by going back to the basics.

That would be mathematics.

If set-theory is good enough for mathematicians shouldn’t it be good enough to describe what you want to retrieve from a database?

Get the basics right, and all the rest will follow. This is a much better approach than working backward from technology to determine how the user should construct a query.

Soldiers At Work

Courtesy of a tweet from @ThomasCrampton I learned of an extraordinary video report about a firefight between Viper Company of the U.S. Army and Taliban forces in Afghanistan.

It shows some of the best soldiers in the world plying their craft:

Viper Company Firefight, 2009-06-30

PC-SPITBOL for Intel 8086 DOS Now Available

I just located my copy of PC-SPITBOL for the IBM PC, 8086, circa 1983. This is a 16-bit version.

It can be downloaded here.

Here are some pictures of the manual and a screenshot showing PC-SPITBOL starting up:

PC-SPITBOL Manual, 1983

I did comparative runs of PC-SPITBOL 8086, SPITBOL/386, and CPython, using Cygwin on Windows XP:

CPython 55 seconds
SPITBOL/86 15 seconds
SPITBOL 8086 22 seconds

The numbers speak for themselves. PC-SPITBOL, written in 1983, is almost three times faster than CPython. SPITBOL/386, created over a decade ago, is more that four times faster than CPython.

Screenshot showing comparative times

Here are the test programs:
Python:

def add(a,b):
 return a+b
def sub(a,b):
 return a-b
n = 0
limit = 1000000
limit = limit * 50
trips = 0
for i in xrange(0, limit):
    m = add(n, 1)
    n = sub(m, 1)
    trips += 1

PC-SPITBOL, 8086, 16-bit:

 &stlimit = -1
 define("add(a,b)")  add_end)
add
 add = a + b: (return)
add_end
 define("sub(a,b)")  sub_end)
sub
 sub = a - b: (return)
sub_end
* repeat for limit1 * limit2 * limit3
 n = 0
* limit = 1000000
* limit = limit * 50
* variant for 16-bit spitbol, need to keep numbers small
 limit1 = 10000
 limit2 = 100
 limit3 = 50
 trip3 = 1
lp3
 trip2 = 1
lp2
 trip1 = 1
lp1
 m = add(n, 1)
 n = sub(m, 1)
 trip1 = trip1 + 1
 le(trip1, limit1) :s(lp1)
 trip2 = trip2 + 1
 le(trip2, limit2) :s(lp2)
 trip3 = trip3 + 1
 le(trip3,limit3)  :s(lp3)
 output = limit1 " " limit2 " " limit3
end

SPITBOL/386, 32-bit:

&stlimit = -1
 define("add(a,b)")  add_end)
add
 add = a + b: (return)
add_end
 define("sub(a,b)")  sub_end)
sub
 sub = a - b: (return)
sub_end
 n = 0
 limit = 1000000
 limit = limit * 50
 trips = 0
lp
 m = add(n, 1)
 n = sub(m, 1)
 trips = trips + 1
 le(trips, limit) :s(lp)
 output = trips
end

There is a bug in the “sourcecode” function in that right parenthesis followed by a colon is deemed to be a “smiley face” and so rendered as an image. I find this so charming that I have left it in.

On Writing at Risk

This blog is my second attempt at writing a blog. I started a blog, in early 2006, as I expect do most bloggers, in the hope that my writing would find an audience.

I deemed my first effort both pompous and presumptous, and so deleted most of my first posts, before resuming the work that resulted in the posts in this blog.

Looking back, I believe that such success as I have enjoyed is a direct result of my decision to write at risk.

By “write at risk” I mean that I decided to make myself write about any topic that came to mind, without fear of what others might think, in the belief that I would become a better writer for taking that risk.

I have found that The only meaningful audience is yourself.

Whether I was right or wrong is for you, the reader, to decide. I believe I was right.

To write publicly is to write to two audiences: yourself, and the rest of the world.

Writing that doesn’t ring true to yourself, even though it may find a wider audience, is an act of betrayal, both to you and your readers.

One must always write with integrity, letting the writing go where it will.

To do otherwise is to betray both yourself and your audience.

Having done this for almost three years now, I can attest the following:

• Your will learn more about yourself than the world will learn about you;
• Your writing will take you places you never dreamed were possible. For example, while attending a Memorial Day Ceremony at the Chappaqua Train Station in May 2007, I guessed that few present were active bloggers, and so decided to write a post about the event, Writing that post changed my life.

What I find most surprising is that I have yet to see another blogger knowingly take the same approach. Those who I have found to be most readable seem to have stumbled into this approach, without a conscious plan.

Be that as it may, I believe that to take risk in blogging is a good approach.

I have also found that writing at risk on your own blog makes you more likely to take risk when writing about your other work.

If you don’t believe in yourself, then how can you expect others to believe in you?

All the rest is detail.

The Korean War Project

Among the most dedicated, selfless, and important projects I have encountered in the last few years is the Korean War Project.

It is the work of Ted Barker, the son of a soldier who fought in Korea.

I have yet to see a word out of place — or a thought unexpressed — as Mr. Barker has demonstrated by each and every post his dedication to honoring those who fought with his father in Korea.

I first became aware of this site a few years back. I was at the Bat Mitzvah of a family member when, sitting at a table, I struck up a conversation with the gentlemen sitting near me.

His name was Lou Colangelo. I learned that he had gone ashore as a soldier in the U.S. Army in late 1942 in North Africa, and had been engaged in combat almost continuously until April 1945. Among his last actions was the crossing of a lake in Austria, near the Italian border, using a DKW amphibious craft. He was commended in battle for his heroism by William Orlando Darby, founder of Darby’s Rangers, the forerunner of the US Army Rangers, one of America’s greatest fighting forces. Col. Darby was killed within an hour by an artillery shell. He was the only officer to be posthumously promoted to General in WWII.

Mr. Coangelo informed me that one of his cousins had been among the first American soldiers to die in Korea, in theBattle of the Pusan Perimeter.

I first encountered the Korean War Project via a web search, and entered the name of Mr. Colangelo’s cousin in an entry on the site.

I was born in early December of 1944, and so played no role in the fighting of WWII. Because of my age, and my interest in that war, I was witness to the way in which the media, notably in the form of movies, decided to honor those who did fight in that war.

For example, among my earliest memories is the movie The Steel Helmet. Released in 1951, I saw it before I was seven years old. Looking back, I see it was an anti-war movie in a profound sense, as it captured both the dedication — and the insanity — of soldiers drawn into battle by a cause for which they were willing to give their lives.

The director of the movie, as I learned decades later, was Samuel Fuller, who was the director of the movie The Big Red One, about the First Infantry Division. Starring Lee Marvin in his finest role, the film continues the random nature of war first described by Fuller two decades earlier in “The Steel Helmet.”

The Korean War was perhaps the most unusual of America’s wars. We engaged in it almost by chance, since the Russians chose to sit out the key meeting of the United Nations at which Pres. Harry Truman offered the assistance of our armed forces in defending Korea.

Though unusual in its origin, the Korean War resulted in much of the finest fighting ever done to defend our country, notably in the battles around the Chosin Reservoir. Though I consider David Halberstam to be the finest writer of his generation, I deem the accounts of the fighting given in the work of James Brady, one-time editor of Women’s Wear Daily, to be superior.

The Korean War as fought not only by Americans but by Koreans who were equally willing to go into harm’s way to defend their country.

They differ from us not in their courage but by their modesty. For example, for well over a decade I have had the pleasure of watching an elderly Korean couple, the parents of a fellow employee at IBM Research, walk every day to take their exercise. I learned only recently that the father was once a senior academic in a major Korean University, yet I know him only as a person who has *always* taken the time to share a welcoming thought and wish me and my family a happy day.

Would that are allies were always so gracious, courageous, and kind.

It thus comes as no surprise that perhaps the most courageous person I have never met was also Korean.

That would be SSgt. Kyu Hyuk Chae, the subject of many — yet too few — posts in this blog. His example of integrity and courage is so great that I find it hard to write about him without shedding a tear — as I have just done while writing this post — in his memory.

In conclusion, I ask that my fellow open-source developers extend whatever help they can muster to assist Mr. Barker in his noble mission.

The St. Clair McKelway Test

In my previous post, , I posted some photos of the obituary of A. J. Llebling — the namesake of this blog — written by Tom Wolfe. Now a famed novelist and writer, Wolfe was then — in late 1963 — a young reporter for the New York Herald Tribune.

I just revisited this post, and on viewing the photos I posted of Wolfe’s work I noticed the name St. Clair McKelway!

Aside from A.J. himself, Mr McKelway was among my favorite writers from the New Yorker.

I suspect that not one in 10,000 or so working journalists would know his name.

I knew that Tom Wolfe was good, but I didn’t appreciate that Wolfe – or his editors at the Trib — were that good.

To include St. Clair in Liebling’s obituary was both an act of brilliance and a demonstration of profound understanding.

If you have ever read St. Clair’s work then please post a comment.

I’ll pay the bar tab if we ever meet, and I do hope we do so as soon as possible, so we can jointly pay tribute to Colonel Stingo.

Fun is fun, but this is serious business.

Good writers deserve recognition.