2

Here's an excerpt from the Wikipedia entry on K programming language:

The small size of the interpreter and compact syntax of the language makes it possible for K applications to fit entirely within the level 1 cache of the processor.

What in particular makes K programs so small? When one uses ' operator in K, map in compiled functional language like Haskell, or equivalent for loop in a compiled imperative language like C, I can't imagine either compiler generating radically different assembly code or that what happens in interpreter's internals will be very different from for loop. Is there anything special in K that makes its runtime and programs so small?

There's a similar question on SO, but the answers there basically clarify nothing.

Community
  • 1
  • 1
Sergey Mikhanov
  • 8,880
  • 9
  • 44
  • 54

2 Answers2

1

I am not the author of the wikipedia statement above, just somebody who uses K extensively.

As for code, K is not unrolling loops or making other changes to the program structure that would increase it in size beyond what you're expecting. The executable interpreter itself is tiny. And the programs tend to be small (though not necessarily so). It's not the execution of any particular instructions for mapping, etc. that make it more likely that the code itself will execute all within cache.

K programs tend to be small because they are a small, tight bytecode in storage, and their syntax tends to yield very small amounts of code for a given operation.

Compare this Java program:

int r=0;
for(int i=0; i<100; i++) {
  r+=i;
}

Against this K program to yield the same result:

+/!100

The amount of code being executed is similar, but the storage required by the program (much less typing!) is far less. K is great for those with repetitive stress injuries.

As for the data, the encouragement to work on multiple data items with single instructions tends to make access sequential, in a manner friendly to the cache, rather than random access. All of this merely makes it more likely that the program will be cache friendly.

But this is all just tendencies and best practices within the language in combination with the K executable itself. If you link in large amounts of additional code, special case lots of functions, and randomize your indices before accessing your data, your program will be just as unfriendly to the cache as you'd expect.

Thomas Smyth - Treliant
  • 4,993
  • 6
  • 25
  • 36
Brian Sullivan
  • 11
  • 1
  • Thanks for the answer. The things you're saying about data access seem reasonable with regards to cache hits/misses, etc. When comparing to the Java code snippet, I guess I can imagine what will bring some difference to the bytecode size (virtual calls in Java, 2 variables declaration/access, etc). But what about, say, Haskell's `fold (+) 0 [0.. 100]`? It seems to me like there are few reasons why functional code couldn't be just as compact as K. – Sergey Mikhanov Feb 11 '11 at 22:10
1

There are ways of generating a very compact code. For example, a http://en.wikipedia.org/wiki/Threaded_code of Forth and alike. It is likely that K is compiled into some form of it.

SK-logic
  • 9,605
  • 1
  • 23
  • 35