Todo lo que un programador de C debería saber sobre el comportamiento indefinido

Hace unos días descubrí un enlace al blog del proyecto LLVM (del que hablaremos en otro momento) sobre el comportamiento indefinido de C, sus ventajas e inconvenientes. Me parece muy interesante de cara a producir código rápido y portable. De hecho, me gustó tanto que voy a colgaros su traducción tras estas líneas. No obstante se trata de una serie de tres artículos así que comienzo por el principio con este primer post que habla sobre las ventajas de no asumir ciertos comportamientos en C y por qué esto supone una ventaja en cuanto a optimización.

De vez en cuando, la gente se pregunta por qué el código compilado para LLVM genera ocasionalmente señales SIGTRAP cuando la optimiazación está acividas. Tras investigar, encuentran que Clang generó una instrucción “ud2” (asumiendo que se trate de código X86) – lo mismo que se generaría usando __builtin_trap(). Hay muchos factores en juego aquí, todos relativos al comportamiento indefinido en el código C y cómo LLVM lo maneja.

Este post (el primero de una serie de tres) trata de explicar algunos de estos factores para que puedas comprender mejor los tejemanejes y complejidades involucrados, y quizá aprender un poco más del lado oscuro de C. Resulta que C no es un “ensamblador de alto nivel” como a muchos programadores experimentados de C (particularmente aquellos con un enfoque de bajo nivel) les gusta creer, y que C++ y Objective-C han heredado directamente de él muchos de estos factores.

Introducción al comportamiento indefinido

Ambos, LLVM IR y el lenguaje de programación C, contemplan el concepto de “comportamiento indefinido”. El comportamiento indefinido es un tema muy extendido con un montón de matices. La mejor introducción que he encontrado es este artículo en el blog de John Regehr. La moraleja de este excelente artículo es que un significativo montón de cosas en C tienen, realmente, un comportamiento indefinido y son fuente común de bugs en los programas. Más allá, cualquier comportamiento indefinido en C da licencia a la implementación (el compilador y el entorno de ejecución) para producir código capaz de formatear tu disco duro, hacer cosas completamente inesperadas, o peor. De nuevo, recomiendo encarecidamente leer el artículo de John.

El comportamiento indefinido existe en los lenguajes basados en C porque los diseñadores del mismo querían que fuera un lenguaje de programación ultraeficiente a bajo nivel. En contraste, lenguajes como Java (y otros lenguajes “seguros”) han evitado el comportamiento indefinido porque querían un comportamiento seguro y reproducible entre implementaciones, aun a expensas de sacrificar rendimiento por ello. A pesar de que ninguna de las aproximaciones “es el objetivo correcto”, si eres programador de C, deberías comprender qué es el comportamiendo indefinido.

Antes de entrar en detalles, merece mencionar brévemente qué supone para un compilador conseguir un buen rendimiento en un buen rango de aplicaciones C, porque aquí no hay ninguna solución mágica. A muy alto nivel, los compiladores producen código de alto rendimiento a) haciendo un buen trabajo artesanal con algoritmos como la asignación de registros, planificación, etc; b) conociendo montones y montones de “trucos” (por ejemplo, optimizaciones en las burbujas de los pipelines, transformaciones de loops, etc) y aplicándolos cuando fuese necesario; c) siendo buenos eliminando abstracciones innecesarias (por ejemplo, redundancia debida a macros en C, función en línea, eliminando objetos temporales en C++, etc); y d) no jorobando nada. Aunque alguna de estas optimizaciones pueda parecer trivial, resulta que ganar un sólo ciclo en un bucle crítico puede hacer que un mismo código se ejecute un 10% más rápido o gaste un 10% menos de energía.

Ventajas del comportamiendo indefinido en C, con ejemplos

Antes de adentrarnos en el lado oscuro del comportamiento indefinido y las políticas y comportamientos de LLVM cuando se usa como compilador de C, he pensado que podría ser de ayuda considerar algunos pocos y específicos casos de comportamiento indefinido y hablar sobre como permiten obtener un mejor rendimiento que en el caso de un lenguaje seguro como Java. Puedes contemplar los siguiente ejemplos ya sea como “optimizaciones activadas” por el comportamiento indefinido, o bien como la “sobrecarga evitada” que sería necesaria para hacer que cada caso estuviese definido. Pese a que el optimizador del compilador podría eliminar algunas de estas sobrecargas de vez en cuando, hacerlo en general (para cada caso) requeriría solucionar el problema de la parada y muchos otros “desafíos interesantes”.

También merece la pena apuntar que tanto Clang como GCC concretan algunos pocos comportamientos que el estándard C dejaba indefinidos. Las cosas que describiré son indefinidas tanto en lo que al estándard se refiere como al comportamiento exhibido por ambos compiladores en sus modos por defecto.

Uso de una variable no inicializada: esto es una fuente común de problemas en los programas C y existen muchas herramientas para evitarlo: desde advertencias del compilador has analizadores dinámicos o estáticos. Este comportamiento mejora el rendimiento puesto que no requiere que todas las variables sean inicializadas a cero cuando entran en alcance (como sí lo hace Java). Para muchas variables enteras esto podría incurrir en una ligera sobrecarga, pero los vectores en la pila o la memoria reservada mediante malloc requerirían utilizar memset lo que podría ser bastante costoso, particularmente teniendo en cuenta que a menudo se debe establecer a cero todo el espacio.

Desbordamiento de los enteros con signo: si la aritmética de un tipo “int” (por ejemplo) desborda, el resultado es indefinido. Otro ejemplo de esto es que no se garantiza que “INT_MAX+1” sea “INT_MIN”. Este comportamiento permite cierta clases de optimizaciones que son importantes para algunos códigos. Por ejemplo, saber que INT_MAX+1 es indefinido permmite el reemplazo de “X+1 > X” por “true”. Sabiendo que la multiplicación “no puede” desbordarse (porque hacerlo resultaría indefinido) permite el reemplazo de “X*2/2” por “X”. Aunque pueda parecer trivial, esta suerte de situaciones se dan a menudo en la expansión de funciones en línea y macros. Una más importante optimización se dan en los bucles de condición “<=” como este:

for (i = 0; i <= N; ++i) { ... }

En este bucle, el compilador puede asumir que el bucle se repetirá exactamente N+1 veces si “i” es indefinida en caso de desbordamiento, lo que permite a una gran variedad de optimizaciones entrar en juego. Por otro lado, si en caso de desbordamiento, la variable volviese a comenza, el compilador debería asumir que el bucle es posiblemente infinito (lo que sucede si N es INT_MAX) – lo que incapacita la actuación de estas importantes optimizaciones de bucle. Esto afecta particularmente a las plataformas de 64bits donde gran parte del código usa “int” como variables de inducción.

Vale la pena hacer notar que se garantiza que el desbordamiento de enteros sin signo el es desbordamiento por complemento a 2 (vamos, que da la vuelta) de manera que siempre podrás usarlo. El coste de hacer el desbordamiento de enteros con signo definido es que esta clase de optimizaciones simplemente se pierden (por ejemplo, un síntoma común de esto es la tonelada de extensiones de signo que ocurre dentro de bucles en plataformas de 64bits). Ambos, Clang y GCC, aceptan la opción “-fwrapv” que fuerza al compilador a tratar el desbordamiento de los enteros con signo como definido (otro que dividir INT_MIN por -1).

Desbordamiento por desplazamiento: desplazar un uint_32 treinta y dos o más bits está indefinido. Mi intuición me dice que esta situación se originó por cómo trataban varias CPUs la operación de desplazamiento: por ejemplo, el X86 trunca la cantidad de desplazamiento de 32bits a 5bits (lo que resulta que un desplazamiento de 32 es igual a un desplazamiento de 0 y el valor se mantiene igual), pero el PowerPC trunca las cantidades de desplazamiento a 6bits (luego desplazar 32 veces un número produce cero). Debido a las diferencias en el hardware, el comportamiento es completamente indefinido en C (así, desplazar 32bits en un PowerPC podría formatear tu disco duro y *no* se garantiza que produzca cero). El coste de elimina el comportamiento indefinido es que el compilador tendría que emitir una operación extra (como un ‘and’) para los desplazamientos de variables, lo que las convertiría en el doble de costosas en la mayoría de las CPUs.

Derreferencia a punteros no definidos o accesos fuera de los límites de un vector: derreferenciar un puntero aleatorio (como NULL, punteros a memoria liberada por free, etc) y el caso especial de acceder a un vector fuera de sus límites is un bug común en las aplicaciones C que, espero, no necesita explicación alguna. Para eliminar esta fuente de comportamiento indefinido, deberían verificarse los límites del vector por cada acceso, y el ABI debería alterarse para asegurar que la información sobre el rango es parte de cualquier puntero que pudiera ser objeto de aritmética de punteros con él. Esto resultaría en un coste extremadamente alto para la mayría de las aplicaciones numéricas o de otra índole y además rompería la compatibilidad con todas las librerías C existentes.

Derreferencia de un puntero NULL: contrariamente a la creencia popular, derreferenciar un puntero nulo no está definido en C. No está definido para originar un trap, y si realizas mmap a la página 0, no está definido que acceda a dicha página. Esto cae fuera de las reglas que prohiben derreferenciar punteros no definidos y el uso de NULL como centinela. Mantener las derreferencias a punteros NULL indefinidas habilitan un buen rango de optimizaciones: en contraste, Java prohibe al compilador extender operaciones con efectos colaterales a través de cualquier derreferencia de un puntero que no haya sido probada por el optimizador como no nulo. Esto perjudica notoriamente la planificación y otras optimizaciones. En los lenguajes basados en C, NULL indefinido habilita un gran número de optimizaciones simples para escalares que son el resultado de la expansión de macros y funciones en línea.

Si estás usando un compilador basado en LLVM, puedes derreferencia un puntero nulo “volátil” para obtener un error en el programa si es lo que estabas buscando dado que las instrucciones load o store volátiles no son alteradas por el optimizador. Actualmente no hay ninguna opción que habilite el tratamiento de loads con punteros a NULL como accesos válidos u opción que permita a los load saber que a sus punteros “se kes permite ser nulos”.

Violar las reglas de tipos: es un comportamiento indefinido hacer cast de un int* a un float* y derreferenciarlo (acceder a un “int” como si fuera un “float”). C requiere que este tipo de conversiones ocurran a través de memcpy: usar un cast sobre un puntero no es correcto y resulta en un comportamiento indefinido. Las reglas que rigen estas situaciones están lo suficientemente definidas y no quiero entrar en detalles aquí (hay una excepción para los char*, los vectores tienen propiedades especiales, las uniones son una cosa distinta, etc). Este comportamiento permite un tipo de análisis conocido como “Análisis de Alias Basado en Tipo” (Type-Based Alias Analysis o TBAA) el cual se usa en un gran rango de optimizaciones del compilador para acceso a memoria, y puede mejorar significativamente el rendimiento del código generado. Por ejemplo, estas reglas permitan a Clang reemplazar esta función:

float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
 }

por “memset(P, 0, 40000)“. Esta optimización también permite que muchos loads sean extraidos fuera de los bucles, algunas subexpresiones comunes eliminadas, etc. Esta forma de comportamiento indefinido puede desactivarse pasando la opción -fno-strict-aliasing, lo que impide este tipo de análisis. Cuando se pasa esta opción, Clang compila este bucle como 10000 almacenamientos de 4 bytes (lo cual es muchas veces más lento), dado que debe asumir que es posible que cualquiera de las intrucciones de almacenamiento cambie el valor de P, como ocurriría en el algo como esto:

int main() {
  P = (float*)&P;  // el cast causa una violación del TBAA en zero_array.
  zero_array();
}

Este tipo de abusos es muy inusual lo cual explica por qué el comité de estandarización decidió que las significativas ganancias de rendimiento merecíeran el resultado inesperado para los cast “razonables” entre tipos. Vale la pena hacer notar que Java se beneficia de optimizaciones basadas en tipos sin estas desventajas porque no tiene que lidiar con casts inseguros entre punteros.

De cualquie forma, espero que esto te haya dado una idea de los tipos de optimizaciones que el comportamiento indefinido en C permite. Hay otros tipos de comportamientos indefinidos, por supuesto, incluyendo violaciones de secuencia como en “foo(i, ++i)”, condiciones de carrera en programas multi-hilo, violaciones de tipo “restrict”, divisiones entre cero, etc.

En nuestro siguiente post, discutiremos acerca de por qué el comportamiento indefinido en C es algo que da mucho miedo si tu objetivo no es solamente la optimización. En el último artículo hablaremos de como LLVM y Clang lidian con él.

Fuente: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

Autor de la versión original en inglés: Chris Lattner

Anuncios

3 comentarios en “Todo lo que un programador de C debería saber sobre el comportamiento indefinido

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s