loop trick

Discussion in 'Programming & Software Development' started by Luke212, Jul 22, 2007.

  1. akashra

    akashra Member

    Joined:
    Apr 25, 2003
    Messages:
    3,910
    Location:
    Melbourne, AU
    Once again, you fail at programming.
    In fairness though, 98% of programmers/developers these days are useless when it comes to writing fast code. I certainly didn't learn it from uni - probably why in a uni assignment where you mark was based on the speed at which your application ran compared to the rest of the class, mine had to be excluded as it was twice as quick as the next best - which was about 10 times quicker than the average - fortunately I have a background dealing with serial communications, which has to be incredibly optimized.

    But even the uArch stuff they teach these days is crap. People learn jack about uOps and speed. Most wouldn't even know the benefits (and restrictions) of using registers.

    I was going to back off, but once I saw your followup posts, it just reminded me of what a clown you are.
    If you can't tell the difference between what 3 and 2 cycles is going to do in a tight loop, you need to find another profession.

    Oh but according to mordy we just need to throw more processing power at it, not make better use of the equipment we have.
    Never mind the fact that we have 160 blades running our current app.

    My current job is to get our renders from 750ms down to sub 100ms. Shared across dozens of blades, that's a truckload more output. Too bad at some point fibre channel just isn't fast enough :(
     
  2. mordy

    mordy Member

    Joined:
    Aug 30, 2001
    Messages:
    5,100
    Location:
    melb
    akashra, we arent talking about the same thing at all.

    Ur talking about super-optimised server applications where every ms does count, I was talking about desktop apps (the ones written high level, like in lukes post c#) where if you optimise your algorithm, you have an app which is just fine.

    further optimising such an application is a waste of time, using assembly hacks etc really gives you nothing except trouble mantaining the solution at a later time.

    Obviously I wasnt insinuating that something like apache or a dbms shouldnt be optimised, thats just stupid.
     
  3. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    You know what is also stupid?

    Making statements without considering the corner cases. I used to have a bit of fun whilst at uni helping other students debug and test their code. I generally used to find corner cases they hadn't considered.
     
  4. mordy

    mordy Member

    Joined:
    Aug 30, 2001
    Messages:
    5,100
    Location:
    melb
    Servers arent a corner case, theyre a completely different class of software.

    Writing for 1 user is a completely different thing to writing applications for hundreds of similtaneous users.
     
  5. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    Yet they are still software.

    What you have to consider is that not all software is the same as the stuff in mordyworld. I can name plenty of desktop applications that can always do with more speed.
     
  6. Elyzion

    Elyzion Member

    Joined:
    Oct 27, 2004
    Messages:
    7,449
    Location:
    Singapore
    I can name one!!!! Windows!!!
     
  7. mordy

    mordy Member

    Joined:
    Aug 30, 2001
    Messages:
    5,100
    Location:
    melb
    haha, am i right in saying that even the fastest computer in the world cant run windows vista normally.


    All you are doing is giving examples of the software that i mentioned which would need optimising, which makes sense because there is alot of software that would benefit from exact speed gains.

    On the other hand, your mp3 cataloguing app or your label maker app doesnt need optimised for loops, thats just a waste of time.
     
  8. Elyzion

    Elyzion Member

    Joined:
    Oct 27, 2004
    Messages:
    7,449
    Location:
    Singapore
    My mp3 renaming app rocks!!!

    Regular Expression capturing is awesome.

    I'm writing my own BBCode script at the moment. Was working on it last night and got it working and decided to check the internet to see how they did
    Code:
     and found out what i had written was almost identicle to whats on the net, minus varible names and such. :(
    
    Trying to think if theres another way to write it now. I'm gonna add in a Syntax Highlighter http://code.google.com/p/syntaxhighlighter/ with it tho and a few other things that i wish were in BBCode.
    
    Oh in my App i wrote in (im newbie at windows apps cos ive only really delt with web/console stuff) the process bar but because its only looping through like 15 items 3 times each its pretty much instant. Only get to see the process bar work when its processing like 100+
     
  9. OP
    OP
    Luke212

    Luke212 Member

    Joined:
    Feb 26, 2003
    Messages:
    10,041
    Location:
    Sydney
     
  10. Elyzion

    Elyzion Member

    Joined:
    Oct 27, 2004
    Messages:
    7,449
    Location:
    Singapore
    Each file that is updated is looped through 3 times (depending on the format its checking for).

    So i update after each file is done it updates. So if there was 10 files. It loops a total of 30 times but updates 10 times. If that makes sense.

    It's just that it loops them so fast because its not complex or anything. If i have 20 files i can see it update twice :)
     
  11. GumbyNoTalent

    GumbyNoTalent Member

    Joined:
    Jan 8, 2003
    Messages:
    9,743
    Location:
    Briz Vegas
    Any software that requires large number crunching can always be improved with optimized code.

    e.g. graphically intense computer games.
     
  12. mordy

    mordy Member

    Joined:
    Aug 30, 2001
    Messages:
    5,100
    Location:
    melb
    the main executable will usually be optimised in assembly to get the frame-buffer to spit out the maximum fps.
     
  13. xsive

    xsive Member

    Joined:
    Jun 29, 2001
    Messages:
    4,343
    *sigh*
    From a software engineering standpoint this is a horrid abuse of tooling to get the job done. At best it's a hack; a temporary hack that noone should ever see and that should never make it into production code.

    As a specific optimisation technique for high performance computing it's pretty stupid also. The example given is a toy problem with highly limited real-world uses. The performance wins are pretty damn trivial in comparison to the kind of work a real scientific alg has to go through.
    As you should be well aware, there are many other things you can do to optimise a program before resorting to such futile efforts as optimising away bounds checking. The thing that gets me the most is that the OP seems to have no appreciation of how this stuff actually works -- someone very astutely pointed out earlier that *something* still has to do the bounds checking which is spot on. The compiler most likely makes use of similar techniques to the ones I linked to earlier (like 'cash' or segmentation hardware) to optimise these bounds checks which is why the improvement is so small. The number of checks also isn't very high to begin with -- branch prediction is pretty fricking efficient in most modern CPUs so that helps to alleviate the problem also.

    Finally, I'm kinda dismayed that a seemingly seasoned and experienced programmer would encourage such hacks instead of using the right tool for the job. If you need fine-grain control over what is executed you don't use a high-level language!

    Gah!
     
  14. OP
    OP
    Luke212

    Luke212 Member

    Joined:
    Feb 26, 2003
    Messages:
    10,041
    Location:
    Sydney
    the run-time management will occur whether you like it or not, so your choice is either 1 limit check or 2.

    should we show people how to write conditional statements to minimise prediction misses?


    i already said i was hard pressed to find a use for it.

    if you want to get ahead in the business, often you need to use the skills available to you, and not to lay down jobs to the so called low-level development houses.
     
  15. akashra

    akashra Member

    Joined:
    Apr 25, 2003
    Messages:
    3,910
    Location:
    Melbourne, AU
    yield(), you hungry bastard :p
     
  16. akashra

    akashra Member

    Joined:
    Apr 25, 2003
    Messages:
    3,910
    Location:
    Melbourne, AU
    Eventually you're going to realize that in the real world, management inevitably makes stupid decisions in to which you have no say.
    For those, you have to deal with the situations the best you can.

    Not to mention often low-level code means writing for a specific processor. Here, we write software for PowerPC 5 (Mac G5s), Intel, and Sparc (mmmmm, T1000) based systems.
     
  17. OP
    OP
    Luke212

    Luke212 Member

    Joined:
    Feb 26, 2003
    Messages:
    10,041
    Location:
    Sydney
    yeah kinda ironic ;)

    hmm what next? ;)

    DoEvents: Is DoEvents Evil?

    best solution is: Thread.CurrentThread.Interrupt();
     
    Last edited: Jul 25, 2007
  18. xsive

    xsive Member

    Joined:
    Jun 29, 2001
    Messages:
    4,343

    If you want to get ahead in the programming trade you should learn to use the tools at your disposal. I started looking into this issue in any depth for the first time tonight. It took me all of 5 minutes to confirm that both HotSpot and .NET optimise away range checking when the compiler can prove that the array is within bounds.

    It speaks very poorly for you, as a programmer, to start a thread offering optimisation advice to others when you yourself don't understand what the code you wrote is doing. It's worse that you actively promote such horrendously bad practice when you can get better performance for free using a simple for loop.

    See for yourself.

    Run #1
    done (with exceptions). time: 2.166
    done (no exceptions). time: 1.942
    Press ENTER or type command to continue

    Run #2
    done (with exceptions). time: 2.261
    done (no exceptions). time: 1.977
    Press ENTER or type command to continue

    Run #3
    done (with exceptions). time: 2.078
    done (no exceptions). time: 1.977

    Code:
    class bench
    {
    
            public static void main(String args[])
            {
                    try {
                            throw new Exception();
                    }
                    catch(Exception e)
                    {
                            e=e;
                    }
    
                    int size = 500000000;
                    boolean[] b = new boolean[size];
                    long start = System.currentTimeMillis();
                    try
                    {
                            int c=0;
                            while(true)
                            {
                                    b[c] = true;
                                    c++;
                            }
                    }
                    catch(Exception e)
                    {
                            e=e;
                    }
                    long end = System.currentTimeMillis();
                    System.out.println("done (with exceptions). time: "+(end-start)/1000.0);
    
    
                    b = new boolean[size];
                    start = System.currentTimeMillis();
                    for(int i=0;i<b.length;i++)
                    {
                            b[i]=true;
                    }
                    end = System.currentTimeMillis();
                    System.out.println("done (no exceptions). time: "+(end-start)/1000.0);
            }
    
    }
    
     
  19. OP
    OP
    Luke212

    Luke212 Member

    Joined:
    Feb 26, 2003
    Messages:
    10,041
    Location:
    Sydney
    When i read that article i thought we both may have learned something new. Ive always read .Length is the slowest. However, in practise .Net 2 doesnt seem to be optimising the .Length statement. And if it isnt, it will be slower because of an extra operation.

    I've already mentioned previously why your code is wrong.

    Here are the results:

    for-loop with 500000000: 2.59
    for-loop with .Length: 2.62
    exception: 2.30

    the results are consistent discarding run #1
     
  20. xsive

    xsive Member

    Joined:
    Jun 29, 2001
    Messages:
    4,343
    Just for you, I re-organised my code to more to equivalently match yours. I went one better and separated out each test, removed code re-creating the array before each test (I had this in originally to remove caching benefits) and I even put your exception hack last in the tests being executed just so it's not somehow hampered.

    Heres's another 4 runs of the new code (excluding run #1)
    Press ENTER or type command to continue
    done (with exceptions). time: 2.23
    done (no exceptions). time: 2.155
    done (no exceptions; const). time: 2.094

    Press ENTER or type command to continue
    done (with exceptions). time: 2.098
    done (no exceptions). time: 2.014
    done (no exceptions; const). time: 2.242

    Press ENTER or type command to continue
    done (with exceptions). time: 2.078
    done (no exceptions). time: 2.0
    done (no exceptions; const). time: 2.392

    Press ENTER or type command to continue
    done (with exceptions). time: 2.11
    done (no exceptions). time: 2.038
    done (no exceptions; const). time: 2.605

    The results are spot on with what one would expect; We see a small overhead from using the exception (when it falls over and needs to be handled) vs the optimised for-loop and finally an overhead associated with the re-introduced bounds checking because the compiler can't confirm the value of the array index upper-bound (since we pass it as a param).

    NB: It's worth mentioning the variation between results; I suspect this is because of paging effects stemming from the insanely large data structure being iterated over.

    I can only surmise something is wrong with your testing methodology or .net configuration. I can confirm the behaviour for HotSpot. I'm on leave at the moment so I don't have access to .NET but I don't see why MS would remove such an optimisation.

    I'll leave it as an excercise to your programming prowess to figure out what is happening on your machine and why it's not behaving as described.

    Code:
    class bench 
    {
    
    	public static void main(String args[]) 
    	{
    		throwStuff();
    
    		int size = 550000000;
    		boolean[] b = new boolean[size];
    		double hacktime = runHack(size, b);
    		double consttime = runConst(size, b);
    		double lengthtime = runLength(size, b);
    
    		System.out.println("done (with exceptions). time: "+hacktime);
    		System.out.println("done (no exceptions). time: "+lengthtime);
    		System.out.println("done (no exceptions; const). time: "+consttime);
    	}
    
    	public static void throwStuff() 
    	{
    		try {
    			for(int i=0;i<10;i++) 
    			{
    				Thread.sleep(200);
    			}	
    			throw new  Exception();	
    		}
    		catch(Exception e) { e=e; }
    
    	}
    
    	public static double runHack(int size, boolean[] b) 
    	{
    		long start = System.currentTimeMillis();
    		try 
    		{
    			int c=0;
    			while(true)
    			{
    				b[c] = true;
    				c++;
    			}
    		}
    		catch(Exception e) 
    		{
    			e=e;
    		}
    		long end = System.currentTimeMillis();
    		return (end-start)/1000.0;
    	}
    	
    	public static double runLength(int size, boolean[] b) 
    	{	
    		long start = System.currentTimeMillis();
    		for(int i=0;i<b.length;i++)
    		{
    			b[i]=true;
    		}
    		long end = System.currentTimeMillis();
    		return (end-start)/1000.0;
    	}
    
    	public static double runConst(int size, boolean[] b) 
    	{	
    		long start = System.currentTimeMillis();
    		for(int i=0;i<size;i++)
    		{
    			b[i]=true;
    		}
    		long end = System.currentTimeMillis();
    		return (end-start)/1000.0;
    	}
    
    }
    
     
    Last edited: Jul 26, 2007

Share This Page

Advertisement: