11 ms·
Why SQLite Uses Bytecode
- chrisaycock 3y agoSQLite's design docs were the first time I had seen a database use a virtual machine instead of walking a tree. I later noticed VMs in libraries, embedded DSLs, and other applications outside of large general-purpose programming languages. That really drove home for me that VMs could be anywhere and were often a useful step in handling a user's expressions.
- runlaszlorun 3y agoSQLite is the first one I’ve looked at the internals of. Do others walk an AST of the query instead?
- __s 3y agoYes, postgres for example. It maps pretty close to what you see from `explain` where the ops are pretty high level, reducing interpreter overhead. JIT's big gain is speeding up reading values out of row data
- hn_throwaway_99 3y agoFTA: > Tree-Of-Objects → The input SQL is translated in a tree of objects that represent the processing to be done. The SQL is executed by walking this tree. This is the technique used by MySQL and PostgreSQL.
- Sesse__ 3y agoNote that this only holds true for fairly recent MySQL (MySQL 8.x, not including the oldest 8.0.x releases). 5.7 and older, and by extension MariaDB, instead models pretty much everything as a large fixed-function recursive function that calls itself for each new table in the join, plus some function pointers for handling of GROUP BY and such. TBH, when it comes to query execution (A JOIN B JOIN C GROUP BY …), I think the difference between SQLite's bytecode and a tree of iterators (the classical Volcano executor) is fairly small in practice; they are quite interchangeable in terms of what they can do, and similar when it comes to performance. The difference between bytecode and tree structure is much larger when it comes to evaluation of individual expressions (a + b * cos(c)), especially since that involves much more of a type system; that is more obviously in the “bytecode is the way to go” camp to me.
- runlaszlorun 3y agoSorry, I’d read the article a couple years ago and forgot he goes into depth on the other approaches. My bad.
- whateveracct 3y agoEverything is either a compiler or interpreter
- Zambyte 3y agoThat's why SICP is often brought up in contexts that are not explicitly about interpreters :)
- bane 3y agoVMs really can be. They have a long history in code portability. In the old days it really wasn't uncommon to use an approach centered around some interpretable byte code running in a vm, where the reusable vm was all that needed porting to different architectures and operating systems. This all happened well before Java. It was really big in gaming, Zork, Sierra games, LucasArts games, and even a few more "action" games like Flashback were all designed around VMs to make porting somewhat sane. Running the byte code is usually not the performance bottleneck in these cases but drawing stuff to the screen is, and the VM had to handle that.
- runlaszlorun 3y agoAnd Pascal p-code! Not the first, I’ve heard, but I believe it’s close to being the first.
- pjmlp 3y agoOne of the first was Burroughs B5000, https://en.wikipedia.org/wiki/Burroughs_Large_Systems https://en.wikipedia.org/wiki/Burroughs_Large_Systems It used an almost memory safe systems language, ESPOL, zero Assembly, all CPU capabilities are exposed via intrisics, one of the first recoded uses of unsafe code blocks, there was tagging and capabilities support, the CPUs were microcoded. All of this in 1961, a decade before C came to be. ESPOL was quickly replaced by NEWP, although there are very little data when it happened, probly a couple of years later. Nowadays it is still sold by Unisys under the guise of being a mainframe system for those that value security above all, as ClearPath MCP, and you can get NEWP manual. https://www.unisys.com/solutions/enterprise-computing/clearpath-forward/ https://www.unisys.com/solutions/enterprise-computing/clearp... https://public.support.unisys.com/aseries/docs/ClearPath-MCP-18.0/86002003-408.pdf https://public.support.unisys.com/aseries/docs/ClearPath-MCP...
- kragen 3y agothe b5000 was one of the first non-virtual stack machines, but its instruction set isn't any more of a virtual machine than the 8088's or the pdp-10's. there were a number of interpreted stack languages in the 50s, though not nearly as many as there would be later
- hiAndrewQuinn 3y agoVMs are a persistently underrated tool by people who think the conversation begins and ends at VirtualBox. They are a phenomenal way to constrain the surface area of what one's own code has to target, and that's always a plus.
- kqr 3y agoOr indeed any time complexity need to be layered. A VM design doesn't even have to have an explicit bytecode compilation stage -- you can write an interpreter that runs as the instructions are issued. David Parnas talks a lot about this as a way to reliable modularisation: https://two-wrongs.com/deliberate-abstraction.html https://two-wrongs.com/deliberate-abstraction.html
- anon291 3y agoStack-based VMs, like SQLite's (I think), ARE trees. A stack based VM's bytecode (without DUP and POP) is just the post-order depth-first traversal of the corresponding expression tree. With DUP you have a connected acyclic DAG. With POP you have an acyclic DAG with one or more components. With loops you have a full graph. When looked at this way, a VM makes the most sense actually because a pointer-heavy tree implementation is just terrible for caching and is super wasteful. Also, most SQL plans are trees (Until you get to WITH RECURSIVE). I'm working on a CEP in C right now and a stack-based bytecode is simply the most 'obvious' way to represent a tree when you don't want to have to deal with lots of memory allocations. Just pre-allocate a buffer large enough and increment and go. Either way, try taking something like the following and printing an expression tree like the one below LITERAL 2 LITERAL 3 LITERAL 4 MUL PLUS now, write something to produce on a terminal, the following: Plus Mul 3 4 2 You should be able to do this in a simple iteration through the ops. Try it! Then try it with the variations above. Now, try writing ops to manipulate and rewrite it. It's actually really a fun way to represent trees.
- Scaevolus 3y agoSQLite's VM is register-based, not stack-based.
- ojosilva 3y agoDoes SQLite's VM have an API? I mean, one where I can build and issue opcodes into directly.
- OskarS 3y agoNot a public one, because they want to have the freedom to change how it works. But if you type in `EXPLAIN CREATE TABLE x(y);` or `EXPLAIN SELECT 3;` or whatever into `sqlite3`, you can see it. And it's reasonably straightforward to dig into the source code (SQLite is very well-written C) to hook that up yourself if you really wanted to.
- bch 3y ago
- surfingdino 3y agoDoesn't MS Word internally run a Forth-like VM? I remember reading an article by someone who decompiled an early MS-DOS version of Word only to discover that there was a VM inside.
- jpfr 3y agoThey called it p-code at the time. The purpose was (purported) to simplify the porting between architectures. https://casadevall.pro/articles/2020/11/compiling-word-for-windows-from-os/2-1.2/ https://casadevall.pro/articles/2020/11/compiling-word-for-w...
- canucker2016 3y agofrom http://www.trs-80.org/multiplan/ http://www.trs-80.org/multiplan/ "Originally code-named “EP” (for “Electronic Paper”), Multiplan was written to use a very clever p-code compiler system created by Richard Brodie. This p-code system, which was also used later by Microsoft Word, allowed Microsoft to target Multiplan to a huge number of different 8-bit and 16-bit computer systems. (Charles Simonyi once estimated that Multiplan was available for 100 platforms.)" Many people say that the 'p' in 'p-code' stands for 'pseudo', i.e. pseudo code. But the article archived at https://techshelps.github.io/MSDN/BACKGRND/html/msdn_c7pcode2.htm https://techshelps.github.io/MSDN/BACKGRND/html/msdn_c7pcode... says the 'p' is short for 'packed'. "Microsoft has introduced a code compression technology in its C/C++ Development System for Windows version 7.0 (C/C++ 7.0) called p-code (short for packed code) that provides programmers with a flexible and easy-to-implement solution for minimizing an application's memory requirements. In most cases, p-code can reduce the size of an executable file by about 40 percent. For example, the Windows Project Manager version 1.0 (resource files not included) shrinks from 932K (C/C ++ 7.0 with size optimizations turned on) to 556K when p-code is employed." "Until now, p-code has been a proprietary technology developed by the applications group at Microsoft and used on a variety of internal projects. The retail releases of Microsoft Excel, Word, PowerPoint�, and other applications employ this technology to provide extensive breadth of functionality without consuming inordinate amounts of memory."
- bitwize 3y agoWozniak found that 16-bit arithmetic was much easier to perform on a 16-bit machine. So he wrote SWEET16, a VM with its own bytecode, to work with 16-bit pointers in Apple's Integer BASIC. Similarly, the TI-99/4 series of computers had a cumbersome way of accessing memory, because most of the RAM in the machine was exclusively controlled by the video chip and could only be accessed by poking a few registers. So the designers implemented a bytecode VM in ROM called GPL (Graphics Programming Language) that would make accesses to this video RAM seem like straightforward RAM accesses. TI encouraged the use of GPL to develop games and other applications for the system. Unfortunately, the fact that it was interpreted by the CPU, plus the fact that the CPU could only access video-chip memory during the horizontal and vertical retrace intervals, made GPL execution very slow. And since the machine's in-ROM BASIC interpreter was written in GPL, you now know why BASIC programs on the TI-99/4 and /4A crept along at the most leisurely of paces. So VMs were definitely a thing used to make certain kinds of tradeoffs, even way back in the 8-bit days when systems had mere kilobytes of memory. Who knows how many might be lurking in a modern system!
- krallja 3y agoThe unfortunate history of SWEET16 is that it was never used for its intended purpose - https://retrocomputing.stackexchange.com/a/14513/11579 https://retrocomputing.stackexchange.com/a/14513/11579
- naasking 3y ago> That really drove home for me that VMs could be anywhere and were often a useful step in handling a user's expressions. I think it's a special case of the fact that finite state machines are everywhere you look.
- atombender 3y agoMonetDB is another database that uses a VM [1], using an instruction set called the MonetDB Assembly Language (MAL). I believe it pioneered the technique [2]. The VM is basically designed to express the query as vectorized functions on columns. [1] https://stratos.seas.harvard.edu/files/MonetDebull2012.pdf https://stratos.seas.harvard.edu/files/MonetDebull2012.pdf [2] https://www.researchgate.net/publication/220538804_Database_Architecture_Evolution_Mammals_Flourished_long_before_Dinosaurs_became_Extinct https://www.researchgate.net/publication/220538804_Database_...
- lovich 3y ago[flagged]
- deleted 3y ago[deleted]
- userbinator 3y agoThe problem of rendering a tree-of-objects as a table is sufficiently difficult that nobody does it, as far as I know. Hence, no tree-of-objects database engine provides the level of detail in their "EXPLAIN" output that SQLite provides. I believe Microsoft SQL Server uses an object tree internally, and yet its query plan output is a table: https://learn.microsoft.com/en-us/sql/t-sql/statements/set-showplan-all-transact-sql https://learn.microsoft.com/en-us/sql/t-sql/statements/set-s...
- jiggawatts 3y agoTypically you get XML for showplan because it can represent the tree structure better.
- kruador 3y agoYou get XML for estimated execution plans if you use SET SHOWPLAN_XML ON. You get the actual execution plan XML along with your results if you use SET STATISTICS XML. You can see cached execution plans in the sys.dm_exec_query_plan dynamic management view. The estimated/actual execution plan feature in SQL Server Management Studio was changed to use XML in SQL Server 2005. The SQL Server team are only adding new information to the XML representation, not the text representation. The name "estimated" execution plan is a bit misleading. If you executed the statement(s) with the current indexes and statistics, that's how it would be executed. I think the "estimated" part of the name is because the number of rows returned from each node, and the execution time of each node, is an estimate. Assuming that the indexes and statistics don't change, you should expect the "actual" execution plan to have the same shape. It will just be annotated with the number of rows that were actually retrieved as well as the estimated numbers. SQL Server doesn't re-plan if it turns out the number of rows was greater (or fewer) than expected. As a SQLite and SQL Server user, I find that I would like something more detailed from SQLite than EXPLAIN QUERY PLAN (which just tells you the join order), but less detailed than the bytecode. Particularly I want to know why it chose that join order or to use that index.
- yread 3y ago
- darlingdem 3y ago[dead]
- Dwedit 3y agoRunning bytecode is much lower latency than compiling into native code. If you're not bottlenecked by running the bytecode (as opposed to memory or disk speed), you don't really have to JIT it any further into native code.
- winrid 3y agoYeah, but nobody is seriously considering that unless maybe for huge prepared statements. The argument is usually bytecode vs parser and associated data structures.
- _flux 3y agoPostgreSQL is not only considering it, they're doing it! https://www.postgresql.org/docs/current/jit-reason.html https://www.postgresql.org/docs/current/jit-reason.html I don't have personal experience on it, but I've read that in practice it's not worth the effort—at least not yet. Apparently there are some issues with it and it barely speeds up queries (except perhaps certain ones?). I imagine this could be in big part because LLVM is not really a good fit for JIT where you want to spend very little time to do the compilation itself.
- masklinn 3y agoYeah my experience of the pg jit is mostly negative, it’s quite slow and it has a hard time estimating the cost of interpreted v compilation + compiled execution so more often than not it’s actively detrimental. It might fare better if you make heavy use of a limited number of prepared statements.
- winrid 3y agoInteresting, thanks. I imagine they will have a query planner for the query planner to determine to JIT or not :)
- rhdunn 3y agoWhich is why JavaScript engines (and JIT compilers for other languages) are typically designed to: 1. start interpreting the code once it has been parsed, and start jitting a function being called; 2. generate naive bytecode for the function that generates native code equivalents of the run actions of the AST (including some fast-path code for simple cases such as adding two 32-bit integers, and falling back to function calls to perform the add on more complex types); 3. generate more optimal code for sequences of instructions in the background, such as entire for/while loops, then patch in calls to those fast-path versions when ready. That way you can start running the code immediately after parsing it, and can switch to the faster versions when they are ready if the code takes longer to run in the slower version.
- MrBuddyCasino 3y agoI was surprised the text didn’t mention one major difference between the byte code approach vs AST: coupling. When your database engine runs in-process, there is no possibility of the server and the client library having diverging versions. But this is common with traditional databases. Once you bake in the execution steps („how to execute“) instead of describing the query via AST („what to execute“), an important part of the execution logic now lives in the driver. I suspect this complicates version upgrades and bugfixes, because the database is less self-contained. Not an issue for sqlite, potentially disastrous for mysql.
- tadfisher 3y agoDo clients typically communicate with the server in some AST representation instead of, well, SQL? I'd be surprised if that much parsing/planning happens on the client.
- MrBuddyCasino 3y agoSince prepared statements are created by the driver, I was assuming this was the case - but I might be completely wrong here.
- _flux 3y agoConverting a SELECT to a PRPEPARE does not really require parsing the complete query—or even it it did, some small concessions for this could be implemented in the line protocol to enable the server to do the prepared statement out of client query. I don't believe *any* SQL client library actually tries to parse e.g. PostgreSQL itself at any point of processing. You can read what the PostgreSQL protocol does here: https://www.postgresql.org/docs/current/protocol-flow.html#PROTOCOL-FLOW-SIMPLE-QUERY https://www.postgresql.org/docs/current/protocol-flow.html#P...
- layer8 3y agoNo, prepared statements are server-side.
- 3y ago
- megadal 3y agoPerhaps my understanding is off, but I am pretty sure parsing and translating SQL into bytecode still involves an AST. Just that query processing itself is done from the bytecode (produced presumably from an AST or something similar) rather than directly from the AST itself. If I'm right I can't really see how this performs better unless you're excluding the parsing step from benchmarks
- forgotmypw100 3y agoI asked on the mailing list years ago if there was an AST that I could generate from my general purpose language, and the answer was no. It's SQL and then it's bytecode.
- lifthrasiir 3y agoYou don't need one, Lua is another example where no AST is ever generated. In some sense the resulting bytecode closely corresponds to the AST that would have been generated though.
- megadal 3y agoGenuinely asking as parsing without an AST is something I've never seen explained: How do you go from source code to bytecode without an AST? Isn't the bytecode just a flattened representation of an AST obtained by some sort of tree traversal? This seems to imply an AST is involved in the generation of the bytecode
- lifthrasiir 3y agoHave you used any parser generator like yacc/bison? They have "actions", which are arbitrary codes that will be executed when some grammar production is detected. For example, `expr ::= expr mulop expr { some code }` will execute `some code` when a multiplicative expression is detected, where intermediate results from two `expr`s and `mulop` are available to that code. This concept of actions generally applies to all sort of parsers, not just generated parsers. Those actions would typically allocate and build (partial) ASTs, but you can do anything with them. You can for example directly evaluate the subexpression if your grammar is simple enough. Likewise bytecodes can be generated on the fly; the only concern here is a backward reference, which has to be patched after the whole expression block gets generated, but otherwise you don't have to build any tree-like structure here. (Most practical parsers only need a stack to function.)
- wolf550e 3y agoThe page is the result of this exchange on Twitter: https://twitter.com/gorilla0513/status/1784756577465200740 https://twitter.com/gorilla0513/status/1784756577465200740 I was surprised to receive a reply from you, the author. Thank you :) Since I'm a novice with both compilers and databases, could you tell me what the advantages and disadvantages are of using a VM with SQLite? https://twitter.com/DRichardHipp/status/1784783482788413491 https://twitter.com/DRichardHipp/status/1784783482788413491 It is difficult to summarize the advantages and disadvantages of byte-code versus AST for SQL in a tweet. I need to write a new page on this topic for the SQLite documentation. Please remind me if something does not appear in about a week.
- paulddraper 3y agoThere are three approaches: 1. interpreted code 2. compiled then interpreted bytecode 3. compiled machine code The further up, the simpler. The further down, the faster.
- branko_d 3y ago> 2. compiled then interpreted bytecode You can also compile to bytecode (when building), and then compile that bytecode to the machine code (when running). That way, you can take advantage of the exact processor that is running your program. This is the approach taken by .NET and Java, and I presume most other runtime environments that use bytecode.
- alex_smart 3y agoI recently implemented my own expression evaluator in java for in-memory data frames, and once you think about doing that deeply, you very quickly understand the need for bytecode. If you directly evaluate the expression using a tree representation, you basically have to do a whole lot of branching (either via switch statements or polymorphism) for every single line of useful operation. Yes, the branch predictor kicks in and it means that your code wouldn’t be as slow as if it didn’t, but it is still measurably slower than if you converted the expression into bytecode once and just ran that on all rows instead.
- eklavya 3y agoBytecode will only impact packing, so more efficient ram, cache and cpu wise. But I don't understand how it would help with branching? You still have to make the same decisions? As in the bytecode executor still needs to do differnt things based on the op code, its not in hardware.
- hickelpickle 3y agoThere is threaded bytecode as well, which uses direct jumping vs a switch for dispatch. This can improve branch prediction, though it is a debated topic and may not offer much improvement for modern processors.
- immibis 3y agoHow does it know where to jump to?
- deleted 3y ago[deleted]
- chuckadams 3y agoThe jump target is compiled into the bytecode, so rather than return to the big switch statement, it jumps straight to the next opcode's implementation. The process is called "direct threading". These days a decent switch-based interpreter should fit in cache, so I'm not sure direct threading is much of a win anymore.
- adontz 3y agoLooks like SQLite could benefit from copy-and-patch JIT compiler.
- Someone 3y agoI think that would make it cross a border where ‘Lite’ no longer applies. It also would be quite a challenge given their long-term-support statement (https://www.sqlite.org/lts.html https://www.sqlite.org/lts.html): “Cross-platform Code → SQLite runs on any platform with an 8-bit byte, two's complement 32-bit and 64-bit integers, and a C compiler. It is actively tested on all currently popular CPUs and operating systems. The extreme portability of the SQLite code and file format will help it remain viable on future platforms.”
- adontz 3y agoThere is no implied requirement to support JIT everywhere.
- samatman 3y agoI think this is unlikely for SQLite (other comments cover why it probably wouldn't happen even if it were likely to benefit), but I happened to have the copy and patch paper open in a tab, so I'll take the opportunity to share it here. https://sillycross.github.io/assets/copy-and-patch.pdf https://sillycross.github.io/assets/copy-and-patch.pdf It has great potential for many applications, if not this particular one.
- bambax 3y agoTypo: A prepared statement is an object that represents the steps needed [to] accomplish the input SQL.
- sgbeal 3y agoFixed, thank you for the report. It won't be visible on the site until the next time it's rebuilt.
- jiehong 3y agoSQLite EXPLAIN plan is indeed represented as a table, but I don’t find it necessarily that much easier to read and understand. I often miss having the cardinality and the amount of bytes read for each part of the query like Oracle query plans provide. Or is everyone really that happy with SQLite query plans?
- bvrmn 3y agoThere is EXPLAIN QUERY PLAN which outputs usual high level plan description. But there is no easily reached disk/cache usage stats.
- manx 3y agoI'm wondering if one could write this bytecode directly (or with a higher level imperative language) instead of SQL. Often, the programmer knows exactly which index lookups need to happen in a loop, while it seems like a burden to express that in SQL. This might also be an opportunity to create a different type safe dsl for database access.
- thayne 3y agoI was wondering the same thing. And in particular if a new query language that avoided many of the pitfalls of SQL could compile down to that bytecode and avoid having to deal with SQL as an intermediate representation. Also, if you can compile to bytecode ahead of time, then that could save the time needed to parse the text of a sql query to bytecode at runtime.
- nraynaud 3y agoI'm puttig my wish list here: - be able to put the projection in a varable and reuse it (and I think orm people might love it) - have a quick way to forward the the non-aggregated fields of projection to a group by (maybe with the aforementionned variables)
- TachyonicBytes 3y agoThe DuckDB API I was talking above seem to already meet your use-cases? - Does this[1] solve the group by wish? - Depending on what you mean by projection, maybe this[2] or this[3]? [1] https://duckdb.org/docs/api/python/relational_api#aggregateexpr-groups-- https://duckdb.org/docs/api/python/relational_api#aggregatee... [2] https://duckdb.org/docs/api/python/relational_api#projectexpr https://duckdb.org/docs/api/python/relational_api#projectexp... [3] https://duckdb.org/docs/api/python/expression#column-expression https://duckdb.org/docs/api/python/expression#column-express...
- nraynaud 3y agothat's really great!
- Retr0id 3y ago> Hence, no tree-of-objects database engine provides the level of detail in their "EXPLAIN" output that SQLite provides. I've seen some cool graphical visualisation tools for postgres http://tatiyants.com/postgres-query-plan-visualization/ http://tatiyants.com/postgres-query-plan-visualization/
- chucke1992 3y agoWell SQLite is basically a religious cult at this point. I am always impressed by it.
- euroderf 3y agoDoesn't the Go language also execute bytecode ? There's gotta be a hyperefficient hybrid lurking in there somewhere.
- zadokshi 3y agogo compiles to binary files and libraries. it’s more like c than Java
- euroderf 3y agoBut it has an intermediate stage of "Go assembler", which is what I misremembered.
- euroderf 3y agoAah OK my bad. https://github.com/teh-cmc/go-internals/blob/master/chapter1_assembly_primer/README.md#pseudo-assembly https://github.com/teh-cmc/go-internals/blob/master/chapter1...
- matharmin 3y agoWhat I find interesting is that this approach means the query plan is chosen when "compiling" the statement, not when running it. However, there are still some cases where SQLite will recompile the statement when running, such as when the schema changed.
- groue 3y agoOut of curiosity, I asked on the SQLite forum how the query optimizer fits in this schema: https://sqlite.org/forum/forumpost/93f9bfcec0 https://sqlite.org/forum/forumpost/93f9bfcec0
- carterschonwald 3y agoSo one thing that’s not often talked about is that with the right invariants/program transformations, the two approaches are equivalent :)
- zoomablemind 3y agoHow does this reflect on SQLite's possibilty of parallelizing some of the operations, like aggregates, for example?
- Ericson2314 3y agoAt the bottom, it it says that is a downside
- dittonedo 3y agoI just wonder why can't hackers write homoiconic (if thats the word), languages that get array tokens and provide results like so. I often wonder what if sqlite was also designed to have its statements like ('select '* 'from 'table), it would also had been better for third part libraries, to implement their orms. Since all of this (byte coding) (AST) is done by almost many programming languages I ever explored (Python,Ruby, lua, ...). It would have been awesome, if they were easily parse-able I guess. Most of the ORM implementations are very error prone to those design decisions. (Especially SQL databases).
- pizlonator 3y agoThat’s awesome, I didn’t know SQLite had a bytecode. Based on my experience writing interpreters, I know that bytecode is faster to interpret. (Source: I wrote JavaScriptCore’s interpreter and it’s optimizing JITs. I’ve also worked on other language implementations. I’ve seen the AST vs bytecode thing play out more than once.)
- andruc 3y agoFaster to interpret than what?
- jjice 3y agoI assume they meant faster to interpret than a tree of objects, since that's the other concept discussed in the article.
- pizlonator 3y agoYes
- iainmerrick 3y agoMaybe I'm missing something, but the bytecode approach seems really obviously better, just from a memory usage and locality point of view. Scanning an array of bytes or words is obviously going to be faster than traversing a tree of pointers. So I'd be surprised to find a serious language implementation using a pure AST in its interpreter, without at the very least flattening it to an array! Edit to add: of course there are some cases where you might actually want the AST approach, as the Sqlite doc is careful to point out. But not very many.
- pizlonator 3y agoIt’s fine to use an AST interpreter if you pair it with really great JITs. That has its own problems though - using an AST as a shared source of truth for your JIT compilers is cumbersome for implementing stuff like OSR. But from a perf standpoint, it’s probably fine. Also - say you want to optimize just for startup time, like if the code you’re running has minimal looping or reexecution. Then AST is better because you skip a step before first execution.
- pdubroy 3y agoI think most people associate bytecode VMs / interpreters with general-purpose programming languages, but it's a surprisingly useful concept in other contexts. Sometimes bytecode VMs appear in unexpected places! A few that I'm aware of: - eBPF, an extension mechanism in the Linux kernel - DWARF expression language, with interpreters in debuggers like GDB and LLDB - The RAR file format includes a bytecode encoding for custom data transformation More here: https://dubroy.com/blog/bytecode-vms-in-surprising-places/ https://dubroy.com/blog/bytecode-vms-in-surprising-places/
- WickedSmoke 3y agoBytecode is great for tiny domain languages and I use them in many projects. Ultima IV used one to animate sprites on it's title screen map. For the next version of XU4 I implemented three bytecode interpreters to script the entire title sequence. There's a high level presentation interpreter, a GPU rendering interpreter, and one for the Ultima IV bytecode.
- xymostech 3y agoThe original TeX Fonts stored their metrics in TFM (short for TeX font metrics) files, which contains a bytecode interpreter for calculating ligatures and kerning between characters. I learned about that when I tried reading the files myself. From what I can tell, modern fonts using OpenType just have tables to accomplish something similar now, in the form of the GSUB and GPOS tables? Documentation for the TFM format here: https://tug.org/TUGboat/Articles/tb02-1/tb02fuchstfm.pdf https://tug.org/TUGboat/Articles/tb02-1/tb02fuchstfm.pdf (search for lig/kern)
- atombender 3y agoTrueType (and OpenType, which is an evolution of TT) absolutely includes a bytecode instruction set: https://developer.apple.com/fonts/TrueType-Reference-Manual/RM05/Chap5.html https://developer.apple.com/fonts/TrueType-Reference-Manual/...
- xymostech 3y ago
- naasking 3y agoOn incrementally running bytecode: > This is more difficult to achieve in a tree-of-objects design. When the prepared statement is a tree-of-objects, execution is normally accomplished by walking the tree. To pause the statement in the middle of a computation means unwinding the stack back up to the caller, all the while saving enough state to resume evaluation where it last left off. This is not impossible to do, but it is sufficiently difficult that I have never seen it actually done. I don't think it's too difficult. You can avoid stack unwinding by just not using the native stack in the first place and using an explicit stack. This is one step towards a bytecode VM though, as you're virtualizing the stack. Definitely easier in bytecode though as it already makes all of that state explicit. For the article overall, isn't it a bit trivial to see that a bytecode interpreter must be faster and more compact? Write out the expression tree to an array as an in-order traversal and this is basically an executable bytecode. It will be more compact because you no longer need hidden malloc/object headers and pointers for subexpressions (they're preceding indices!), and it will be faster because it's basically all in cache, so no cache misses from pointer chasing. I can't imagine a situation in which the tree would ever be faster for execution, in general. At best, the overhead might be just too small to care about. We use trees in compilers because we need to perform incremental rewrites. This is trivial with trees but can get expensive when expanding and contracting arrays. Execution doesn't need to perform rewrites though, it needs linear, cache-friendly access patterns. However, the article does make a good point that the query plan may be tuned on the fly during execution, eg. the small rewrites I mentioned above occurring while executing. I'm not fully convinced this couldn't be done in bytecode though.
- iainmerrick 3y agoI think the article is just trying to be scrupulously fair by listing all possible disadvantages as well as advantages. But I agree with you, the bytecode approach seems obviously better.