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 what’s 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 Kite’s slowness and my rationale behind The Big LLVM Changeover. I expressed misgivings about LLVM as well, because I’m 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 classes—in 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 Kite’s feature set. This results in a minimum size of 120 bytes (at least on 64–bit Intel processors) per Kite object. Note that this also includes primitives such as integers and floating point numbers.
So, after that get–together, 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 it’s not strictly necessary for immutable values such as numbers, but due to compiler structure alignment, I won’t 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 dynamically–allocated 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. :) There’ll be a new release out soon with these changes, once I’m sure I didn’t 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, I’ve 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. I’ve created basic method and constant value classes to represent those values in the AST, and wrote a test app to ensure this works. I’m 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 didn’t forget about Kite, don’t 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 won’t be resolved with the interpreter–only code. Enter LLVM, which promises the ability to write a compiler for any programming language.
Today, I’ve begun work on stripping out all of the interpreter–specific code from the parser and the lexer. This allows me to see what needs to be done to create an abstract syntax tree.
Because I’m 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. :)
That’s all for now. More later when more code’s been checked in. :D