91–100 of 154 posts
Also: a software rasterizer. Most people refuse to write one because it's so easy not to. Why bother? It will make you a better coder for the rest of your life. Let's make a list of "power projects" like this. A bytecode interpreter, a software rasterizer... What else?
Earlier quoted context omitted.
According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and diffic…
I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck. That's why they are working on incremental compilation to improve compilation times. They detect changes in the input files by comparing the AST to the old version. So parsing is always necessary but later stages can be cached. That seems…
Possible with rust that moves a bunch of the grant work into the code generator. AKA where as in C/C++ by the time you're generating code all your type information is set in stone, possible in rust a bunch of stuff isn't resolved yet.
Earlier quoted context omitted.
> But I can't imagine a lexer would ever be the performance bottleneck in a compiler. one rather trivial way to observe the effects of avoiding building a source file is to use ccache. ccache avoids the recompilation (even if you do a make clean, or some such), and it is not uncommon to observe speed ups of factor of 5 or so. however, once you have crossed that barrier, you hit the linking wall. which is where you wo…
No chance, modern compilers spend most of their time in the optimization stages. Lexing is peanuts.
ORG START
START: ST_B 10
LOOP: ST_B 10
ADD_B ;;value will go back on stack
LD_B V1
SM_B V1 ;;value we use next loop
SM_B V1 ;;value we compare
SM_B V1 ;;value we echo to console
TRP 21 ;;writes to the console
ST_S '',13,10,$
TRP 21 ;;writes to the console
CMP_B 50 ;;compares stack to the constant
JNE LOOP
ST_S 'The End',13,10,$
TRP 21 ;;writes to the console
END
Earlier quoted context omitted.
The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.
It is rare for lexers to use actual regex engines, in my experience, as it's impractical if you want to do proper error reporting unless you write your own regex engine in which case people tend to opt for hand-writing lexer rules. It's not unheard of , and I have the impression it's getting more common, but still only a small proportion of the compilers I've seen over the years explicitly use regexps.
I saw the matrix after I first implemented a virtual machine. I recommend everyone does it because it will teach you a lot about how code is executed and transformed from the syntax to the actual assembly/bytecode. A stack based virtual machine is so simple it takes a lot of thinking to understand how they work. (or maybe I'm just not that smart). It's interesting that he implemented function calls via a jump. In my…
Earlier quoted context omitted.
It is rare for lexers to use actual regex engines, in my experience, as it's impractical if you want to do proper error reporting unless you write your own regex engine in which case people tend to opt for hand-writing lexer rules. It's not unheard of , and I have the impression it's getting more common, but still only a small proportion of the compilers I've seen over the years explicitly use regexps.
So, what parses the regex in the lex, flex, Jison, etc...
Also: a software rasterizer. Most people refuse to write one because it's so easy not to. Why bother? It will make you a better coder for the rest of your life. Let's make a list of "power projects" like this. A bytecode interpreter, a software rasterizer... What else?
* Implementing Internet protocols (TCP, IP, SMTP etc) * Floating point manipulation and numerical computation * Rolling some own crypto (strictly for fun use)
With proper test vectors and some code review, crypto is in fact quite easy. More dangers lie un the use of crypto, especially when the API is flexible or complex. And of course good old exploitable bugs.
Two approaches are severely underused in the software world: 1) Domain-specific languages (DSLs) 2) Virtual machines (or just explicit state machines more generally) What I mean is, alot of problems could be solved cleanly, elegantly, more safely, and more powerfully by using one (or both) of the above. The problem is that when people think DSL or VM, they think big (Scheme or JVM) instead of thinking small (printf).…
Earlier quoted context omitted.
Interesting. One thing that I still haven't solved yet is the "break" and "continue" statement inside loops. For a break statement, it seems like it would just be the same a JMP with an address as the operand, but there would need to be some sort of registration of "The VM is in the loop now, and the break address is X", and continue would also be a JMP with an address to the top of the code for the loop. I haven't i…
You can implement those as part of a linking phase during bytecode generation: emit a placeholder value (e.g. 0) for the jump address and when you've finished compiling the block go back and fill-in the placeholder with the correct address/offset. That's relatively easy when implementing an assembler for your opcodes. Just keep track of symbolic labels and their associated jump points (as a simple array or linked lis…
It all depends how your interpreter PC (program counter) works. Some have just opcode offsets (like a real PC, as %eip, e.g. lua, ruby, ..) some have opcode addresses (perl, lisp, ...).
With offsets you can encode jumps relative, which is a huge advantage. With addresses you have to remain absolute, which means the data needs a full pointer (cache), and you cannot move the code around for optimizations afterwards. With offsets you have a cache-friendly op-array, with addresses you have a fullblown tree (AST) or linked list, with its cache-unfriendly pointer chasing overhead.
But with full addresses you can avoid the big switch loop overhead in an interpreter, you just pass around the next pointer instead if incrementing the PC. But then it gets interesting how to keep the state of the stack depth.