Lenguaje más rápido para los bucles FOR

Question

Estoy tratando de encontrar el mejor lenguaje de programación para un modelo analítico que estoy construyendo. La consideración principal es la velocidad a la que ejecutará los bucles FOR.

Algunos detalle:

• El modelo necesita realizar numerosas (~ 30 por entrada, de más de 12 ciclos) operaciones en un conjunto de elementos de una matriz - hay ~ 300k filas, y ~ 150 columnas en el conjunto. La mayoría de estas operaciones son de naturaleza lógica, por ejemplo, si place (i) = 1, entonces j (i) = 2.
• He creado una versión anterior de este modelo usando Octave - para ejecutarlo toma ~ 55 horas en una instancia de Amazon EC2 m2.xlarge (y utiliza ~ 10 GB de memoria, pero estoy muy contento de tirar más memoria). Octave/Matlab no realizará operaciones lógicas con elementos, por lo que se necesita una gran cantidad de bucles para for - estoy relativamente seguro de haber vectorizado tanto como sea posible - los bucles que quedan son necesarios. He obtenido octava-multicore para que funcione con este código, lo que mejora (~ 30% de reducción de velocidad cuando lo ejecuto en 8 núcleos EC2), pero termina siendo inestable con bloqueo de archivos, etc. + Estoy realmente estoy buscando un cambio radical en el tiempo de ejecución: sé que el hecho de utilizar Matlab me da una mejora de hasta un 50% si miro algunos puntos de referencia, pero eso es un costo prohibitivo. El plan original al comenzar esto era ejecutar un Monte Carlo con esto, pero a las 55 horas de carrera, eso es completamente impráctico.
• La próxima versión de esto va a ser una reconstrucción completa desde cero (por razones de IP que no entraré si nada más), por lo que estoy completamente abierto a cualquier lenguaje de programación. Estoy muy familiarizado con Octave/Matlab, pero he incursionado en R, C, C++, Java. También soy hábil con SQL si la solución implica almacenar los datos en una base de datos. Aprenderé cualquier idioma para esto: estas no son funcionalidades complicadas que estamos buscando, no interactúan con otros programas, etc., así que no estamos demasiado preocupados por la curva de aprendizaje.

Con todo lo dicho, ¿cuál es el lenguaje de programación más rápido específicamente para los bucles FOR? A partir de una búsqueda de SO y Google, Fortran y C llegan a la cima, pero buscan más consejos antes de sumergirse en uno u otro.

Gracias!

Answer 1

En términos de velocidad absoluta, probablemente Fortran seguido de C, seguido de C++. En la aplicación práctica, un código bien escrito en cualquiera de los tres, compilado con un compilador de bajada debe ser bastante rápido.

Edición: en general, verá un rendimiento mucho mejor con cualquier tipo de código en bucle o bifurcación (por ejemplo, si las declaraciones) con un lenguaje compilado, frente a un idioma interpretado.

Para dar un ejemplo, en un proyecto reciente en el que estaba trabajando, los tamaños de datos y las operaciones eran aproximadamente 3/4 del tamaño de lo que está hablando aquí, pero como su código, tenía muy poco espacio para vectorización y requirió un looping significativo. Después de convertir el código de matlab a C++, los tiempos de ejecución pasaron de 16 a 18 horas, hasta alrededor de 25 minutos.

Answer 2

¿Cómo se almacenan los datos? Su tiempo de ejecución probablemente se vea más afectado por las E/S (especialmente el disco o peor, la red) que por su idioma.

Suponiendo que las operaciones en las filas son ortogonales, me gustaría ir con C# y usar PLINQ para explotar todo el paralelismo que pueda.

Answer 3

Este bucle se ve no más complejo que esto cuando llegue a la CPU:

for(int i = 0; i != 1024; i++) se traduce en

mov r0, 0   ;;start the counter  
top: 

;;some processing 

add r0, r0, 1  ;;increment the counter by 1 
jne top: r0, 1024 ;;jump to the loop top if we havn't hit the top of the for loop (1024 elements) 

;;continue on 

Como se puede ver, esto es lo suficientemente sencillo que en realidad no puede optimizarlo muy bien [1] ... Reenfoque hacia el nivel del algoritmo.

El primer corte en el problema es buscar en la localidad de caché. Busque el ejemplo clásico de multiplicación de matrices e intercambie los índices i y j.

editar: Como segundo corte, yo sugeriría que evalúe el algoritmo para las dependencias de datos entre iteraciones y la dependencia de datos entre las localidades en su 'matriz' de datos. Puede ser un buen candidato para la paralelización.

[1] Hay algunas micro -optimizations posibles, pero ésas no producirán las aceleraciones que estás buscando.

Answer 4

Para lo que está discutiendo, Fortran es probablemente su primera opción. El segundo lugar más cercano es probablemente C++. Algunas bibliotecas C++ usan "plantillas de expresión" para ganar algo de velocidad sobre C para este tipo de tarea. No es del todo seguro que te sirva de algo, pero C++ puede ser al menos tan rápido como C, y posiblemente algo más rápido.

Al menos en teoría, no hay ninguna razón por la que Ada tampoco sea competitiva, pero hace tanto tiempo que no la utilicé como para dudar en recomendarla, no porque no sea buena, pero porque simplemente no he hecho un seguimiento de los compiladores de Ada lo suficientemente bien como para comentar sobre ellos de forma inteligente.

Answer 5

~300k * ~150 * ~30 * ~12 = ~16G iteraciones, ¿no? Este número de operaciones primitivas debería completarse en cuestión de minutos (si no de segundos) en cualquier lenguaje compilado en cualquier CPU decente. Fortran, C/C++ debería hacerlo casi igual de bien. Incluso los lenguajes administrados, como Java y C#, solo se quedarían atrás por un pequeño margen (si es que lo hacen).

Si tiene un problema de ~ 16G iteraciones corriendo 55 horas, esto significa que están muy lejos de ser primitivas (80k por segundo, esto es ridículo), así que tal vez deberíamos saber más. (como ya se sugirió, ¿el acceso al disco limita el rendimiento? ¿es el acceso a la red?)

Answer 6

¿No sería mejor con un inserto de ensamblador codificado a mano? Suponiendo, por supuesto, que no necesita portabilidad.

Eso y un algoritmo optimizado deberían ayudar (¿y quizás reestructurar los datos?).

Es posible que también desee probar varios algoritmos y perfilarlos.

Answer 7

¿qué tal un lenguaje de carga vago como clojure. es un ceceo, así que, como la mayoría de los dialectos de lisp, carece de un bucle for, pero tiene muchas otras formas que operan más idiomáticamente para el procesamiento de listas. También podría ayudarlo con sus problemas de escala porque las operaciones son seguras para hilos y, dado que el lenguaje es funcional, tiene menos efectos secundarios. Si desea encontrar todos los elementos en la lista que tenían valores 'i' para operarlos, podría hacer algo como esto.

(def mylist ["i" "j" "i" "i" "j" "i"]) 
(map #(= "i" %) mylist) 

resultado

(true false true true false true)

Answer 8

Cualquier lenguaje compilado debe realizar el propio bucle en términos más o menos iguales.

Si puede formular su problema en sus términos, es posible que desee ver CUDA u OpenCL y ejecutar su código de matriz en la GPU, aunque esto es menos bueno para el código con muchos condicionales.

Si desea permanecer en las CPU convencionales, es posible que pueda formular su problema en términos de operaciones de dispersión/recopilación SSE y máscara de bits.

Answer 9

APL.

Aunque se interpreta, todos sus operadores primitivos operan en matrices de forma nativa, por lo que rara vez necesita ningún bucle explícito. Usted escribe el mismo código, ya sea que los datos sean escalares o de matriz, y el intérprete se encarga de cualquier bucle necesario internamente y, por lo tanto, con la sobrecarga mínima: los bucles están en un lenguaje compilado y se han optimizado en gran medida para el específico arquitectura de la CPU en la que se está ejecutando.

Aquí está un ejemplo de la simplicidad de la matriz de manipulación en APL:

A <- 2 3 4 5 6 8 10 
    ((2|A)/A) <- 0 
    A 
2 0 4 0 6 8 10 

La primera línea de los conjuntos A a un vector de números. La segunda línea reemplaza todos los números impares en el vector con ceros. La tercera línea consulta los nuevos valores de A, y la cuarta línea es la salida resultante.

Tenga en cuenta que no se requiere bucle explícito, como operadores escalares como '|' (resto) se extiende automáticamente a las matrices según sea necesario. APL también tiene primitivas integradas para buscar y clasificar, que probablemente serán más rápidas que escribir sus propios bucles para estas operaciones.

Wikipedia tiene un buen article on APL, que también proporciona enlaces a proveedores como IBM y Dyalog.

Answer 10

Como dijo @Rotsor, 16G operaciones/55 horas son aproximadamente 80,000 operaciones por segundo, o una operación cada 12.5 microsegundos. Eso es mucho tiempo por operación.

Eso significa que sus bucles no son la causa del bajo rendimiento, es lo que es en el bucle más interno que se está tomando el tiempo. Y Octave es un lenguaje interpretado. Eso solo significa una desaceleración de orden de magnitud.

Si desea velocidad, primero necesita estar en un lenguaje compilado. Luego necesita hacer ajuste de rendimiento (también conocido como perfilado) o, solo un paso en un depurador en el nivel de instrucción. Eso te dirá lo que realmente está haciendo en el fondo de su corazón. Una vez que lo hagas donde no está desperdiciando los ciclos, el hardware más elegante, los núcleos, CUDA, etc. te darán una aceleración de paralelismo. Pero es una tontería hacerlo si su código toma innecesariamente muchos ciclos. (Here's an example of performance tuning - a 43x speedup just by trimming the fat.)

No puedo creer la cantidad de personas que responden hablando de matlab, APL y otros lenguajes vectorizados. Esos son intérpretes. Le dan concisa código fuente, que no es en absoluto lo mismo que ejecución rápido.Cuando se trata del bare metal, están atrapados con el mismo hardware que cualquier otro idioma.

---

Agregado: para mostrar lo que quiero decir, yo acabo de encontrar el código C++, lo que hace operaciones 16G, en este viejo portátil con moho, y tardó 94 segundos, o alrededor de 6ns por iteración. (No puedo creer que hayas dormido esa cosa por 2 días completos.)

void doit(){ 
    double sum = 0; 
    for (int i = 0; i < 1000; i++){ 
    for (int j = 0; j < 16000000; j++){ 
     sum += j * 3.1415926; 
    } 
    } 
} 

Answer 11

Probablemente el lenguaje ensamblador para cualquiera que sea tu plataforma. Pero los compiladores (especialmente los de propósito especial que se dirigen específicamente a una sola plataforma (por ejemplo, Analog Devices o TI DSP) son a menudo tan buenos o mejores que los humanos. Además, los compiladores a menudo conocen trucos que tú no conoces. Por ejemplo, los DSP antes mencionados admiten bucles de cero gasto y el compilador sabrá cómo optimizar el código para usar esos bucles.

Answer 12

Cualquier lenguaje moderno compilado o JIT se va a procesar hasta casi el mismo código de lenguaje de máquina, dando un ciclo de sobrecarga de 10 nano segundos o menos, por iteración, en procesadores modernos.

@Rotsor Citando:

Si usted tiene un problema de iteraciones ~ 16G ejecutan 55 horas, esto significa que están muy lejos de ser primitiva (80k por segundo esto es ridículo?), Así que tal vez debería saber mas

Las 80k operaciones por segundo son alrededor de 12,5 microsegundos cada una, un factor de 1000 veces mayor que la sobrecarga del circuito que cabría esperar.

Asumiendo que su tiempo de ejecución de 55 horas es de rosca simple, y si sus operaciones por artículo son tan simples como se sugiere, podrá (conservadoramente) lograr una aceleración de 100x y reducirla a menos de una hora muy fácilmente.

Si desea ejecutar aún más rápido, querrá buscar la solución de escritura de subprocesos múltiples, en cuyo caso, un lenguaje que proporcione un buen soporte sería esencial. Me inclinaría hacia PLINQ y C# 4.0, pero eso es porque ya sé C# - YMMV.

Answer 13

Matlab hará operaciones lógicas con los elementos y generalmente son bastante rápidas.

Aquí está un ejemplo rápido en mi equipo (AMD Athlon 2,3 GHz w/3GB):

d=rand(300000,150); 
d=floor(d*10); 

>> numel(d(d==1)) 
ans = 
    4501524 

>> tic;d(d==1)=10;toc; 
Elapsed time is 0.754711 seconds. 

>> numel(d(d==1)) 
ans = 
    0 
>> numel(d(d==10)) 
ans = 
    4501524 

En general he encontrado operadores de MATLAB son muy rápido, sólo hay que encontrar maneras de expresar su algoritmos directamente en términos de operadores de matriz.

Answer 14

C++ es no rápido al hacer cosas matrices con bucles for. C es, de hecho, específicamente malo en eso. Ver good math bad math.

He oído que C99 tiene __restrict punteros que ayudan, pero no saben mucho al respecto.

Fortran sigue siendo el lenguaje común para la computación numérica.