Updates from July, 2012 Toggle Comment Threads | Keyboard Shortcuts

  • Mark Sinnathamby 4:35 PM on 15/07/2012 Permalink | Reply  

    Stack based vs Register based Virtual Machine Architecture, and the Dalvik VM 

    [Kostja Stern has been kind enough to translate this article in russian, which can be found here]
    A virtual machine (VM) is a high level abstraction on top of the native operating system, that emulates a physical machine. Here, we are talking about process virtual machines and not system virtual machines. A virtual machine enables the same platform to run on multiple operating systems and hardware architectures. The Interpreters for Java and Python can be taken as examples, where the code is compiled into their VM specific bytecode. The same can be seen in the Microsoft .Net architecture, where code is compiled into intermediate language for the CLR (Common Language Runtime).

    What should a virtual machine generally implement? It should emulate the operations carried out by a physical CPU and thus should ideally encompass the following concepts:

    • Compilation of source language into VM specific bytecode
    • Data structures to contains instructions and operands (the data the instructions process)
    • A call stack for function call operations
    • An ‘Instruction Pointer’ (IP) pointing to the next instruction to execute
    • A virtual ‘CPU’ – the instruction dispatcher that
      • Fetches the next instruction (addressed by the instruction pointer)
      • Decodes the operands
      • Executes the instruction

    There are basically two main ways to implement a virtual machine: Stack based, and Register based. Examples of stack based VM’s are the Java Virtual Machine, the .Net CLR, and is the widely used method for implementing virtual machines. Examples of register based virtual machines are the Lua VM, and the Dalvik VM (which we will discuss shortly). The difference between the two approaches is in the mechanism used for storing and retrieving operands and their results.

    Stack Based Virtual Machines

    A stack based virtual machine implements the general features described as needed by a virtual machine in the points above, but the memory structure where the operands are stored is a stack data structure. Operations are carried out by popping data from the stack, processing them and pushing in back the results in LIFO (Last in First Out) fashion. In a stack based virtual machine, the operation of adding two numbers would usually be carried out in the following manner (where 20, 7, and ‘result’ are the operands):

    stackAdd

    1. POP 20
    2. POP 7
    3. ADD 20, 7, result
    4. PUSH result

    Because of the PUSH and POP operations, four lines of instructions is needed to carry out an addition operation. An advantage of the stack based model is that the operands are addressed implicitly by the stack pointer (SP in above image). This means that the Virtual machine does not need to know the operand addresses explicitly, as calling the stack pointer will give (Pop) the next operand. In stack based VM’s, all the arithmetic and logic operations are carried out via Pushing and Popping the operands and results in the stack.

    Register Based Virtual Machines

    In the register based implementation of a virtual machine, the data structure where the operands are stored is based on the registers of the CPU. There is no PUSH or POP operations here, but the instructions need to contain the addresses (the registers) of the operands. That is, the operands for the instructions are explicitly addressed in the instruction, unlike the stack based model where we had a stack pointer to point to the operand. For example, if an addition operation is to be carried out in a register based virtual machine, the instruction would more or less be as follows:

    registerAdd

    1. ADD R1, R2, R3 ;        # Add contents of R1 and R2, store result in R3

    As I mentioned earlier, there is no POP or PUSH operations, so the instruction for adding is just one line. But unlike the stack, we need to explicitly mention the addresses of the operands as R1, R2, and R3. The advantage here is that the overhead of pushing to and popping from a stack is non-existent, and instructions in a register based VM execute faster within the instruction dispatch loop.

    Another advantage of the register based model is that it allows for some optimizations that cannot be done in the stack based approach. One such instance is when there are common sub expressions in the code, the register model can calculate it once and store the result in a register for future use when the sub expression comes up again, which reduces the cost of recalculating the expression.

    The problem with a register based model is that the average register instruction is larger than an average stack instruction, as we need to specify the operand addresses explicitly. Whereas the instructions for a stack machine is short due to the stack pointer, the respective register machine instructions need to contain operand locations, and results in larger register code compared to stack code.

    A great blog article I came across (At this link), contains an explanatory and simple C implementation of a register based virtual machine. If implementing virtual machines and interpreters is your main interest, the book by ANTLR creator Terrence Parr titled ‘Language Implementation Patterns: Create your own domain-specific and general programming languages’, might come in very handy.

    The DALVIK virtual machine

    The Dalvik virtual machine is implemented by Google for the Android OS, and functions as the Interpreter for Java code running on Android devices. It is a process virtual machine, whereby the the underlying Linux kernel of the Android OS spawns a new Dalvik VM instance for every process. Each process in Android has its own Dalvik VM instance. This reduces the chances of multi-application failure if one Dalvik VM crashes. Dalvik implements the register machine model, and unlike standard Java bytecode (which executes 8 bit stack instructions on the stack based JVM), uses a 16 bit instruction set.The registers are implemented in Dalvik as 4 bit fields.

    If we want to dive a bit deep into the internals of how each process gets an instance of the Dalvik VM, we have to go back to the beginning… back to where the Linux kernel of the Android OS boots up:

    androidBoot

    When the system boots up, the boot loader loads the kernel into memory and initializes system parameters. Soon after this,

    • The kernel runs the Init program, which is the parent process for all processes in the system.
    • The Init program starts system daemons and the very important ‘Zygote’ service.
    • The Zygote process creates a Dalvik instance which will be the parent Dalvik process for all Dalvik VM instances in the system.
    • The Zygote process also sets up a BSD read socket and listens for incoming requests.
    • When a new request for a Dalvik VM instance is received, the Zygote process forks the parent Dalvik VM process and sends the child process to the requesting application.

    This is in essence, how the Dalvik virtual machine is created and used in the Android system.

    Coming back to the topic of virtual machines, Dalvik differs from the Java virtual machine in that it executes Dalvik byte code, and not the traditional Java byte code. There is an intermediary step between the Java compiler and the Dalvik VM, that converts the Java byte code to Dalvik byte code, and this step is taken up by the DEX compiler. The difference between the JVM and Dalvik is depicted in the following diagram (Click here for image source):

    dalvikOperation

    The DEX compiler converts the java .class file into a .dex file, which is of less size and more optimized for the Dalvik VM.

    In Ending…

    There is no clear cut acceptance as to whether stack based virtual machines are better than register based implementations, or vice versa. This is still a subject of ongoing debate, and an interesting research area. There is an interesting research paper where the authors have re-implemented the traditional JVM as a register based VM, and recorded some significant performance gains. Hopefully, I have shown the reader the difference between stack and register based virtual machines, and also explained the Dalvik VM in some detail. Please feel free to provide your feedback or any questions you have regarding this article.

    Advertisements
     
    • Hariraju 4:59 PM on 11/09/2012 Permalink | Reply

      Awesome Article………really thank u a lot to share this wonderful article..

    • Isuru 4:16 PM on 19/09/2012 Permalink | Reply

      This is a good article.
      Good for everyone who like to find info about Dalvik VM

    • Nafz 12:06 PM on 25/09/2012 Permalink | Reply

      Very good article..
      Really Helped for my seminar

    • Chucherm 9:33 AM on 23/10/2012 Permalink | Reply

      Very good article, just what I was looking for

    • shubhm 10:07 AM on 23/11/2012 Permalink | Reply

      Like Einstein said “If u cant explain it simply, u didn’t understand it well enough”. Great article

      • Mark Sinnathamby 8:13 PM on 23/11/2012 Permalink | Reply

        Thanks 🙂 Indeed, Einstein said it best, and practiced it as well. Sometimes one can wonder how the theory of relativity can be understood so simply, while the world of software is made so complex 😉

    • Mallikarjuna Veerabommala 4:57 PM on 18/12/2012 Permalink | Reply

      Very good and detail info. In a Glance, Pictures narrates the whole thing.

    • Amit 7:47 PM on 19/01/2013 Permalink | Reply

      Thank you Mark. Was a great read.

    • Zenth 2:26 AM on 20/01/2013 Permalink | Reply

      Thank you for a nice article.
      One mistake: dex compiler converts .class file(s) to .dex file, not the .java file(s).

    • Tom 5:15 PM on 01/03/2013 Permalink | Reply

      Thanks you very much..
      Very nice artical and you have cleared my worng ideas about VMs.

    • Sandro 12:39 AM on 18/03/2013 Permalink | Reply

      Register-based VMs are well known to be superior in throughput. The paper you linked to was pretty definitive on that issue. Stack VMs are only slightly better in program size, and for simplicity of understanding.

      • krischik 7:48 PM on 30/04/2013 Permalink | Reply

        I rather think that the current VM designers make the mistake of using only single stack system.

        When I was young I used Forth which had a VM with two stacks. And it was blazingly fast.

        (If you read my posting below: the program counter is a register — one register + one stack is Turing complete as well)

    • jvishal 1:44 PM on 18/03/2013 Permalink | Reply

      Excellent article !!! thank you very much.

    • Brijendra 5:37 PM on 23/04/2013 Permalink | Reply

      Fabulous article……….

    • krischik 7:17 PM on 30/04/2013 Permalink | Reply

      Interesting. But you overlooked something: A true stack based CPU (virtual or hardware) needs at least TWO stacks. Just as register based CPU needs at least TWO register (program counter, stack counter and one data register would count as three).

      Without they can not be Turing complete.

      An example would be the VMs for the Forth programming language where a separate data and return stack is used.

      And once you have two stacks the the disadvantages you mentioned disappear.

      Also:

      LoadR1 20
      LoadR2 7
      Add R1,R2, R3
      StoreR3 result

      Are four statements as well.

      • minirop 5:04 AM on 05/10/2016 Permalink | Reply

        the “add” opcode of a stack-based VM has to pop both arguments, do the addition and push the result (4 operations) on the stack whilst the register-based doesn’t, and does the addition directly: R3 = R1 + R2

        • Martin Krischik 5:03 PM on 05/10/2016 Permalink

          And how does the data get into the register? And how does the result get out of the register? A register based CPU has a very limited amount of register. Currently somewhere between 8 and 16 so you frequently have to move data in and out.

          A stack, like the one used by the FORTH virtual machine can grow to size of main memory. Therefore you can just leave the results on the stack for far longer time to be used as input for the next operation.

          Most notably on a stack based CPU you can keep intermediate values on the stack while making a function call. You can’t do that on a register based CPU. Either the caller or the callee need to store and restore the registers somewhere. Usually on the stack. Because most (but not all) register based CPUs have a stack as well.

    • Abhi 1:46 PM on 08/05/2013 Permalink | Reply

      hi..Great article..
      But, speaking about the bytecode, which either machine executes, how are local variables represented.Are they compiled into addresses as actual machines need. or are they provided as an index into registers.For e.g., Parrot provides an arbitrary number of registers which is fixed at compile time per subroutine.

    • learntodesire43 6:11 PM on 15/06/2013 Permalink | Reply

      Its good article…

    • suresh 12:44 AM on 03/07/2013 Permalink | Reply

      Very good informative article …

    • alok 3:38 AM on 29/07/2013 Permalink | Reply

      Thanx to provide such a good information..:)

    • kostja 7:51 PM on 03/11/2013 Permalink | Reply

      Thank you for a nice article.
      I translated it into Russian

    • Eng Sultan 9:01 PM on 18/12/2013 Permalink | Reply

      Thanks for your great effort 😀

    • Baseer 8:27 PM on 04/05/2014 Permalink | Reply

      smoothly swallowed a mountain…! very well explained!

    • frodeborli 5:40 PM on 25/06/2014 Permalink | Reply

      This sounds incorrect. Pop would involve moving data from stack to a CPU register. The time for a pop should be equal to the time for copying a data by memory address. Further, I suspect that further optimizations can be made using a stack based VM rather than a register based vm, due to the fact that the data the operation is working on resides next to each other when using a stack. Finally, the stack is usually stored in the L1, L2 or L3 cache. There are no such guarantees with arbitrary addresses as operands.

      But I may be incorrect. But it seems weird that Microsoft and Sun chose “inferior” (according to this post it sounds obviously inferior) technology for something so central to their business.

      I think the reason Android uses a register based VM may be that it allowed them to reuse bigger parts of a compiler toolchain.

      Also, android is noticeably more sluggish on similar hardware than Windows Phones running .NET.

    • michalmynarski 4:57 AM on 26/06/2014 Permalink | Reply

      As someone noticed it above you forget about loading values to registers (f.e. mov) which makes register based vm demanding the same amount of steps to add two numbers.

    • prasadjachak 3:35 PM on 16/12/2015 Permalink | Reply

      This is very Complex topic..But explained it very simply and looks like normal to understand..Thank you…

    • Sam 9:59 AM on 19/05/2016 Permalink | Reply

      Why I see an exactly identical article here? That one is later than this post.
      http://www.codeproject.com/Articles/461052/Stack-based-vs-Register-based-Virtual-Machine-Arch

      • Mark Sinnathamby 1:25 AM on 03/06/2016 Permalink | Reply

        Hi Sam, what you are referring to is the same article, but (automatically) exposed to codeproject via a feed from my blog 🙂

    • Long Nguyen Vu 10:24 PM on 20/06/2016 Permalink | Reply

      Excellent writing. It helps a lot

      p/s just a very small typo in the word “deamons”, for the completeness!

    • Andrew Runner 8:10 PM on 07/08/2016 Permalink | Reply

      Really good article. And still great after 4 years!

    • Akbar 11:38 PM on 21/08/2016 Permalink | Reply

      Great Article..All clear..

    • the best 8:11 PM on 19/01/2017 Permalink | Reply

      thank very much…

    • Abhijit 4:12 PM on 19/03/2017 Permalink | Reply

      Very good explanation Mark. Thank you very much.

    • Roh 8:23 PM on 24/05/2017 Permalink | Reply

      Mark you have explained it in a lay man language with appropriate examples. This was really helpful. Thank you!

    • Ashokumar 11:17 PM on 20/06/2017 Permalink | Reply

      Very cool, thanks.

      Can I tell that Windows running c, c++ codes are the system based virtual machines whereas the JVM is process based ?

    • Faisal Nadeem 9:46 PM on 27/07/2017 Permalink | Reply

      great work

    • mohammad 2:05 PM on 07/10/2017 Permalink | Reply

      thanks alot
      very helpful

    • Thurupathan 9:09 PM on 16/04/2018 Permalink | Reply

      This is a great read and helped recently while reading about web assembly. Good to see such an old post and being useful and always will be. Thanks

    • Mahdi 1:04 PM on 17/06/2018 Permalink | Reply

      a concise read. thanks!

    • keroroxx520 8:32 AM on 12/10/2018 Permalink | Reply

      Awesome! Thanks for your simple explanation, like your summarization of several concepts which VM must be included (compilation, stack&IP, virtual CPU, executes). And the reference articles are great too.

  • Mark Sinnathamby 2:13 PM on 13/02/2011 Permalink | Reply  

    Thoughts on the Microsoft-Nokia Collaboration 

    Microsoft and Nokia have announced a partnership last Friday (11th Feb 2011) stating that Windows phone will be the OS for Nokia smart phones, leveraging each others complementary innovations. Going through the literature on the web, this announcement has invoked mixed reactions from various parties. My take on this matter is an objective look at what changes can be expected of this collaboration and what impacts they may have, gathered from the information that is currently available.

    Firstly, the announcement is not the death spell for Symbian and Meego. The Symbian platform which is open source will be available at the symbian blog via FTP till March of this month. Nokia is committed to the development and evolution of the platform, although it is not clear how this will take place in the future. Meego is stated to be offered as an open source mobile platform in the future. Nokia expects to sell around 150 million Symbian devices in the next few years, and will be producing Meego devices till the end of this year after which it will transform into an experimental platform for research.

    That being said, it is not clear what the real forecast is for Symbian and Meego is. Nokia has stated that Symbian will be a franchise platform, but it has been degrading in a low curve for some time now and it is hard to envision getting the boost from Nokia in the years to come. Meego could fare better as a test bed for research and innovation, and being open source, anything could happen.

    Looking to the future where Nokia smartphones will be running the windows phone platform, there is a huge impact in the mobile, business and software development circles. The windows phone OS will be running on the top selling handset device globally, virtually overnight. Developers would spring to the opportunity provided by the platform explosion in scale. Businesses and end users could be targeted with the synergy of Nokia and Microsoft innovations. In an open letter by the CEO’s of Microsoft and Nokia, the decisions and changes to take place are stated, and it is interesting to note that many deal with the integration of the technical innovations of both parties to a large extent. This would open up avenues in the current market by leveraging developers to innovate and develop in quality and quantity, and by having the vast array of Microsoft services at the fingertips of a Nokia user base, not to mention cloud capabilities.

    What seems to be an unexpected decision could very well be what is needed to turn the tables. Apple and Google will most certainly not be sitting around and observe proceedings. In my view, the partnership between Microsoft and Nokia and the expected outcome would boil down to a few questions:

    • What will the collaboration offer to end users, in terms of smartphone capability and visual appeal?
    • What will be the reception of the Windows, Symbian and other developer communities?
    • What will be catered to the existing Nokia customers and how will they respond?
    • How can Microsoft and Nokia collaborate and address the above points to the best positive effect?

    It would be interesting to observe how the other players in the market respond to the ‘best of both worlds’ approach by the Microsoft-Nokia partnership. This is my perspective of last Friday’s announcement in a nutshell and I welcome your thoughts and suggestions on the turn of events.

     
    • Hasith 10:39 AM on 17/02/2011 Permalink | Reply

      With Symbian Foundation transforming to a licensing entity, they have handed over the Symbian development back to Nokia. It is interested to see Nokia getting in to Windows platform while committing to further develop ‘dying’ platform of Symbian.In my opinion, this partnership orders the last nail for Symbian coffin signalling other partners such as NTT DOCOMO to think again on their Symbian dependency.

      • markfaction 8:49 PM on 17/02/2011 Permalink | Reply

        Agreed 🙂 Symbian won’t be an optimistic prospect for many people in the future, unless of course something radical happens. barring that, there’s a feeling that Nokia’s commitment to Symbian development would be to turn it into an ‘experimental platform for research’ in a few years time 😉

        • Hasith 9:25 PM on 17/02/2011 Permalink

          I wouldn’t bet on doing my next research on a dying platform unless it is a historical research :D.

    • Clement 1:05 PM on 08/05/2011 Permalink | Reply

      I just bought the C7 cell using symbian os. Will Nokia upgrade my C7 to run on windows mobile?

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel