Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why SQLite Uses Bytecode

sqlite.org

Post reply on HN
Print view View original

111–120 of 231 posts

Re: Why SQLite Uses Bytecode

#111

Post by bena »

coolandsmartrr wrote: post #46
wolf550e wrote: post #29

The page is the result of this exchange on Twitter: 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 It is difficult to summarize the advan…

I am amazed that the author (D Richard Hipp) made an effort to find and respond to a tweet that was (1) not directed/"@tted" at him or (2) written in his native language of English (original tweet is in Japanese[1]). [1] https://twitter.com/gorilla0513/status/1784623660193677762

He might have a google alert for sqlite.org

Re: Why SQLite Uses Bytecode

#112

Post by vidarh »

megadal wrote: post #28
lifthrasiir wrote: post #23

Earlier quoted context omitted.

You 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.

Genuinely 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

Consider that if the bytecode is just a flattened representation, then instead of generating and traversing the tree, you can just traverse what would have been turned into the tree in the same traversal order directly.

E.g. imagine you're in a leaf production for some simple grammar for an operator that can only take integers, w/all error handling ignored:

     parse_fooexpr() {
          left = parse_int
          emit_int(left)
          expect_token(FOO_OP)
          right = parse_int
          emit_int(right)
          emit_foo_op()
     }
Whether emit_int outputs a "push " VM instruction to a bytecode buffer, or constructs an IntNode and pushes it to an argument stack, and whether "emit_foo_op" emits a "foo_op" bytecode instruction or pops the argument stack and constructs a FooOpNode(...argument stack values) AST node is an implementation detail in terms of the parser.

Wirth's compilers usually didn't use an AST, and his book on compiler construction contains a thorough walkthrough on generating code as you parse, if you want to see it explained in a lot more detail and w/tricks to generate better code than the most naive approaches will.

The difficulty with this approach comes when you want to apply optimisations or where it's inconvenient to generate the code in parse-order because the language tries to smart about what feels better to write, but you can get pretty far with this method.

Re: Why SQLite Uses Bytecode

#114

Post by vidarh »

ufo wrote: post #104
megadal wrote: post #28

Earlier quoted context omitted.

Genuinely 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

It's as if they generated an AST and then immediately converted it to bytecode, all at once. The key restriction is that you must be able to generate the bytecode in a single pass over the source code. For example, the compilation of a function at the top of the file must not depend on declarations further down the file.

Depending on the form the dependencies takes you can handle that too. E.g. if it's "just" about knowing addresses, then just building up a list of relocation records where you need to patch in addresses as they become known works just fine. Of course the more work like that you have to do, the less you save over just building an AST anyway.

Re: Why SQLite Uses Bytecode

#115

Post by ksherlock »

megadal wrote: post #28
lifthrasiir wrote: post #23

Earlier quoted context omitted.

You 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.

Genuinely 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

Take a look at the evergreen Let's Build a Compiler, by Jack Crenshaw

https://compilers.iecc.com/crenshaw/

Chapter 2 and 3, expression parsing, should give you the idea. Instead of building the AST, you build code. So you're cutting out the middle man (AST).

Re: Why SQLite Uses Bytecode

#116

Post by beeboobaa3 »

SQLite wrote: post #96
paulddraper wrote: post #34

Earlier quoted context omitted.

There 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.

Performance analysis indicates that SQLite spends very little time doing bytecode decoding and dispatch. Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records - all of which happens in compiled C code. Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements. So at least in the case of SQLite, compiling all the way down to machine code might…

> Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements

> compiling all the way down to machine code might provide a performance boost 3% or less

This logic doesn't seem sound? Because the application now spends 3% on bytecode dispatch doesn't tell us anything about how long it would instead spend on e.g. interpreting SQL.

Re: Why SQLite Uses Bytecode

#117

Post by krallja »

bitwize wrote: post #103
chrisaycock wrote: post #2

SQLite'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.

Wozniak 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 d…

The unfortunate history of SWEET16 is that it was never used for its intended purpose - https://retrocomputing.stackexchange.com/a/14513/11579

Re: Why SQLite Uses Bytecode

#118

Post by yayr »

Cthulhu_ wrote: post #109
yayr wrote: post #101

Earlier quoted context omitted.

Actually, SAP HANA has a nice tool called PlanViz for that in Eclipse. A google image search gives you a good impression how that works. There are also some blogs about it, e.g. https://community.sap.com/t5/enterprise-resource-planning-bl...

I love how the example SQL query uses abbreviated columns that sound like runes: select -- count(*) a.mandt, b.rldnr, a.bukrs, a.gjahr, a.belnr, b.docln, a.buzei -- * from BSEG as a innerjoin ACDOCA as b on b.rclnt = a.mandt and b.rbukrs = a.bukrs and b.gjahr = a.gjahr and b.belnr = a.belnr where a.mandt = '715' and b.rldnr = '0L' and b.docln = '000001' and a.buzei = '001' and a.gjahr = '2018' --and a.gjahr = '2017'…

yeah, these accounting table field names have not changed since around 30 years, which is not necessarily a bad thing...

for a human readable view of this you can look e.g. here https://docsfortec.com/sap/S4/tables/ACDOCA

Re: Why SQLite Uses Bytecode

#119

Post by temporarely »

SQLite wrote: post #96
paulddraper wrote: post #34

Earlier quoted context omitted.

There 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.

Performance analysis indicates that SQLite spends very little time doing bytecode decoding and dispatch. Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records - all of which happens in compiled C code. Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements. So at least in the case of SQLite, compiling all the way down to machine code might…

A while back was musing if it was possible to come up with something resembling the instruction set for a CPU for an abstract relational-engine. Is this basically what SQLite is doing with bytecodes?

Re: Why SQLite Uses Bytecode

#120

Post by wglb »

blacklion wrote: post #107
SQLite wrote: post #96

Earlier quoted context omitted.

Performance analysis indicates that SQLite spends very little time doing bytecode decoding and dispatch. Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records - all of which happens in compiled C code. Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements. So at least in the case of SQLite, compiling all the way down to machine code might…

Looks like SQLIte bytecode is similar to IBM RPG language from "IBM i" platform, which is used directly, without translation from SQL :) Edit: PRG->RPG.

I'm curious. Would you have a pointer to the documentation of PRG language?
Post reply on HN