Asynchronous code generation

[konsoletyper]

TeaVM should be capable of transforming of serial code to a CPS-style code on demand. When method calls an asynch code, it should be also rendered as async.

When there is serial contract, we can't render method as async. For example, consider Element.addListener(listener). A listener is expected to call Event.stopPropagation() syncrhonously to stop event bubbling. If listener got rendered as async, this contract will be violated, as Event.stopPropagation might go to continuation. So TeaVM needs some mechanism that declares explicit border between sync and async code.

Async code is a good opportunity to implement cooperative multitasking. TeaVM could provide threading, switching on Thread.yield or on blocking I/O operations. Simple synchronization primitives could be implemented as well.

The most challenging thing is to deal with debugger, which is to increase its complexity.

[ivanceras]

First of all this is cool project.

Generating code an asynchronous code from a synchronous structure was one of my quest to solve, up until now.

Take note I am using GWT.

Writing Database API calls in jdbc are syncrhonous in nature, which is also a comfortable way of writing the code. Of course it is working well on server side platform since it is using the real jvm.

With the rise of html5 client side database/storage and the desire to support offline capabilities of the apps, while reusing the same server side logic/code to work on the client side would get me away from having two write versions of the same logic. I was finding a way to recreate the execution on the client side / javascript.

1st approach

Implement an asynchronous version of the API. This then leads to more code and still create 2 version of the same logic that handles the data(which is of course very messy to comprehend, think of callback hell). So i gave up with these approach.

2nd approach

Mark or Identify the part where the code is calling the synchronous code which would have an asynchronous version for a client side execution. A tool I would be building would then automatically create an asynchronous version of that code. Well, it turns out it isn't simple as I think it would be, first, you have to traverse the AST and determine which variables are used on the succeeding calls, thereby effectively creating a closure. I am in no way programming language expert so I gave on this approach too. This kind of similar to what you are trying to do, I was using the @yield annotations as a marker of these synchronous calls.

3rd approach

SQL.js, sqlite was compiled to javascript thereby I can use SQL calls, even on browser that don't implement webSQL (firefox), and the database calls on sql.js was synchronous, so the server side logic code works with sql.js + wrappers. This kind of solve the problem.
Except for minor things

• persisting the data to the actual data storage supported by the browser. Having to write the whole array of bytes to local storage does the job, but I am not sure how well it does when the data gets larger, and having a small window to complete the process hooked to the browser's onclose event.
• When the user open another window, they will have different data context, synching will have to go through the real data storage.

4th approach

I am still not satisfied with third approach, since it may be consuming a lot of processing power specially if its on the mobile device. I've read the ES6 yield/functions and generators which make an asynchronous call look like it is synchronous, jump on it and experiment with it. Turns out when you wrapped these function calls, or be called from other functions, you loose the synchronous ability of the function/generators, so it is only limited to calls within the function itself. API would not be possible with that limitation.

5th approach:

I stumbled upon this JS-interpreter. Which creates a JS runtime to run your javascript code in it, and you can control the execution/pause the execution of the runtime. As ridiculous as it sounds, it kind of solve the problem, since I can hook to the interpreter and inspect through which methods are called at a certain time, So when a certain method call(database call) is about to be called, I pause the execution of the interpreter then execute the database calls(this is outside the interpreter), callback retrieving the value, inject the value to the interpreter runtime, unpause the interpreter. The next succeeding call of the javascript code running inside the interpreter will then have to fetch the data that was injected from outside. It works, and not only limited to database calls and, but also ajax calls, phonegap/cordova plugin calls, anything that is asynchronous. Also, I believe this leads to more consumption of resources due to ridiculously several layers of runtimes, not to mention native javascript itself is inside a runtime.

I am not sure which approach these project is going to take, I'm betting it will be similar to 2.
I will watch these project and see where I can help, and apology for making a long comment here.

[konsoletyper]

@ivanceras, definetily it will be the second approach. The problem of generating CPS is well known for decaded and has a lot of good solutions. I am not going to introduce any annotations to mark asyncrhonous code, instead I may add annotation to restrict generating asynchronous code for certain methods, as async code is generally much slower and sometimes you need to be sure that the method runs as fast as possible.

[shannah]

Have you considered generating StratifyJS code? They provide all of the primitives required to implement green threads.
http://onilabs.com/stratifiedjs

Their waitfor primitive is the easiest way I have seen to do synchronous programming in javascript. I think we could probably achieve green threads by just converting Object.wait() and Object.notify() into event.wait() calls. If I get time, I plan to experiment with this myself.

[konsoletyper]

I know about stratify.js, but it won't fit needs of TeaVM. TeaVM has everything needed to produce asynchronous code, except for several little things. The big work, however, is maintain debugging. Also, we need to check whether all the existing code works properly in concurrent environment and that there are not existing contracts (such as event bubbling) are broken. Don't forget, that callback mashup is always much slower, than straight code, so green threads must be designed very carefully.

[shannah]

Can you elaborate on why it doesn't fit the needs of TeaVM. I'm looking at trying to use TeaVM for a project that is heavy on the synchronous code. (In fact my other team members don't think it is even feasible to make it run with green threads.. they think we need real threads). I was thinking I could probably just hack the code that TeaVM generates for Object.notify() and Object.wait() and that would be the end of it... But I'm not too familiar with the TeaVM source base, so I could be way off here.

[konsoletyper]

TeaVM produces both source maps and its own debug symbol table. They map Java source locations to JavaScript source locations. If the generated JS code is altered, this mapping becomes irrelevant and though debugging becomes impossible. If you need async code that much, I'll try to implement all the necessary transformations in TeaVM very soon. However, you will experience great problems with debugger, since CPS will remove concept of call stack. I'll need some time to rewrite debugger, so that it could re-build stack trace from clousure contexts of CPS-generated callbacks.

[shannah]

Thanks. That makes sense. Debugging and source maps are very handy indeed.

[konsoletyper]

@shannah, I have working prototype of CPS generator. It successfully produced asynchronous code for a little sample program. There is a lot of work to do still, but core algoritm is implemented. AsyncProgramSplitter class shows the main idea of the whole algorithm. We get CFG and for each occurence of asynchronous invocation "split" our CFG into two parts, one that preceedes the invocations, and another that follows the invocation. Then we handle all the produced CFGs almost the usual way. You can fetch async branch and build TeaVM from it, then see what TeaVM produces for teavm-samples-async module.

Another advantage of doing CPS in the side of TeaVM is that TeaVM has information about types, hence it can build call graph properly. It gives chance to determine, which methods are reallly needed to be transformed into CPS. Most of methods from teavm-samples-async projects are compiled into synchronous version. AsyncMethodFinder class is responsible for determining which methods are actually asynchronous.

[shannah]

That looks great. I have looked through the code and can't wait to try it out (I'll be trying it out this morning). My plan is to also make wait(), notify(), and notifyAll() async also. Except, wait() will add a callback to an event queue bound to the object, notify() will execute and pop the first callback in the event queue, and notifyAll() will execute all of the callbacks in the event queue. I think that will replicate full threaded behaviour pretty closely. Do you see any flaws in this plan?

[shannah]

I ran your example and it works great. I've made an attempt at adding support for Thread.start(), Object.wait(), Object.notify(), and Object.notifyAll(). I have it working for some simple tests. I am running into a problem where, at the end of my Thread.run() execution, I get an error because TeaVM is trying to call a $return() callback that doesn't exist. I have posted a fork at https://github.com/shannah/teavm/tree/threads.

You can see the modified demo here:
https://github.com/shannah/teavm/blob/threads/teavm-samples/teavm-samples-async/src/main/java/org/teavm/samples/async/AsyncProgram.java

You should be able to just check out this fork and run the demo to see the error that I'm talking about.

BTW. Really like working with TeaVM so far. The source maps and debugger stuff you did if phenomenal. And this Async functionality is really breaking new ground. Keep up the great work.

[konsoletyper]

@shannah good work! Go on, but, please, not very deep, since I am going to implement one little feature to make more convenient writing of async methods. Look at AsyncCallback. The will be convention: if native method is Async and there is method with the same parameters plus one parameter of type AsyncCallback, then this second method will be implementation of the first method. Also I am going to rewrite classlib to avoid manual generation of JavaScript in favour of using JSO (so I'll extend JSO).

As for your particular problem. Here is the patch: http://pastebin.com/T9XTRMgQ And don't forget merge the latest changes async branch. Please, if you want explanations, ask questions in google group

[shannah]

Brilliant! Works perfectly. I'll take a look through your changes and, if I can't understand something, I'll post to the forum.
Are you interested in receiving a pull request for any of these changes (I still need to clean it up), or are you planning of implementing the same in a different way? If you want a pull request, just let me know how you want it or if there are changes you want me to make first, and I'll do my best to comply.

[konsoletyper]

Of course, make pull request. I'll improve your implementation eventually, but for now it is sufficient.

[shannah]

I did some preliminary work to add support for Thread.currentThread() returning the current thread. E.g.

final Thread t = new Thread(new Runnable(){
    public void run(){
        if ( t != Thread.currentThread() ){
             System.out.println("In a correct implementation this shouldn't happen");
        } else {
             System.out.println("This case should happen every time.");
        }
    }
});
t.start();

(This is pseudo code... I don't think it compiles.... I just posted to demonstrate)

I override the setTimeout() function to keep track of the current thread. If we use other mechanisms for calling async code, I may have to patch those also. It might also be possible to move this type of thread tracking mechanism elsewhere, but I don't know the code intimately enough to make such changes yet.

shannah@e6e52d1

[konsoletyper]

Good! Tracking existing thread is very important to implement MONITOENTER/MONITOREXIT opcodes, as well as synchronized methods. Do you want to implement this? If you do, please, don't forget that non-async code will always run exclusively, so you can still ignore these instructions there. Also, I am going to change the way how TeaVM handles async exceptions. I'd like to get rid of the second ($throw) callback in favour of passing function to continuation, so this function would either return value or throw exception. This could affect implementation of locks.

Do you mind to introduce $rt_setTimeout instead of redefining existing setTimeout function? TeaVM should interact with the existing JavaScript and I'm not sure whether they won't interfere with the overriding setTimemout function.

[konsoletyper]

@shannah, please, note the latest changes (73721e5) I made to support exceptions in async methods. Now, $return function accepts function instead of value. You should wrap your value with $rt_asyncResult. If there is nothing to pass (i.e. when method is void), you can simply pass null. Additionally, you can use $return($rt_asyncError(e)) to throw exception out of native async method.

[shannah]

Tracking existing thread is very important to implement MONITOENTER/MONITOREXIT opcodes, as well as synchronized methods. Do you want to implement this?

Sure. I'll need to get more familiar with how TeaVM generates the Async stuff. If the monitorenter and monitorexit opcodes just mapped to methods monitorEnter() and monitorExit() (for example), implementation would be trivial (i could just implement those methods with the Async annotation and implement them natively similar to the way wait() and notify() are implemented. I just don't yet know how to connect the dots from the opcodes to those hypothetical methods. Or can you think of a better way?

If you do, please, don't forget that non-async code will always run exclusively, so you can still ignore these instructions there.

What implications does that have on how I should implement it? Is this something I need to consider (e.g. does my implementation have to do some sort of check "if (isAsyncCode()) .... else ...")?

[konsoletyper]

I just don't yet know how to connect the dots from the opcodes to those hypothetical methods. Or can you think of a better way?

Two new instructions (see org.teavm.model.instructions) must be added. Or a single one, with a flag indicating what particular operation must be applied. ProgramParser should be modified to generate these instruction when it meets corresponding JVM opcodes. Decompiler should either produce direct invocations or generate new type of statements (see org.teavm.javascript.ast). Well, it might be too complicated, but I could assist you if you implemented monitorEnter/monitorExit methods. They are trivial, indeed.

What implications does that have on how I should implement it? Is this something I need to consider (e.g. does my implementation have to do some sort of check "if (isAsyncCode()) .... else ...")?

No, that does not affect implementation. That affects how decompiler handles MONITORENTER/MONITOREXIT instruction. Current implementation just skips them as if they were NOP. It must be extended to understand these instructions, but it should check whether the code is sync or async. With sync code it should still skip new instruction, with async code it should call monitorEnter/monitorExit methods.

[shannah]

Thanks. That's helpful. I should be able to figure it out from here. I'll be working on this over the next few days.

[shannah]

I have put in most of the pieces now. It is all in the branch:
https://github.com/shannah/teavm/tree/threads

Currently I'm getting an error why I try to compile code with synchronized sections

Caused by: java.lang.IllegalArgumentException: This instruction is in some basic block org.teavm.model.instructions.AssignInstruction@18fa822a, org/teavm/samples/async/AsyncProgram.java:86
    at org.teavm.model.BasicBlock$1.add(BasicBlock.java:82)
    at org.teavm.model.BasicBlock$1.add(BasicBlock.java:56)
    at java.util.AbstractList.add(AbstractList.java:108)
    at java.util.AbstractCollection.addAll(AbstractCollection.java:344)
    at org.teavm.model.util.ProgramUtils.copy(ProgramUtils.java:95)
    at org.teavm.model.util.ModelUtils.copyMethod(ModelUtils.java:52)
    at org.teavm.model.util.ModelUtils.copyClass(ModelUtils.java:37)
    at org.teavm.dependency.DependencyClassSource.findClass(DependencyClassSource.java:78)
    at org.teavm.dependency.DependencyClassSource.findAndTransformClass(DependencyClassSource.java:65)
    at org.teavm.dependency.DependencyClassSource.access$000(DependencyClassSource.java:33)
    at org.teavm.dependency.DependencyClassSource$1.map(DependencyClassSource.java:41)
    at org.teavm.dependency.DependencyClassSource$1.map(DependencyClassSource.java:39)
    at org.teavm.common.CachedMapper.map(CachedMapper.java:49)
    at org.teavm.dependency.DependencyClassSource.get(DependencyClassSource.java:52)
    at org.teavm.dependency.DependencyChecker.findMethodReader(DependencyChecker.java:284)
    at org.teavm.dependency.DependencyChecker.access$000(DependencyChecker.java:51)
    at org.teavm.dependency.DependencyChecker$1.map(DependencyChecker.java:79)
    at org.teavm.dependency.DependencyChecker$1.map(DependencyChecker.java:77)
    at org.teavm.common.CachedMapper.map(CachedMapper.java:49)
    at org.teavm.dependency.DependencyChecker$3.map(DependencyChecker.java:89)
    at org.teavm.dependency.DependencyChecker$3.map(DependencyChecker.java:87)
    at org.teavm.common.CachedMapper.map(CachedMapper.java:49)
    at org.teavm.dependency.DependencyChecker.linkMethod(DependencyChecker.java:259)
    at org.teavm.vm.TeaVM.entryPoint(TeaVM.java:243)
    at org.teavm.tooling.TeaVMTool.generate(TeaVMTool.java:266)
    at org.teavm.maven.BuildJavascriptMojo.execute(BuildJavascriptMojo.java:256)
    ... 21 more

So I must have something wrong. I won't have a chance to work on this over the weekend, but will be picking it up again on Monday.

[shannah]

Thanks for the comments. I have made the changes you suggested. I'm still getting the same error when building the sample. Do you know what would cause an error like this?

[konsoletyper]

It seems that you've broken instruction copier. You might forget implement some of the visitor methods.

[shannah]

Bingo! That was it. It now builds ok. I'm hitting a runtime error during execution now.

[Error] TypeError: undefined is not a function (evaluating 'continuation($rt_asyncError(e))')
    callback (classes.js, line 7)

Off for the weekend... will pick this up on Monday.

[konsoletyper]

It seems, that you encounter problem (see test case) I've fixed recently. Sorry for making so much breaking changes in the last commit. Hope, it won't be to hard to rename some imports.

[konsoletyper]

@shannah BTW, look at new implementation of Thread.sleep. Hope writing async methods this way will be much easier.

[shannah]

The new format looks nice. Will update my code accordingly. I plan to run code inside web workers which don't have access to "window". It would be nice to keep the core agnostic in this way (not relying specifically on window). That should be a simple change.

[konsoletyper]

Yes, it should be. You can simply assign window = this; in the beginning of the script.

[shannah]

I may still want to just implement heavy hitters like wait and notify directly in JavaScript for best performance. Will the old method for async still work?

[konsoletyper]

Yes, old method works. However, you may prefer to use JSO instead of direct JS generation. First option seems easier to implement/support.

[shannah]

I have updated my implementations to use the new AsyncCallback approach and JSO instead of native methods. It builds OK, but I have broken something in the AsyncProgram sample.

[Error] TypeError: undefined is not a function (evaluating 'otp_Platform18_getConsole225().rt_putStdout(a)')
    (anonymous function) (runtime.js, line 410)
    (anonymous function) (runtime.js, line 430)
    (anonymous function) (runtime.js, line 465)
    otsa_AsyncProgram48_main326 (classes.js, line 2386)
    (anonymous function) (runtime.js, line 344)
    (anonymous function) (runtime.js, line 432)
    onload (teavm-samples-async, line 24)

[shannah]

Fixed that error:
shannah@a78d5de

Now facing a number of errors of the form:

[Error] TypeError: undefined is not a function (evaluating 'continuation($rt_asyncError(e))')
    (anonymous function) (runtime.js, line 410)
    (anonymous function) (runtime.js, line 430)
    (anonymous function) (runtime.js, line 465)
    (anonymous function) (runtime.js, line 465)
    complete31 (classes.js, line 1091)
    jl_Thread$3144_onTimer132 (classes.js, line 812)
    (anonymous function) (classes.js, line 817)
    (anonymous function) (classes.js, line 1111)

[konsoletyper]

@shannah fixed this issue. Please, make TObject.window reference static. However, event after this change I still encounter strange error.

[shannah]

Thanks. Done. I just noticed that with my new implementation I'm not making use of $rt_rootInvocationAdapter as I was with the old native implementation. Not sure if this is the issue.

[konsoletyper]

There are problems with compiling this code: notifyListeners.push(new NotifyListener(){. JSO has major design flaw there. It will take some time to figure out how to solve the problem. Or you can just wrap NotifyListener in JS.function explicitly.

[shannah]

Can you elaborate on "wrap NotifyListener in JS.function"?
I may just return to using native generators for now.

[konsoletyper]

I just realized, that you can't proceed further with functors here. The problem is that you can't use native Arrays to store/retrieve Java objects directly. Consider using java.util.ArrayList (or java.util.ArrayDeque), and a bit later I provide a lightweight PlatformList, capable of storing/retrieving Java objects and having Array as a backing storage, without overhead.

[shannah]

I changed it back to native generators for now (just commented out the JSO code). Still getting errors of the form

[Error] TypeError: undefined is not a function (evaluating 'continuation($rt_asyncError(e))')
    (anonymous function) (runtime.js, line 411)
    (anonymous function) (runtime.js, line 431)
    (anonymous function) (runtime.js, line 466)
    (anonymous function) (runtime.js, line 466)
    (anonymous function) (runtime.js, line 466)
    (anonymous function) (runtime.js, line 466)
    (anonymous function) (runtime.js, line 466)
    complete134 (classes.js, line 999)
    jl_Thread$2138_onTimer133 (classes.js, line 770)
    (anonymous function) (classes.js, line 775)
    (anonymous function) (classes.js, line 1021)

hmm..

This is after merging your latest changes in async. I have pushed my latest to my "threads" branch.

[shannah]

OK. Solved that issue. Now it runs, but I'm not sure that it is picking up the fact that my monitorEnter function is async. For the portion of the sample:

synchronized(lock){
            System.out.println("Inside locked section of thread "+Thread.currentThread());
            Thread.sleep(2000);
            System.out.println("Finished locked section of thread "+Thread.currentThread());
        }

And with monitorEnter looking like:

@Async
    static void monitorEnter(TObject o){
        if ( o.monitorLock == null ){
            o.monitorLock = new TObject();
        }
        System.out.println("Thread "+Thread.currentThread()+" waiting  on lock for "+o);
        System.out.println("Lock owned by "+o.owner);
        if ( o.owner != null ){
            System.out.println(o.owner.getName());
        }
        while (o.owner != null && o.owner != TThread.currentThread() ){
            try {
                System.out.println(Thread.currentThread()+" waiting on lock");
                o.monitorLock.wait();
            } catch (InterruptedException ex) {
                throw new RuntimeException("Interrupted", ex);
            }
        }
        if ( o.owner != null && o.owner != TThread.currentThread()){
            System.out.println("Thread "+TThread.currentThread()+" has been granted a lock which is owned by "+o.owner);
            throw new RuntimeException("Thread "+TThread.currentThread()+" has been granted a lock which is owned by "+o.owner);
        }
        System.out.println("Thread "+Thread.currentThread()+" obtaining lock for "+o);
        System.out.println("The old owner was "+o.owner);
        o.owner = TThread.currentThread();
        o.monitorCount++;

    }

I get the following output

[Log] Thread java.lang.Thread@b43 waiting  on lock for java.lang.Object@b41 (runtime.js, line 353)
[Log] Lock owned by null (runtime.js, line 353)
[Log] Thread java.lang.Thread@b43 obtaining lock for java.lang.Object@b41 (runtime.js, line 353)
[Log] The old owner was null (runtime.js, line 353)
[Log] Inside locked section of thread java.lang.Thread@b43 (runtime.js, line 353)
[Log] Thread java.lang.Thread@b45 waiting  on lock for java.lang.Object@b41 (runtime.js, line 353)
[Log] Lock owned by java.lang.Thread@b43 (runtime.js, line 353)
[Log] Test Thread (runtime.js, line 353)
[Log] java.lang.Thread@b45 waiting on lock (runtime.js, line 353)
[Log] Inside locked section of thread java.lang.Thread@b45 (runtime.js, line 353)
[Log] Finished locked section of thread java.lang.Thread@b43 (runtime.js, line 353)
[Log] Finished locked section of thread java.lang.Thread@b45 (runtime.js, line 353)
[Log] Thread java.lang.Thread@b45 obtaining lock for java.lang.Object@b41 (runtime.js, line 353)
[Log] The old owner was null (runtime.js, line 353)

Which indicates, that the locking behaviour is working correctly (I.e. Thread@b45 doesn't obtain the lock for Object@b41 until Thread@b43 has released it). However the code is being allowed to proceed past the monitorEnter() call anyways.

I suspect this is something to do with the way that I am converting the MonitorEnterInstruction to a MonitorEnterStatement to a monitorEnter() method. TeaVM is not generating the transformations correctly i.e. monitorEnter() is just being treated as a regular sync method.

Any ideas what I've done incorrectly? I've posted my latest in my threads branch.

[shannah]

I got it working. I removed the MonitorEnter/Exit Instruction and Statement classes altogether and just made the program parser produce method invocations for my monitorEnter and monitorExit methods, and all seems to be working. I have pushed it to github, but still need to clean up the code (e.g. I still have the instructions and statement classes that are no longer being used... need to strip them out. Will do that tomorrow.

[konsoletyper]

@shannah, don't be hasty. You are trying to guess the reason instead of debugging. Let me find the error and fix it instead of trying to rewrite everything with raw JavaScript and eliminating instructions. I'll fetch your previous commits and provide a patch. It is important to retain MonitoEnter/MonitorExit instructions, as it can give useful information for optimizations. The only thing to do is to modify ProgramSplitter to insert split points after MonitorEnter instructions. Another solution is to replace MonitorEnter/MonitorExit instructions at the very last stage, just before splitting async methods. Also, won't it be better to continue this conversation by email directly?

[shannah]

Email works for me. steve@weblite.ca.
Thanks for taking a look at the code. You're probably right that it would be better to retain the MonitorEnter/MonitorExit instructions.

[konsoletyper]

Debugging of async code can be very difficult. I am going to support async code in debugger, however, either Google Crhome does not provide me sufficien information or I can't fetch it properly. Here is my question in Stack Overflow. If someone is interested in debugger support of async code, please, vote for this question.

[konsoletyper]

My latest commit fixes all known issues with synchronized blocks and Object.wait/Object.notify methods. I compared output of AsyncProgram sample both in JVM and TeaVM, and they are identical, except for prime numbers. I encountered one unpleasant issue with AsyncProgramSpitter. The problem is that after splitting program into parts we can get irreducible CFGs. Irreducible CFGs are not supported by TeaVM, and may cause unpredictable results. The solution is either to convert irreducible CFGs into reducible CFGs or to make additional splitting of parts so that every part is reducible.