array-size
Author
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 ?
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...
Hm, you could always code it and see.
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
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;}// dissassemblyPUBLIC _mainEXTRN __chkstk:NEAREXTRN _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
tags still interpret [ i ] as italics. d'oh.<br><br>Edited by - Stoffel on August 7, 2001 1:53:18 PM
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.
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.
Author
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 ?
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 ?
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?
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
