How to optimize the size of jump tables?

Consider a typical enumeration type in a C-like language like this:

enum foo {
    FOO_A,
    FOO_B,
    FOO_C,
    /* ... */
    FOO_N
};

There are switch statement over values of type enum foo , possibly not handling certain enumeration values:

enum foo bar;
/* ... */
switch (bar) {
case FOO_A: /* ... */
case FOO_B: /* ... */
case FOO_D: /* ... */
case FOO_L: /* ... */
default: /* ... */
}

Now, for a sufficiently high amount of enumeration values handled, the compiler will to implement the switch statement using a jump table with size (<highest handled value> - <lowest handled value> + 1) * sizeof(void*).

Consider I have multiple such switch statements that are known to use jump tables, for each one is known which values are being handled and which values aren't. How can I reorder the values in enum foo in a way, that the total size of all jump tables generated is minimal?

Example

Here is a slightly simplified example which assumes that the compiler generates jump tables for all switch statements. This is the enumeration:

enum example {
    EX_A,
    EX_B,
    EX_C,
    EX_D
};

And these are the two switch-statements:

enum example a, b;

switch (a) {
case EX_A: /* ... */
case EX_C: /* ... */
default: /* ... */
}

switch (b) {
case EX_B: /* ... */
case EX_D: /* ... */
default: /* ... */
}

For this example, the compiler would generate two jump tables with three entries each (in the first case from EX_A to EX_C , in the second case from EX_B to EX_D ), amounting to a total of 6 machine words used for jump tables. If I did reorder the enumeration like this:

enum example {
    EX_A,
    EX_C,
    EX_B,
    EX_D
};

I would only need 4 data words for the jump tables.

---

This problem is NP-hard, because it generalizes the minimum linear arrangement problem (MinLA) from graphs to hypergraphs, and MinLA is NP-hard (Garey--Johnson--Stockmeyer 1976).

Some research has been done on solving MinLA, both exactly and approximately. There's a Theta(2^nm)-time dynamic program (Koren--Harel 2002) that looks generalizable. There's a lot of work on linear programming relaxations, both to obtain guaranteed approximations and for use in branch-and-bound. Unfortunately, these relaxations all seem to be rather too large for direct consumption by a solver. Probably someone's tried constraint programming, but my cursory searches turned up nothing. There are many heuristics, including the following cute idea due to Juvan and Mohar (1992): sort the labels according the second eigenvector of the Laplacian.

With only 50 labels, I wouldn't be surprised if a provably optimal arrangement could be found, but I would be surprised if it didn't take several rounds of novel algorithm design, implementation, and experiments on the instance(s) of interest. If you want to learn some of the techniques involved, I would recommend Pascal van Hentenryck's Discrete Optimization course on Coursera (I took an earlier version from when he was affiliated with Brown University).

---

One solution (there likely is a faster one). Is by doing partial brute force.

If you treat each switch as a set, the intersection of all sets (ie switches) could be bunched first.

Having the following enum:

enum example {
    EX_A,
    EX_B,
    EX_C,
    EX_D,
    EX_E
};

And these two switch statements:

enum example a, b;

switch (a) {
case EX_A: /* ... */
case EX_C: /* ... */
case EX_E: /* ... */
default: /* ... */
}

switch (b) {
case EX_B: /* ... */
case EX_D: /* ... */
case EX_E: /* ... */
default: /* ... */
}

The intersection is:

{ EX_E }

and the remaining elements are:

{ EX_A, EX_B, EX_C, EX_D }

So you can put the intersection first, and go through all permutations of the rest and generate all the jump tables and see which one is the smaller one. This is n! (in this example you would have to look at 4! = 24 configurations).

链接地址: http://www.djcxy.com/p/15634.html

上一篇: Eclipse库中的Android应用程序的Android库项目

下一篇: 如何优化跳转表的大小？