value range propagation for _bitwise_ OR

[Steven Schveighoffer]

On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger <jeberger at free.fr>  
wrote:

> Steven Schveighoffer wrote:
>> J�r�me M. Berger Wrote:
>>
>>> J�r�me M. Berger wrote:
>>>> 	OK, I found a solution that is optimal in over 99% of the cases
>>>> (99.195% to be precise), while still being fast (because it avoids
>>>> looping over the bits):
>>>>
>>> 	I've run my function and Andrei's on all possible min, max pairs in
>>> 0..299 without checking, just for the timing. On my computer (Athlon
>>> X2 64 @2GHz), my function took 50s and Andrei's took 266s. The
>>> difference should be even bigger for larger numbers.
>>
>> Can I ask, what is the point of having a non-exact solution (unless you  
>> are just doing this for fun)?
>>
>> We are talking about range propagation, a function of the compiler, not  
>> a function of the compiled program.  Therefore, slower but more exact  
>> functions should be preferred, since they only affect the compile  
>> time.  Note that you will only need to do this range propagation on  
>> lines that "or" two values together, and something that reduces the  
>> runtime of the compiler by 216 seconds, but only when compiling enough  
>> code to have over 8 billion 'or' operations in it (300^4), I don't  
>> think is really that important.  Give me the exact solution that  
>> prevents me from having to cast when the compiler can prove it, even if  
>> the runtime of the compiler is slightly slower.
>>
> 	Funny you should say that given the current thread comparing the
> speed of the D compiler to that of the Go compiler...

My point was simply that the amount of time saved is relative to the size  
of the program being compiled.  If we assume conservatively that every  
other line in a program has bitwise or in it, then you are talking about a  
16 billion line program, meaning the 216 seconds you save is insignificant  
compared to the total compile time.  My point was that your fast solution  
that is inaccurate is not preferable because nobody notices the speed,  
they just notice the inaccuracy.

> 	We are talking about range propagation, a function of the compiler,
> not a function of the compiled program. Since we can't get a 100%
> accurate representation of the possible values anyway (even yours
> might leave holes in the middle after all), then it might be better
> to choose a faster, slightly less precise algorithm if the
> difference is not too great. That's the difference between a
> compiler and a full-fledged static code analysis an program prover.

When we're talking about the difference between O(1) and O(lgn), I'll take  
accuracy over speed in my compiler any day.  The solution should be 100%  
accurate for the problem statement.  If the problem statement is not what  
we need, then we need a new problem statement :)  Solving the problem  
statement for 99% of values is not good enough.

>
> 	Anyway, the point is moot, I have a new version of my algorithm
> with 100% precision and high speed.

Yes, I'm still trying to understand how it works :)

-Steve