1
$\begingroup$

I initially brought this up on the Swift Forums, and it was suggested that this might be a thing better suited for CS SE. So here goes:

I had this thought that the compiler already has enough information to be able to infer an appropriate data structure to use given the rest of the usage patterns that follow. This sounds too hard and abstract when I put it into words (and I'm sure this is intractable in its full generality), but what I have in mind is more simple rules of thumb based substitutions. Like if I'm using a special "List" type that the compiler knows about, and the compiler sees that the bulk of what I'm doing are checking for element memberships, then it puts in a Set in the code it emits. Or if it sees that I'm doing a lot of prependings, then it uses a dequeue. And if it doesn't see me doing anything special (or if it can't infer what I'm doing), it falls back to using a regular array.

This sounds doable in my head using the similar sort of static analysis that compilers already do for other forms of program optimization. But based on the responses I got in the Swift forum, it seems I have vastly underestimating the difficulty of doing even a toy version of this with the sort of techniques compilers use today.

So my question here is twofold - Can compilers (theoretically) infer the best (from an available set) of concrete data types for use in a given program? This is not for picking from all possible data structures, it is a more narrow question of picking from say 3 or 4 alternative implementations, when the programmer specifies he's using a "generic linear sequence" (let's call it a List) type.

And is this prior art or research around this? I looked, but I'm not able to hit on the correct search term.

Thank you!

$\endgroup$

2 Answers 2

1
$\begingroup$

If I understand your question correctly, you are asking whether the compiler can choose the implementation of a generic data structure, exactly how a programmer would define some variable to be a template in C++, and then specify how memory access and presence testing are carried out choosing the concrete implementation.

I think there are a few problems with the algorithm responsible for deciding which data structure to use:

  1. correctness,
  2. precision,
  3. actual costs.

Concerning correctness, in the most general case, the problem could even be undecidable because the compiler would be forced to decide whether some branches can be reached. Consider the following (contrived, artificial) excerpt:

std::set<C> S;
unsigned long int r = ...;// A huge random natural number.
if (collatz(r)==1) {
  /* A huge number of insertions of sorted elements on S. */
} else {
  /* A huge number of removal of scattered elements on S. */
}

int collatz(unsinged long int r) {
  while (r!=1){
        if (r%2==1)
            ans=(3*r)+1;
        else
            r /= 2;
  }
  return 1;
}

Here I take advantage of Collatz's function, which is nowadays not known to always terminate for all inputs. In this situation, the compiler would be forced to determine which data structure to use depending on the content of the two branches. Here I am abstractly hinting that in the first branch, a list would suffice, in the second case a hashtable would be preferable. Since nobody has ever proved that collatz terminates for all naturals, this task will certainly be out of reach for the compiler.

Concerning precision, in my opinion, this shows that the compiler must make a guess and approximate. This could generate some software that behaves properly under some loads and improperly under others.

On the other hand, let's say we are happy with such an approximation and the compiler makes correct choices on practical input programs. In that case, I would ask why we should add this check in the compiler itself. It sounds to me like it should be a task more suited for a lint'er or a performance evaluation suite. This last observation helps me to cover the last point; the compiler must produce the output in finite time, and doing so while producing high-quality output is time-consuming. Here there a two cases: either the compiler has only one candidate or it has more; the only way to choose the best is to generate each solution and run it. Postponing the whole pipeline because the compiler must benchmark the source code for making the most efficient decision sounds strange to me, however, it is a possible strategy.

Last, but not least, it comes the problem of declaring new data structures the compiler could choose from. Let's say I devised a new data structure perfect for querying spatial data in some program of mine, how should I inform the compiler of its existence? How could the compiler state that a set is not efficient while my new structure would be preferable?

Concluding, I think there exists a strategy that achieves what you are asking, but I don't expect amusing results, especially in non-trivial programs/environments.

$\endgroup$
0
$\begingroup$

The problem is too ill-defined to admit a definite answer.

Can you construct some heuristics for a compiler to choose a data structure that might be suitable, with no guarantees? Sure, of course.

Can a compiler guarantee to select the data structure that will provide optimal performance? No, that is undecidable. For instance, consider code of the following rough form:

l = new List()
if (hard_to_predict()) {
    while (True) { ... operations on l that are best for a singly linked list ... }
} else {
    while (True) { ... operations on l that are best for an array ... } 
}

Here hard_to_predict() might be anything -- it might even be as hard as the halting problem to predict at compile time whether it will return true or false.

I'm guessing that in practice we probably care about something in between those two extremes. For instance, maybe we want to know whether a compiler can perform reasonably well at this problem on common workloads, under some metric. Those kinds of engineering questions can probably only be answered experimentally, by trying to build such a scheme, and measuring how well it performs on a particular dataset of programs. They can't be answered based on theoretical considerations.

Will the benefits be worth the costs (implementation complexity of the compiler, unpredictability to the developer, the risks that the compiler makes a bad choice)? Unclear, and probably a matter of opinion.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.