Asked  7 Months ago    Answers:  5   Viewed   30 times

Below are two programs that are almost identical except that I switched the i and j variables around. They both run in different amounts of time. Could someone explain why this happens?

Version 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Version 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

 Answers

13

As others have said, the issue is the store to the memory location in the array: x[i][j]. Here's a bit of insight why:

You have a 2-dimensional array, but memory in the computer is inherently 1-dimensional. So while you imagine your array like this:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Your computer stores it in memory as a single line:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

In the 2nd example, you access the array by looping over the 2nd number first, i.e.:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Meaning that you're hitting them all in order. Now look at the 1st version. You're doing:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Because of the way C laid out the 2-d array in memory, you're asking it to jump all over the place. But now for the kicker: Why does this matter? All memory accesses are the same, right?

No: because of caches. Data from your memory gets brought over to the CPU in little chunks (called 'cache lines'), typically 64 bytes. If you have 4-byte integers, that means you're geting 16 consecutive integers in a neat little bundle. It's actually fairly slow to fetch these chunks of memory; your CPU can do a lot of work in the time it takes for a single cache line to load.

Now look back at the order of accesses: The second example is (1) grabbing a chunk of 16 ints, (2) modifying all of them, (3) repeat 4000*4000/16 times. That's nice and fast, and the CPU always has something to work on.

The first example is (1) grab a chunk of 16 ints, (2) modify only one of them, (3) repeat 4000*4000 times. That's going to require 16 times the number of "fetches" from memory. Your CPU will actually have to spend time sitting around waiting for that memory to show up, and while it's sitting around you're wasting valuable time.

Important Note:

Now that you have the answer, here's an interesting note: there's no inherent reason that your second example has to be the fast one. For instance, in Fortran, the first example would be fast and the second one slow. That's because instead of expanding things out into conceptual "rows" like C does, Fortran expands into "columns", i.e.:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

The layout of C is called 'row-major' and Fortran's is called 'column-major'. As you can see, it's very important to know whether your programming language is row-major or column-major! Here's a link for more info: http://en.wikipedia.org/wiki/Row-major_order

Tuesday, June 1, 2021
 
dmp
answered 7 Months ago
dmp
88

The first method is slightly better, as the cells being assigned to lays next to each other.

First method:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

Second method:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
Wednesday, June 2, 2021
 
hjalpmig
answered 6 Months ago
97

Well, it partly depends on the exact type of list. It will also depend on the exact CLR you're using.

Whether it's in any way significant or not will depend on whether you're doing any real work in the loop. In almost all cases, the difference to performance won't be significant, but the difference to readability favours the foreach loop.

I'd personally use LINQ to avoid the "if" too:

foreach (var item in list.Where(condition))
{
}

EDIT: For those of you who are claiming that iterating over a List<T> with foreach produces the same code as the for loop, here's evidence that it doesn't:

static void IterateOverList(List<object> list)
{
    foreach (object o in list)
    {
        Console.WriteLine(o);
    }
}

Produces IL of:

.method private hidebysig static void  IterateOverList(class [mscorlib]System.Collections.Generic.List`1<object> list) cil managed
{
  // Code size       49 (0x31)
  .maxstack  1
  .locals init (object V_0,
           valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object> V_1)
  IL_0000:  ldarg.0
  IL_0001:  callvirt   instance valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!0> class [mscorlib]System.Collections.Generic.List`1<object>::GetEnumerator()
  IL_0006:  stloc.1
  .try
  {
    IL_0007:  br.s       IL_0017
    IL_0009:  ldloca.s   V_1
    IL_000b:  call       instance !0 valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object>::get_Current()
    IL_0010:  stloc.0
    IL_0011:  ldloc.0
    IL_0012:  call       void [mscorlib]System.Console::WriteLine(object)
    IL_0017:  ldloca.s   V_1
    IL_0019:  call       instance bool valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object>::MoveNext()
    IL_001e:  brtrue.s   IL_0009
    IL_0020:  leave.s    IL_0030
  }  // end .try
  finally
  {
    IL_0022:  ldloca.s   V_1
    IL_0024:  constrained. valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<object>
    IL_002a:  callvirt   instance void [mscorlib]System.IDisposable::Dispose()
    IL_002f:  endfinally
  }  // end handler
  IL_0030:  ret
} // end of method Test::IterateOverList

The compiler treats arrays differently, converting a foreach loop basically to a for loop, but not List<T>. Here's the equivalent code for an array:

static void IterateOverArray(object[] array)
{
    foreach (object o in array)
    {
        Console.WriteLine(o);
    }
}

// Compiles into...

.method private hidebysig static void  IterateOverArray(object[] 'array') cil managed
{
  // Code size       27 (0x1b)
  .maxstack  2
  .locals init (object V_0,
           object[] V_1,
           int32 V_2)
  IL_0000:  ldarg.0
  IL_0001:  stloc.1
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.2
  IL_0004:  br.s       IL_0014
  IL_0006:  ldloc.1
  IL_0007:  ldloc.2
  IL_0008:  ldelem.ref
  IL_0009:  stloc.0
  IL_000a:  ldloc.0
  IL_000b:  call       void [mscorlib]System.Console::WriteLine(object)
  IL_0010:  ldloc.2
  IL_0011:  ldc.i4.1
  IL_0012:  add
  IL_0013:  stloc.2
  IL_0014:  ldloc.2
  IL_0015:  ldloc.1
  IL_0016:  ldlen
  IL_0017:  conv.i4
  IL_0018:  blt.s      IL_0006
  IL_001a:  ret
} // end of method Test::IterateOverArray

Interestingly, I can't find this documented in the C# 3 spec anywhere...

Wednesday, June 9, 2021
 
Ultimater
answered 6 Months ago
62

I don't think there is a way to avoid this problem in the general case. But there is a way if your cell array has all numbers or all chars. You can convert to an array and let the for loop iterate over that.

For example, this:

some_cell_array = {1,2,3}
for s = [some_cell_array{:}] % convert to array
    s
end

Gives:

s =
     1
s =
     2
s =
     3

Another option is to create a function that operates on every cell of the array. Then you can simply call cellfun and not have a loop at all.

I don't have any ideas about who would want this behavior or how it could be useful. My guess as to why it works this way, however, is that it's an implementation thing. This way the loop iterator doesn't change type on different iterations. It is a cell every time, even if the contents of that cell are different types.

Saturday, September 25, 2021
 
Rupesh Patel
answered 2 Months ago
36

I have to disagree with all previous answers, and the reason is simple: if you change the order of your left join, your queries are logically different and as such they produce different result sets. See for yourself:

SELECT 1 AS a INTO #t1
UNION ALL SELECT 2
UNION ALL SELECT 3
UNION ALL SELECT 4;

SELECT 1 AS b INTO #t2
UNION ALL SELECT 2;

SELECT 1 AS c INTO #t3
UNION ALL SELECT 3;

SELECT a, b, c 
FROM #t1 LEFT JOIN #t2 ON #t1.a=#t2.b
  LEFT JOIN #t3 ON #t2.b=#t3.c
ORDER BY a;

SELECT a, b, c 
FROM #t1 LEFT JOIN #t3 ON #t1.a=#t3.c
  LEFT JOIN #t2 ON #t3.c=#t2.b
ORDER BY a;

a           b           c
----------- ----------- -----------
1           1           1
2           2           NULL
3           NULL        NULL
4           NULL        NULL

(4 row(s) affected)

a           b           c
----------- ----------- -----------
1           1           1
2           NULL        NULL
3           NULL        3
4           NULL        NULL
Saturday, October 30, 2021
 
Ripon Al Wasim
answered 1 Month ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share