Suspect stack issue

[GoogleCodeExporter]

I'm having some performance issues with kahlua, and I *strongly* suspect that 
this is the result of 
some bug in the interpreter. Basically, if I build a MIDlet including the 
vanilla kahlua interpreter and 
I run the attached lua script, it takes around 140 seconds to run on a Nokia 
6212 NFC, which is way 
too long. The lua code seems ok, as it is almost the same as the sort function 
in the stdlib, so the 
bug must be in the interpreter. The script is run as follows:

    LuaState state = new LuaState(System.out);
    LuaClosure callback = state.loadByteCodeFromResource("/qsort", state.getEnvironment());
    state.call(callback, null, null, null);

I compiled the bytecode using luaj-0.97.

What version of the product are you using? On what operating system?
2009-04-26 on Nokia 6212 NFC. Couldn't try with 2009-06-11 as I'm working at 
home at the 
moment and I don't have a phone to try it on. On the <a 
href="http://www.forum.nokia.com/Tools_Docs_and_Code/Tools/Plug-
ins/Enablers/Series_40_Nokia_6212_NFC_SDK/" alt="Nokia Emulator">Nokia 6212 NFC 
Emulator</a> the bug is still reproducible with kahlua version 2009-06-11. I'm 
using Eclipse 
Pulsar Galileo RC1 to compile the code and package the jar.

Original issue reported on code.google.com by j0t...@gmail.com on 16 Jun 2009 at 3:30

Attachments:

• qsort.lua
• qsort.lbc.out

[GoogleCodeExporter]

whoops, html glitch :)

Original comment by j0t...@gmail.com on 16 Jun 2009 at 3:31

[GoogleCodeExporter]

I tested this, and various other code snippets and there is no bug.
All I could determine is that the performance is much better when running in a 
plain
J2SE environment than on an emulator or on an actual phone.

So, it's not a bug, but there is always room for optimizations.

I might spend some time later to work on improving the performance of Kahlua, 
but I
can't promise anything. If you find any good optimizations, feel free to send a 
patch
or a report, and I'll try to implement in the Kahlua trunk.

In the mean time, I think the proper solution is to implement sorting and other
computationally intensive operations in plain Java instead of Lua.

Original comment by kristofer.karlsson@gmail.com on 16 Jun 2009 at 7:23

• Changed state: Invalid

[GoogleCodeExporter]

You'll admit, though, that 143 secs to run that script is way too much, and I'm 
still struggling to find an 
explanation for that. I don't think the JVM on the phone is slow: that same 
script, translated in javascript and 
run with minijoe (www.minijoe.com) on the phone takes only 7 seconds. There 
MUST be something wrong 
somewhere, it'd be nice to point it out. The script is fine (it's almost the 
same as the sort function in lua's 
stdlib), the JVM is ok (the same code runs fine on minijoe), so there must be 
something wrong with kahlua...

As a matter of fact, kahlua on a plain J2SE takes 830 millisecs to run that 
quicksort script. Minijoe, on the 
other hand, on the same J2SE, takes 40 millisecs to run the translated 
quicksort... That's 20 times faster! How 
do you explain that? (7s x 20 = 140 s, and 40ms x 20 = 800ms, it's the same 20x 
increase in running time, 
on both JVMs!)

It's no surprise performance is better on plain J2SE. Computers run programs at 
lightning speed, so a 20-fold 
difference can go unnoticed if the overall running time is less than 1 second. 
But even the PC JVM shows the 
same symptoms as the phone JVM, and I think that clearly shows there's 
something wrong in kahlua...

Original comment by j0t...@gmail.com on 16 Jun 2009 at 10:53

[GoogleCodeExporter]

Yes, it's a performance problem.
Kahlua is currently not optimized at all for dealing with numeric arrays.
There are two major reasons why Minijoe is faster than Kahlua for quicksort.
1) Minijoe has both an array-implementation and a map-implementation. Kahlua 
only has
a map implementation which makes array access slower.
2) Minijoe distinguishes objects and numbers, which means that it allocates a 
lot
fewer Double objects.

Point 2 is probably a minor issue. I considered doing something similar for 
Kahlua
mostly to avoid all the memory allocations when doing arithmetic operations but
haven't gotten around to it yet.
I may try implementing it and measure how much better it gets (if at all)

I also have plans on releasing a pure array type in the Kahlua core, which will
dramatically speed up array operations.
With the current prototype (not yet checked in), running quicksort is about 4-5 
times
faster in Kahlua than in Minijoe.

Here are my current benchmarks:
Kahlua              :         91 ms
minijoe             :        178 ms

Kahlua              :        232 ms
minijoe             :        236 ms

Kahlua              :         64 ms
minijoe             :         62 ms

Kahlua              :          7 ms
minijoe             :        180 ms

Kahlua              :          6 ms
minijoe             :        178 ms

Kahlua              :         34 ms
minijoe             :        117 ms

Kahlua              :          6 ms
minijoe             :         83 ms

Kahlua              :          5 ms
minijoe             :         19 ms

Kahlua              :          5 ms
minijoe             :         17 ms

Kahlua              :          5 ms
minijoe             :         41 ms

Kahlua              :         35 ms
minijoe             :         56 ms

Kahlua              :          6 ms
minijoe             :         17 ms

Kahlua              :          5 ms
minijoe             :         17 ms

Kahlua              :          4 ms
minijoe             :         17 ms

Kahlua              :          6 ms
minijoe             :         18 ms

Kahlua              :          5 ms
minijoe             :         17 ms

Kahlua              :          4 ms
minijoe             :         17 ms

Kahlua              :          4 ms
minijoe             :         18 ms

Kahlua              :          5 ms
minijoe             :         17 ms

Kahlua              :          4 ms
minijoe             :         17 ms

Original comment by kristofer.karlsson@gmail.com on 17 Jun 2009 at 9:14

[GoogleCodeExporter]

>With the current prototype (not yet checked in), running quicksort is about 
4-5 times
>faster in Kahlua than in Minijoe.
I'm glad to hear that.

Thank you for the exhaustive explanation.

Original comment by j0t...@gmail.com on 17 Jun 2009 at 10:00

[GoogleCodeExporter]

The optimized LuaArray type is now commited into subversion.
It can be used instead of tables for pure array purposes.
It only allows setting when the keys are integers in the range [1..n]

See luaarray.lua in testsuite/lua for examples on how to use.

Original comment by kristofer.karlsson@gmail.com on 6 Jul 2009 at 11:16

• Changed state: Fixed