Impending kOS
by Stephen Taylor (sjt@5jt.com)
It began badly. We were walking along the South Downs Way in early summer, the sun glittering on the English Channel on our right, the Weald of Sussex stretching away to our left. “How big,” asked Arthur, “should a text editor be?”
I’ve known Whitney most of my life. I know what he does. I know his stupid questions. And still I can’t resist trying to give helpful answers. “I don’t know. One could find out, surely? What do Emacs and Vim weigh – tens of megabytes?”
“I’ve got a text editor in four lines of K. Just need to add Copy and Paste.”
Ah, we’re back to that. Of course. K is the language part of kdb+, Arthur’s frighteningly fast column-store database, used by trading rooms to handle huge real-time data flows from financial exchanges. It started off at Morgan Stanley in the 1980s as an APL stripped for speed and became A+[1], and for two decades the bank’s development environment for trading applications. For the last twenty years it has evolved as kdb+, trading as Kx Systems, Inc.[2] It’s a two-orders-of-magnitude sort of thing: two orders of magnitude faster than industry-standard database, two orders of magnitude smaller code volume. Four lines of K equate to about four hundred lines of C.
The kdb+ interpreter is tiny: about 100Kb. (And yes, kdb+ programs are interpreted, not compiled.) As the code base improved, kdb+ releases became faster – and smaller. Kdb+ has sharp elbows. Impatient with the speed of Windows, kdb+ wins a ×3 performance improvement by managing memory itself.
Whitney is no respecter of rules. One of the scariest things I ever did as a young man was following him through central Toronto on a bicycle.
An apocryphal story. At the first of the three universities he claims to have been thrown out of, Whitney’s class was given an assignment: write a program that will print the most successive prime numbers possible with limited CPU time and limited green-striped paper. (Yes, that long ago.) His solution won by a handsome margin and was disqualified on two counts. In the first place he had ignored everything the class had been taught about modularisation and code re-use. He just wrote code optimised to solve one problem spectacularly fast. He had also noticed the problem did not specify printing spaces between the primes. The printouts were a sea of ink. And his code looked like woodgrain.
As a rule, it was the fittest who perished; the misfits,
Forced by failure to emigrate into unsettled niches,
Who altered their structure and prospered.
— WH Auden
Kdb+ is a testament to the rewards available from finding the right abstractions. K programs routinely outperform hand-coded C. This is of course, impossible, as The Hitchhiker’s Guide to the Galaxy likes to say. K programs are interpreted into C. For every K program there is a C program with exactly the same performance. So how do K programs beat hand-coded C? As Whitney explained at the Royal Society in 2004, “It is a lot easier to find your errors in four lines of code than in four hundred.”
What would computing be like if it were all done this way? The decades-long sleigh-ride of Moore’s Law[3] has ended. What if we could get another two orders of magnitude of performance out of the hardware?
This question has been asked before, notably by Alan Kay at the Viewpoints Research Institute.[4]
Whitney means to find out. The first phase of the project is to escape the bloated embrace of the operating systems and run kdb+ on the bare metal.
“If you keep on chipping at that rust, eventually you’ll reach flat, bright metal.” – Herman Wouk, The Caine Mutiny
Whitney started replacing calls to Linux, working, alone as always, in his garage office. Characteristically, it’s a simple workplace: a pool table, a desk, a chair and a PC with a single monitor. When I saw it in 2007 it was running Windows XP and had five windows open: two MS-DOS and three Notepad. Brutally simple IDE. Doubtless things have improved since.
Oleg and Pierre had heard of Whitney and kdb+. They study computer science in St Petersburg. (Russia, not Florida.) With a great deal of trepidation and some support from a teacher they wrote asking Whitney what he was doing. He replied with some C code he was working on.
Everyone knows how C programs look: tall and skinny. Whitney’s don’t. I first encountered them in the 1980s. I was working for I.P. Sharp Associates in Sydney. My boss wanted to port the SHARP APL interpreter onto the fast new Hewlett-Packard HP1000 minicomputer. I recommended Whitney, then the youngest member of the IPSA systems-programming team, for the job. (Probably the best thing I’ve done in my professional life.)
There was, of course, a catch. The interpreter was a 500Kb program developed over 15 years and supported by an 11-man team. The original language had been considerably extended – most recently with ‘general’ or ‘nested’ arrays – and all the extensions had to be ported too. Although the target machine was attractively fast, most of the speed disappeared for programs larger than 80Kb. The interpreter had not just to be ported, but also made six times smaller. Game over?
Whitney’s strategy was to implement a core of the language – including the bits everyone thought most difficult, the operators and nested arrays – and use that to implement the rest of the language. The core was to be written in self-expanding C. As far as I know, the kdb+ interpreter is built the same way.
Unlike the tall skinny C programs in the textbooks, the code for this interpreter spills sideways across the page. It certainly doesn’t look like C.
In Sydney we assigned Whitney two coding assistants. Not that he needed or wanted help, but when he eventually left we’d need some idea how it all worked. His assistants had a very hard time. They would struggle through the week, get their assignments half finished, then on Monday discover Whitney had dropped in over the weekend, rewritten most of the interpreter, and included their assignments. (The interpreter got finished. A decade later I saw one of the HP machines still running on Westpac’s trading floor. Not long after that, Whitney started work at Morgan Stanley on what became A+.)
Whitney sent Oleg and Pierre some of the C code he was working on, and notes on a problem he didn’t know how to solve. They emailed back a solution, coded in his style. A partnership was born: a garage in California, a school in Russia.
Whitney demonstrated his “research K interpreter” at the Iverson College meeting[5] in Cambridge in 2011. We had visitors from Microsoft Research. The performance was impressive as always. The tiny language, mostly familiar-looking to the APL, J and q programmers participating, must have impressed the visitors. Perhaps conscious that with the occasional wrong result from an expression, the interpreter could be mistaken for a post-doctoral project, Whitney commented brightly, “Well, we sold ten million dollars of K3 and a hundred million of K4, so I guess we’ll sell a billion dollars worth of this.”
Someone asked about the code base. “Currently it’s 247 lines of C.” Some expressions of incredulity. Whitney displayed the source, divided between five text files so each would fit entirely on his monitor. “Hate scrolling,” he mumbled.
At Iverson College in 2013 he demonstrated the new graphics layer, z – 9Kb of code to replace the X Windows system. For the first time we saw the kOS desktop, solid black with a Tolkienesque legend top left: one system/all devices. Arrayed on the right edge, the icons of five kOS apps. He launched the text editor app and then wrote a new one, working out the key callbacks in front of us and explaining them as he worked. As he defined each callback the new app acquired it: no compile, load, install cycle. In eight lines of K he had replicated the core function of Notepad. At this point, with the new z layer in place, kOS weighed 62Kb.
Last autumn the kOS team recruited a fourth member, Geo, and in November announced it had removed the last connection to Linux. kOS was running on bare metal. Whitney announced the project would now go dark and return, perhaps in the summer of 2014, with a platform on which apps can be built.
kOS is coming.[6] Nothing will be the same afterwards.