Q

Quali sono alcune operazioni che richiedono molto tempo in C?

2009-07-15 4 views 13 likes

13

Sto cercando di scrivere un programma di benchmark veloce che possa essere compilato ed eseguito su varie macchine. Piuttosto che usare le opzioni commercialmente/open-sourly disponibili, preferirei che fosse il mio a giocare con le tecniche di ottimizzazione del thread e dell'algoritmo.Quali sono alcune operazioni che richiedono molto tempo in C?

Ho un paio che uso già, che include ricorsivamente il calcolo dell'ennesimo numero della sequenza di Fibonacci, e di seeding/rand() in poche migliaia di volte.

Esistono altri algoritmi relativamente semplici, ma allo stesso tempo intensi di calcolo (e possibilmente correlati alla matematica)?

(Si noti che queste operazioni saranno attuate nel linguaggio C.)

2009-07-15 Craig Otis

+0

Allora, cosa vuoi fare un punto di riferimento? Prestazioni intere? Virgola mobile? Velocità di accesso alla RAM? La dimensione e la velocità dei vari livelli di cache? L'unica cosa che posso vedere è che non ti interessa I/O (che probabilmente domina per i compiti che la maggior parte delle persone fa). – starblue

+0

Qualsiasi e tutte le precedenti. :) –

A

risposta

8

Il Ackermann function è di solito un divertimento uno, ma non danno molto grandi ingressi se si vuole che finisca nella vostra vita .

2009-07-15 18:57:38 Welbog

2

Inverso grandi matrici.

2009-07-15 18:57:46 levesque

0

La ricerca di numeri primi è considerata piuttosto lunga.

2009-07-15 18:59:09 AlbertoPL

2

È possibile calcolare i numeri primi grandi o gli interi di fattorizzazione.

2009-07-15 18:59:28 Jonathan

0

Questo fa un sacco di più:

int c = 0; 
for (int n = 0; n < INT_MAX; n++) 
    for (int m = 0; m < INT_MAX; m++) 
     c++; 

std::cout << c;

2009-07-15 18:59:57

+5

In realtà, non è così. Qualsiasi decompattatore vedrà che non hai fatto assolutamente nulla con n o m, e quindi ottimizzerà tutto via. –

+1

E l'aggiunta di numeri è una delle cose che i computer fanno meglio. La moltiplicazione fluttuante della larghezza arbitraria sarebbe più intensa! –

+0

@Ken White - hanno apportato delle modifiche. –

2

Date un'occhiata al NAS Parallel Benchmarks. Questi sono stati originariamente scritti da NASA in Fortran per i supercomputer che utilizzano MPI (e sono ancora disponibili in quel modo), ma sono disponibili anche implementazioni C, Java e OpenMP.

La maggior parte di questi sono molto molto intensi dal punto di vista computazionale, in quanto sono destinati a rappresentare gli algoritmi numerici utilizzati nel calcolo scientifico.

2009-07-15 19:00:07 tgamblin

3

frattali

(in varie risoluzioni) Some fractal source in C (without opengl)

2009-07-15 19:00:25

+0

+1: Mi piace questo perché puoi goderti i risultati. Oppure se usi un algoritmo che migliora se stesso iterativamente puoi vederlo funzionare, il che è sempre più divertente! – Welbog

+0

Sì, è sufficiente non utilizzare una GPU tramite OpenGL, ovviamente ciò vanificherà lo scopo del benchmarking. Puoi anche divertirti con un sacco di matematica complessa che insieme abusano dell'API di matematica per il benchmarking e crea un bel frattale. –

3

So che hai detto che volevi fare il vostro proprio, ma forse si potrebbe attingere benchmark esistenti per l'ispirazione. The Computer language benchmark game ha eseguito molti linguaggi di programmazione attraverso una serie di benchmark. Forse puoi avere qualche idea guardando i loro benchmark.

Alcune idee veloci della parte superiore della mia testa:

moltiplicazione di matrici: mulitplying 2 grandi matrici è relativamente computazionalmente intensive, anche se si dovrà prendere il caching in considerazione
Generazione di numeri primi
Factorage intero
Metodi numerici per ODE solving - Runge-kutta ad esempio

2009-07-15 19:02:06 Falaina

+0

Raytracing è un'altra buona attività che richiede molta CPU. – KitsuneYMG

0

Acquista i parametri di riferimento della sparatoria lingua: http://shootout.alioth.debian.org/

Tuttavia: parametri di riferimento sono solo punti di riferimento e non necessariamente ti dicono molto su il mondo reale e, al contrario, può essere fuorviante.

2009-07-15 19:02:30 bayer

1

Provare a calcolare migliaia o milioni di cifre pi. Ci sono un bel po 'di formulas per quell'attività.

2009-07-15 19:03:05

+0

Fabrice Bellard di QEmu è lo scopritore della formula di calcolo Pi più efficiente ... bellard.org/pi multi-talento! ... e ha vinto un contest di offuscamento alla fonte con l'implementazione! –

+0

Ho letto un articolo su Fabrice Bellard in una rivista Linux. Ragazzo intelligente! –

0

Se vuoi provare il parallelismo, fai un sacco di matematica a matrice. La dimensione della matrice che puoi usare sarà limitata dalla memoria, ma puoi fare quante iterazioni vuoi.

Questo sottolineerà le istruzioni SIMD fornite dalle moderne CPU.

2009-07-15 19:10:24 samoz

1

Ne avete alcuni davvero belli in project euler, quelli sono tutti correlati alla matematica e possono richiedere molto tempo, come si desidera utilizzare valori più elevati.

2009-07-15 19:18:58

+0

non proprio, con gli algoritmi appropriati (che è quello che i puzzle cercano di motivare) la maggior parte dei problemi si bilancia ragionevolmente bene. sfortunatamente, per molti di questi problemi l'hardware comune è abbastanza veloce da rendere la forza bruta abbastanza veloce, a volte con un enorme margine. – Javier

+0

so ma se usa alcuni dei problemi più difficili (e quelli che aumentano i valori li rende molto più dispendiosi in termini di tempo) otterrà algoritmi degni di utilizzo in un'app benchmark –

0

Si può provare un tsort (Turbo Sort) con un set di input molto grande. Capisco che sia un'operazione comune.

2009-07-15 19:32:08

0

Euristiche per i problemi NP-Complete sono un modo divertente per ottenere un codice intensivo della CPU. È possibile codificare una "soluzione" :) per uno dei problemi NP-Karps completi.

2009-07-15 21:16:36 tr9sh