Автор Тема: Задача на C  (Прочетена 2383 пъти)

task_struct

  • Напреднали
  • *****
  • Публикации: 576
  • Distribution: Kubuntu 14.04
  • Window Manager: KDE 4.13
    • Профил
Re: Задача на C
« Отговор #15 -: May 04, 2010, 00:34 »
Според мен просто му искат 2 функци - едната с входен параметър указател, а другата с матрица. ;)

Другият вариант е една функция за смятане на статично заделена матрица, а другата с динамично заделена.

Реално погледнато няма разлика между: a[ i ][j] и *((b+i)+j), това би трябвало да са един и същ брой инструкции, дори да се еднакви :) ( не съм го тествал)

i и j ще отидат в регистрите на процесора поради това, че са локални променливи. Остават самите мартици - при данимично създадените не знам как ще е ( пиша за embedded, а там няма динамична памет ), при статичните може да се оптимизира при компилирането и част от матриците също да отидат в регистрите. Също така съвременните процесори поддръжат Very long instruction word ( http://en.wikipedia.org/wiki/Very_long_instruction_word ), така че компилаторът да оптимизира кода и част от него да се изпълнява успоредно. ( Някъде бях намерил 1 pdf за AMD процесори, където беше описано как може да се пише кода така, че компилатора да оптимизира като използва тези инструкции ). Също така който е заинтересован може да прегледа проекта Eigen(http://eigen.tuxfamily.org/index.php?title=Main_Page) той е точно за работа с матрици и вектори и там се използват допълнителните инструкции на процесора. В заключение: Смятам, че няма да има разлика между двата метода :)
Активен

"Minds are like parachutes. They only function when they are open." - James Dewar

irc.freenode.net  / #linux-bg

niakoi

  • Напреднали
  • *****
  • Публикации: 49
    • Профил
Re: Задача на C
« Отговор #16 -: May 04, 2010, 11:11 »
привет,
не претендирам, че съм гуру в С, обаче винаги съм вярвал, че
Код
GeSHi ():
  1. a[i] е абс. същото като *(a+i)
, дори в някои книги по този начин обясняват работата с масиви и каква е връзката с пойнтерите

поздрави
нас
« Последна редакция: May 04, 2010, 11:13 от niakoi »
Активен

remotex

  • Напреднали
  • *****
  • Публикации: 344
    • Профил
Re: Задача на C
« Отговор #17 -: May 04, 2010, 11:36 »
Надали ще е само до аритметиката  с указатели - според мен дали ще е изписано със квадратни скоби или обикновени за процесора е се тая..

Хе-хе всяко нещо си има предимства и недостатъци... едва ли ще задълбават чак толкова надълбоко в архитектури, процесори и оптимизации за тях. Предполагам "грешният" отговор който обикновено признават за верен в сл. е:
  Масивите са по-бързи, но си ограничен до размерността на масива
 ...а пък с указатели можеш да си направиш динамичен масив/структура от данни (макар и по-бавна заради динамичното заделяне и после търкане на елементите 1 по 1 - т.е. само така си мислят даскалята и карат "децата" да преоткриват топлата вода като прескачат stl, boost etc.)
Активен

lkr

  • Напреднали
  • *****
  • Публикации: 81
    • Профил
Re: Задача на C
« Отговор #18 -: May 04, 2010, 13:51 »
Достъпът до индекс е еднакъв откъм инструкции, но динамичните почти винаги ще бъдат по-бавни, task_struct изреди някои причини. Други такива са, че при достатъчно големи масиви може да се получи memory fragmentation, а това води до cache misses, което е една от най-бавните операции при днешните x86.
Активен

hyankov

  • Напреднали
  • *****
  • Публикации: 86
    • Профил
Re: Задача на C
« Отговор #19 -: May 04, 2010, 15:10 »
Хахах, тъкмо се готвех, да се изрежа квалитетно, че в C (респективно и в C++) такова животно като масиви няма, когато видях, че niakoi ме е изпреварил ;)

Някой може ли да отговори, ако има "масиви" в С, защо следните две операции при са синтактично верни и при това ще дадат един резултат:
Код:
int array[10];

array[5];
5[array];

Отговорът е написан няколко поста по-нагоре. Не се заяждам, но заданието е доста идиотско "Веднъж с масиви, веднъж с указатели" иначе сигурен съм, че има някакъв замисъл.
Активен

task_struct

  • Напреднали
  • *****
  • Публикации: 576
  • Distribution: Kubuntu 14.04
  • Window Manager: KDE 4.13
    • Профил
Re: Задача на C
« Отговор #20 -: May 04, 2010, 15:32 »
Защото операцията [] се замества с поинтър аритметика от предпроцесора :)
Активен

"Minds are like parachutes. They only function when they are open." - James Dewar

irc.freenode.net  / #linux-bg

task_struct

  • Напреднали
  • *****
  • Публикации: 576
  • Distribution: Kubuntu 14.04
  • Window Manager: KDE 4.13
    • Профил
Re: Задача на C
« Отговор #21 -: May 04, 2010, 15:55 »
Хъм, излязоха доста интересни резултати на VS 6.0 За съжаление вмомента нямам под ръка GCC за да тествам там как стоят нещата :(

Код
GeSHi (C):
  1. int main()
  2. {
  3.    int arr[5] = { 1, 2, 3, 4, 5 };
  4.    int *p = arr;
  5.  
  6.    arr[2] = 10;
  7.    3[arr] = 11;
  8.  
  9.  
  10.    *(p + 2) = 25;
  11.  
  12.  
  13.    return 0;
  14. }
  15.  

Генерираният от това асемблер е:

Код:
TITLE D:\Opit\main.c
.386P
include listing.inc
if @Version gt 510
.model FLAT
else
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
_DATA SEGMENT DWORD USE32 PUBLIC 'DATA'
_DATA ENDS
CONST SEGMENT DWORD USE32 PUBLIC 'CONST'
CONST ENDS
_BSS SEGMENT DWORD USE32 PUBLIC 'BSS'
_BSS ENDS
$$SYMBOLS SEGMENT BYTE USE32 'DEBSYM'
$$SYMBOLS ENDS
$$TYPES SEGMENT BYTE USE32 'DEBTYP'
$$TYPES ENDS
_TLS SEGMENT DWORD USE32 PUBLIC 'TLS'
_TLS ENDS
; COMDAT _main
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
FLAT GROUP _DATA, CONST, _BSS
ASSUME CS: FLAT, DS: FLAT, SS: FLAT
endif
PUBLIC _main
; COMDAT _main
_TEXT SEGMENT
_arr$ = -20
_p$ = -24
_main PROC NEAR ; COMDAT

; 2    : {

push ebp
mov ebp, esp
sub esp, 88 ; 00000058H
push ebx
push esi
push edi
lea edi, DWORD PTR [ebp-88]
mov ecx, 22 ; 00000016H
mov eax, -858993460 ; ccccccccH
rep stosd

; 3    :     int arr[5] = { 1, 2, 3, 4, 5 };

mov DWORD PTR _arr$[ebp], 1
mov DWORD PTR _arr$[ebp+4], 2
mov DWORD PTR _arr$[ebp+8], 3
mov DWORD PTR _arr$[ebp+12], 4
mov DWORD PTR _arr$[ebp+16], 5

; 4    :     int *p = arr;

lea eax, DWORD PTR _arr$[ebp]
mov DWORD PTR _p$[ebp], eax

; 5    :
; 6    :     arr[2] = 10;

mov DWORD PTR _arr$[ebp+8], 10 ; 0000000aH

; 7    :     3[arr] = 11;

mov DWORD PTR _arr$[ebp+12], 11 ; 0000000bH

; 8    :
; 9    :
; 10   :     *(p + 2) = 25;

mov ecx, DWORD PTR _p$[ebp]
mov DWORD PTR [ecx+8], 25 ; 00000019H

; 11   :
; 12   :
; 13   :     return 0;

xor eax, eax

; 14   : }

pop edi
pop esi
pop ebx
mov esp, ebp
pop ebp
ret 0
_main ENDP
_TEXT ENDS
END


Както виждате arr[2] = 10; и  3[arr] = 11; генерират по 1 инструкция, докато *(p + 2) = 25; генерира 2. Следователно варианта с масиви/матрици би трябвало да е по-бърз.  ::)
« Последна редакция: May 04, 2010, 16:35 от task_struct »
Активен

"Minds are like parachutes. They only function when they are open." - James Dewar

irc.freenode.net  / #linux-bg

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Задача на C
« Отговор #22 -: May 04, 2010, 17:36 »
Още по-забавни резултати :)

t1.c:
Код
GeSHi (C):
  1. #include <unistd.h>
  2.  
  3. void main()
  4. {
  5. int a[2][2];
  6. int b;
  7.  
  8. b = a[1][1];
  9. }
  10.  


t2.c:
Код
GeSHi (C):
  1. void main()
  2. {
  3. int *a;
  4. int b;
  5. b = *(a+4);
  6. }
  7.  


Асемблерен код на main() функцията, компилираме го без оптимизации:

t1:
Код:
0x08048384 <main+0>:    lea    0x4(%esp),%ecx
0x08048388 <main+4>:    and    $0xfffffff0,%esp
0x0804838b <main+7>:    pushl  0xfffffffc(%ecx)
0x0804838e <main+10>:   push   %ebp
0x0804838f <main+11>:   mov    %esp,%ebp
0x08048391 <main+13>:   push   %ecx
0x08048392 <main+14>:   sub    $0x20,%esp
0x08048395 <main+17>:   mov    0xfffffff4(%ebp),%eax
0x08048398 <main+20>:   mov    %eax,0xfffffff8(%ebp)
0x0804839b <main+23>:   add    $0x20,%esp
0x0804839e <main+26>:   pop    %ecx
0x0804839f <main+27>:   pop    %ebp
0x080483a0 <main+28>:   lea    0xfffffffc(%ecx),%esp
0x080483a3 <main+31>:   ret


t2:
Код:
0x08048384 <main+0>:    lea    0x4(%esp),%ecx
0x08048388 <main+4>:    and    $0xfffffff0,%esp
0x0804838b <main+7>:    pushl  0xfffffffc(%ecx)
0x0804838e <main+10>:   push   %ebp
0x0804838f <main+11>:   mov    %esp,%ebp
0x08048391 <main+13>:   push   %ecx
0x08048392 <main+14>:   sub    $0x10,%esp
0x08048395 <main+17>:   mov    0xfffffff4(%ebp),%eax
0x08048398 <main+20>:   add    $0x10,%eax
0x0804839b <main+23>:   mov    (%eax),%eax
0x0804839d <main+25>:   mov    %eax,0xfffffff8(%ebp)
0x080483a0 <main+28>:   add    $0x10,%esp
0x080483a3 <main+31>:   pop    %ecx
0x080483a4 <main+32>:   pop    %ebp
0x080483a5 <main+33>:   lea    0xfffffffc(%ecx),%esp
0x080483a8 <main+36>:   ret

Или демек 5 инструкции повече. Обаче компилираме ли го с флаг за оптимизация (O1 и нагоре), и двете генерират абсолютно идентичен код:

Код:
0x08048384 <main+0>:    lea    0x4(%esp),%ecx
0x08048388 <main+4>:    and    $0xfffffff0,%esp
0x0804838b <main+7>:    pushl  0xfffffffc(%ecx)
0x0804838e <main+10>:   push   %ebp
0x0804838f <main+11>:   mov    %esp,%ebp
0x08048391 <main+13>:   push   %ecx
0x08048392 <main+14>:   pop    %ecx
0x08048393 <main+15>:   pop    %ebp
0x08048394 <main+16>:   lea    0xfffffffc(%ecx),%esp
0x08048397 <main+19>:   ret


Има една разлика между масивите и указателите обаче - масивите могат да бъдат в стека или data секцията (в зависимост от това дали са локални/глобални променливи), указателите се очаква да сочат към памет в хийпа. Обаче последното не е задължително - примерно ако се ползва alloca() няма да е така.

Обаче и при това положение, не виждам разлика. Паметта би трябвало да се dereference-ва еднакво бързо без значение къде е. Performance драми може да има с TLB misses при големи матрици, но това трябва да е валидно и за двата варианта. Другото което си мисля е дали линукс ядрото не предпочита при нужда да pageout-ва страници памет от хийпа пред страници памет от стека, ама много ме съмнява да (може да) го прави, а и не виждам с какво това би било по-умно от LRU стратегията. 

Та все още не мога да се сетя защо едното трябва да е по-бързо от другото.

В хийпа трябва да е по-бавно заради malloc() ама ако е малка матрицата може да го заделим в стека и тва е доста бърза операция (измества се само стек пойнтера). После, не е казано че трябва да ползваме malloc() въобще, може и сaмо с mmap(), което ще е малко по-бързо.

Ако изключим времето за заделяне и освобождаваме, двете трябва да са еднакво бързи.
« Последна редакция: May 04, 2010, 17:38 от gat3way »
Активен

"Knowledge is power" - France is Bacon