13 replies to this topic

[Imprecision]

Hey, I have some lopps that repeat more than 1000 times.
In these loops, I use alot of new variables like so

for (int i = 0; i > 500; i++)
{
	for (int j = 0; j > 500; j++)
	{
		int foo = 0;
		int bar = 2;
		double a;
		double b;
		double c;
		double x;
		double y;
		double z;
		// Do Something
        }
}

that means to me, that I allocate new memory everytime I run trough the loop.

When done something like this:

int foo = 0;
int bar = 2;
double a;
double b;
double c;
double x;
double y;
double z;
for (int i = 0; i > 500; i++)
{
	for (int j = 0; j > 500; j++)
	{
		 // Do Something
	  }
}

isn't that pretty much faster?
Because I use the same memory for every loop, instead of allocate evertime new one?

Edited by Imprecision, 29 April 2012 - 09:10 AM.

[rip-off]

Any sane compiler will not allocate memory during the loop for this. The stack for a given function is typically "allocated" or reserved during function entry, and this adjustment will include the maximal amount of space required.

Remember, if it is a trivial and safe transformation, the compiler writers will probably have already implemented it.

Finally, are you sure you need all these variables? For optimisation, the fastest code is the code that doesn't have to run. Perhaps some of these values are actually redundant.

[SimonForsman]

Hey, I have some lopps that repeat more than 1000 times.
In these loops, I use alot of new variables like so

for (int i = 0; i > 500; i++)
{
	for (int j = 0; j > 500; j++)
	{
		int foo = 0;
		int bar = 2;
		double a;
		double b;
		double c;
		double x;
		double y;
		double z;
		// Do Something
		}
}

that means to me, that I allocate new memory everytime I run trough the loop.

When done something like this:

int foo = 0;
int bar = 2;
double a;
double b;
double c;
double x;
double y;
double z;
for (int i = 0; i > 500; i++)
{
	for (int j = 0; j > 500; j++)
	{
		 // Do Something
	  }
}

isn't that pretty much faster?
Because I use the same memory for every loop, instead of allocate evertime new one?

The compiler should be smart enough to reuse variables declared in a loop and can even use registers for some of them, stack allocation is also very very cheap so its almost always best to declare variables in the scope in which they are used. (If you declare them outside the scope they're used in they will hang around for longer and make it harder for the compiler to optimize)

[bglanzer]

It uses the same amount of memory because the variables are taken out of scope after leaving the inner for loop. The only consequence is the variables being added to the stack each loop, but a compiler may compensate for this and leave them on the stack.

[Imprecision]

[...]

Remember, if it is a trivial and safe transformation, the compiler writers will probably have already implemented it.

I don't count on that since I've read that this:

int length = List.Count
for (int i = 0; i < length; i++
{
	//Run through list
}

is several times faster than

for (int i = 0; i < List.Count; i++
{
	//Run through list
}

One line of code optimization.

Finally, are you sure you need all these variables? For optimisation, the fastest code is the code that doesn't have to run. Perhaps some of these values are actually redundant.

It generates a planet chunk with curvature, trianglelist, heighmap and textures coordinates at once. Yes I need that many variables



But thanks for all your answers. Now I'm able to clean up my code a bit

Edited by Imprecision, 29 April 2012 - 06:02 PM.

[ChaosEngine]

int length = List.Count
for (int i = 0; i < length; i++
{
	//Run through list
}

is several times faster than

for (int i = 0; i < List.Count; i++
{
	//Run through list
}

One line of code optimization.

I find that difficult to believe. Do you have a source for this?
Besides, in this case, you should really be using foreach

[Oolala]

Interesting. I didn't believe it either. I just tried it though. This code:

  int length = 5000000;
  int sum = 0;
  int[] x = new int[length];
  for(int i = 0; i < length; i++)
  {
   x[i] = i;
  }
  System.DateTime start = System.DateTime.Now;
  for (int j = 0; j < 1000; j++)
  {
   //int lim = x.Length;   //Version A
   //for (int i = 0; i < lim; i++)
   for (int i = 0; i < x.Length; i++)   //Version B
   {
	sum += x[i];
   }
  }
  System.Console.WriteLine((System.DateTime.Now - start).ToString());

Yielded 5.024 seconds with Version A, optimizations on, and 7.5364 seconds with optimizations off.
Version B, with optimization on took 7.16 seconds, and 7.5364 seconds with optimizations off.
Both were run many times, and the numbers shown are the average. Variation was typically on the order of a few milliseconds at most. I know this doesn't prove one is faster than the other in a concrete way, but still, unexpected case study.

I don't have a disassembler where I am right now, but it would be interesting to know what is going on here. The only thing I can figure [since turning optimizations off in VS is sufficient to actually make a difference] is that some static analysis is making different use of the pre-calculated version. Strange. "Several times faster" though, it is not.

I'm not going to change the way I program from case B to case A though.

Edited by Oolala, 29 April 2012 - 07:43 PM.

[Digitalfragment]

This:
for (int i = 0; i < x.Length; i++)
equates to x.Length() as the compiler can't guarantee that Length is not going to change during the course of the loop (Items can be added/removed from other threads)

This:
int count = x.Length;
for (int i = 0; i < count; i++)
Localises Length and the compiler can then see that nowhere in that loop does count change, and ideally count can remain in a register, or at least just on the stack.

[Trienco]

In other words: "don't call a function on every iteration if the result won't change" has nothing to do with "declaring stack variables inside or outside a loop".

[Oolala]

...the compiler can then see that nowhere in that loop does count change, and ideally count can remain in a register, or at least just on the stack.

The compiler can surely deduce that the value of Length is immutable, even if only because there is no assignment anywhere to the array or any element of the array [and thus the array itself can be treated as immutable in that context]. Whether this is being done, it's hard to say, especially given the current setup.

Can it be done? Absolutely.

I still think they need to let you provide hints to the .NET JIT to indicate to it optimization levels programatically. It seems to be an easy thing if you could just specify the intended execution time of your program [even if just a choice between 'really short', and 'not really short'], to indicate whether or not heavy-weight optimizations are worth undertaking.

[taz0010]

The compiler can surely deduce that the value of Length is immutable, even if only because there is no assignment anywhere to the array or any element of the array [and thus the array itself can be treated as immutable in that context]. Whether this is being done, it's hard to say, especially given the current setup.

The reason the compiler isn't optimising out the call is because there's no guarantee that the value isn't being changed by another thread. Other compilers might optimise more aggressively and rely on the programmer to use the proper keywords (volatile) on all objects used in multithreading, but VS does not. I'm not 100% sure of the situation in C#, but in c++ under VS, levels of indirection are not cached at all. If you access a->b->c multiple times, you pay for the dereferences each time. This might be different if you create everything on the stack and don't use dynamic allocation at all, however.

I prefer to write my loops like this:

for (int i = 0, len = x.Length; i < len; ++i) { // actions }

This should produce optimal code while avoiding the need to waste lines on declarations. Of course the effort is only of benefit 1% of the time (premature optimisation and all), but if you get in the habit of writing all loops like that, you're not wasting any time.

[Antheus]

Loop invariants are an important topic to mention here.

Boundary condition ('length') may be an invariant, but doesn't have to be. General form of for or foreach do not assume it is.

In Java or .Net, containers throw a runtime exception if structure of container changes, such as if elements are added or removed, but foreach by itself does not check for it. For simplicity and correctness of code and KISS principle, such approach works better.

Many compilers today will attempt to detect invariants, but in order to work reliably, they need to know exact implementation of everything involved. When it comes to containers (or more accurately Iterators) in managed languages, they might not have this code - implementatoin of the interface might not have been written yet.


Caution is advised when making such optimizations, especially if working mostly with generic interfaces (mostly good practice) or if relying on many external implementations of said interfaces.

In general case, assuming boundary condition is constant does not need to hold, so technically such optimization is not correct.

To make use of it, prefer structures which guarantee such behavior. Immutable strings, arrays or similar.

For iterators, length might not be known anyway, it might be structured like:

for (  ;  i.hasMore(); i.next) { }

[Digitalfragment]

...the compiler can then see that nowhere in that loop does count change, and ideally count can remain in a register, or at least just on the stack.

The compiler can surely deduce that the value of Length is immutable, even if only because there is no assignment anywhere to the array or any element of the array [and thus the array itself can be treated as immutable in that context]. Whether this is being done, it's hard to say, especially given the current setup.

Can it be done? Absolutely.

Not true as .net also supports code reflection and injection/emission, and so the compiler *cannot* make that guarantee, if the object has any functionality that changes the value of Length past construction. So, the only time your statement is true, is if you are calling Length on an array. If it is a dynamic container type, then it cant.

[Zoner]

My guideline is:

built-in types will be optimized very well by the compiler, user-defined types can be iffy though structs are about as trivial as built-in types, but types that dynamically allocate memory (like array containers) need to be hoisted out of loops.

None of this is 100% true but its close enough as the exceptional cases only show up in a profiler when you are serious about squeezing some more time out of a function.