2013-12-02

Converting synced C/C++ into asynced JavaScript

Emscripten is a C/C++ -> LLVM -> JavaScript compiler. It's useful and interesting, but one of its biggest limitations is about the sync/async model: JavaScript is single-threaded event-driven languages, therefore you cannot do a sleep() in the hope of receiving and processing extra events.

Demo


First of all, please enjoy this demo, on which I really spent some time.

tl;dr

  • Motivation: to make `sleep` and other similar functions actually work in our Runtime, without lots of labor work porting the C/C++ code
  • I actually made it worked
  •  `sync->async` is doable and I think it's not too hard - there are already implementations for JS
  • I think this is a feature that cannot be supported by merely an external library
  • Does it fit emscripten? Or is it possible to write a plugin for emscripten?

Demo explained(?)


The demo is basically a stop-time animation:

//draw something
//wait for some while
//draw something else
//wait...


You can verify this in the source code.

We all know that it is hard to convert it into the async model of JavaScript. Now would you please take a look at my ported code, it's almost identical to the original code, except for:
  • A few macros are introduced, which are defined in asyn2.h — actually the macros are pretty much just placeholders. 
  • A js function js_napms defined  — which is a wrapper of setTimeout

I fed emscripten with the code and blablabla — and the demo works. But wait! The code should be identical to the original code, which is synced!
Well, please let me explain a few more things before I reveal the secrets.

Another Demo

Here's another demo, which is... the same as above. So what's the deal?

We may imagine that, to really 'go to sleep', we need to store all the context and restore it when we come back again. Indeed, I did so in the source code, whenever you see a `ASYNC_` macro, it involves pushing and poping to maintain the async stack.

The actual functions behind those macros are defined in async.h.

Well, I'm NOT going to propose a set of API or a library, instead I'm proposing a way of pre-processing the code, and I did that myself manually. It's doable and there're patterns, you may see how a for-loop is broken down according to the comments. I'll put technical details in the end.

The porting experience may not be as smooth as it looks like, actually `xmas` is rather straightforward, where there are rarely recursive for-loops or branches. But if you take a look at other demos, it is a nightmare to define callbacks and maintain the stack manually, just imagine that there's no `call` and `ret ASM macros, and you have to do `push`, `pop` and `jump` manually.

My point is that: the sync->async process can, and should be done by the pre-processor/compiler


The Secrets of the 1st Demo

You didn't skip the previous section did you?

Actually I made the second demo at first, before I knew the the secret weapon — streamlinejs, and here is an intuitive demo.

It's not a library, but a parser/compiler instead. I didn't go too deep into its mechanism, but from the results it generated, the mechanism should be similar as what I'll mentioned below. You may read  this article for more details.

To build the first demo, all the placeholders are replace with underscores, which will be recognized by streamlinejs (as placeholders for calback), fortunately un-optimized JS generated by emscripten can be parsed without any problem — at lesat my demo.

Technical stuffs

Imagine that there a stack dedicated for async function calls, it is different from traditional stacks in that this stack is not cleared when a function exits.

Async function calls are different from (normal) sync funtion calls, an async call pushes the context into the async stack, including the callback (similar as the return address in the synced case) and returns. The central event dispatcher (the JS engine in our case) will call the callback eventually.

So the central idea is to identify all the async function calls, which are usually casuse by two reasons:

  • Calling an async function
  • `jump` over an async call

The first one should be easy: some functions are async natively, e.g. `SDL_Delay`. And if a function calls any other async funtions inside, it is async.

The second one is usually originated from loops and branches, which will be explained later.

I think that these can be identified by the compiler, in one of following stages:

- Pre-processing C/C++ — I did that manually myself
- LLVM bitcode — which I'm not so sure
- JavaScript — streamline itself is an example

There are advantages and disadvantages in different stages, for example it might be easier to optimize the code when parsing the C code; while it may be more light-weighted to store the local variables using JavaScript closures.


Identify and transfrom async functions


Here's an example:


// sync version
void work()
{
    int j = 99;
    SDL_Delay(1000);
    printf("result %d\n", j);
}


Since SDL_Delay is natively async, we have to transform `work` into its async counterpart, as follows:


// async version
// context: stack for async calls
int work(context_t * context)
{
    int j = 99;

    push_callback(context, work__cb1);  // set up callback
    put_variable(context, j); // save local variables

    SDL_Delay(1000, context); // async version of SDL_Delay
 
    return 0; // get out and wait for SDL_Delay
}
int work__cb1(context_t * context)
{
    get_variable(context, j);
    pop(context);  // prepare to return the previous chained callback
    printf("result %d\n", j);
    context->callback();
}
```

For-loops make the situation more complicated, which causes another type of async calls:


int f()
{
    for(int i = 0; i < 10; ++i)
    {
        printf("hi ");
        SDL_Delay(10);
        printf("%d\n", i);
    }
}



f() can be flattened as


int f()
{
   int i = 0;
start:
   if(i >= 10) goto end;
   printf("hi");
   SDL_Delay(10);
   printf("%d\n", i);
   ++ i;
   goto start;
end:
   // nothing
}


Now it is clear that we can split the function and make async calls


int f(context)
{
  int i = 0;
  // save i to the stack
  // async call f_start();
}
int f_start(context)
{
  // restore i
  //pop stack

  if(i >= 10) // async call f_end();

  printf("hi ");

  // save i
  // push f_start2 into the stack
  SDL_Delay(10, context);
  return 0;
}
int f_start2(context)
{
   // restore i
   //pop stack

   printf("%d\n", i);

  // push i
  // async call f_start() to continue the loop
   return 0;
}
int f_end(context)
{
   // pop stack
   // async call callback of f()
}


Braches (if, switch etc)  are similar, as long as we consider them as `goto`'s.


local variables and return values

local variables may be stored and retrieved when we push/pop the async stack,
and so are return values.

Compiler/Preprocessor Integration: Step 1

It should be clear now that this feature is kind of transformation, which cannot be supported by linking to an external library. Of course the pre-condition is that the transformation should be (almost) transparent, it should not be necessary for developers to maintain the stack manually.

The first step, I'd imagine, is that the async functions are explicitly marked through some mechanism. In my example, a placeholder is used.

Developers may still write programs in the sync fashion, for two reasons: one for the convenience writing new program, and the other for porting existing ones.

The compiler should detect, split and setup async functions automatically, the async stack should be managed by standard library while some API might be exposed.

There are two ways  of managing the local variables, let me call them the C style and the JavaScript style:

The C style: Local variables of async functions are stored in dedicated area in the memory (HEAP or a special stack for async functions), instead of the normal stack. To avoid lots of memcpy's, the variables may be directly allocate there. Some push/pop operations may be optimized if the caller/callee is known (e.g. loops/branches)

The JavaScript style: streamlinejs is a good example. Async functions are broken into a series of resursive functions, and local variables are stored into the closures.

The JavaScript style is easy and intuitive, but the hidden overhead might not be negligible. It may be too late to optimize when the LLVM bitcode have been transformed into JavaScript.


Compiler/Preprocessor Integration: Step 2

It might be possible to further reduce the work of writing/porting, as even marking async functions and define the placeholders for every async function declaration and every async function call is boring and error-prone.

My (naive & wild) imagination is that by defining a few essential async functions (such as SDL_Delay), the compiler would automatically recognize async functions, and set up the hidden parameter. It's not perfect, especially when we need to link a number libraries, but at least I think a C/C++ transformer would be possible and nice, perhaps based on LLVM?

Limitations

  • It might not work for muti-threading. Indeed I've been only thinking about single-threaded programs, especially most ones for terminal — But this should not affect the importance of this issue I think.
  • Lots of overhead might be introduced in this way — But I guess the performance should not be affected much if well optimized
  • C++: ctr/copy/dectr  of objects might be a problem, or maybe not since they can be `flattened` into C-style?
  • C++: try-catch might not work, the control flow is already diverted
  • There a few limitations of streamlinejs, but I think many of them can be addressed if we process in the C phase.

Discussion

Please follow this thread on GitHub.

2013-10-23

杂记 2013.10.23

png优化工具:pngnq(有损)和 pngcrush(无损)

ubuntu gnome 13.10的input source里找不到输入法:手动修改dconf键值
org.gnome.desktop.input-sources.sources
,在数组里添加('ibus','sunpinyin')('ibus', 'anthy')但是mozc似乎不行,原因不明。观望。mozc在dconf里要打('ibus', 'mozc-jp')

2013-10-20

Ubuntu 下 mount windows 共享目录

一般来说遇到标题所述问题我马上会想到smbfs,不过好久不用,最近发现smbfs已经没有了,取而代之的是cifs,于是命令大约是

sudo mount -t cifs //hostname//folder /localfolder -o user=username

不过总是报 Input/ouput error

google了一阵,有的说加上sec=ntlm有的说加iocharset=utf8,不过都没用。其中加了后者还会出 Can not access a needed shared library 的错误。根据 http://wiki.openwrt.org/doc/howto/cifs.client   和 https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1067681, 安装了linux-image-extra-***的包以后才可以,但是mount还是不行。(我的linux是在虚拟器,装的最小内核linux-virtual)

于是尝试了一下smbclient,也是报错:tree connect failed: NT_STATUS_INSUFF_SERVER_RESOURCES 根据 http://klebom.net/melazy/tricks/ 查到是IRPStackSize过小的问题, 我在windows也确实查到了事件:
Log Name:      System
Source:        srv
Date:          2013-10-20 14:08:29
Event ID:      2011
Task Category: None
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      ***
Description:
The server's configuration parameter "irpstacksize" is too small for the server to use a local device.  Please increase the value of this parameter.

于是查到需要改注册表
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lanmanserver\parameters\IRPStackSize

这是个DWORD值,根据http://support.microsoft.com/kb/285089说其默认值是15,可取范围是11-50。之前那个链接说改成了17,18才可以,但我一直尝试到20都不行,于是一口气改成32才可以。

但愿没有后遗症。具体原因仍不明,不知道是否跟在跑linux虚拟机有关。

2013-09-01

Install Ubuntu 13.10 via Grub Legacy



I need to install Ubuntu 13.10 into an old Linux machine. The BIOS has been locked such that I cannot boot from CD or USB drives.

The machine has grub 0.97 and a pretty old CentOS installed on it, which I've got the root access, so I decided to try to load the ubuntu iso file with it.

I tried to enter the grub commands there, but then it failed with error like this:

stdin: error 0
/init: line 7: can't open /dev/sr0: No medium found
After spending hours in searching and trying, I found this url: http://askubuntu.com/questions/47076/usb-boot-problems
which solved the problem for me.

The full commands I used are:

root (hd1,0)
kernel /casper/vmlinuz.efi boot=casper live-media-path=/casper/ ignore_uuid
initrd /casper/initrd.lz

This link http://manpages.ubuntu.com/manpages/karmic/man7/casper.7.html
describes the parameters for casper

Screen Color Calibration


configure softwares
gimp: edit->preferences->color management->try to use system monitor profile
firefox: about:config -> gfx.color_management.mode -> 1
 
test pages


I bought a spyder 4 express and would like to try dispcalGUI on my surface pro, so I have to install Argyll CMS's driver, which is not signed.

For windows 8, one option to disable driver signature enforcement is through "advanced startup settings", which lists a few options after a restart, and you can press f7 or 7 to disable it.
However for my surface pro, it refused to recognize my keyboard, no matter it is a bluebooth keyboard, a usb wireless keyboard or a normal usb keyboard.
I guess a touch/type cover might work, but I don't have one.

Another option is to enable test mode (bcdedit -set testsigning on), before which you should also disable secure boot in the bios setting 
(shut down the device, hold the volumn up key before pressing the power button and release it when you see the surface logo)
However in this case, any signed driver could be installed, but unsigned drivers are still rejected.
For windows 7, there are words that you may use dseo13b to hack, but no luck for me on windows 8.

I had thought about using my Linux VM to do the calibration, which is running under Hyper-V, but unfortunately Hyper-V does not support USB forwarding.
I'd even thought about other VM softwares, but according to the Internet, it might not work. (because VM may not access the graphics card)

Another solution came into my mind is to boot up the device with a Linux on a USB stick, then I'll be able to do whatever I want. 
But there is only one USB port on Surface Pro, and I'm not sure if USB boot or Spyder would work behind a USB hub.

Finally I gave up.

Other possible solutions:
- Sign the driver with WDK, with your own certificates
- Install Linux and free the power of the device


2013-08-21

杂记 20130821

一直纠结是用中文写还是英文写还是都写,随心情好了。

Windows 8 FileHistory 不能指定外置硬盘
参考:http://answers.microsoft.com/en-us/windows/forum/windows_8-hardware/windows-8-file-history-does-not-recognize-my/361a527b-d35b-4753-b4a6-3ccff738ff62?page=2
- 确定该硬盘没有被加入任何library
- 删除 C:\Users\USERNAME\AppData\Local\Microsoft\Windows\File History


给我妹家里配无线路由,主要是希望用一个小路由增强一个大路由(外接adsl)的信号
一开始给小路由设的repeater模式,但是不太好使,于是用ap模式+开启wds,然后小路由自动禁用了dhcp。这时在小路由的信号内手动设置ip和dns可以上网。最后把小路由dhcp打开,然后把两个路由分配的ip段分开就可以了。
两个路由的ssid,信道和加密方式都应该相同。
按理说WDS应该可以的,但是似乎小路由不太行。


利用PuttyGen声称公钥然后让服务器信任
参考:http://www.dailyiteration.com/howto-passwordless-ssh-authentication-with-putty/
主要是需要用sshkeygen -i -f 转一下格式


Gmail里拖拽图片附件,如果拖到正文,就会添加成inline image;如果拖到下方工具栏上,就会添加成附件

2013-07-02

Misc Notes 20130702

- To remove the 'new release available' message, remove the file
/etc/update-motd.d/91-release-upgrade

- To remove unused language packs from Windows 8, run `lpksetup`

- If Cygwin X server crashed with `-multiwindow` on HD4000 graphics card, try updating the graphics card driver

- halt vs poweroff: halt does not send the acpi power off signal

- MyPaint picker offset on windows 64bit with high dpi
- Also how to set the high dpi compatibility setting for 64bit programs
http://forum.intilinux.com/mypaint-help-and-tips/color-picker/

- Super useful shortcut, show advanced management menu: winkey+x

- The 'Send to OneNote' feature replies on the xps printer

2013-05-05

Notes 20130505

'tc' and 'netem' allow you to simulate some network environments
http://www.linuxfoundation.org/collaborate/workgroups/networking/netem#Delay_distribution
For example, I can delay every packet for 1s, such that in some case I can cheat in games.

Google Chrome complains about "profile cannot be opened correctly": remove the 'web data' folder in the config dir
http://www.fourleaftechnology.com/index.php/General/google-chrome-profile-could-not-be-opened-correctly-error.html

To remove PDF password with gs
http://www.cyberciti.biz/faq/removing-password-from-pdf-on-linux/
gs -q -dNOPAUSE -dBATCH -sDEVICE=pdfwrite -sOutputFile=unencrypted.pdf -c .setpdfwrite -f encrypted.pdf

IE10 would ignore the `word-spacing` CSS rule if the width for the space char is 0, in a TTF font. Is it a bug of IE?

杂记 20130505

使用tc + netem可以模拟一些网络环境
http://www.linuxfoundation.org/collaborate/workgroups/networking/netem#Delay_distribution
比如我可以让每个包都延迟1秒,某些情况下玩游戏还可以作弊

Google Chrome说Profile无法正确打开: 把配置目录里的'Web Data'目录干掉
http://www.fourleaftechnology.com/index.php/General/google-chrome-profile-could-not-be-opened-correctly-error.html

用gs去除PDF的密码:
http://www.cyberciti.biz/faq/removing-password-from-pdf-on-linux/
gs -q -dNOPAUSE -dBATCH -sDEVICE=pdfwrite -sOutputFile=unencrypted.pdf -c .setpdfwrite -f encrypted.pdf

IE10下如果TTF字体的空格宽度是0,就会无视word-spacing的css规则,不知道是不是IE的bug。

2013-04-01

Misc 20130401

  • To reset all shortcut definitions in evince, run
    rm ~/.config/evince/accels
  • GCC would complain if you define a variable without actually using it. To silience it, use
    (void)var;
  • DNS is not working in VirtualBox: Run
    VBoxManage modifyvm "VM name" --natdnshostresolver1 on
    Ref 
  • A useful link talking about ravlue reference in C++11 http://thbecker.net/articles/rvalue_references/section_01.html 
  • To clear disk cache in Linux: Run
    sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
    Ref
  •  "screen-256color not found": Run
    infocmp xterm-256color > screen-256color.ti
    on a machine without this error, copy the file to the target machine and then run
    tic screen-256color.ti
    Ref
  • Just switch to fcitx from ibus. I like a theme called 'anran'. If fcitx cannot follow the cursor on Firefox, turn on preedit, as said in the official wiki.
  • Just played with a vim plugin called youcompleteme, for C++ autocomplete, which is quite powerful. Also I installed vundle, a vim plugin manager.
  • To update vimrc just after some modification, run
    so %

杂记 20130401

  • 之前evince的快捷键乱套了,使用
    rm ~/.config/evince/accels
    复位
  • 定义了变量var又不用的话,gcc会报warning"unused variable",解法是
    (void)var;
  • VirtualBox中DNS不工作:运行
    VBoxManage modifyvm "VM name" --natdnshostresolver1 on
    Ref 
  • 一个讲c++11右值引用的link:http://thbecker.net/articles/rvalue_references/section_01.html 
  • Linux清除disk cache:
    sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' 
    Ref
  •  遇到错误screen-256color not found需要支持新的终端类型:找一台支持screen-256color的机器执行
    infocmp xterm-256color > screen-256color.ti
    把文件拷贝到目标机器后执行
    tic screen-256color.ti
    Ref
  •  最近从ibus换到了fcitx,起初是由于sogou发布了,不过后来还是卸掉了。anran主题不错。fcitx在firefox中光标跟随有点问题,按官方wiki说法打开preedit后就没事了。
  •  最近在vim里折腾youcompleteme这个补全插件,挺好用。顺便也装了vundle来管理插件,很不错
  •  vim更新.vimrc后想直接应用,执行
    so %

2013-02-26

Blogging: The 6th Year

It's been 6 years since the start of this blog, I still remember that soul-stirring accident which made me decide to start blogging.

6年博客回顾

这个blog写了6年了,还依稀记得当初促使我开始写blog的那次事故,那次真的是惊心动魄。

2013-02-05

杂记 20120205 | Misc Notes 20120205

1. Javascript 图表库比较
Ext JS 各种模型比较折腾,画出来还不错。
flot,配合jQuery写着比较顺手,但是功能不够多,内置符号只有圆圈,加个插件发现图例中不能显示符号。logscale还有坐标的分点都要自己实现。。。

2.gnuplot编译时报错,libpng冲突

3.Excel中方向键不工作
按一下ScrollLock试试

1. A few JS libraries for plotting
Ext JS, with rather complicated data models, but worthy. Produced figures look good.
flot, a smooth coding experience with jQuery, but also lack of features. E.g. by default the only available symbol is circle. There are plugins available for extra symbols, but only in legend...Also I have to specify all the ticks...

2. libpng confliction when compiling gnuplot.

3. Arrow keys not working in excel
Try to press the ScrollLock key

4. To play white noise in Linux
install sox
play -n synth 60:00 whitenoise