IF-free conception.
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: IF-free conception.

  1. #1
    Join Date
    Feb 2013
    Posts
    7

    IF-free conception.

    Good Time to all, Amici(Friends).

    Here, i'd like to discuss how to reduce conditional branches in the code. 1st of the all, i would like to share some tricks. Their description is here
    -----------------------
    Thanks in Advance for attention of Yours.

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,011

    Re: IF-free conception.

    Your code doesn't compile. You cannot multiply a pointer with an int.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  3. #3
    Join Date
    Feb 2013
    Posts
    7

    Re: IF-free conception.

    D_Drmmr, code in the blog cannot be compiled because pointers must be casted to integers, then sum of addresses is casted back to pointer. actually, it's all done in the source. But(!) i used trick w/ pointers only for experiment's sake -- don't use it there is the way w/ no messy pointers:
    Code:
     
    empty=a[root];
    a[root]=i2*a[child] + i1*a[root];
    a[child]=i2*empty +  i1*a[child];
    simpler & faster. ;D

  4. #4
    Join Date
    Feb 2013
    Location
    United States
    Posts
    56

    Re: IF-free conception.

    Your IF-free concept seems to be a lose-lose situation.

    Not only would your examples execute more slowly, but their cryptic nature means they take much more time to develop and maintain.

    I see what you are doing by multiplying by either a 1 or 0, but multiplications take more clock cycles than a simple comparison and branch.

    Now, regarding the following example:
    Code:
    for(int i=0; i<N; i++){
    if(A[i])a[i]++;
    }
    Whether or not this could be implemented faster without an if statement depends on how the code gets compiled and how much time it takes to access memory. For example, assuming A represents an array of booleans that are mostly false, the increment instruction would rarely be executed. If this were to be implemented without an if statement, every value in the a array would have to read and written even though they do no change.

    If execution time is that critical to you, then you should be programming in assembly. The assembly code may even be easier to read than your pointer multiplications.

  5. #5
    Join Date
    Feb 2013
    Posts
    7

    Re: IF-free conception.

    Quote Originally Posted by Coder Dave View Post
    Your IF-free concept seems to be a lose-lose situation.

    Not only would your examples execute more slowly, but their cryptic nature means they take much more time to develop and maintain.
    Hi, Dave. here we got really comic situation: at C-level, it's if-free code, but compilers provide horrible amount of conditional jumps in the Asm output. in short, i see only solution: to write Asm code for truly if-free result, otherwise app has been about 10X-100X slowly than must be

  6. #6
    Join Date
    Feb 2013
    Location
    United States
    Posts
    56

    Re: IF-free conception.

    Hi S@rKOY. I think I understand what you mean about compilers creating a large number of conditional jumps when you have a switch instruction followed by many cases. Depending on the case values, a better solution would be for the compiler to create a jump table that is indexed by the case values. I have looked at the assembly code for some executables and sometimes the compiler has done this. I guess it depends on the compiler and what optimizations are turned on.

    When we use higher level languages, we trade control for shorter development times. Higher level languages seem to produce less efficient code. This is at least true for Java and .NET languages. I guess C++ is still a very popular programming language because it is sort of in the middle. It is not tedious like assembly, but you still get to work with pointers and type casts, both very powerful programming constructs.

    I have resorted to using in-line assembly myself because C++ does not provide a way to branch three different ways for one comparison. In C++ and other languages, a condition is either true or false, so either one chunk of code gets executed or another chunk gets executed. If you need more done, more comparisons are needed. In assembly, when you compare two values, say A and B, you can jump one way if A is less than B, another way if A is greater than B, and yet another way if A is equal to B. (Of course, the third jump is not needed since the instruction address will just fall through the other conditional jumps.)

    Now, I bet some people, who are reading this, are thinking we are both crazy for even considering this stuff. Right?

    In some applications were calculations need to be made millions of times per second, such as applications that render 3D graphics in real-time, seemingly little things can add up. So there are real applications for this stuff. But do not do this stuff solely because you can. Cryptic code can be very frustrating to read and understand, even when you were the one who wrote it.
    Last edited by Coder Dave; February 20th, 2013 at 11:31 PM.

  7. #7
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,583

    Re: IF-free conception.

    Quote Originally Posted by Coder Dave View Post
    Now, I bet some people, who are reading this, are thinking we are both crazy for even considering this stuff. Right?
    Errr... no. I mean, at least not everyone does.

    Here's a rather in-depth discussion of the switch statement, including a hands-on excaple of the machine code the VC++ compiler generates out of it: http://forums.codeguru.com/showthrea...ething-better! Perhaps it's interesring with regard to this thread.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  8. #8
    Join Date
    Feb 2013
    Posts
    7

    Re: IF-free conception.

    i'm back, my Friends here (http://alg0z.blogspot.ru/2014/07/fas...-vs-qsort.html) is very nutty-freaky, but fast code. i'd like to see benchmarks on your hardware. Thanks a lot in advance.

  9. #9
    Join Date
    Jul 2013
    Posts
    204

    Re: IF-free conception.

    Quote Originally Posted by S@rK0Y View Post
    Here, i'd like to discuss how to reduce conditional branches in the code.
    Branch reduction is fine if the purpose is to lay down cleaner and leaner code but there's a risk to it. You may start feeling an urge to remove every branch in sight using all sorts of obscure tricks turning your code into a complete mess.

    Okay, if you identify a performance bottleneck caused by branching mispredictions then by all means fix it with some dirty coding. But doing it routinely everywhere to "help" the systems software is very counterproductive. Branch reduction is like a drug to the typical programmer personality so beware.

    But I do see the advantages of if-free conception. How convenient to have a fitting name already when the stork delivers the baby!
    Last edited by razzle; Today at 11:15 AM.

  10. #10
    Join Date
    Feb 2013
    Posts
    7

    Re: IF-free conception.

    Razzle, 1st of the all, Thanks for your reply. Frankly, Epoch of readable codes was passed by: we have a lot of ways to speed-up our codes thanks to modern hardware, but high-level programming has no ways to utilize all-that features at full scale. We must write hardware-friendly algos to step upon highest performance. Yes, of course, here we have encountered with sad fact of severe lack of specialists to maintain that paradigm. if this problem will not be solved, hi-tech's stagnation shall deepen. And it's only the best scenario.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center