Wie findet man das größte Element eines Arrays bekannter Größe?

Question

Ich muss das größte Element in einem Array finden, das genau 16 ganze Zahlen enthält. Ich überlege mir zwei mögliche Implementierungen. Erstens ist die sinnvolle Umsetzung:

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

Und dann ist da noch die etwas verrückt Implementierung, die sich die Tatsache zunutze nimmt, dass die Größe des Arrays bekannt ist:

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])))); 

Welches ist die bessere Umsetzung ist? Ist max typischerweise in Hardware implementiert?

Answer 1

Lassen Sie uns sie kompilieren und sehen, was wir bekommen!

Zuerst, AFAIK, gibt es keine "Max" -Funktion/Makro in der C-Norm definiert. Also habe ich eins hinzugefügt (das sieht kompliziert aus, weil es die doppelte Auswertung seiner Eingaben vermeidet).

#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; 
} 

Meine gcc-Version, die relevant ist, wenn es um Optimierungen zu sprechen:

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 für Optimierungen, -S zu Ausgabebaugruppe, -o - zur Ausgabe an stdout.

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 

Okay, so sieht test2() sicherlich viel länger aus.Es verzweigt sich jedoch überhaupt nicht. Und es sind nur ~ 3 Anweisungen (Speicherlast, Vergleich, bedingte Verschiebung) pro Element. test1() hat 6 Anweisungen (Speicherbelastung, Vergleich, bedingte Verschiebung, Schleifenzählerinkrement, Schleifenzählervergleich, bedingte Verzweigung). Viele Zweige in test1, die lästig sein können (abhängig davon, wie gut die Verzweigungsvorhersage Ihrer Architektur ist). Auf der anderen Seite, test2 erhöht die Code-Größe, die notwendigerweise etwas anderes aus dem Befehls-Cache schieben wird. Und es gibt viele Datenhindernisse in test2 (gut, und test1 ...) - vielleicht könnten wir es umschreiben, um ein paar zusätzliche Register zu verwenden, um die Anzahl von Pipeline-Ständen zu reduzieren?

Also, wie Sie jetzt wahrscheinlich sehen können, ist dies keine einfache Frage zu beantworten.

Der einzige wirkliche Weg zu wissen ist, es zu messen. Und selbst dann wird es abhängig von der internen Implementierung/Optimierung/Cachegröße jedes CPU-Modells variieren.

Also schrieb ich einen kleinen Maßstab:

#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; 
} 

Und die Ergebnisse:

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 

Fazit: Die max() Version ist schneller auf meinem Intel Core i7-3517U mit 4 MB Cache (und ich würde nicht mehr beanspruchen, da die Ergebnisse wiederum mit der Mikroarchitektur variieren können).

Auch -funroll-loops oder die extra aggressive (und weniger sicher) Optimierungen aktiviert durch -O3 wirklich einen großen Unterschied für den test1 Fall machen, es im Wesentlichen gleich in der Zeit test2 machen - vielleicht sogar etwas besser mit -funroll-loops, aber in der Nähe Genug, dass wir aus den Zahlen, die ich bekommen habe, keine sichere Schlussfolgerung ziehen können. Es wäre wahrscheinlich interessant, die Versammlung für test1 dort zu sehen, aber ich werde das als eine Übung für den Leser verlassen. ;)

Also, ich denke die Antwort ist "es kommt darauf an".

Answer 2

Versuchen Sie diese Funktion verwenden:

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:

Sorry, sah nicht, dass du das ausprobiert. Aber wie auch immer - das ist die bessere Umsetzung, die zweite, die Sie vorgeschlagen haben, ist einfach monströs. Ich denke, wenn Sie Ihren Code sauber halten wollen, ist das so weit wie Sie gehen.

Answer 3

Offensichtlich der erste, es ist lesbarer und robust. Vielleicht ist max() nicht in Hardware implementiert.

Hasen ein implementation von 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) 
} 

und gcc-4.9.2 Implementierung von C max definieren als

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

Also, es ist besser, zuerst zu verwenden. Obwohl eine Größe von weniger als 3 in Betracht gezogen werden kann, ist es sinnvoll, diese mit der zweiten zu implementieren.

Answer 4

Soweit ich weiß, gibt es in den C- oder GNU-Standardbibliotheken keine Max- oder Min-Funktion. Die erste wäre besser zu verwenden. Sie können Array [i] auch direkt mit dem aktuellen Maximum vergleichen.

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

Answer 5

Die erste ist eindeutig die einfachste Implementierung.

Nichtsdestoweniger ist dieses Problem mit dem Konzept von Sorting Networks, die eine überraschend komplexe Theorie zum Sortieren von Datensätzen fester Größe ist.