24 ms·

I find stack based assembly easier to understand over register based assembly. I read this article recently: https://www.mattkeeter.com/blog/2022-10-04-ssra/ h

I find stack based assembly easier to understand over register based assembly. I read this article recently: https://www.mattkeeter.com/blog/2022-10-04-ssra/ https://www.mattkeeter.com/blog/2022-10-04-ssra/ It's regarding register allocation. According to comments on the HN post for it, it uses the same algorithm that Luajit uses. It uses a technique by searching backwards through the code to work out whether it needs to spill a register from memory or to memory. I haven't written a bytecode interpreter or a compiler but I wrote a parallel interpreter that is multithreaded. Its code is plaintext so it's not particularly fast but is built with an actor implementation and can send and receive integers between threads. If it supported objects and network requests, it could be useful. I am yet to implement any stack based operations but I have an idea for an object oriented design similar to Java JVM specification. Here's the assembly. Colons indicate labels. addv adds values to variables. add adds two variables. send sends messages to a thread number. receive receives a message. The send and receive commands jump to the label indicated if there is no messages. threads 25 <start> set running 1 set current_thread 0 set received_value 0 set current 1 set increment 1 :while1 while running :end receive received_value :send :send add received_value current addv current_thread 1 modulo current_thread 25 send current_thread increment :while1 endwhile :while1 :end This program gets between 1.5-65 million messages per second. If the data was larger, you could send arbitrary sized objects between threads in constant time so this rate shouldn't change but it doesn't support objects yet. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro...

Joker_vD 4y ago
What a weird article. The author essentially compiles a huge expression made up entirely of function calls (with opaque definitions, so no inlining opportunities) and zero primitive operations like addition or indexing — compiler writers don't, as a rule, push their effort into optimizing such kinds of workloads. They are much more interested in spending effort on optimizing expressions that involve arithmetic/string operations and indexing of arrays, in inner loops, because that's where most common programs spend their time in. Also, counting the number of load/stores is useful, but why not run the resulting binary programs and measure actual run times? Compilation times are important, of course, but run times are more important: most computer users are not programmers, they run precompiled binaries, so for them compilation times don't matter. And a note about the algorithm itself. If you're not in a JIT scenario and can afford to spend a couple of millseconds, you can determine optimal variables to spillusing ILP and then allocate registers using "optimistic coalescing", see [0]. Of course, on a RISC machine with lots of registers you can, most of the time, on usual workloads, pretty much ignore the problem of spilling. And if you are in a JIT scenario and need very fast register allocator but don't care that much about the efficiency of the produced code... you can use whatever algorithm Wirth have been using in his compilers since the 70-ies: [1], "10. Expressions and Assignments". [0] Andrew W. Appel, Lal George. Optimal Spilling for CISC Machines with Few Registers. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.8264&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92... [1] Niclaus Wirth. Compiler Construction. https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction2.pdf https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil...

Joker_vD 4y ago

What a weird article. The author essentially compiles a huge expression made up entirely of function calls (with opaque definitions, so no inlining opportunities) and zero primitive operations like addition or indexing — compiler writers don't, as a rule, push their effort into optimizing such kinds of workloads. They are much more interested in spending effort on optimizing expressions that involve arithmetic/string operations and indexing of arrays, in inner loops, because that's where most common programs spend their time in. Also, counting the number of load/stores is useful, but why not run the resulting binary programs and measure actual run times? Compilation times are important, of course, but run times are more important: most computer users are not programmers, they run precompiled binaries, so for them compilation times don't matter. And a note about the algorithm itself. If you're not in a JIT scenario and can afford to spend a couple of millseconds, you can determine optimal variables to spillusing ILP and then allocate registers using "optimistic coalescing", see [0]. Of course, on a RISC machine with lots of registers you can, most of the time, on usual workloads, pretty much ignore the problem of spilling. And if you are in a JIT scenario and need very fast register allocator but don't care that much about the efficiency of the produced code... you can use whatever algorithm Wirth have been using in his compilers since the 70-ies: [1], "10. Expressions and Assignments". [0] Andrew W. Appel, Lal George. Optimal Spilling for CISC Machines with Few Registers. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.8264&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92... [1] Niclaus Wirth. Compiler Construction. https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction2.pdf https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil...