View mode: basic / threaded / horizontal-split · Log in · Help
April 12, 2010
Re: value range propagation for _bitwise_ OR
On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger <jeberger@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
April 12, 2010
Re: value range propagation for _bitwise_ OR
On Mon, 12 Apr 2010 13:56:23 -0400, Jérôme M. Berger <jeberger@free.fr>  
wrote:

> 	Here's a fast 100% precise solution:
>
> ==============================8<------------------------------
> uint32_t maxOr (uint32_t minA, uint32_t minB,
>                 uint32_t maxA, uint32_t maxB)
> {
>    assert (minA <= maxA);
>    assert (minB <= maxB);
>
>    if (maxA == 0) return maxB;
>    if (maxB == 0) return maxA;
>
>    uint32_t a = maxA ^ minA;
>    if (a != 0) {
>       a = ((1 << (highbit (a)+1)) - 1) & maxA & maxB;
>       if (a != 0)
>          a = (1 << highbit (a)) - 1;
>    }
>
>    uint32_t b = maxB ^ minB;
>    if (b != 0) {
>       b = ((1 << (highbit (b)+1)) - 1) & maxA & maxB;
>       if (b != 0)
>          b = (1 << highbit (b)) - 1;
>    }
>
>    return maxA|maxB|a|b;
> }
> ------------------------------>8==============================


Fails for test case:

minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).

I'm not quite sure what you are trying to do, but I think you are on the  
right path to getting a faster solution.

-Steve
April 12, 2010
Re: value range propagation for _bitwise_ OR
Steven Schveighoffer wrote:
> On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger <jeberger@free.fr>
> wrote:
> 
>>     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.
> 
	And when we're talking about the difference between 10s and 55s for
a minimal loss of accuracy, which will you take? Especially if the
accuracy loss is less than is lost elsewhere (due to holes in the
ranges).

>>
>>     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 :)
> 
	:)

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
April 12, 2010
Re: value range propagation for _bitwise_ OR
Steven Schveighoffer wrote:
> Fails for test case:
> 
> minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).
> 
	Nope, outputs 6. Note that I've run an exhaustive search for all
combinations in the [0, 63] range, so if there are mistakes they
have to be outside that range...

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
April 12, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger wrote:
> Steven Schveighoffer wrote:
>> Fails for test case:
>>
>> minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).
>>
> 	Nope, outputs 6. Note that I've run an exhaustive search for all
> combinations in the [0, 63] range, so if there are mistakes they
> have to be outside that range...
> 
> 		Jerome

I confirm. Jerome's code passes my randomized test.

Ali
April 13, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger Wrote:

> Steven Schveighoffer wrote:
> > Fails for test case:
> > 
> > minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).
> > 
> 	Nope, outputs 6. Note that I've run an exhaustive search for all
> combinations in the [0, 63] range, so if there are mistakes they
> have to be outside that range...
> 

I'll have to double check, I thought I copied your code verbatim (I did switch around the arguments to be minA, maxA, minB, maxB to fit my test harness, and I changed the uint_32_t to uint).  I'll check tomorrow at work where the computer I used to test is.

-Steve
April 13, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger Wrote:

> Steven Schveighoffer wrote:
> > When we're talking about the difference between O(1) and O(lgn), I'll
> > take accuracy over speed in my compiler any day.
> 	And when we're talking about the difference between 10s and 55s for
> a minimal loss of accuracy, which will you take? Especially if the
> accuracy loss is less than is lost elsewhere (due to holes in the
> ranges).

Really?  You rebuilt the compiler with your range propagation algorithm and verified that it adds 10 seconds versus an accurate one that adds 55s?  How much time did the compiler spend to compile?  I'd hazard to guess that a code base that adds 10s worth of your algorithm takes at least a few hours to compile.  Is 55s that bad at that point?

Again, if it takes the compiler an extra insignificant amount of time to be more accurate, I'm all for accuracy over speed when you get down to that level of insignificance.  I'd say the point of pain has to be at least 10% of the compile time before it makes any sizable difference.

-Steve
April 13, 2010
Re: value range propagation for _bitwise_ OR
Steven Schveighoffer Wrote:

> I'll have to double check, I thought I copied your code verbatim (I did switch around the arguments to be minA, maxA, minB, maxB to fit my test harness, and I changed the uint_32_t to uint).  I'll check tomorrow at work where the computer I used to test is.
> 

I think I see the issue, I was using an older version of your highbit, at some point you changed it, but didn't repeat it in this solution, so I searched for it on the newsgroup and found your first version.  That differs from later versions you posted, but I can't find where you identified there was a bug.

I'll test again tomorrow, but it looks like that probably accounts for the problem.

The version I was using: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108788

The later version: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108855

It looks like in that second post that Ali had the same problem I did.

Next time, you should include your whole code each time, especially parts you changed.

-Steve
April 13, 2010
Re: value range propagation for _bitwise_ OR
On 12-apr-10, at 21:40, Steven Schveighoffer wrote:

> On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger  
> <jeberger@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 :)

Sorry for the probably stupid question, but I don't understand much  
the need of all this range propagation, in the compiler either you  
have a a constant (and then you have the value at compile time, and  
you don't need any range propagation, you can compare with the value),  
or you have a runtime value.
Do you want to explicitly add in the compiler the support for more  
limited runtime values?
Otherwise the range of a runtime value is a priori the whole possible  
range, and thus any rule based on range propagation might be expressed  
as static type based rule (as done in C).
You can gain something for example you can know that summing 4 shorts  
you will never overflow an int, is this where you want to go?
What kind of bugs you are trying to avoid? Or is it simply having the  
max and min properties defined?

Nobody commented on my proposal, but there I see the potential for  
bugs (1u-2)+1UL is 4294967296 and this happens also at runtime if you  
have, for example, a function returning size_t and another returning  
uint, and you combine them without thinking much and then you switch  
to 64 bits...

There I see a problem, but this you see without any special range  
propagation, just thinking that subtraction or negation of unsigned  
types is modulo 2^bit size, and thus cannot be then changed to another  
size without explicit cast.
Maybe in some cases using enums range propagation might spare a cast,  
but is it really an improvement?
I guess that I am missing something obvious, so I don't see the reason  
for range propagation, but maybe I am not the only one, so thanks for  
an explanation...

Fawzi
April 13, 2010
Re: value range propagation for _bitwise_ OR
Fawzi Mohamed:
> I guess that I am missing something obvious, so I don't see the reason  
> for range propagation, but maybe I am not the only one, so thanks for  
> an explanation...

Range propagation can improve the situation a little, so it's not bad. But it can't replace proper integral overflows. You need integral overflows at runtime.

Bye,
bearophile
2 3 4 5 6 7 8 9
Top | Discussion index | About this forum | D home