Come trovare l'elemento più grande di una matrice di dimensioni note?

Question

Devo trovare l'elemento più grande in una matrice che contenga esattamente 16 numeri interi. Sto considerando due possibili implementazioni. In primo luogo, il sensibile implementazione:

int largest = array[0]; 
for (int i = 1; i < 16; i++) { 
    const int val = array[i]; 
    if (val > largest) { 
    largest = val; 
    } 
} 

E poi c'è l'implementazione leggermente folle che sfrutta il fatto che la dimensione della matrice è nota:

const int max_value = 
    max(
    max(
     max(
     max(array[0], array[1]), 
     max(array[2], array[3])), 
     max(
     max(array[4], array[5]), 
     max(array[6], array[7]))), 
    max(
     max(
     max(array[8], array[9]) 
     max(array[10], array[11])), 
     max(
     max(array[12], array[13]) 
     max(array[14], array[15])))); 

Quale è il migliore attuazione? max è in genere implementato nell'hardware?

Answer 1

Compiliamoli e vediamo cosa otteniamo!

Prima di tutto, AFAIK, non esiste una funzione/macro "max" definita nello standard C. Così ne ho aggiunto uno (che sembra contorto perché evita la doppia valutazione dei suoi input).

#define max(a,b) ({ \ 
    const __typeof__ (a) _a = (a); \ 
    const __typeof__ (b) _b = (b); \ 
    _a > _b ? _a : _b; \ 
}) 

int __attribute__ ((noinline)) test1(const int* array) { 
    int largest = array[0]; 
    for (int i = 1; i < 16; i++) { 
     const int val = array[i]; 
     if (val > largest) { 
     largest = val; 
     } 
    } 
    return largest; 
} 

int __attribute__ ((noinline)) test2(const int* array) { 
    const int max_value = 
     max(
     max(
      max(
      max(array[0], array[1]), 
      max(array[2], array[3])), 
      max(
      max(array[4], array[5]), 
      max(array[6], array[7]))), 
     max(
      max(
      max(array[8], array[9]), 
      max(array[10], array[11])), 
      max(
      max(array[12], array[13]), 
      max(array[14], array[15])))); 
    return max_value; 
} 

La mia versione gcc, che è rilevante quando si parla di ottimizzazioni:

tmp$ gcc --version 
gcc (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4 
Copyright (C) 2013 Free Software Foundation, Inc. 
This is free software; see the source for copying conditions. There is NO 
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

-O2 per ottimizzazioni, -S all'assemblaggio uscita, -o - a allo standard output.

tmp$ gcc -std=c99 -O2 -S test.c -o - 
    .file "test.c" 
    .text 
    .p2align 4,,15 
    .globl test1 
    .type test1, @function 
test1: 
.LFB0: 
    .cfi_startproc 
    movl (%rdi), %eax 
    xorl %edx, %edx 
    .p2align 4,,10 
    .p2align 3 
.L3: 
    movl 4(%rdi,%rdx), %ecx 
    cmpl %ecx, %eax 
    cmovl %ecx, %eax 
    addq $4, %rdx 
    cmpq $60, %rdx 
    jne .L3 
    rep ret 
    .cfi_endproc 
.LFE0: 
    .size test1, .-test1 
    .p2align 4,,15 
    .globl test2 
    .type test2, @function 
test2: 
.LFB1: 
    .cfi_startproc 
    movl (%rdi), %edx 
    cmpl %edx, 4(%rdi) 
    cmovge 4(%rdi), %edx 
    movl 8(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 12(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 16(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 20(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 24(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 28(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 32(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 36(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 40(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 44(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 48(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 52(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 56(%rdi), %eax 
    cmpl %eax, %edx 
    cmovl %eax, %edx 
    movl 60(%rdi), %eax 
    cmpl %eax, %edx 
    cmovge %edx, %eax 
    ret 
    .cfi_endproc 
.LFE1: 
    .size test2, .-test2 
    .ident "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4" 
    .section .note.GNU-stack,"",@progbits 

Va bene, così test2() certamente sembra molto più a lungo.Tuttavia, non si dirama affatto. Ed è solo ~ 3 istruzioni (carico di memoria, confronto, spostamento condizionale) per elemento. test1() ha 6 istruzioni (caricamento della memoria, confronto, spostamento condizionale, incremento del contatore del ciclo, confronto del contatore del ciclo, ramo condizionale). Un sacco di rami in test1, che può essere fastidioso (a seconda di quanto sia buona la previsione della branca dell'architettura). D'altra parte, test2 aumenta la dimensione del codice, che necessariamente spingerà qualcos'altro fuori dalla cache delle istruzioni. E ci sono molti pericoli di dati in test2 (beh, e test1 ...) - forse potremmo riscriverlo per usare alcuni registri extra per ridurre il numero di stalli della pipeline?

Quindi, come probabilmente puoi vedere ora, questa non è una domanda facile a cui rispondere.

L'unico vero modo per sapere è misurarlo. E anche allora, varierà a seconda dell'implementazione interna/ottimizzazioni/dimensione della cache di ogni modello di CPU.

così ho scritto un piccolo punto di riferimento:

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

#define N (1000000) 

int main() { 
    printf(" %12s %12s %12s %12s\n", "test1 time", "test2 time", "test1 out", "test2 out"); 
    int* data = malloc(N * 16 * sizeof(int)); 
    srand(1); 
    for (int i=0; i<16*N; ++i) { 
     data[i] = rand(); 
    } 

    const int* a; 
    struct timespec t1, t2, t3; 
    for (int attempt=0; attempt<10; ++attempt) { 
     uint32_t sum1 = 0; 
     uint32_t sum2 = 0; 

     clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t1); 
     a = data; 
     for (int i=0; i<N; ++i) { 
      sum1 += test1(a); 
      a += 16; 
     } 

     clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t2); 
     a = data; 
     for (int i=0; i<N; ++i) { 
      sum2 += test2(a); 
      a += 16; 
     } 

     clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t3); 
     uint64_t nanos1 = (t2.tv_sec - t1.tv_sec) * 1000000000L + (t2.tv_nsec - t1.tv_nsec); 
     uint64_t nanos2 = (t3.tv_sec - t2.tv_sec) * 1000000000L + (t3.tv_nsec - t2.tv_nsec); 
     printf("%2d: %12lu %12lu %12u %12u\n", attempt+1, nanos1, nanos2, sum1, sum2); 
    } 
    return 0; 
} 

E i risultati:

tmp$ gcc -std=gnu99 -O2 test.c -o test 
tmp$ ./test 
     test1 time test2 time  test1 out test2 out 
1:  16251659  10431322 4190722540 4190722540 
2:  16796884  10639081 4190722540 4190722540 
3:  16443265  10314624 4190722540 4190722540 
4:  17194795  10337678 4190722540 4190722540 
5:  16966405  10380047 4190722540 4190722540 
6:  16803840  10556222 4190722540 4190722540 
7:  16795989  10871508 4190722540 4190722540 
8:  16389862  11511950 4190722540 4190722540 
9:  16304850  11704787 4190722540 4190722540 
10:  16309371  11269446 4190722540 4190722540 
tmp$ gcc -std=gnu99 -O3 test.c -o test 
tmp$ ./test 
     test1 time test2 time  test1 out test2 out 
1:  9090364  8813462 4190722540 4190722540 
2:  8745093  9394730 4190722540 4190722540 
3:  8942015  9839356 4190722540 4190722540 
4:  8849960  8834056 4190722540 4190722540 
5:  9567597  9195950 4190722540 4190722540 
6:  9130245  9115883 4190722540 4190722540 
7:  9680596  8930225 4190722540 4190722540 
8:  9268440  9998824 4190722540 4190722540 
9:  8851503  8960392 4190722540 4190722540 
10:  9767021  8875165 4190722540 4190722540 
tmp$ gcc -std=gnu99 -Os test.c -o test 
tmp$ ./test 
     test1 time test2 time  test1 out test2 out 
1:  17569606  10447512 4190722540 4190722540 
2:  17755450  10811861 4190722540 4190722540 
3:  17718714  10372411 4190722540 4190722540 
4:  17743248  10378728 4190722540 4190722540 
5:  18747440  10306748 4190722540 4190722540 
6:  17877105  10782263 4190722540 4190722540 
7:  17787171  10522498 4190722540 4190722540 
8:  17771172  10445461 4190722540 4190722540 
9:  17683935  10430900 4190722540 4190722540 
10:  17670540  10543926 4190722540 4190722540 
tmp$ gcc -std=gnu99 -O2 -funroll-loops test.c -o test 
tmp$ ./test 
     test1 time test2 time  test1 out test2 out 
1:  9840366  10008656 4190722540 4190722540 
2:  9826522  10529205 4190722540 4190722540 
3:  10208039  10363219 4190722540 4190722540 
4:  9863467  10284608 4190722540 4190722540 
5:  10473329  10054511 4190722540 4190722540 
6:  10298968  10520570 4190722540 4190722540 
7:  9846157  10595723 4190722540 4190722540 
8:  10340026  10041021 4190722540 4190722540 
9:  10434750  10404669 4190722540 4190722540 
10:  9982403  10592842 4190722540 4190722540 

Conclusione: il max() versione è più veloce sul mio Intel Core i7-3517U con 4 MB di cache (e non chiederei più di questo perché, ancora una volta, i risultati potrebbero variare con la microarchitettura).

Inoltre, -funroll-loops o le ottimizzazioni in più aggressivi (e meno sicure) abilitate da -O3 davvero fare una grande differenza per il caso test1, in sostanza, il che rende uguali in tempo per test2 - forse anche un po 'meglio con -funroll-loops, ma quasi abbastanza da non poter trarre una conclusione sicura dai numeri che ho ricevuto. Sarebbe probabilmente interessante vedere l'assemblea per test1 lì, ma lo lascerò come esercizio per il lettore. ;)

Quindi, credo che la risposta sia "dipende".

Answer 2

Prova di utilizzare questa funzione:

int max_array(int a[], int count) { 
    int i, 
    max = a[0]; 

    for (i = 1; i < count; i++) { 
    if (a[i] > max) { 
     max = a[i]; 
    } 
    } 

    return max; 
} 

Edit:

Siamo spiacenti, non sono visto che si è tentato che fuori. Ma comunque - questa è l'implementazione migliore, la seconda che hai proposto è semplicemente mostruosa. Penso che se vuoi mantenere pulito il tuo codice, questo è il massimo.

Answer 3

Ovviamente il primo, è più leggibile e robusto. Forse max() non è implementato nell'hardware.

Hare di un implementation di max in C++

template <class T> const T& max (const T& a, const T& b) { 
    return (a<b)?b:a;  // or: return comp(a,b)?b:a; for version (2) 
} 

E gcc-4.9.2 implementazione di C max definiscono

#define max(a,b) \ 
    ({ typeof (a) _a = (a); \ 
     typeof (b) _b = (b); \ 
    _a > _b ? _a : _b; }) 

Quindi, è meglio usare prima. Anche se le dimensioni inferiori a 3 possono essere considerate da implementare con la seconda.

Answer 4

Per quanto ne so, non esiste una funzione max o min nelle librerie standard C o GNU. Il primo sarebbe meglio da usare. Inoltre, è possibile confrontare direttamente la matrice [i] per presentare il massimo.

int largest = array[0]; 
for (int i = 1; i < 16; i++) { 
    if (array[i]>largest) 
     largest=array[i]; 
} 

Answer 5

Il primo è chiaramente l'implementazione più semplice.

Tuttavia, questo problema è correlato al concetto di Sorting Networks, che è una teoria sorprendentemente complessa sull'ordinamento di insiemi di dati a dimensione fissa.