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

121–130 of 231 posts

Re: Why SQLite Uses Bytecode

#121

Post by AtlasBarfed »

paulddraper wrote: post #34
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…

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.

optimizing runtimes (usually bytecode) can beat statically compiled code, because they can profile the code over time, like the JVM.

... which isn't going to close the cold startup execution gap, which all the benchmarks/lies/benchmarks will measure, but it is a legitimate thing.

I believe Intel CPUs actually sort of are #2. All your x86 is converted to microcode ops, sometimes optimized on the fly (I remember Intel discussing "micro ops fusion" a decade ago I think).

Re: Why SQLite Uses Bytecode

#122

Post by naasking »

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.

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

Re: Why SQLite Uses Bytecode

#125

Post by blacklion »

wglb wrote: post #120
blacklion wrote: post #107

Earlier quoted context omitted.

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?

Oooops, it is IBM RPG, not PRG! My bad!

There are some links in Wikipedia.

I never used it, but only read big thread about SQL vs RPG on Russian-speaking forum, and there was a ton of examples from person who works with IBM i platform in some big bank. Basic operations look like SQLite bytecodes: open table, move cursor after record with key value "X", get some fields, update some field, plus loops, if's, basic arithmetic, etc.

Re: Why SQLite Uses Bytecode

#126

Post by naasking »

alex_smart wrote: post #83
eklavya wrote: post #50

Earlier quoted context omitted.

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

Consider evaluating an expression like "col1 + col2 == col3" A tree based evaluator has to do something like - for (int i = 0; i whereas a bytecode based evaluator is able to run something equivalent to - for (int i = 0; i

You still have to branch on opcode selection which you're omitting in your translation. Branching on "expression type" and column type in your first example is also unnecessary. Bytecodes have different opcodes to operate on different types and different arities, so in both cases you have only one unpredictable branch for each operation/opcode.

The main benefit of bytecodes is then cache friendliness, by removing all of those unpredictable loads and stores to obtain the expression details (opcode, arguments, etc.). All of those are inlined into the bytecode array which is already in cache.

Re: Why SQLite Uses Bytecode

#127

Post by rkrzr »

temporarely wrote: post #119
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…

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?

No. The SQLite bytecode is much higher-level than the instruction set of a CPU.

Re: Why SQLite Uses Bytecode

#128

Post by asimpletune »

beeboobaa3 wrote: post #116
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…

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

He’s saying in the best case scenario that 3% would go to 0. Therefore the reality would probably be even less.

Re: Why SQLite Uses Bytecode

#129

Post by kayodelycaon »

blacklion wrote: post #125
wglb wrote: post #120

Earlier quoted context omitted.

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

Oooops, it is IBM RPG, not PRG! My bad! There are some links in Wikipedia. I never used it, but only read big thread about SQL vs RPG on Russian-speaking forum, and there was a ton of examples from person who works with IBM i platform in some big bank. Basic operations look like SQLite bytecodes: open table, move cursor after record with key value "X", get some fields, update some field, plus loops, if's, basic arith…

For those that aren’t familiar, IBM i is ye olde A/S 400.

To be fair, RPG has been continuously updated and the version I’ve seen has Java integration.

It’s somewhat amusing that a single developer using Python can run circles around entire teams of RPG programmers. Technology marches on. :)

Re: Why SQLite Uses Bytecode

#130

Post by titzer »

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…

Part of the benefit of compiling bytecode (or anything) is specializing code to the context (types, values, etc) in which it appears. While I don't doubt your analysis, it could be the case that compiled C code in question is full of branches that can be folded away when specialized to the context of the query, such as the structure of the rows, the type and values of columns, etc.

Basically all of what you are saying about high-level bytecodes applies to dynamic languages, too. But they benefit highly from specializing each bytecode given static and dynamic context, and shortcutting dataflow through local variables.

Post reply on HN