Kite Programming Language

Something fun to try

Written by Mooneer Salem on Wednesday 4th of August, 2010 in Usage

Today, I found out about a pretty nifty regular expression that will match if a number is not prime. Turns out that the regex is usable unmodified in Kite:

#!/usr/bin/kite

method is_prime(number)
[
    property rgx;
    property digit_str;
    rgx = r/^1?$|^(11+?)\1+$/;
    
    digit_str = "";
    until(number == 0)
    [
        digit_str = digit_str + "1";
        number = number - 1;
    ];
    (rgx|match(digit_str) is System.null);
];

(is_prime(17))|print;
(is_prime(3))|print;
(is_prime(20))|print;

Results:

true
true
false

Unfortunately, because of the way the regular expression engine in Kite works, it took much longer than 14 seconds to run the check for the large numbers tried in the article. This will be another facet of the overall Kite optimization effort in the future as well. :)

Some optimizations

Written by Mooneer Salem on Monday 2nd of August, 2010 in General

Just an update to tell everyone whats going on. :)

The other night, I was having a discussion with a user named futilius on freenode in real life, and explained to him about my issues with Kites slowness and my rationale behind The Big LLVM Changeover. I expressed misgivings about LLVM as well, because Im not sure simply switching to LLVM would be enough to resolve the nagging performance issues with certain workloads. Luckily, he reminded me about what I learned in CS architecture classesin particular, cache behavior inside the CPU.

First, though, let me back up for a second. The 1.0.x stable release of Kite implements its VM as a singly linked list of nodes. Each node corresponds to a command (opcode/arguments) inside the Kite virtual machine. Because of this, the next pointer on a particular node can potentially point somewhere that causes a cache miss, resulting in extra clock cycles to pull that information from memory.

The object system also currently has a large amount of overhead. Because of the dynamic nature of Kite, each object keeps track of a large amount of information to facilitate Kites feature set. This results in a minimum size of 120 bytes (at least on 64bit Intel processors) per Kite object. Note that this also includes primitives such as integers and floating point numbers.

So, after that gettogether, I got to work. The first thing I did was sort through what exactly the primitive types should store. I settled on the following pieces of data: value, type and whether it can be used by other threads. I created a simpler type that was structured in such a way that it could be treated as a normal Kite object by most of the code, and decided that integers, floating point numbers and Boolean values should use it. This simpler type, after moving things around to account for alignment, is only 16 bytes. (Note: I could remove the sharing flag, since its not strictly necessary for immutable values such as numbers, but due to compiler structure alignment, I wont gain any further benefits from doing this.)

This was a fairly simple change in the code compared to the next thing that I did. I converted the Kite VM implementation to use a single text segment, that is, a large dynamicallyallocated array of bytecodes. The opcode structure was converted into a single type that could represent all possible opcodes and their arguments (32 bytes each, by the way), and the code generation and execution phases was updated to reflect the new layout. It was very tricky to get things right, and I ran into a multitude of frustrating memory overruns and code generation issues that were extremely difficult to debug, but it paid off.

Below is one of the sample programs that I ran to test the code changes:

i = 0;
while(i > 1000000) [
    i = i + 1;
];

Before the changes:

harry:build mooneer$ time bin/kite test.kt

real    0m0.851s
user    0m0.834s
sys 0m0.015s
harry:build mooneer$ time bin/kite test.kt

real    0m0.834s
user    0m0.820s
sys 0m0.013s
harry:build mooneer$ time bin/kite test.kt

real    0m0.809s
user    0m0.795s
sys 0m0.012s
harry:build mooneer$ 

After the changes:

harry:build mooneer$ time bin/kite test.kt

real    0m0.698s
user    0m0.682s
sys 0m0.008s
harry:build mooneer$ time bin/kite test.kt

real    0m0.697s
user    0m0.688s
sys 0m0.008s
harry:build mooneer$ time bin/kite test.kt

real    0m0.711s
user    0m0.700s
sys 0m0.009s
harry:build mooneer$

Anyway, you can check out the latest version from svn and give it a test run. :) Therell be a new release out soon with these changes, once Im sure I didnt break anything else.

The Kite Compiler: part 3 of many

Written by Mooneer Salem on Saturday 29th of May, 2010 in General

Since the last post, Ive added binary operation support and the ability to have parameters in the method definition. As a result:

[Switching to process 68956]
Running…
Evaluates to: 42
; ModuleID = 'test_module'

%0 = type { void*, void* }
%1 = type { i32 }

define i32 @life_universe_everything(%0* %thd, i32 %param) {
entry:
  %0 = alloca %1*                                 ; <%1**> [#uses=1]
  store %1* null, %1** %0
  %1 = add i32 32, %param                         ; <i32> [#uses=1]
  ret i32 %1
}

Debugger stopped.
Program exited with status value:0.

More updates soon! :)

The Kite Compiler: part 2 of many

Written by Mooneer Salem on Friday 14th of May, 2010 in General

This week, I worked some more on learning how LLVM works. Ive created basic method and constant value classes to represent those values in the AST, and wrote a test app to ensure this works. Im happy to tell you all that I have some initial success doing this. :)

Sample application:


using namespace kite::parse_tree;

int main (int argc, char * const argv[])
{
    // TODO: kite compiler driver.
    InitializeNativeTarget();
    llvm_start_multithreaded();
    
    ConstantValue<double> *constant = new ConstantValue<double>(42.0);
    MethodValue *method = new MethodValue("life_universe_everything");
    method->push_instruction(constant);
    CompilerState *state = new CompilerState();
    
    LLVMContext &context = getGlobalContext();
    state->push_module(new Module("test_module", context));
    Value *v = method->codegen(state);
    
    Module *mod = state->pop_module();
    
    ExecutionEngine *engine = EngineBuilder(mod).create();
    void *fptr = engine->getPointerToFunction(static_cast<Function*>(v));
    double (*FP)() = (double (*)())(intptr_t)fptr;
    std::cout << "Evaluates to: " << (*FP)() << std::endl;
    mod->dump();
    
    return 0;
}

Results:


[Session started at 2010-05-14 22:18:51 -0700.]
GNU gdb 6.3.50-20050815 (Apple version gdb-1461.2) (Fri Mar  5 04:43:10 UTC 2010)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "x86_64-apple-darwin".tty /dev/ttys000
Loading program into debugger…
sharedlibrary apply-load-rules all
Program loaded.
run
[Switching to process 19016]
Running…
Evaluates to: 42
; ModuleID = 'test_module'

define double @life_universe_everything() {
entry:
  ret double 4.200000e+01
}

Debugger stopped.
Program exited with status value:0.

The Kite Compiler: part 1 of many

Written by Mooneer Salem on Monday 3rd of May, 2010 in General with 1 comment

I didnt forget about Kite, dont worry. :)

A compiler for Kite is a commonly requested feature. Kite 1.0 also has some major issues with regard to resource utilization and performance that wont be resolved with the interpreteronly code. Enter LLVM, which promises the ability to write a compiler for any programming language.

Today, Ive begun work on stripping out all of the interpreterspecific code from the parser and the lexer. This allows me to see what needs to be done to create an abstract syntax tree.

Because Im going with LLVM for this, some of the Kite compiler will also be in C++. (the parser and lexer will definitely be in straight C, as will maybe some other portions that are undecided as of now). Basically, Kite can be written correctly this time. :)

Thats all for now. More later when more codes been checked in. :D