# IF-free conception.

Show 50 post(s) from this thread on one page
Page 1 of 4 1234 Last
• February 15th, 2013, 01:50 PM
S@rK0Y
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.
• February 16th, 2013, 07:26 AM
D_Drmmr
Re: IF-free conception.
Your code doesn't compile. You cannot multiply a pointer with an int.
• February 16th, 2013, 06:14 PM
S@rK0Y
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 :D 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
• February 20th, 2013, 01:53 AM
Coder Dave
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. :ehh:
• February 20th, 2013, 06:28 PM
S@rK0Y
Re: IF-free conception.
Quote:

Originally Posted by Coder Dave
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. :ehh:

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. :eek: 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 :)
• February 20th, 2013, 11:22 PM
Coder Dave
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? :ehh:

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. :confused:
• February 22nd, 2013, 07:39 AM
Eri523
Re: IF-free conception.
Quote:

Originally Posted by Coder Dave
Now, I bet some people, who are reading this, are thinking we are both crazy for even considering this stuff. Right? :ehh:

:lol: Errr... no. :D 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.
• July 20th, 2014, 07:02 PM
S@rK0Y
Re: IF-free conception.
i'm back, my Friends :D 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.
• July 24th, 2014, 03:28 AM
razzle
Re: IF-free conception.
Quote:

Originally Posted by S@rK0Y
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!
• July 24th, 2014, 01:50 PM
S@rK0Y
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.
• July 25th, 2014, 12:27 AM
razzle
Re: IF-free conception.
Quote:

Originally Posted by S@rK0Y
[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.
• July 25th, 2014, 02:08 PM
S@rK0Y
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:

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??? :rolleyes: ;)
• July 25th, 2014, 05:20 PM
razzle
Re: IF-free conception.
Quote:

Originally Posted by S@rK0Y
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.
• July 25th, 2014, 06:28 PM
S@rK0Y
Re: IF-free conception.
Quote:

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

Quote:

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.
Quote:

Thank you for this discussion.
You're welcome. :D
• July 26th, 2014, 12:00 PM
razzle
Re: IF-free conception.
Quote:

Originally Posted by S@rK0Y
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.

Quote:

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.
Show 50 post(s) from this thread on one page
Page 1 of 4 1234 Last