Is there a design doc for the virtual machine re-write?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Is there a design doc for the virtual machine re-write?

Rob Sciuk

I seem to recall that not too long ago, the SQLite vm was re-written for
some reason, and I wonder if there is any documentation on the details of
what was done, and why?  I think it may have something to do with moving
off a stack architecture, but I don't think I ever saw a detailed
rationale for such a major undertaking.  My concern is *NOT* SQLite
related in any way, but rather I'm interested in VM's just now, and I was
hoping to fall in a pile of warm steaming information related to
VM performance etc.

I put this on the list, for fear of wasting any of D.R.H.'s time, in the
hopes that someone can point me to something which exists (and I hope, I
simply overlooked).

Cheers,
Rob Sciuk
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is there a design doc for the virtual machine re-write?

Darren Duncan
Rob Sciuk wrote:

> I seem to recall that not too long ago, the SQLite vm was re-written for
> some reason, and I wonder if there is any documentation on the details of
> what was done, and why?  I think it may have something to do with moving
> off a stack architecture, but I don't think I ever saw a detailed
> rationale for such a major undertaking.  My concern is *NOT* SQLite
> related in any way, but rather I'm interested in VM's just now, and I was
> hoping to fall in a pile of warm steaming information related to
> VM performance etc.
>
> I put this on the list, for fear of wasting any of D.R.H.'s time, in the
> hopes that someone can point me to something which exists (and I hope, I
> simply overlooked).
>
> Cheers,
> Rob Sciuk

You may be referring to SQLite's conversion from a stack-based to a
register-based virtual machine, which happened with release 3.5.5 on 2008 Jan
31.  This was a completely backwards-compatible change, hence it came in a 0.0.1
version update. -- Darren Duncan
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is there a design doc for the virtual machine re-write?

Rob Sciuk

On Sat, 28 Aug 2010, Darren Duncan wrote:

> Date: Sat, 28 Aug 2010 15:58:08 -0700
> From: Darren Duncan <[hidden email]>
> To: [hidden email],
>     General Discussion of SQLite Database <[hidden email]>
> Subject: Re: [sqlite] Is there a design doc for the virtual machine re-write?
>
> Rob Sciuk wrote:
>> I seem to recall that not too long ago, the SQLite vm was re-written for
>> some reason, and I wonder if there is any documentation on the details of
>> what was done, and why?  I think it may have something to do with moving
>> off a stack architecture, but I don't think I ever saw a detailed rationale
>> for such a major undertaking.  My concern is *NOT* SQLite related in any
>> way, but rather I'm interested in VM's just now, and I was hoping to fall
>> in a pile of warm steaming information related to VM performance etc.
>>
>> I put this on the list, for fear of wasting any of D.R.H.'s time, in the
>> hopes that someone can point me to something which exists (and I hope, I
>> simply overlooked).
>>
>> Cheers,
>> Rob Sciuk
>
> You may be referring to SQLite's conversion from a stack-based to a
> register-based virtual machine, which happened with release 3.5.5 on 2008 Jan
> 31.  This was a completely backwards-compatible change, hence it came in a
> 0.0.1 version update. -- Darren Duncan
>

That is *EXACTLY* what I'm reffering to.  Is there any design info,
rationale or pointers to what changes were made, and why the switch from a
stack to register machine??  Also, is there any performance data?

Just wondering.

Cheer,
Rob Sciuk


_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is there a design doc for the virtual machine re-write?

Max Vlasov
> That is *EXACTLY* what I'm reffering to.  Is there any design info,
> rationale or pointers to what changes were made, and why the switch from a
> stack to register machine??  Also, is there any performance data?
>
>

There's a video where D. Richard Hipp talks about sqlite (interesting in
many other aspects also):
http://video.google.com/videoplay?docid=-5160435487953918649

He mentioned (about 30:00) that with register based engine is much easier to
generate instructions.

Below is my observations about the aspects that makes register-based engine
a better choice:
- vbe codes points to columns, tables and so on while actual data is placed
in the tables (persistent or temporal) so there are actually not so many
cases when you really need much data temporary available so several
registers should be enough
- As long as I noticed there's no such thing as procedures or functions in
the vbe programs, it's just a list of instructions. Stack is useful for
procedures to pass the context, but you don't actually really need it here.
- Operations of placing to stack and removing from it generally is not
expensive, but when an operation takes tiny fraction of time (for example
when the page is already in the cache), this might affect the performance in
general.

Also you can try to compare EXPLAIN QUERY result from a version prior to
3.5.5 to some of the current one for the same sql query. I wanted to do this
myself, but seems like can not access sqlite download page right now.

Max Vlasov
maxerist.net
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is there a design doc for the virtual machine re-write?

Jay Kreibich
On Mon, Aug 30, 2010 at 03:59:51PM +0400, Max Vlasov scratched on the wall:

> > That is *EXACTLY* what I'm reffering to.  Is there any design info,
> > rationale or pointers to what changes were made, and why the switch from a
> > stack to register machine??  Also, is there any performance data?
>
> There's a video where D. Richard Hipp talks about sqlite (interesting in
> many other aspects also):
> http://video.google.com/videoplay?docid=-5160435487953918649
>
> He mentioned (about 30:00) that with register based engine is much easier to
> generate instructions.

  There's also this comment, on a bug that was filed in November of
  2007 (less than 90 days before the release of the register based VDBE):

  http://www.sqlite.org/cvstrac/tktview?tn=2767,39

  "I have long wanted to switch the VDBE from being a stack-based VM to
  being a register based VM. Notice that were the VDBE register based,
  this bug would have never come up...."

> Below is my observations about the aspects that makes register-based engine
> a better choice:
> - vbe codes points to columns, tables and so on while actual data is placed
> in the tables (persistent or temporal) so there are actually not so many
> cases when you really need much data temporary available so several
> registers should be enough

  I think that's key.  The SQLite VDBE is extremely specialized.  Most of
  the "instructions" are very high level abstractions.  If you wanted
  to write a procedural language for database manipulation, it isn't
  difficult to imagine a nearly one-to-one mapping between PL/SQL like
  commands and VDBE instructions.

  I've not spent a ton of time studying the VM, other than trying to
  track down query performance issues, but in my own experience the
  registers don't tend to carry values from instruction to instruction.
  Frequently the registers have immediate values, and are used more as
  instruction parameters, rather than state carrying containers that are
  passed from instruction to instruction.  As Max said, most of the
  manipulated data (i.e. database values and table or index references)
  is held in non-register containers.  The registers are used as index
  references into those stores, and in many cases those index values are
  static for a specific VM instruction in a specific VDBE program.
 
  Because of the nature of the SQL language, this works out very well.
  SQL commands tend to be self-contained and follow specific formats.
  I'm sure a "parameter based" VM makes code generation much simpler
  and much faster and is a very good fit for the needs of SQLite.
  I'm less convinced it could be expanded to deal with more generic
  programming abstractions, such as recursive function calls-- but I
  don't have an extensive amount of VM experience, so I wouldn't put
  much into that opinion.
 
   -j

--
Jay A. Kreibich < J A Y  @  K R E I B I.C H >

"Intelligence is like underwear: it is important that you have it,
 but showing it to the wrong people has the tendency to make them
 feel uncomfortable." -- Angela Johnson
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is there a design doc for the virtual machine re-write?

Rob Sciuk

On Mon, 30 Aug 2010, Jay A. Kreibich wrote:

> Date: Mon, 30 Aug 2010 12:04:25 -0500
> From: Jay A. Kreibich <[hidden email]>
> To: General Discussion of SQLite Database <[hidden email]>
> Cc: [hidden email]
> Subject: Re: [sqlite] Is there a design doc for the virtual machine re-write?
>
> On Mon, Aug 30, 2010 at 03:59:51PM +0400, Max Vlasov scratched on the wall:
>>> That is *EXACTLY* what I'm reffering to.  Is there any design info,
>>> rationale or pointers to what changes were made, and why the switch from a
>>> stack to register machine??  Also, is there any performance data?
>>
>> There's a video where D. Richard Hipp talks about sqlite (interesting in
>> many other aspects also):
>> http://video.google.com/videoplay?docid=-5160435487953918649
>>
>> He mentioned (about 30:00) that with register based engine is much easier to
>> generate instructions.
>
>  There's also this comment, on a bug that was filed in November of
>  2007 (less than 90 days before the release of the register based VDBE):
>
>  http://www.sqlite.org/cvstrac/tktview?tn=2767,39
>
>  "I have long wanted to switch the VDBE from being a stack-based VM to
>  being a register based VM. Notice that were the VDBE register based,
>  this bug would have never come up...."
>
>> Below is my observations about the aspects that makes register-based engine
>> a better choice:
>> - vbe codes points to columns, tables and so on while actual data is placed
>> in the tables (persistent or temporal) so there are actually not so many
>> cases when you really need much data temporary available so several
>> registers should be enough
>
>  I think that's key.  The SQLite VDBE is extremely specialized.  Most of
>  the "instructions" are very high level abstractions.  If you wanted
>  to write a procedural language for database manipulation, it isn't
>  difficult to imagine a nearly one-to-one mapping between PL/SQL like
>  commands and VDBE instructions.
>
>  I've not spent a ton of time studying the VM, other than trying to
>  track down query performance issues, but in my own experience the
>  registers don't tend to carry values from instruction to instruction.
>  Frequently the registers have immediate values, and are used more as
>  instruction parameters, rather than state carrying containers that are
>  passed from instruction to instruction.  As Max said, most of the
>  manipulated data (i.e. database values and table or index references)
>  is held in non-register containers.  The registers are used as index
>  references into those stores, and in many cases those index values are
>  static for a specific VM instruction in a specific VDBE program.
>
>  Because of the nature of the SQL language, this works out very well.
>  SQL commands tend to be self-contained and follow specific formats.
>  I'm sure a "parameter based" VM makes code generation much simpler
>  and much faster and is a very good fit for the needs of SQLite.
>  I'm less convinced it could be expanded to deal with more generic
>  programming abstractions, such as recursive function calls-- but I
>  don't have an extensive amount of VM experience, so I wouldn't put
>  much into that opinion.
>
>   -j

Thanks, Jay.  I'll check the links, and look further afield for what I
seek.  I've been reviewing the Lua design doc recently, and the decision
to move from a stack to a register based VM is well supported there.

  (http://www.lua.org/doc/jucs05.pdf)

Cheers,
Rob Sciuk.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users