Getting rid of "if condition" by some math equation.
in [Java Programming]
|
Prev: MAKE UPTO $5000 MONTHLY! $2000 INYOUR FIRST 30 DAYS!
Next: help: enum cause failure in multi thread run
From: Sanny on 14 Jul 2010 15:11 > Or even (to micro-optimize a bit :) ): > > long xx = 0, bit = 1 << 50; > > for (int i = 0; i <= 50; i++) > { > if (Str.charAt(i) != '-') > { > xx |= bit; > } > > bit = bit >> 1; > } You are correct. I removed the above for loop to increase performance as for (int i = 0; i <= 50; i++) here "i<=50" if condition is executed So there are 2 if condition per loop. By removing the for loop I avoided one if condition. Now, I am looking for some way to use single equation/ Algebric may be to remove all if conditions. I find if conditions take 5-10 times longer than simple arithmetic works. Bye Sanny
From: Peter Duniho on 14 Jul 2010 15:22 Sanny wrote: >> I take that back. It is more complex but you still don't need all those >> if statements. >> > > I agree. I want a simple equation instead of looking for 50 if > conditions. Given the problem statement so far, you cannot avoid the comparisons. The only thing your code appears to deal with is converting a string with hyphens in it into a bitfield where each bit is set in the location corresponding to the character position with hyphens. At some point, you have to inspect the string and convert hyphens to bits. Your code, on most architectures, will cause problems for two reasons: � it has hard-coded the specific character position for each comparison, leading to the excessive length of the code, making it harder for the code to remain in the cache and for branch-prediction tables to stay filled. � it inspects the string in reverse order, which may be more likely to negate any benefit of data caching, as data is more likely to be fetched from memory address locations at and beyond that which the code is actually using. The versions of the code I posted address those issues, by making the code much more compact and (in the case of the second example), inspecting the string in the forward direction. > Simple addition/ multiplication/ division will be faster than 50 if > conditions. Java doesn't have any way to perform mathematical operations on strings. At best, you could perform mathematical operations on individual character values, but at that point you might as well just do a comparison. > Since most of the time taken is by the "if condition." You base that claim on what evidence? > I am thinking of using > > char mm='-'; > int mm1=Character.getNumericValue(mm); > > int mm2=Str.charAt(0); > > int mm3=mm2-mm1; > > Now if I subtract mm2-mm1=mm3 Then I have to have xx+=bit; only when > mm3==0; How is a subtraction and a comparison against 0 any better than a comparison against the character value for '-'? That is: if (Str.charAt(0) - mm1 == 0) { xx += bit; } Or alternatively, how is a subtraction, multiplication and unconditional addition/bitwise-or better? That is: xx += bit * (Str.charAt(0) - mm1); I fail to see why that is necessarily going to be more efficient than just doing a straight comparison. Pete
From: Peter Duniho on 14 Jul 2010 15:24 Sanny wrote: >> Or even (to micro-optimize a bit :) ): >> >> long xx = 0, bit = 1 << 50; >> >> for (int i = 0; i <= 50; i++) >> { >> if (Str.charAt(i) != '-') >> { >> xx |= bit; >> } >> >> bit = bit >> 1; >> } > > You are correct. I removed the above for loop to increase performance > as > > for (int i = 0; i <= 50; i++) here "i<=50" if condition is executed So > there are 2 if condition per loop. Loop-unrolling _may_ improve performance. But it doesn't always, and when done to an excessive degree can actually _hurt_ performance (for the reasons I mentioned elsewhere). > By removing the for loop I avoided one if condition. > > Now, I am looking for some way to use single equation/ Algebric may be > to remove all if conditions. > > I find if conditions take 5-10 times longer than simple arithmetic > works. Again, you find that how? Pete
From: Screamin Lord Byron on 14 Jul 2010 15:59 On 07/14/2010 09:11 PM, Sanny wrote: > Now, I am looking for some way to use single equation/ Algebric may be > to remove all if conditions. Like Peter said, first describe exactly what you want (in English, not Java). If you don't do that, no one will be able to help you, because I doubt anyone here can read minds. And there is no need to repeat yourself. Just describe the problem in it's entirety.
From: Patricia Shanahan on 14 Jul 2010 16:30
Sanny wrote: >> Or even (to micro-optimize a bit :) ): >> >> long xx = 0, bit = 1 << 50; >> >> for (int i = 0; i <= 50; i++) >> { >> if (Str.charAt(i) != '-') >> { >> xx |= bit; >> } >> >> bit = bit >> 1; >> } > > You are correct. I removed the above for loop to increase performance > as > > for (int i = 0; i <= 50; i++) here "i<=50" if condition is executed So > there are 2 if condition per loop. > > By removing the for loop I avoided one if condition. > > Now, I am looking for some way to use single equation/ Algebric may be > to remove all if conditions. > > I find if conditions take 5-10 times longer than simple arithmetic > works. The time for an if condition is highly variable. It can be practically nothing or very expensive, depending on whether the processor guesses correctly in deciding between fetching the instructions following the branch or the branch target. Branch predictors are designed and tested to deal well with sort of pattern that shows up with a simple for-loop. Meanwhile, your hand unrolling may be making it harder for the JVM to optimize the call to charAt. It sees 50 calls each with 1/50 of the real call frequency. I would stick with the more normal form of the code until you are completely happy with the algorithm, and keep it at least as comments even if you do find you need to do micro-optimizations such as hand unrolling. Patricia |