Hi all!

I collected some statistics for SwitchInst, based on our test-suite.

I found that efficiency is meaningful for parser-like applications only, about 15-20% of cases may be reduced (see top 10 items in Raw sheet of attached .xls file).

Below some numbers.

Total number of cases in all test-suite -- 11835.

Clusters possible to make -- 503

Clusters with size (H - L) + 1 >= 8 -- 48

Cases stay single numbers -- 9794

% of all cases may be clustered -- 17.2%

% of all case comparisons may be reduced -- 4.6%

For example if 3 cases turned into cluster with size 3, it means that we reduce 1 comparison. If only 2 cases turned into cluster with size 2, we reduce nothing, since we still need two comparisons: L <= Value and H >= Value.

Average number of switches in application is 1.07.

Average number of cases is 6.4.

How I calculated comparisons-may-be-reduced number.

In spreadsheet file GE3 means cluster with size (H-L+1) greater or equal 3.

Based on number of clusters GE3, GE4, GE8, I calculated number of clusters with

-- size >= 4 and < 8: CLUSTER4_7 = GE4-GE8.

-- size == 3: CLUSTER3 = GE3-GE4

-- size == 2: CLUSTER2 = AllClusters-GE3

Based on assumption that CLUSTER3 allows to reduce 1 comparison, CLUSTER4 allows to reduce 2 comparisons and so on, I calculate lower bound of number of comparisons possible to reduce:

CR = CLUSTER_GE8*6 + CLUSTER4_7*2 + CLUSTER3

where

CLUSTER_GE8 means number of clusters with size H-L+1 >= 8

Spreadsheet (.xls file in .tgz) with statistics data and patch with harness that collects data are in attachment.

How to generate statistics.

1. Apply patch in attachment to clang sources.

2. Go to CompilerInstance::ExecuteAction, setup SwitchStatisticsFileName value.

3. Compile clang.

4. Run test-suite.

5. After test-suite finished the statistics file is ready to use.

P.S.: Of course you may run *any* program with patched clang and look at statistics then.

-Stepan.

switch-statistics.patch (17.1 KB)

Switch-Statistics.tgz (73.6 KB)