CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 4 1234 LastLast
Results 1 to 15 of 53
  1. #1
    Join Date
    Feb 2013
    Posts
    58

    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,042

    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
    58

    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
    58

    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 21st, 2013 at 12:31 AM.

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

    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
    58

    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
    576

    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; July 24th, 2014 at 11:15 AM.

  10. #10
    Join Date
    Feb 2013
    Posts
    58

    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.

  11. #11
    Join Date
    Jul 2013
    Posts
    576

    Re: IF-free conception.

    Quote Originally Posted by S@rK0Y View Post
    [b]
    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.
    I certainly hope the "epoch of readable code" isn't over but has just begun.

    I prefer to trust the systems software to make my highlevel (and hopefully readable) code run efficiently on any target system. But of course there's a need for specialists who develop the optimizing compilers, libraries and runtime systems necessary to make this happen. It's just that this isn't a job for the average application programmer. It should be left to the experts. I think this separation of concerns is important and has served us well.

    Application programmers spend too much time already micro-optimizing code. It's very counterproductive. Rather than worrying about branching mispredictions and the likes one should instead learn how to write conconcurrent code properly using the new features of C++ 11 and Java 8 for example. That's a better way to utilize modern hardware and it's guaranteed to have real impact on performance.

    Note I'm not saying it's wrong to discuss the topic you brought up. But I know there's a certain lure to micro-optimizations that programmer's find hard to resist so I think it's fair to issue a warning. They are very unlikely to make your code faster so they're a waste of time. Application programmers should concentrate on the big picture and leave the details to the systems software.
    Last edited by razzle; July 25th, 2014 at 12:37 AM.

  12. #12
    Join Date
    Feb 2013
    Posts
    58

    Post Re: IF-free conception.

    well, Razzle, let's try to cross our t's at least for a little of possible ones. state-of-the-art hardware has 6-way approach to speed-up algos:

    1. multi-threading.
    2. 3OE (out-of-order execution).
    3. caching.
    4. lessen the number of conditional jumps.
    5. usage of cpu's registers as global vars.
    6. vectorizing.
    ===============
    in short, multi-threading is Just fraction of existed tools. 2nd moment, i don't believe in smarty compilers because we need to get highly-advanced AI to gain really smart ones. even if it'll become possible, why'll we (programmers) be necessary for World then???

  13. #13
    Join Date
    Jul 2013
    Posts
    576

    Re: IF-free conception.

    Quote Originally Posted by S@rK0Y View Post
    in short, multi-threading is Just fraction of existed tools.
    Multi-threading was just an example because I think the multiple cores of modern hardware has great potantial for substantial application performance improvements but hasn't been fully utilized so far. But, it doesn't require the hardware specific programming you're advocating. In fact none of the aspects of your 6-way approach does. Ordinary high-level programming is good enougth and the latest versions of most modern languages are offering that.

    The ambition to produce lean and mean code is better channelled into complexity reduction of general high-level code. This is where programmers will always be needed, not to "help" systems software handle the hardware of the day.

    Thank you for this discussion.
    Last edited by razzle; July 25th, 2014 at 05:26 PM.

  14. #14
    Join Date
    Feb 2013
    Posts
    58

    Re: IF-free conception.

    Multi-threading was just an example because I think the multiple cores of modern hardware has great potantial for substantial application performance improvements but hasn't been fully utilized so far. But, it doesn't require the hardware specific programming you're advocating.
    Razzle, yes, multi-threading can be exploited w/o low-level programming. however, MT has a lot of troubles for developers: you have to sync concurrently-running objects & this moment (in many cases) can ruin the performance of your algo. For instance, you deal w/ N simultaneously-running objects, thereby there could be at least 2^N handlers to manage them. Just for clarity's sake, why number of handlers gets that high. let's we have A, B, C concurrently-doing objects, each of them has flags of current status:

    1. doing the given task.
    2. waiting.
    3. done.
    4. not answering.
    5. crashed.
    ==========================
    (as you can see) even w/ no extra details, we get a lot of states. in our example, three-flag switcher is gotten, each flag got 5 states -- in result, switcher takes about 5^3 (125) states. in short, developer must crawl through all that abomination to heal any bottleneck in code.

    But, it doesn't require the hardware specific programming you're advocating. In fact none of the aspects of your 6-way approach does.
    no, ill-constructed code has a lot of cache-missing, branch misprediction, zeroed 3OE, huge heap of garbage instructions in Asm-listing as well. De-facto hardware-independent algos don't & can't exist. it's very error of modern education to teach students abstract algos, written in pseudo-codes. real HPC is only hardware-friendly.
    Thank you for this discussion.
    You're welcome.

  15. #15
    Join Date
    Jul 2013
    Posts
    576

    Re: IF-free conception.

    Quote Originally Posted by S@rK0Y View Post
    yes, multi-threading can be exploited w/o low-level programming. however, MT has a lot of troubles for developers:
    I never claimed concurrency was a free lunch. But it certainly is best handled at high level. The ideal is a lock free design but even if you don't get all the way you can most certainly do much better than the naive 2^N design you mention where everything is communicating with everything else in a total jumble. Trying to prop up a bad design with hardware micro-optimizations is the wrong approach. It just makes things worse.

    no, ill-constructed code has a lot of cache-missing, branch misprediction, zeroed 3OE, huge heap of garbage instructions in Asm-listing as well. De-facto hardware-independent algos don't & can't exist. it's very error of modern education to teach students abstract algos, written in pseudo-codes. real HPC is only hardware-friendly.
    I think modern hardware should be taught to programmers and it's a sad fact that many programmer don't even know how a computer works so I agree that education has a job to do here. But that doesn't imply that hardware specific optimizations should be the main focus of programming.

    A programming language is a specification of an abstract computer and programs can be written in it even though a physical computer may not even exist. This is the fundamental idea behind high level languages so certainly hardware-independent algorithms exist. Of course to be practical the language must be implemented on concrete hardware and this is best done by a solid layer of systems software. It should not be punctured by worm-holes opened up by micro-optimizing programmers. This seldom increases efficiency but it always causes code decay.
    Last edited by razzle; July 26th, 2014 at 12:03 PM.

Page 1 of 4 1234 LastLast

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
  •  





Click Here to Expand Forum to Full Width

Featured