Re: [android-developers] Re: runtime compilation of dalvik bytecode

[Kristopher Micinski]

On Tue, Sep 25, 2012 at 9:22 PM, Ross Bamford <rosc...@gmail.com> wrote:
> Hi,
>
> On Saturday, 23 June 2012 12:27:31 UTC+1, mame82 wrote:
>>
>> A first naive approach using luajava was far to slow for a method called
>> about 5k times per frame. I need a way to compile to Dalvik bytecode at
>> runtime.
>>
>> Has anybody done sth like this, it seems impossible without the javac
>> class?
>> A scripting language supporting compilation to Dalvik DEX code would also
>> help.
>
> Apologies for reviving an old thread. If you've already found a solution to
> this, please ignore me :)
>
> We open-sourced Deelang, our lightweight in-app scripting language about a
> year ago. Recently, I've been working on a native (i.e. DEX) compiler for
> it. The compiler runs on-device and allows you to take script code and
> compile it a runtime-generated Class. Right now it's almost feature-complete
> but only tested to the extent that we use it in-house. It may well work for
> your needs? And in any case, more testers are always welcome ;)
>

So I guess my question is, what does this provide over something say
like, Groovy, would that work on Android.

Also, generating native != generating Dalvik bytecode, to me :-/ ...
that would be ... generating bytecode.

> You'll find the project at http://deelang.googlecode.com/ . To get the
> native compiler, you'll need to check the DEXCOMPILER branch out of
> subversion (a file release is planned soon, but not yet).

Hm...

You might be surprised that generating Dex doesn't help you as much
here as you might think. Why? Because, let's say you're comparing
this with code that you have running through an interpreter (okay, so
you've converted your scripting language to a sort of intermediate
form or something beforehand like Lua intermediate..) Now, your
interpreter will run over this code in some systematic structure, and
your wanting to use Dex is because you can translate this into Dalvik
bytecode.

But note! You will probably find that you will get "pretty good" perf
out of this interpreter (sans bytecode generation) already, because
Dalvik's (trace based) JIT will knock out "hot paths" of code along
your bytecode generation.

Do you have any firm numbers to support this either way?

kris

[Ross Bamford]

On Wednesday, 26 September 2012 08:01:07 UTC+1, Kristopher Micinski wrote:

On Tue, Sep 25, 2012 at 9:22 PM, Ross Bamford <rosc...@gmail.com> wrote:
> Hi,
>
> On Saturday, 23 June 2012 12:27:31 UTC+1, mame82 wrote:
>>
>> A first naive approach using luajava was far to slow for a method called
>> about 5k times per frame. I need a way to compile to Dalvik bytecode at
>> runtime.
>>
>> Has anybody done sth like this, it seems impossible without the javac
>> class?
>> A scripting language supporting compilation to Dalvik DEX code would also
>> help.
>
> Apologies for reviving an old thread. If you've already found a solution to
> this, please ignore me :)
>
> We open-sourced Deelang, our lightweight in-app scripting language about a
> year ago. Recently, I've been working on a native (i.e. DEX) compiler for
> it. The compiler runs on-device and allows you to take script code and
> compile it a runtime-generated Class. Right now it's almost feature-complete
> but only tested to the extent that we use it in-house. It may well work for
> your needs? And in any case, more testers are always welcome ;)
>

So I guess my question is, what does this provide over something say
like, Groovy, would that work on Android.

AFAIK, Groovy doesn't work on Android at the moment? But in any case, the two are targeting different people - Deelang is very lightweight, and does not aim to be a complete scripting language. It's designed purely to provide the possibility for developers to provide scriptable "extension points" in their apps. This means it can be small (in terms of Jar size). 

 

Also, generating native != generating Dalvik bytecode, to me :-/ ...
that would be ... generating bytecode.

You're right - I meant to put quotes around "native" there. My intention was to draw a comparison between "native" DEX bytecode versus the custom bytecode format and VM used in the original Deelang compiler. I am by no means claiming that this thing compiles directly to machine code.

 

> You'll find the project at http://deelang.googlecode.com/ . To get the
> native compiler, you'll need to check the DEXCOMPILER branch out of
> subversion (a file release is planned soon, but not yet).

Hm...

You might be surprised that generating Dex doesn't help you as much
here as you might think.  Why?  Because, let's say you're comparing
this with code that you have running through an interpreter (okay, so
you've converted your scripting language to a sort of intermediate
form or something beforehand like Lua intermediate..)  Now, your
interpreter will run over this code in some systematic structure, and
your wanting to use Dex is because you can translate this into Dalvik
bytecode.

But note!  You will probably find that you will get "pretty good" perf
out of this interpreter (sans bytecode generation) already, because
Dalvik's (trace based) JIT will knock out "hot paths" of code along
your bytecode generation.

I agree with your sentiment here - I've long been a proponent of not generating code purely for performances' sake. Some years ago I wrote a bytecode generation framework for Java (a project that was lost in the java.net changeover) and included with that was a warning about the perceived "benefits" of code gen with regard to performance from a naive viewpoint.

However, in this case, the compilation to DEX *does* give a considerable performance boost, and mostly for one reason - it allows us to cut out Reflection. In the custom VM, all method calls are done by reflective invocation, which as I'm sure you're aware carries a fairly heavy penalty. When compiling for DEX, method calls are instead statically linked and compile down to invokeVirtual instructions. 

Since everything in Deelang is a method call, getting away from reflection is a huge win here, and was the primary reason I started on the dex compiler.

 

Do you have any firm numbers to support this either way?

The project is still under active development, so obviously it's too early for any real benchmarking to take place, but I did run a quick and simple test so I'd have something to illustrate the kind of performance boost we're getting.

This is running the script "a = foo.timesTwo(3+2)" (where timesTwo is a Java method whose implementation I'm sure you can guess) over 10000 runs, on both the original Deelang VM and as a Dex compiled script. 

09-27 10:45:27.525: I/BENCHMARK(15853): Rehearsal

09-27 10:45:37.665: I/BENCHMARK(15853): DeeVM completed : 10000 runs : 10107ms (10.107 seconds)

09-27 10:45:37.725: I/BENCHMARK(15853): Dex completed   : 10000 runs : 31ms (0.031 seconds)

09-27 10:45:37.725: I/BENCHMARK(15853): Real

09-27 10:45:46.695: I/BENCHMARK(15853): DeeVM completed : 10000 runs : 8938ms (8.938 seconds)

09-27 10:45:46.745: I/BENCHMARK(15853): Dex completed   : 10000 runs : 25ms (0.025 seconds)

(The actual benchmark code can be found at https://code.google.com/p/deelang/wiki/DeelangPerformance) 

kris

Regards,

Ross

[Kristopher Micinski]

These are good insights. I am interested in following your
development, and you've made a convincing argument as to why you need
a new compiler.

I agree that reflection will kill you. I actually hadn't thought
about this, but it seems like there should be some sort of analysis to
be able to get rid of the overly large reflective cost. Since inside
your interpreter you will use a fairly fixed set of reflective calls,
I would assume that for (example) long loops inside the program
reflective calls could also be handled by the JIT (but, I assume they
are *not*). Still, I agree that if the numbers are as you say, then
having a compiler to Dex bytecode will help.

FYI from a research standpoint I am interested in doing something with
this. I was going to work on implementing my own language for
scripting apps, but I feel that would be a slight waste of time, as I
really care more about the semantics within apps.

So this is cool, I'd like to see if the language you have models the
sort of thing I want to express, I believe it may. In any case, I
will take a look at your compiler this weekend.

FYI during a project I work on we've written a compiler (really binary
rewriter) for Dalvik bytecode in OCaml, though if you wanted to use it
as part of your project you would have to properly port the ocaml
runtime to Android (unless you could deal with doing development on a
machine and then having it loaded to a phone all the time, which I
probably would for my research purposes..).

Anyway, thanks for the clarification, I'll be sure to take a look. If
you want any help, or have ideas on what you'd like to do next, I'd be
interested in hearing.

Slight word of advice: android-developers is probably a sort of bad
place to announce this. Why? Because most people on this list are
just here looking for immediate advice about how to fix their broken
app... You might also try broadcasting on android-platform or
something, I'm not sure where the proper place to announce this would
be, actually...

Do you have a community set in place for your language? (I.e., a
mailing list I can join to watch your development?)

Also, as matter of personal preference, would you ever consider
switching to github ... :-P... I just don't like the google code
interface as much...

kris

> --
> You received this message because you are subscribed to the Google
> Groups "Android Developers" group.
> To post to this group, send email to android-d...@googlegroups.com
> To unsubscribe from this group, send email to
> android-develop...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/android-developers?hl=en

[Mark Murphy]

On Tue, Sep 25, 2012 at 9:22 PM, Ross Bamford <rosc...@gmail.com> wrote:
> Recently, I've been working on a native (i.e. DEX) compiler for
> it.

Are you using Dexmaker for this?

http://code.google.com/p/dexmaker/

--
Mark Murphy (a Commons Guy)
http://commonsware.com | http://github.com/commonsguy
http://commonsware.com/blog | http://twitter.com/commonsguy

_The Busy Coder's Guide to Android Development_ Version 4.1 Available!

[Kristopher Micinski]

No, it looks like homebrew code.

I believe you can also just use something like dexgen..

https://github.com/android/platform_dalvik/tree/master/dexgen/src/com/android/dexgen

But no, as far as I was able to tell, this was all homebrewed compiler source...

kris

[Jan Burse]

Ross Bamford schrieb:

> You'll find the project at http://deelang.googlecode.com/ . To get the
> native compiler, you'll need to check the DEXCOMPILER branch out of
> subversion (a file release is planned soon, but not yet).

Does it take a detour over Java bytecode? If yes,
is this bytecode also executable on non Android
platforms? If yes, already done some double deployment
(modulo having a GUI/console)?

Bye

[Kristopher Micinski]

Again, just me running over the code, it looks like this is just
Dalvik bytecode, it doesn't take the step through Java bytecode.

kris

[Ross Bamford]

On Thursday, 27 September 2012 18:28:40 UTC+1, Kristopher Micinski wrote:

I agree that reflection will kill you.  I actually hadn't thought
about this, but it seems like there should be some sort of analysis to
be able to get rid of the overly large reflective cost.  Since inside
your interpreter you will use a fairly fixed set of reflective calls,
I would assume that for (example) long loops inside the program
reflective calls could also be handled by the JIT (but, I assume they
are *not*).  Still, I agree that if the numbers are as you say, then
having a compiler to Dex bytecode will help.

To be fair, the implementation of the Dee VM could be improved somewhat in this respect, although at the cost of flexibility. And in any event, performance would still never reach that of Dex compiled scripts, since the JIT cannot optimize reflection to the same extent as it does bytecode because it can't make the same kind of assumptions as it can when the code is statically compiled. 

(Caveat: I admit that I am basing this on the JVM - I simply don't know enough about Android's JIT at this point to discuss it specifically).

 

FYI from a research standpoint I am interested in doing something with
this.  I was going to work on implementing my own language for
scripting apps, but I feel that would be a slight waste of time, as I
really care more about the semantics within apps.

So this is cool, I'd like to see if the language you have models the
sort of thing I want to express, I believe it may.  In any case, I
will take a look at your compiler this weekend.

Excellent. I would definitely welcome any feedback you have!

 

FYI during a project I work on we've written a compiler (really binary
rewriter) for Dalvik bytecode in OCaml, though if you wanted to use it
as part of your project you would have to properly port the ocaml
runtime to Android (unless you could deal with doing development on a
machine and  then having it loaded to a phone all the time, which I
probably would for my research purposes..).

This interests me. Is this a publicly-available project? If so, do you have a link so I could take a look?

 

Anyway, thanks for the clarification, I'll be sure to take a look.  If
you want any help, or have ideas on what you'd like to do next, I'd be
interested in hearing.

I would certainly be interested in hearing any feedback you have on future direction for the project. And if you feel there is something that should be added or changed, let me know. If you're so inclined, I'd be even more interested to receive patches ;) 

Next on my list is implementing the last couple of features that the Dee VM supports (actually, Java field access is the only unimplemented feature) and extending the tests. There are a fair few bugs that I know about in the Dex compiler, but that still need to be expressed as tests.

I also have a couple of language changes I would like to make, but they'll come after the dex compiler is merged into the trunk and a release is made based on the current spec.

 

Slight word of advice: android-developers is probably a sort of bad
place to announce this.  Why?  Because most people on this list are
just here looking for immediate advice about how to fix their broken
app... You might also try broadcasting on android-platform or
something, I'm not sure where the proper place to announce this would
be, actually...

I monitor quite a few Android-related forums, and I too am not sure where the best place to find interested people might be. I'll definitely take a look at android-platform though, thanks for the pointer. 

 

Do you have  a community set in place for your language?  (I.e., a
mailing list I can join to watch your development?)

There isn't a public mailing list at the moment, although I have been considering setting one up as interest in Deelang grows. I'll look into it over the next few days. 

 

Also, as matter of personal preference, would you ever consider
switching to github ... :-P... I just don't like the google code
interface as much...

I have a vague item on my todo list about switching over to git "at some point" but it's something I've not yet gotten around to. Maybe some day... :)

Regards, 

Ross

 

> android-developers+unsub...@googlegroups.com

[Ross Bamford]

On Thursday, 27 September 2012 18:38:56 UTC+1, Mark Murphy (a Commons Guy) wrote:

On Tue, Sep 25, 2012 at 9:22 PM, Ross Bamford <rosc...@gmail.com> wrote:
> Recently, I've been working on a native (i.e. DEX) compiler for
> it.

Are you using Dexmaker for this?

http://code.google.com/p/dexmaker/

Yes, all the code generation is actually done through Dexmaker. The way it actually works is I wrap a Dexmaker Code object in a proxy which just records the method calls, and then does the generation at the end of the compilation by calling the appropriate methods on the Code object. This way, I can easily change things as the compilation progresses. It also allows me to pool locals, to be reused when they've gone out of scope (e.g. when they're just used temporarily to store some intermediate result, or as a method argument).

If you're interested, the code for this proxy can be found at https://code.google.com/p/deelang/source/browse/branches/DEXCOMPILER/deelang/src/com/roscopeco/deelang/compiler/dex/CodeProxy.java

 

Regards,

Ross

[Kristopher Micinski]

On Thu, Sep 27, 2012 at 6:40 PM, Ross Bamford <rosc...@gmail.com> wrote:
> On Thursday, 27 September 2012 18:38:56 UTC+1, Mark Murphy (a Commons Guy)
> wrote:
>
>> On Tue, Sep 25, 2012 at 9:22 PM, Ross Bamford <rosc...@gmail.com> wrote:
>> > Recently, I've been working on a native (i.e. DEX) compiler for
>> > it.
>>
>> Are you using Dexmaker for this?
>>
>> http://code.google.com/p/dexmaker/
>>
>
> Yes, all the code generation is actually done through Dexmaker. The way it
> actually works is I wrap a Dexmaker Code object in a proxy which just
> records the method calls, and then does the generation at the end of the
> compilation by calling the appropriate methods on the Code object. This way,
> I can easily change things as the compilation progresses. It also allows me
> to pool locals, to be reused when they've gone out of scope (e.g. when
> they're just used temporarily to store some intermediate result, or as a
> method argument).
>
> If you're interested, the code for this proxy can be found at
> https://code.google.com/p/deelang/source/browse/branches/DEXCOMPILER/deelang/src/com/roscopeco/deelang/compiler/dex/CodeProxy.java
>
> Regards,
> Ross

Ah, apologies, I missed this on a cursory glance at the compiler ..

kris

[Ross Bamford]

No, it goes directly to Dex. The original interpreter runs on any Java platform (Deelang was originally intended as a generic scripting language for embedded devices) but the compiler is strictly Dalvik. It wouldn't be difficult to transform the Dee VM bytecode to Java bytecode (they're both stack machines so the biggest challenge would be the static linking) but there are no plans for this at the moment.

Regards,

Ross

[Kristopher Micinski]

On Thu, Sep 27, 2012 at 6:33 PM, Ross Bamford <rosc...@gmail.com> wrote:
> On Thursday, 27 September 2012 18:28:40 UTC+1, Kristopher Micinski wrote:
>>
>> I agree that reflection will kill you. I actually hadn't thought
>> about this, but it seems like there should be some sort of analysis to
>> be able to get rid of the overly large reflective cost. Since inside
>> your interpreter you will use a fairly fixed set of reflective calls,
>> I would assume that for (example) long loops inside the program
>> reflective calls could also be handled by the JIT (but, I assume they
>> are *not*). Still, I agree that if the numbers are as you say, then
>> having a compiler to Dex bytecode will help.
>>
>
> To be fair, the implementation of the Dee VM could be improved somewhat in
> this respect, although at the cost of flexibility. And in any event,
> performance would still never reach that of Dex compiled scripts, since the
> JIT cannot optimize reflection to the same extent as it does bytecode
> because it can't make the same kind of assumptions as it can when the code
> is statically compiled.
>

Not necessarily true (and easier in a trace based JIT, I believe), if
you can reason about the contents of strings and do proper linking.

> (Caveat: I admit that I am basing this on the JVM - I simply don't know
> enough about Android's JIT at this point to discuss it specifically).
>

I don't think that Dalvik's jit does this, however..

>>
>> FYI from a research standpoint I am interested in doing something with
>> this. I was going to work on implementing my own language for
>> scripting apps, but I feel that would be a slight waste of time, as I
>> really care more about the semantics within apps.
>>
>> So this is cool, I'd like to see if the language you have models the
>> sort of thing I want to express, I believe it may. In any case, I
>> will take a look at your compiler this weekend.
>>
>
> Excellent. I would definitely welcome any feedback you have!
>
>>
>> FYI during a project I work on we've written a compiler (really binary
>> rewriter) for Dalvik bytecode in OCaml, though if you wanted to use it
>> as part of your project you would have to properly port the ocaml
>> runtime to Android (unless you could deal with doing development on a
>> machine and then having it loaded to a phone all the time, which I
>> probably would for my research purposes..).
>
>
> This interests me. Is this a publicly-available project? If so, do you have
> a link so I could take a look?
>

Not quite yet, but soon...

It's described on our paper.. http://www.cs.umd.edu/~jfoster/papers/spsm12.pdf

[Ross Bamford]

Thanks for the link, the transformation element of this does interest me. I look forward to seeing some code some day!

Regards,

Ross 

[Jan Burse]

Ross Bamford schrieb:

> No, it goes directly to Dex. The original interpreter runs on any Java
> platform (Deelang was originally intended as a generic scripting
> language for embedded devices) but the compiler is strictly Dalvik. It
> wouldn't be difficult to transform the Dee VM bytecode to Java bytecode
> (they're both stack machines so the biggest challenge would be the
> static linking) but there are no plans for this at the moment.

Thanks for explaining.