Archived

This topic is now archived and is closed to further replies.

kudi

array-size

Recommended Posts

kudi    244
Hi I have two Arrays: array1[100][10000] and array2[1000000] Is it possible that the second one isn''t as fast as the first, if you know what I mean ?

Share this post


Link to post
Share on other sites
sysmark    122
Actually, I think the first one is slower, as in the second one there is only one offset calculation, and I think the first one takes two of them. I''m not sure however...

Share this post


Link to post
Share on other sites
Stoffel    250
Hm, you could always code it and see.
    
int main ()
{
int a[100][10000];
int b[1000000];

for (int i=0; i<100; ++i)
{
for (int j=0; j<10000; ++j)
{
a[i][j] = rand ();
}
}

for (i=0; i<1000000; ++i)
b[i] = rand ();

int y = a[rand () % 100][rand () % 10000];
int z = b[rand () % 1000000];

return y + z;
}
// dissassembly

PUBLIC _main
EXTRN __chkstk:NEAR
EXTRN _rand:NEAR
; COMDAT _main
_TEXT SEGMENT
_a$ = -4000004
_b$ = -8000004
_main PROC NEAR ; COMDAT

; 7 : {

push ebp
mov ebp, esp
mov eax, 8000004 ; 007a1204H
call __chkstk
push ebx
push esi
push edi

; 8 : int a[100][10000];
; 9 : int b[1000000];
; 10 :
; 11 : for (int i=0; i<100; ++i)

lea esi, DWORD PTR _a$[ebp]
mov DWORD PTR -4+[ebp], 100 ; 00000064H
mov ebx, 10000 ; 00002710H
$L7402:

; 12 : {
; 13 : for (int j=0; j<10000; ++j)

mov edi, ebx
$L7406:

; 14 : {
; 15 : a[i][j] = rand ();

call _rand
mov DWORD PTR [esi], eax
add esi, 4
dec edi
jne SHORT $L7406

; 8 : int a[100][10000];
; 9 : int b[1000000];
; 10 :
; 11 : for (int i=0; i<100; ++i)

dec DWORD PTR -4+[ebp]
jne SHORT $L7402

; 16 : }
; 17 : }
; 18 :
; 19 : for (i=0; i<1000000; ++i)

mov edi, 1000000 ; 000f4240H
lea esi, DWORD PTR _b$[ebp]
mov DWORD PTR -4+[ebp], edi
$L7409:

; 20 : b[i] = rand ();

call _rand
mov DWORD PTR [esi], eax
add esi, 4
dec DWORD PTR -4+[ebp]
jne SHORT $L7409

; 21 :
; 22 : int y = a[rand () % 100][rand () % 10000];

call _rand
push 100 ; 00000064H
cdq
pop ecx
idiv ecx
mov esi, edx
imul esi, 10000 ; 00002710H
call _rand
cdq
idiv ebx
add esi, edx
mov esi, DWORD PTR _a$[ebp+esi*4]

; 23 : int z = b[rand () % 1000000];

call _rand
cdq
idiv edi
pop edi

; 24 :
; 25 : return y + z;

mov eax, DWORD PTR _b$[ebp+edx*4]
add eax, esi
pop esi
pop ebx

; 26 : }

leave
ret 0
_main ENDP
_TEXT ENDS


If you look at the disassembly, it takes more time to initialize array1 because there are two variables to increment, even though both arrays are physically the same size and physically have the same layout in memory.

Also, accessing array members by variable requires more work for the first array than the second, again because of the two dimensions.

It should be noted, though I don't show it here, that if you use constants instead of variables, each array requires just one instruction to access elements. This is because the compiler can pre-compute the actual off-set.

Is one faster than the other? That depends on how you get your indexes. If you have a single index into the one-dimensional array, and you need to calculate how to break that into two dimensions, then the first array is much slower.

However, if you have two dimensions (i.e. x & y coordinates), and you need to translate those into a single dimension manually, you are doing the same work the compiler is doing. Therefore, both methods require the exact same amount of time.

edit: the [ code ] tags still interpret [ i ] as italics. d'oh.

Edited by - Stoffel on August 7, 2001 1:53:18 PM

Share this post


Link to post
Share on other sites
BeerNutts    4400
Kudi,

There is no difference between one and the other.
In the end, they''re both basically pointers to some memory space with 1000000 bytes (or whatever the type it is) allocated for it.
The only differnce is how you (the user) access the array elements.

Share this post


Link to post
Share on other sites
kudi    244
Thanks for these answers. But in my program, the second one is still slower. And I don''t think that the problem are the indexes.

I asked this question because I thought that the computer needs more time to work with big arrays than with small ones. Perhaps I can compare it with textures: Isn''t it faster to use a lot of small textures instead of one big ?

Share this post


Link to post
Share on other sites
Stoffel    250
Hem, maybe I should have been more picky about your question when I replied.

When you say "which is faster", that question makes no sense. Arrays are memory. They have no speed. It''s like asking which is faster, a rock or stick? They have no inherent speed, so the question makes no sense.

So, when you put these arrays up, you listed them as static arrays. When you say which is faster, I assumed you meant which one could be accessed faster.

From your last post, it looks like you may be dynamically allocating these arrays. In that case, your question might have been "which is faster to allocate?"

You need to specify what you mean by faster; in other words, what operation with these arrays is specifically slowing things down. Allocation? Reading/writing?

Generally, dynamically allocating a lot of smaller arrays can be faster than allocating a single large array. Reason being that the large array needs to be contiguous in memory, and it may take a while to find that much contiguous memory in the system. On the other hand, you do reach a point of diminishing returns--an array of 1000000 dynamically allocated bytes (i.e. 1 byte per pointer) is obviously just silly and will really hurt performance.

Can you maybe state your question more clearly?

Share this post


Link to post
Share on other sites