Here's an absolutely crazy idea that I had the other day... Since Zig has comptime, couldn't a Zig reimplementation of SQLite use comptime for compile-time query compilation? Including generating native code for fixed queries? So far I haven't been able to come up with any counterargument for why this wouldn't work.
The counter-argument is interpreting the query is not what takes up the time in executing a typical RDBMS query. Imagine a db is just a key-value store, the query is some keys and the db just spits out whatever it found in a giant hashtable. That's not going to get faster if you 'compile' the query. It's not going to get much faster if your db is a more realistic three hashtables, two big arrays and a partridge in a b-tree.
I'm aware of that, but these elementary operations have some definitions in code. Even just calling them in a fixed sequence (as opposed to dispatching at runtime one opcode at a time) would be something optimizable for a sufficiently smart compiler. However, given a good-enough design of the whole system, straight code generation from the query plan shouldn't be a problem either (and at that point, the Zig compiler should be able to do even more work with the generated query code). I mean, any reimplementation would presumably use Zig features heavily anyway -- otherwise you could just link with the C code.
Possibly, but then again, if one's aim is to replace C with Zig in the future perhaps completely, because SQLite became de-facto standard file format for many applications (see OGC GeoPackage for example), you might need some implementation of SQLite for that. If a file format is going to stick for decades, you'll definitely get other implementations of that file format sooner or later in environments that can't or don't want to use C.
So, yes, it'd be nice to have an implementation of SQLite3 in some non-C language. However, that's a tall order.
And here you're proposing Zig while someone else will prefer Rust, and someone else Go. So you'll need N>1 rewrites.
This is why SQLite3 is written in C then, because for all the ways in which C sucks, it is the most common (lowest) denominator that ticks the portability checkbox.
Language runtimes that want to not have a C runtime embedded are the hardest hit. The best thing to do for those in the short-term is to talk to a C-coded IPC service that runs the C-coded thing that otherwise can't be run.
because for all the ways in which C sucks, it is the most common (lowest) denominator that ticks the portability checkbox.
This is actually something that Zig is supposed to do as well. There should be nothing that you can do in C but can't do in Zig. So hypothetically, in the future (say, twenty years from now), a Zig implementation of SQLite could be a preferred one since you're not losing anything with it. (With the additional benefit that should you want to, you might be able to compile application-specific queries into it.)
Well, for instance, famously, any multiple-stack machines will have a hard time trying to run C because C assumes a single hardware stack. Although I imagine that currently, in most cases, you'll want to avoid C for software reasons, rather than hardware reasons (for example, you're required to deploy pure Java code, or pure C# code, or want to avoid any unsafe code in Rust, things like that).
No, it doesn't. C does not even assume a stack. A platform where function call frames are allocated on the heap would not be incompatible with C.
The problem is not with call frames being on the stack or on the heap; even a spaghetti stack would be problematic. One of the problems is that return addresses and data are interleaved in C-style frames, whereas multiple stack machines require them to be separate. It's not that you couldn't write an implementation of C for a stack machine, it's just that it would be probably very primitive and slow. Yes, you can run C at the very least the way it was done on Lisp machines, by allocating a large byte array and treating it as your physical memory, but surely you would want to avoid it if you could. There really is a reason why stack machines historically ran somewhat exotic languages like Forth.
You can't take an address of pretty much any input parameter, return value, or local variable of a function on a stack machine because they're all on the stack CPU core's hardware data stack which has no addresses for its elements. In C you should be able to take the address of these objects, using an ampersand. That's not making an assumption?
If it's addressable memory, you can address it. That does not assume a stack however. You don't get to assume that they are in some order, not if you want your code to be portable. On typical architectures that do use a stack, if you're very careful, you do get to use the addresses of automatics to figure out whether the stack grows up or down, but that's not specifically something in standard C.
Comments
Here's an absolutely crazy idea that I had the other day... Since Zig has comptime, couldn't a Zig reimplementation of SQLite use comptime for compile-time query compilation? Including generating native code for fixed queries? So far I haven't been able to come up with any counterargument for why this wouldn't work.
Similar idea: https://andrewkelley.me/post/string-matching-comptime-perfec...
The counter-argument is interpreting the query is not what takes up the time in executing a typical RDBMS query. Imagine a db is just a key-value store, the query is some keys and the db just spits out whatever it found in a giant hashtable. That's not going to get faster if you 'compile' the query. It's not going to get much faster if your db is a more realistic three hashtables, two big arrays and a partridge in a b-tree.
It might not be worth for everything, but extremely simple queries on extremely simple schemas would not be the goal here.
SQLite already compiles queries into opcodes and then uses its own VM to interpret them. You would have to reimplement the internal VM.
I'm aware of that, but these elementary operations have some definitions in code. Even just calling them in a fixed sequence (as opposed to dispatching at runtime one opcode at a time) would be something optimizable for a sufficiently smart compiler. However, given a good-enough design of the whole system, straight code generation from the query plan shouldn't be a problem either (and at that point, the Zig compiler should be able to do even more work with the generated query code). I mean, any reimplementation would presumably use Zig features heavily anyway -- otherwise you could just link with the C code.
You lose at "reimplementation of SQLite".
Possibly, but then again, if one's aim is to replace C with Zig in the future perhaps completely, because SQLite became de-facto standard file format for many applications (see OGC GeoPackage for example), you might need some implementation of SQLite for that. If a file format is going to stick for decades, you'll definitely get other implementations of that file format sooner or later in environments that can't or don't want to use C.
So, yes, it'd be nice to have an implementation of SQLite3 in some non-C language. However, that's a tall order.
And here you're proposing Zig while someone else will prefer Rust, and someone else Go. So you'll need N>1 rewrites.
This is why SQLite3 is written in C then, because for all the ways in which C sucks, it is the most common (lowest) denominator that ticks the portability checkbox.
Language runtimes that want to not have a C runtime embedded are the hardest hit. The best thing to do for those in the short-term is to talk to a C-coded IPC service that runs the C-coded thing that otherwise can't be run.
This is actually something that Zig is supposed to do as well. There should be nothing that you can do in C but can't do in Zig. So hypothetically, in the future (say, twenty years from now), a Zig implementation of SQLite could be a preferred one since you're not losing anything with it. (With the additional benefit that should you want to, you might be able to compile application-specific queries into it.)
What environment cannot run C?
Well, for instance, famously, any multiple-stack machines will have a hard time trying to run C because C assumes a single hardware stack. Although I imagine that currently, in most cases, you'll want to avoid C for software reasons, rather than hardware reasons (for example, you're required to deploy pure Java code, or pure C# code, or want to avoid any unsafe code in Rust, things like that).
No, it doesn't. C does not even assume a stack. A platform where function call frames are allocated on the heap would not be incompatible with C.
You could say that some C code assumes a stack, but that's pretty exceptional.
Yes.
Hard to imagine hardware on which C could not run. Maybe a JVM chip, but even then, you could compile C to bytecode.
The problem is not with call frames being on the stack or on the heap; even a spaghetti stack would be problematic. One of the problems is that return addresses and data are interleaved in C-style frames, whereas multiple stack machines require them to be separate. It's not that you couldn't write an implementation of C for a stack machine, it's just that it would be probably very primitive and slow. Yes, you can run C at the very least the way it was done on Lisp machines, by allocating a large byte array and treating it as your physical memory, but surely you would want to avoid it if you could. There really is a reason why stack machines historically ran somewhat exotic languages like Forth.
No, really, the C language makes no assumptions about this.
You can't take an address of pretty much any input parameter, return value, or local variable of a function on a stack machine because they're all on the stack CPU core's hardware data stack which has no addresses for its elements. In C you should be able to take the address of these objects, using an ampersand. That's not making an assumption?
If it's addressable memory, you can address it. That does not assume a stack however. You don't get to assume that they are in some order, not if you want your code to be portable. On typical architectures that do use a stack, if you're very careful, you do get to use the addresses of automatics to figure out whether the stack grows up or down, but that's not specifically something in standard C.
GPUs are weird.
HLSL and CUDA have C-like syntax, but underneath the syntax these things are very different from C.
On GPU almost nothing has an address, there's no stack, no malloc/free, no files or printf, and every instruction runs on 32+ threads in lockstep.