Orden de evaluación de índices de matriz (versus la expresión) en C

47

Mirando este código:

static int global_var = 0;

int update_three(int val)
{
    global_var = val;
    return 3;
}

int main()
{
    int arr[5];
    arr[global_var] = update_three(2);
}

¿Qué entrada de matriz se actualiza? 0 o 2?

¿Hay alguna parte en la especificación de C que indique la precedencia de la operación en este caso particular?

Jiminion
fuente
21
Esto huele a comportamiento indefinido. Ciertamente es algo que nunca debe ser codificado a propósito.
Fiddling Bits
1
Estoy de acuerdo en que es un ejemplo de mala codificación.
Jiminion
44
Algunos resultados anecdóticos: godbolt.org/z/hM2Jo2
Bob__
15
Esto no tiene nada que ver con los índices de matriz o el orden de las operaciones. Tiene que ver con lo que la especificación C llama "puntos de secuencia" y, en particular, el hecho de que las expresiones de asignación NO crean un punto de secuencia entre la expresión de la izquierda y la derecha, por lo que el compilador es libre de hacer lo que quiera. elige.
Lee Daniel Crocker
44
Debe informar una solicitud de función para clangque este código active una advertencia en mi humilde opinión.
Malat

Respuestas:

51

Orden de operandos izquierdo y derecho

Para realizar la asignación arr[global_var] = update_three(2), la implementación de C debe evaluar los operandos y, como efecto secundario, actualizar el valor almacenado del operando izquierdo. C 2018 6.5.16 (que trata sobre las asignaciones), el párrafo 3 nos dice que no hay secuencia en los operandos izquierdo y derecho:

Las evaluaciones de los operandos no tienen secuencia.

Esto significa que la implementación de C es libre de calcular primero el valor de l arr[global_var] (al calcular el valor de l, nos referimos a averiguar a qué se refiere esta expresión), luego evaluar update_three(2)y finalmente asignar el valor de este último al primero; o para evaluar update_three(2)primero, luego calcular el valor l, luego asignar el primero al segundo; o para evaluar el valor de l y update_three(2)de alguna manera entremezclada y luego asignar el valor correcto al valor de l izquierdo.

En todos los casos, la asignación del valor al valor l debe ser la última, porque 6.5.16 3 también dice:

... El efecto secundario de actualizar el valor almacenado del operando izquierdo se secuencia después de los cálculos del valor de los operandos izquierdo y derecho ...

Violación de secuencia

Algunos podrían reflexionar sobre el comportamiento indefinido debido al uso global_vary la actualización por separado en violación de 6.5 2, que dice:

Si un efecto secundario en un objeto escalar no está secuenciado en relación con un efecto secundario diferente en el mismo objeto escalar o un cálculo de valor utilizando el valor del mismo objeto escalar, el comportamiento no está definido ...

Es muy familiar para muchos practicantes de C que el comportamiento de expresiones tales como x + x++no está definido por el estándar C porque ambos usan el valor xy lo modifican por separado en la misma expresión sin secuenciar. Sin embargo, en este caso, tenemos una llamada de función, que proporciona una secuencia. global_varse usa arr[global_var]y se actualiza en la llamada de función update_three(2).

6.5.2.2 10 nos dice que hay un punto de secuencia antes de llamar a la función:

Hay un punto de secuencia después de las evaluaciones del designador de funciones y los argumentos reales, pero antes de la llamada real ...

Dentro de la función, global_var = val;hay una expresión completa , y también lo es 3in return 3;, por 6.8 4:

Una expresión completa es una expresión que no es parte de otra expresión, ni parte de un declarador o declarante abstracto ...

Luego hay un punto de secuencia entre estas dos expresiones, nuevamente por 6.8 4:

... Hay un punto de secuencia entre la evaluación de una expresión completa y la evaluación de la próxima expresión completa que se evaluará.

Por lo tanto, la implementación de C puede evaluar arr[global_var]primero y luego hacer la llamada a la función, en cuyo caso hay un punto de secuencia entre ellos porque hay uno antes de la llamada a la función, o puede evaluar global_var = val;en la llamada a la función y luego arr[global_var], en cuyo caso hay un punto de secuencia entre ellos porque hay uno después de la expresión completa. Por lo tanto, el comportamiento no está especificado (cualquiera de esas dos cosas puede evaluarse primero), pero no está indefinido.

Eric Postpischil
fuente
24

El resultado aquí no está especificado .

Si bien el orden de las operaciones en una expresión, que dicta cómo se agrupan las subexpresiones, está bien definido, el orden de evaluación no se especifica. En este caso, significa que se global_varpodría leer primero o que la llamada update_threepodría ocurrir primero, pero no hay forma de saber cuál.

Aquí no hay un comportamiento indefinido porque una llamada a la función introduce un punto de secuencia, al igual que cada declaración en la función, incluida la que modifica global_var.

Para aclarar, el estándar C define el comportamiento indefinido en la sección 3.4.3 como:

comportamiento indefinido

comportamiento, al usar una construcción de programa no portable o errónea o de datos erróneos, para los cuales esta Norma Internacional no impone requisitos

y define el comportamiento no especificado en la sección 3.4.4 como:

comportamiento no especificado

uso de un valor no especificado u otro comportamiento donde esta Norma Internacional ofrece dos o más posibilidades y no impone requisitos adicionales sobre los cuales se elige en ningún caso

El estándar establece que el orden de evaluación de los argumentos de la función no está especificado, lo que en este caso significa que arr[0]se establece en 3 o arr[2]se establece en 3.

dbush
fuente
"Una llamada de función introduce un punto de secuencia" es insuficiente. Si el operando izquierdo se evalúa primero, es suficiente, ya que el punto de secuencia separa el operando izquierdo de las evaluaciones en la función. Pero, si el operando izquierdo se evalúa después de la llamada a la función, el punto de secuencia debido a llamar a la función no está entre las evaluaciones en la función y la evaluación del operando izquierdo. También necesita el punto de secuencia que separa las expresiones completas.
Eric Postpischil
2
@EricPostpischil En la terminología anterior a C11 hay un punto de secuencia en la entrada y salida de una función. En la terminología C11, todo el cuerpo de la función está secuenciado indeterminadamente con respecto al contexto de llamada. Ambos especifican lo mismo, solo que usan términos diferentes
MM
Esto está absolutamente mal. El orden de evaluación de los argumentos de la tarea no está especificado. En cuanto al resultado de esta asignación particular, es la creación de una matriz con un contenido poco confiable, tanto no portátil como intrínsecamente incorrecto (inconsistente con la semántica o con cualquiera de los resultados previstos). Un caso perfecto de comportamiento indefinido.
Kuroi Neko
1
@kuroineko El hecho de que el resultado pueda variar no lo convierte automáticamente en un comportamiento indefinido. El estándar tiene diferentes definiciones de comportamiento indefinido versus no especificado, y en esta situación es el último.
dbush
@EricPostpischil Aquí tiene puntos de secuencia (del C11 informativo Anexo C): "Entre las evaluaciones del designador de funciones y los argumentos reales en una llamada a la función y la llamada real. (6.5.2.2)", "Entre la evaluación de una expresión completa y la siguiente expresión completa que se evaluará ... / - / ... la expresión (opcional) en una declaración de retorno (6.8.6.4) ". Y bueno, también en cada punto y coma, ya que es una expresión completa.
Lundin
1

Lo intenté y obtuve la entrada 0 actualizada.

Sin embargo, de acuerdo con esta pregunta: el lado derecho de una expresión siempre se evalúa primero

El orden de evaluación no está especificado ni secuenciado. Así que creo que un código como este debería evitarse.

Mickael B.
fuente
También recibí la actualización en la entrada 0.
Jiminion
1
El comportamiento no es indefinido sino no especificado. Naturalmente, dependiendo de cualquiera se debe evitar.
Antti Haapala
@AnttiHaapala que he editado
Mickael B.
1
Hmm ah, y no está sin secuenciar, sino que está secuenciado de forma indeterminada ... 2 personas paradas de forma aleatoria en una cola son secuenciadas de forma indeterminada. Neo dentro del Agente Smith no tiene secuencia y sucederá un comportamiento indefinido.
Antti Haapala
0

Como tiene poco sentido emitir código para una asignación antes de tener un valor para asignar, la mayoría de los compiladores de C emitirán primero código que llama a la función y guardarán el resultado en algún lugar (registro, apilamiento, etc.), luego emitirán código que escribe este valor en su destino final y, por lo tanto, leerán la variable global después de que se haya cambiado. Llamemos a esto el "orden natural", no definido por ningún estándar sino por pura lógica.

Sin embargo, en el proceso de optimización, los compiladores intentarán eliminar el paso intermedio de almacenar temporalmente el valor en algún lugar e intentar escribir el resultado de la función lo más directamente posible en el destino final y, en ese caso, a menudo tendrán que leer primero el índice , por ejemplo, a un registro, para poder mover directamente el resultado de la función a la matriz. Esto puede hacer que la variable global se lea antes de que se cambie.

Entonces, este es básicamente un comportamiento indefinido con la muy mala propiedad de que es bastante probable que el resultado sea diferente, dependiendo de si se realiza la optimización y qué tan agresiva es esta optimización. Es su tarea como desarrollador resolver ese problema codificando:

int idx = global_var;
arr[idx] = update_three(2);

o codificación:

int temp = update_three(2);
arr[global_var] = temp;

Como buena regla general: a menos que las variables globales sean const(o no lo sean, pero usted sabe que ningún código las cambiará como efecto secundario), nunca debe usarlas directamente en el código, como en un entorno de subprocesos múltiples, incluso esto puede ser indefinido:

int result = global_var + (2 * global_var);
// Is not guaranteed to be equal to `3 * global_var`!

Como el compilador puede leerlo dos veces y otro hilo puede cambiar el valor entre las dos lecturas. Sin embargo, una vez más, la optimización definitivamente haría que el código solo lo lea una vez, por lo que es posible que nuevamente tenga resultados diferentes que ahora también dependen del momento de otro hilo. Por lo tanto, tendrá mucho menos dolor de cabeza si almacena variables globales en una variable de pila temporal antes de su uso. Tenga en cuenta que si el compilador cree que esto es seguro, lo más probable es que optimice incluso eso y, en su lugar, use la variable global directamente, por lo que al final, puede que no haya diferencia en el rendimiento o el uso de la memoria.

(En caso de que alguien pregunte por qué haría alguien en x + 2 * xlugar de hacerlo 3 * x, en algunas CPU la adición es ultrarrápida y también lo es la multiplicación por una potencia dos, ya que el compilador los convertirá en cambios de bits ( 2 * x == x << 1), aunque la multiplicación con números arbitrarios puede ser muy lenta , por lo tanto, en lugar de multiplicar por 3, obtienes un código mucho más rápido cambiando bit x por 1 y agregando x al resultado, e incluso ese truco lo realizan los compiladores modernos si multiplicas por 3 y activas la optimización agresiva a menos que sea un objetivo moderno CPU donde la multiplicación es igual de rápida que la suma, ya que el truco ralentizaría el cálculo).

Mecki
fuente
2
No es un comportamiento indefinido: el estándar enumera las posibilidades y una de ellas se elige en cualquier caso
Antti Haapala
El compilador no se convertirá 3 * xen dos lecturas de x. Puede leer x una vez y luego hacer el método x + 2 * x en el registro en el que lee x
MM
66
@Mecki "Si no puede decir cuál es el resultado simplemente mirando el código, el resultado es indefinido" : el comportamiento indefinido tiene un significado muy específico en C / C ++, y eso no es todo. Otros respondedores han explicado por qué esta instancia particular no está especificada , pero no está indefinida .
marcelm
3
Aprecio la intención de arrojar algo de luz en el interior de una computadora, incluso si eso va más allá del alcance de la pregunta original. Sin embargo, UB es una jerga C / C ++ muy precisa y debe usarse con cuidado, especialmente cuando la pregunta es sobre un tecnicismo del lenguaje. En su lugar, podría considerar usar el término apropiado de "comportamiento no especificado", que mejoraría significativamente la respuesta.
Kuroi Neko
2
@Mecki " Indefinido tiene un significado muy especial en el idioma inglés " ... pero en una pregunta etiquetada language-lawyer, donde el idioma en cuestión tiene su propio "significado muy especial" para indefinido , solo causarás confusión al no usar La definición del lenguaje.
TripeHound
-1

Edición global: lo siento chicos, me emocioné mucho y escribí muchas tonterías. Sólo un viejo geezer despotricando.

Quería creer que C se había salvado, pero desgraciadamente desde C11 se ha equiparado a C ++. Aparentemente, saber qué hará el compilador con los efectos secundarios en las expresiones requiere ahora resolver un pequeño acertijo matemático que involucra un ordenamiento parcial de secuencias de código basado en un "se ubica antes del punto de sincronización de".

Por casualidad, diseñé e implementé algunos sistemas integrados críticos en tiempo real en los días de K&R (incluido el controlador de un automóvil eléctrico que podría hacer que las personas se estrellaran contra la pared más cercana si el motor no se controlaba, un industrial de 10 toneladas robot que podría aplastar a las personas hasta convertirlo en una pulpa si no se ordena adecuadamente, y una capa de sistema que, aunque inofensiva, tendría unas pocas docenas de procesadores que absorberían su bus de datos con menos del 1% de sobrecarga del sistema).

Podría ser demasiado senil o estúpido para obtener la diferencia entre indefinido y no especificado, pero creo que todavía tengo una muy buena idea de lo que significa la ejecución concurrente y el acceso a datos. En mi opinión posiblemente informada, esta obsesión por los C ++ y ahora los chicos C con sus lenguajes de mascotas asumiendo los problemas de sincronización es un sueño costoso. O sabes lo que es la ejecución concurrente, y no necesitas ninguno de estos artilugios, o no, y le harías al mundo en general un favor sin tratar de meterse con él.

Toda esta carga de abstracciones de barrera de memoria que hacen agua la vista se debe simplemente a un conjunto temporal de limitaciones de los sistemas de caché de múltiples CPU, todos los cuales se pueden encapsular de forma segura en objetos de sincronización de SO comunes como, por ejemplo, los mutexes y las variables de condición C ++ ofertas.
El costo de esta encapsulación no es más que una caída diminuta en el rendimiento en comparación con lo que podría lograr el uso de instrucciones específicas de CPU específicas en algunos casos.
La volatilepalabra clave (o un#pragma dont-mess-with-that-variablepara todos, como programador del sistema, cuidado) hubiera sido suficiente para decirle al compilador que deje de reordenar los accesos a la memoria. El código óptimo se puede generar fácilmente con directivas asm directas para rociar el controlador de bajo nivel y el código del sistema operativo con instrucciones específicas de CPU específicas. Sin un conocimiento íntimo de cómo funciona el hardware subyacente (sistema de caché o interfaz de bus), de todos modos está obligado a escribir código inútil, ineficiente o defectuoso.

Un ajuste minucioso de la volatilepalabra clave y Bob habría sido todo el mundo menos el tío de programadores de bajo nivel más duro. En lugar de eso, la pandilla habitual de fanáticos de las matemáticas de C ++ tuvo un día de campo diseñando otra abstracción incomprensible, cediendo a su tendencia típica de diseñar soluciones en busca de problemas inexistentes y confundiendo la definición de un lenguaje de programación con las especificaciones de un compilador.

Solo que esta vez el cambio requirió desfigurar un aspecto fundamental de C también, ya que estas "barreras" tuvieron que generarse incluso en código C de bajo nivel para funcionar correctamente. Eso, entre otras cosas, causó estragos en la definición de expresiones, sin explicación o justificación alguna.

Como conclusión, el hecho de que un compilador pueda producir un código de máquina consistente a partir de esta pieza absurda de C es solo una consecuencia distante de la forma en que los chicos de C ++ hicieron frente a posibles inconsistencias de los sistemas de caché de finales de la década de 2000.
Se hizo un desastre terrible de un aspecto fundamental de C (definición de expresión), de modo que la gran mayoría de los programadores de C, a quienes no les importan los sistemas de caché, y con razón, ahora se ven obligados a confiar en los gurús para explicar el diferencia entre a = b() + c()y a = b + c.

Intentar adivinar qué será de este desafortunado conjunto es una pérdida neta de tiempo y esfuerzo de todos modos. Independientemente de lo que haga el compilador, este código es patológicamente incorrecto. Lo único responsable de hacerlo es enviarlo a la papelera.
Conceptualmente, los efectos secundarios siempre se pueden eliminar de las expresiones, con el esfuerzo trivial de permitir explícitamente que la modificación ocurra antes o después de la evaluación, en una declaración separada.
Este tipo de código de mierda podría haberse justificado en los años 80, cuando no se podía esperar que un compilador optimizara nada. Pero ahora que los compiladores se han vuelto más inteligentes que la mayoría de los programadores, todo lo que queda es un código de mierda.

Tampoco entiendo la importancia de este debate indefinido / no especificado. O puede confiar en el compilador para generar código con un comportamiento consistente o no puede. Si llama a eso indefinido o no especificado parece un punto discutible.

En mi opinión posiblemente informada, C ya es lo suficientemente peligroso en su estado K&R. Una evolución útil sería agregar medidas de seguridad de sentido común. Por ejemplo, al hacer uso de esta herramienta avanzada de análisis de código, las especificaciones obligan al compilador a implementar al menos para generar advertencias sobre el código de bonkers, en lugar de generar en silencio un código potencialmente poco confiable al extremo.
Pero en cambio, los chicos decidieron, por ejemplo, definir un orden de evaluación fijo en C ++ 17. Ahora, cada imbécil de software se incita activamente para poner efectos secundarios en su código a propósito, disfrutando de la certeza de que los nuevos compiladores manejarán ansiosamente la ofuscación de una manera determinista.

K&R fue una de las verdaderas maravillas del mundo de la informática. Por veinte dólares obtuviste una especificación completa del idioma (he visto a individuos solteros escribir compiladores completos simplemente usando este libro), un excelente manual de referencia (la tabla de contenido generalmente te indicará en un par de páginas de la respuesta a tu pregunta), y un libro de texto que le enseñaría a usar el lenguaje de una manera sensata. Completo con fundamentos, ejemplos y sabias palabras de advertencia sobre las numerosas formas en que podría abusar del lenguaje para hacer cosas muy, muy estúpidas.

Destruir esa herencia por tan poco beneficio me parece un desperdicio cruel. Pero de nuevo, bien podría dejar de ver el punto por completo. ¿Quizás algún alma amable podría señalarme en la dirección de un ejemplo de nuevo código C que aproveche significativamente estos efectos secundarios?

kuroi neko
fuente
Es un comportamiento indefinido si hay efectos secundarios en el mismo objeto en la misma expresión, C17 6.5 / 2. Estos no están secuenciados según C17 6.5.18 / 3. Pero el texto de 6.5 / 2 "Si un efecto secundario en un objeto escalar no está secuenciado en relación con un efecto secundario diferente en el mismo objeto escalar o un cálculo de valor usando el valor del mismo objeto escalar, el comportamiento es indefinido". no se aplica, ya que el cálculo del valor dentro de la función se secuencia antes o después del acceso al índice de la matriz, independientemente de que el operador de asignación tenga operandos no secuenciados en sí mismo.
Lundin
La llamada a la función actúa como "un mutex contra el acceso no secuenciado", por así decirlo. Similar a la basura oscura del operador de coma como 0,expr,0.
Lundin
Creo que usted creyó en los autores de la Norma cuando dijeron "El comportamiento indefinido le da al implementador la licencia para no detectar ciertos errores del programa que son difíciles de diagnosticar. También identifica áreas de posible extensión de lenguaje conforme: el implementador puede aumentar el lenguaje al proporcionar un definición del comportamiento oficialmente indefinido ". y dijo que no se suponía que la Norma degradara los programas útiles que no se ajustaban estrictamente. Creo que la mayoría de los autores de la Norma habrían pensado que era obvio que las personas que buscan escribir compiladores de calidad ...
supercat
... debe tratar de usar UB como una oportunidad para hacer que sus compiladores sean lo más útiles posible para sus clientes. Dudo que alguien haya imaginado que los escritores de compiladores lo usarían como una excusa para responder a las quejas de "Su compilador procesa este código de manera menos útil que los demás" con "Eso es porque el Estándar no requiere que lo procesemos de manera útil, y las implementaciones que procesan de manera útil programas cuyo comportamiento no es obligatorio según el Estándar simplemente promueven la escritura de programas rotos ".
supercat
No veo el punto en tu comentario. Confiar en el comportamiento específico del compilador es una garantía de no portabilidad. También requiere una gran fe en el fabricante del compilador, que podría suspender cualquiera de estas "definiciones adicionales" en cualquier momento. Lo único que puede hacer un compilador es generar advertencias, que un programador sabio y experto podría decidir manejar errores similares. El problema que veo con este monstruo ISO es que hace que un código tan atroz como el ejemplo del OP sea legítimo (por razones extremadamente confusas, en comparación con la definición de K&R de una expresión).
Kuroi Neko