3 ms·

> However, very well engineered purpose built solvers still beat datalog engines by a large factor (again, no theoretical reason this should be true, but it is)

> However, very well engineered purpose built solvers still beat datalog engines by a large factor (again, no theoretical reason this should be true, but it is) Sure there is a reason: Many applications, alias analysis in particular, only use a subset of Datalog. Subsetting languages very often makes for easier and more efficient implementation. If you know that there is no negation in your alias problems, your special purpose solver can be much more efficient than a Datalog solver that must be prepared to deal with negation. Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver". As for the "built in" part, anything that is not built in must cross an API boundary and usually translate between different data representations. That is a theoretical reason for being slower.

Jweb_Guru 8y ago
> But that is then no longer a Datalog solver but a "well engineered purpose built solver". I don't really agree. Specialized implementations for instances of a problem that can solved more efficiently than the general case are a pretty fundamental part of any mature solver (GMP is probably the most well-known example). This includes even cases where the user says to try the specialized algorithm and the solver checks that you indeed have an instance of it, rather than the specialized subproblem being automatically detected by the solver (there are many examples, but I always think of optimizations for read only transactions in databases--generally you have to declare the transaction read-only up front). > As for the "built in" part, anything that is not built in must cross an API boundary and usually translate between different data representations. That is a theoretical reason for being slower. The abstractions required for getting solvers to perform well on problems like this are usually sufficiently far removed from the representation you'd have had if you didn't have to solve the problem that (1) transforming it is only a small part of the overall time to solve, and (2) it is often a cost you already have to pay to some extent.
DannyBee 8y ago
FWIW: None of this is a theoretical reason. This is no different than the problems any other compiler/JIT faces. What you've offered are practical reasons it hasn't happened yet, but not theoretical reasons.
- tom_mellior 8y ago
  "System A must do more work than system B" seems a pretty theoretical reason why, in the limit (after sinking an arbitrary number of engineer hours in each), system A must be slower than system B. But your interpretations of the word "theoretical" may differ.
  - frankmcsherry 8y ago
    I think the point is that there is no clear reason System A must do more work than System B. Serious Datalog environments will identify strictly monotonic programs and execute them more efficiently (e.g. with racy asynchrony); they will identify linear recursion and partition work accordingly. They could identify programs corresponding to DannyBee's hypothetical purpose-build industrial winners and execute them using the exact same techniques, but apparently they don't. I suspect the point of disagreement is > Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver". which I don't think is correct. A Datalog solver with the property that it can run faster on certain classes of input is great; it is not "no longer a Datalog solver".
    - tom_mellior 8y ago
      > Serious Datalog environments will identify strictly monotonic programs [...] Yes. And that is extra work that must be done. Admittedly, it probably isn't the "large factor" mentioned by DannyBee. > A Datalog solver with the property that it can run faster on certain classes of input is great; it is not "no longer a Datalog solver". I was talking of a special, user-requested mode in which the user guarantees that the input program they are interested in will not contain certain constructs, and the solver can reject programs that do contain them. A "Datalog" solver that rejects programs containing, say, negation, does not handle the full Datalog language and is therefore no longer a Datalog solver. As an analogy, Clang is a C++ compiler, but passing it the "-xc" flag causes it to reject valid C++ programs, so then it's no longer a C++ compiler (although it is still the same program!).

Jweb_Guru 8y ago

> But that is then no longer a Datalog solver but a "well engineered purpose built solver". I don't really agree. Specialized implementations for instances of a problem that can solved more efficiently than the general case are a pretty fundamental part of any mature solver (GMP is probably the most well-known example). This includes even cases where the user says to try the specialized algorithm and the solver checks that you indeed have an instance of it, rather than the specialized subproblem being automatically detected by the solver (there are many examples, but I always think of optimizations for read only transactions in databases--generally you have to declare the transaction read-only up front). > As for the "built in" part, anything that is not built in must cross an API boundary and usually translate between different data representations. That is a theoretical reason for being slower. The abstractions required for getting solvers to perform well on problems like this are usually sufficiently far removed from the representation you'd have had if you didn't have to solve the problem that (1) transforming it is only a small part of the overall time to solve, and (2) it is often a cost you already have to pay to some extent.

DannyBee 8y ago

FWIW: None of this is a theoretical reason. This is no different than the problems any other compiler/JIT faces. What you've offered are practical reasons it hasn't happened yet, but not theoretical reasons.

tom_mellior 8y ago
"System A must do more work than system B" seems a pretty theoretical reason why, in the limit (after sinking an arbitrary number of engineer hours in each), system A must be slower than system B. But your interpretations of the word "theoretical" may differ.
- frankmcsherry 8y ago
  I think the point is that there is no clear reason System A must do more work than System B. Serious Datalog environments will identify strictly monotonic programs and execute them more efficiently (e.g. with racy asynchrony); they will identify linear recursion and partition work accordingly. They could identify programs corresponding to DannyBee's hypothetical purpose-build industrial winners and execute them using the exact same techniques, but apparently they don't. I suspect the point of disagreement is > Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver". which I don't think is correct. A Datalog solver with the property that it can run faster on certain classes of input is great; it is not "no longer a Datalog solver".
  - tom_mellior 8y ago
    > Serious Datalog environments will identify strictly monotonic programs [...] Yes. And that is extra work that must be done. Admittedly, it probably isn't the "large factor" mentioned by DannyBee. > A Datalog solver with the property that it can run faster on certain classes of input is great; it is not "no longer a Datalog solver". I was talking of a special, user-requested mode in which the user guarantees that the input program they are interested in will not contain certain constructs, and the solver can reject programs that do contain them. A "Datalog" solver that rejects programs containing, say, negation, does not handle the full Datalog language and is therefore no longer a Datalog solver. As an analogy, Clang is a C++ compiler, but passing it the "-xc" flag causes it to reject valid C++ programs, so then it's no longer a C++ compiler (although it is still the same program!).