llvm dev - Jul 2012 - [LLVMdev] Statistics for 'switch' instruction.

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.









-------------- next part --------------
A non-text attachment was scrubbed...
Name: switch-statistics.patch
Type: text/x-patch
Size: 17541 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120720/e374e0cc/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Switch-Statistics.tgz
Type: application/x-compressed-tar
Size: 75316 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120720/e374e0cc/attachment-0001.bin>

Hi Stepan,

These are quite interesting numbers. Thanks for running this experiment!
Do you have some numbers on the difference of memory consumption and  
compile time (at -O0 and -O2) with and without case ranges?  I think  
we need to see those numbers before we can decide wether it's  
interesting to commit to case ranges or not.

Thanks,
Nuno


Quoting Stepan Dyatkovskiy <stpworld at narod.ru>:
> 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.

Hi,

You cannot call removeModule on a JIT with no modules: jitstate will be 
0 and therefore we have a null-pointer exception.
The function returns a boolean for success/failure, however, so you 
would expect to be able to call it and get false back.

Should we be checking for jitstate != 0 before accessing the variable?

-  if (jitstate->getModule() == M) {
+  if (jitstate && jitstate->getModule() == M) {


  Verena