Foro de elhacker.net

Ya sé que este suele ser un tema básico pero me he encontrado con un resultado inesperado en el funcionamiento de estos operadores.
Mi problema es que estaba implementando un algoritmo de ordenamiento por inserción tanto en C++ como en Java; sin embargo, el resultado obtenido en C++ no era el que esperaba por eso pongo la duda en este foro.
Aquí el código en Java:

public static void insertionSort(int[] numbers){
    for(int i = 1; i < numbers.length; ++i){
        int currentValue = numbers[i];
        int previousIndex = i-1;
        while(previousIndex >= 0 && currentValue < numbers[previousIndex])
            numbers[previousIndex+1] = numbers[previousIndex--];
        numbers[previousIndex+1] = currentValue;
        showArray(numbers);
    }
} 

Y aquí el código en C++:

void insertionSort(int *numbers, const int size){
    for(size_t i = 1; i < size; ++i){
        int currentValue = numbers[i];
        int previousIndex = i-1;
        while(previousIndex >= 0 && currentValue < numbers[previousIndex])
            numbers[previousIndex+1] = numbers[previousIndex--];
        numbers[previousIndex+1] = currentValue;
        showArray(numbers, size);
    }
} 

Como se puede ver, códigos idénticos. El problema está en la línea 6 del código en C++. He visto que había valores que se repetían y después de un rato investigando he visto que si en C++ se cambia la línea 6 por:

numbers[previousIndex+2] = numbers[previousIndex--]; 

Entonces sí funciona. Y si se cambia el bucle <while> por:

while(previousIndex >= 0 && currentValue < numbers[previousIndex]){
    numbers[previousIndex+1] = numbers[previousIndex];
    --previousIndex;
} 

También funciona correctamente. Entonces el problema sé que está en el orden en que se realiza el decremento. Me gustaría sabes cómo funciona eso en profundidad ya que veo que no funciona igual en Java que en C++.

PD: Agradecería también una explicación del funcionamiento en Java para ver cuáles son las diferencias exactamente. O si es mejor que abra otro tema en el foro de Java para esta parte me lo podéis decir también. :-X :-X

aqui hay un tema que se explicó con un poco de detalle el asunto relacionado a los incrementos/decrementos post/pre, esto es un problema comun a descubrir cuando se está aprendiendo

https://foro.elhacker.net/buscador-t483138.0.html

no es un asunto de java vs c++ es un asunto de nivel mas bajo...

Yo por lo que ten entendido en C++ operadores unarios en preincremento la ejecución es más rápida. No sé nada más.

XD claramente entonces lo que sabes es mito XD

no es mas rápida en ningún sentido

https://stackoverflow.com/questions/24901/is-there-a-performance-difference-between-i-and-i-in-c

Sí, parece que el postincremento genera más instrucciones.

Según https://godbolt.org que trabaja con gcc, si no se dan optimizaciones tenemos que el siguiente código

int main() {
    int a = 0;
    int b = 0;
    int m = ++a;
    int n = b++;
}

se traduce a

main:
        ; prepara el stack para la función
        push    rbp
        mov     rbp, rsp
        ; int a = 0;
        mov     DWORD PTR [rbp-4], 0
        ; int b = 0;
        mov     DWORD PTR [rbp-8], 0
        ; int m = ++a;
        add     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        mov     DWORD PTR [rbp-12], eax
        ; int n = ++b;
        mov     eax, DWORD PTR [rbp-8]
        lea     edx, [rax+1]
        mov     DWORD PTR [rbp-8], edx
        mov     DWORD PTR [rbp-16], eax
        ; código para regresar de la función
        mov     eax, 0
        pop     rbp
        ret

Cómo se puede ver con el postincremento hay una instrucción de más.

cuidado con el vicio de la falsa optimizacion... el orden de los factores afecta, se pueden hacer operaciones extras...

https://godbolt.org

int main() {
    int a = 0;
    int b = 0;
    int n = b++;
    int m = ++a;
}

 
        push    rbp
        mov     rbp, rsp
        ; int a = 0;
        mov     DWORD PTR [rbp-4], 0
        ; int b = 0;
        mov     DWORD PTR [rbp-8], 0
        ; int n = ++b;
        mov     eax, DWORD PTR [rbp-8]
        lea     edx, [rax+1]
        mov     DWORD PTR [rbp-8], edx
        mov     DWORD PTR [rbp-12], eax
        ; int m = ++a;
        add     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        mov     DWORD PTR [rbp-16], eax
        mov     eax, 0
        ; código para regresar de la función       
        pop     rbp
        ret
 
 

Como ya habrás visto, el problema se debe a que C++ no especifica(ba) un orden de evaluación. Que esa línea funcione o no, dependería del compilador e incluso en un mismo compilador, el nivel de optimización seleccionado o incluso el código concreto en el que se use, podría alterar el resultado, precisamente porque, al no estar definido el orden de evaluación, los compiladores pueden hacerlo como quieran. Sin embargo esto ya se subsanó en C++17, por lo que si compilas para este estándar, aquí:

            numbers[previousIndex+1] = numbers[previousIndex--];

tienes garantizado que primero se evaluará lo de la derecha (previousIndex--) y obtendrás resultados consistentes. Aún así, yo recomendaría que hagas el decremento en su propia línea, tanto porque así tu programa funcionará en cualquier versión de C++, como porque es menos ambiguo para el programador; no todos están familiarizados con C++17, y aunque lo estemos, se nos pueden olvidar las reglas de evaluación.

Lo del incremento/decremento quizás amerita algo más de detalle. Primero, en C y C++, los operadores de preincremento no son más eficientes que los post. La confusión viene debido a que, en el caso de los objetos (a diferencia de los tipos básicos como int, long, etc.), al implementar la sobrecarga de dichos operadores, en el postincremento/decremento se debe crear una copia del objeto, lo que es menos eficiente. Pero recordar que con los objetos no estamos invocando a los operadores de incremento/decremento, sino a funciones que sobrecargan esos operadores, que no es lo mismo. Sin embargo, si no nos interesan los detalles internos, basta decir que el preincremento es más eficiente únicamente en el caso de objetos. Para variables de tipos básicos, no hay diferencia.

En realidad, como curiosidad, y contrario a la engañosa creencia antes mencionada, en algunos casos el postincremento/postdecremento (con tipos básicos) en teoría podría ser más eficiente que el preincremento, ya que el preincremento genera una dependencia de datos que no existe con el post, por lo que en este último caso podría haber un mejo aprovechamiento de los pipelines del procesador. Eso sí, en la práctica yo nunca lo he visto, pero he leído de dos programadores que lo afirman.

Edito: como dice engel lex, cuidado con las falsas optimizaciones. No podemos simplemente contar las instrucciones generadas y sacar conclusiones. Hay muchos factores en juego y para poder evaluar correctamente el rendimiento hay que conocer con cierta profundidad la arquitectura para la que se está programando, así como los patrones de uso concretos del programa a evaluar. Suponer que menos instrucciones == mayor velocidad no tiene sentido. De hecho, hace unos días aquí en otro tema del foro hablé de una función en la cual modifiqué el ensamblador generado por el compilador. El resultado fue una función con 4 o 5 instrucciones adicionales, pero que es un 20% más rápida que la original. Y esto no es ningún caso aislado, de hecho es muy común.

Gracias por el enlace. No sabía nada de los sequence points. Lo de Java vs C++ lo decía porque aun suponiendo que cada lenguaje funciona con sus normas, pensaba que seguirían un mismo estándar de orden de procesamiento. Pero como explico más adelante parece que cada uno usa un orden diferente.

Ya he visto que es mejor separar los incrementos/decrementos en líneas diferentes pero quiero terminar de entenderlos. He realizado otra prueba con:

int numeros[5] = {1,2,3,4,5};
int j = 2;
numeros[j+1] = -numeros[j--]; 

Y el resultado es: numeros = {1,2,-3, 4,5}. Por lo que saco que primero se obtiene el valor almacenado en <numeros[j]>, luego se decrementa <j> y después se calcula la posición de memoria del valor <numeros[j+1]>. Como el índice <j> se decrementa antes de calcular la posición de memoria pues la posición vuelve a ser la misma al sumarle 1 al índice. (Todo esto compilado con -std=c++17)

Sin embargo, en Java si probamos a hacer lo mismo:

int numeros[] = {1,2,3,4,5};
int j = 2;
numeros[j+1] = -numeros[j--]; 

El resultado es: numeros = {1,2,3,-3,5}. Por lo que aquí parece que antes de realizar el decremento ya tiene la posición de memoria donde lo va a guardar calculada y por eso el decremento no se junta con el +1 llegando de nuevo a la misma posición como ocurre en C++.

Estoy estudiando la precedencia de los operadores y por eso me ha sorprendido que el resultado fuera diferente teniendo en cuenta que los incrementos/decrementos tienen más preferencia que las asignaciones.
También he visto en algunos sitios que los operadores en postfijo tienen más preferencia que en prefijo... pero en otros sitios aparece como que tienen la misma prioridad. No sé si esto depende también del estándar.
Y la última pregunta es: en una sentencia con postincremento, el incremento se produce cuando ya se ha terminado de ejecutar la sentencia (línea completa) o justo después de usar el valor sin incrementar?

El operador de postincremento/decremento sí tiene mayor prioridad que la asignación, pero ése no es el problema. Lo que aquí entra en juego es lo que pasa antes de la asignación. Si tenemos algo así (un ejemplo más sencillo, para simplificar):

numeros[n] = n++;

obviamente, antes de la asignación, se debe determinar qué es lo que vamos a modificar (operando izquierdo),y qué valor le vamos a dar (derecho), es decir, se deben evaluar ambos lados de la operación. La cuestión es ¿cuál se evalúa primero? Antes estaba indefinido, pero C++17 dice que el de la derecha. Ése es precisamente el cambio relevante aquí.


Correcto. Podemos distinguir dos partes en la evaluación de n++ (como la de cualquier expresión): el cálculo del valor de retorno de la expresión, y sus efectos colaterales. En el caso de n++, lo que retorna dicha expresión es el valor de que tiene n al momento de evaluarse, y el efecto es la modificación de la propia variable n. Las dos cosas deben ocurrir en ese orden. Por eso, cuando se evalúa la parte derecha de tu asignación, como j vale 2, queda -numeros[2]. Cuando se termina de evaluar la expresión completa de la derecha (incrementar j, tomar el valor del elemento 2 de numeros, y negarlo), se procede a evaluar la parte izquierda, y como j ahora vale 1, queda numeros[1+1].

Los operadores en posfijo tienen mayor prioridad.


Bueno, en realidad eso no se define por sentencias sino por lo que se conocía como sequence points, pero resulta que incluso ese término es algo impreciso en C++ y ha quedado en desuso desde hace tiempo. Hasta donde sé, lo que preguntas sigue estando sin especificar, pues el estándar dice que, a menos que se indique lo contrario, el orden de los efectos colaterales de las expresiones y subexpresiones se considera "no especificado", y que yo sepa, sólo señala lo que sucede en casos concretos (como cuando expresiones tipo n++ se usan como argumentos a funciones, o con el operador ternario) pero no de forma general. Por eso, incluso en C++17, esto da un resultado indefinido (reiterar que el cambio en C++17 referido en este post habla sólo del orden de evaluación de los dos "lados" de una asignación):

n = n++ + n;

De cualquier forma, si nos limitamos a usos correctos, es bastante irrelevante el orden. Lo mejor es, ante la duda, hacer el incremento en su propia línea; el compilador no va a generar código menos (o más) eficiente por ello.

Se me olvidaba, en Java obtienes otros resultados simplemente porque sus reglas son diferentes a las de C++. En Java sí se especifica lo que debe suceder, y ahí el orden es de izquierda a derecha y, si no recuerdo mal, los efectos colaterales suceden de forma inmediata. No hay realmente nada de especial en como lo hace C++. Es simplemente que este lenguaje (igual que C) siempre ha sido demasiado permisivo, y deja muchas cosas indefinidas o no especificadas, muchas veces en aras de la portabilidad o para permitir que cada implementación pueda ser lo más eficiente posible.

Cada lenguaje tiene su sintaxis y su especificación. Esperar resultados idénticos es pecar de ingenuo (precisamente porque la mayor parte de las veces así sucederá, teniendo ambos lenguajes un origen común).

Ese "Quiero terminar de entenderlo", me suena a perder el tiempo...
En vez de hacer pruebas, lo que tienes que hacer es consultar la especificación del lenguaje (de uno y otro)... para ver cuál es el orden de precedencia de la asignación. Ya está, 1 minuto de lectura, no varios días haciendo pruebas... si no, aprender se te hará eterno.
Si la especificación del lenguaje es ambigua en tal punto, entonces ten por cierto que cada compilador tiene vía libre para hacer como le dé la gana. Ahí, si procede hacer pruebas para ver como se comporta el compilador que estés usando.

No había procesado esto bien y la verdad nunca habría pensado que eso fuera así ya que yo creía que el operador que mantiene una dependencia es el postfijo que necesita usar otro registro (como se veía en los ensambladores de MAFUS y engel lex) para almacenar el valor todavía sin incrementar. Sin embargo, me parece curioso aunque se me escape de las manos el entenderlo.

Entonces para resumir: el estándar C++17 especifica que primero se evalúa la parte de la derecha y después la de la izquierda pero los efectos colaterales siguen sin estar definidos; a diferencia de Java que evalúa de izquierda a derecha y especifica que los efectos colaterales se resuelven inmediatamente después.

Es posible que algunas personas lo vean como una pérdida de tiempo pero me interesaba saber cuáles eran las diferencias entre estos dos lenguajes en este aspecto y al final parece que lo estoy consiguiendo con las aportaciones del resto de miembros y sobre todo con las explicaciones de RayR, que agradezco.
También es verdad que consultando las especificaciones de cada lenguaje acabaría antes pero entre que no sé dónde localizarlas ni hasta donde llegaría a entender pues... supongo que dentro de mis posibilidades haré lo que pueda y en este caso lo que podía hacer eran pruebas para intentar sacar alguna conclusión de forma práctica. He visto que no llegaba a nada con pruebas pues entonces he probado en el foro.
Si todos nos tuviésemos que buscar la vida yendo a las fuentes oficiales de cada tema, no servirían de nada los foros porque lo que cualquiera pueda afirmar en un foro tendrá que estar apoyado por algún tipo de documentación oficial.

Me meto en la conversación un poco tarde...

Yo creo estamos todos de acuerdo que es mala idea escribir
Y se van dando distintas razones que vamos entendiendo, o más o menos. Lo bueno es que está claro que no se hace. La definición sólida de por qué no se hace está en "la documentación": Order of Evaluation (https://en.cppreference.com/w/cpp/language/eval_order (https://en.cppreference.com/w/cpp/language/eval_order))

Puse eso de "la documentación" entre comillas porque es lo más parecido que conozco a una documentación de consulta eficiente, y que para mí es suficiente. Para cosas más peludas siempre queda la documentación oficial, el documento del estándar C++17; lo que establece qué es C++ y qué no lo es. La ley: (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf))

En este caso, me parece que no es necesario ser tan drástico y que el artículo de "la documentación" es más que suficiente; sobre todo cuando dice que este tipo de expresiones se califican como UB, Undefined Behavior, que no quiere decir "comportamiento indefinido", o que algo no está del todo bien, es una categoría específica que invalida al programa enteramente; no es que alguna operación puede dar un resultado diferente a la misma operación en otros lenguajes, o que en un compilador pase una cosa y en otro otra; es bastante más drástico que eso: una UB convierte al programa en una pila de basura. Ver: [https://en.cppreference.com/w/cpp/language/ub (https://en.cppreference.com/w/cpp/language/ub)]

Y con respecto al asunto este del pre-incremento o post-incremento, algunas veces dará lo mismo usar uno u otro y otras no, es porque hacen cosas diferentes. Por ejemplo:

En general los compiladores son más inteligentes y saben hacerlo mejor que yo, pero no pueden escapar a la realidad de que el post-incremento hace más cosas que el pre-incremento. En un ciclo for, donde se usa para incrementar la variable de control, el compilador puede lucirse con poco, usa la versión más eficiente sin preguntar. Sin trucos ++i hace menos cosas que i++.

Es que de ese código no se puede sacar ninguna conclusión. Primero, porque fue compilado sin optimizaciones, y eso por sí sólo lo descarta para este objetivo, ya que el código generado no es realista, y los compiladores hacen cosas que normalmente no harían, por ejemplo, pueden tomar ciertas decisiones que empeoran el rendimiento, pero facilitan la depuración, etc. Además, el ensamblador que pusieron sólo aplica para GCC, pues si compilamos el código con Visual C++, genera la misma cantidad de instrucciones para ambas. Y es que GCC no necesitaba generar 4 instrucciones para el int n = b++. Pudo haber hecho simplemente esto:

        mov     eax, DWORD PTR [rbp-8]
        add     DWORD PTR [rbp-8], 1
        mov     DWORD PTR [rbp-16], eax

Y ya está. No hay ninguna razón que obligue a que la forma postfija requiera más instrucciones. Lo que vimos en el ejemplo original sin optimizar es simplemente lo que GCC decicidió hacer (por las razones que sea) en este caso concreto. Pero aún en el caso en el que GCC generó 4 instrucciones, usó lea en la suma. Esa instrucción no es para operaciones aritméticas, pero es una "optimización" común usarla para eso. Lo pongo entre comillas porque depende del procesador, pero en algunos casos, esa operación podría salir casi "gratis" (se podría ejecutar en paralelo con otras) por lo que, para efectos de tiempo de ejecución, sería prácticamente como si no existiera. Como había dicho antes, contar instrucciones no es suficiente.

De cualquier forma, nunca se debería un ejemplo tan simple, ya que los compiladores son bastante inteligentes (casi siempre) y no traducen instrucción por instrucción sino que analizan bloques de código y a partir de ahí deciden. Por eso es muy importante el uso, el contexto, sobre todo porque los compiladores de C/C++ tienen permitido hacer muchísimas modificaciones a nuestro código, siempre que no modifiquen su comportamiento observable. Porque si compilamos el código original de MAFUS con optimizaciones, como es debido, veremos que tampoco es de utilidad, ya que todos los compiladores modernos se darán cuenta de que no hace nada, así que eliminarán todas las instrucciones y simplemente harán que main retorne 0.


Lo que puse de la dependencia tómalo con muchas reservas, ya que, como dije, no sé realmente qué tanta diferencia pueda hacer en la práctica. Y ten en cuenta que en la mayoría de arquitecturas, incluidos procesadores de Intel/AMD, muchas operaciones no se pueden realizar directamente en la memoria, por lo que es forzoso usar registros para valores intermedios. Esto lo menciono porque se pudiera pensar que el incremento/decremento prefijo nos podemos ahorrar alguna instrucción, pero en general, no es así. Aclarado eso, ambas versiones del operador requieren dos cosas: incrementar el valor de la variable y retornar "algo". En el postfijo, el valor original, y en el prefijo el nuevo. La cuestión es si hay interdependencia entre esas dos acciones. Esto es importante porque la mayoría de los procesadores modernos pueden ejecutar más de una instrucción de forma concurrente, siempre que una no dependa de la otra. Teniendo en cuenta que en general necesitamos una copia temporal, con el operador posfijo la asignación y el incremento se pueden hacer simultáneamente, pero en el prefijo el incremente debo ir antes. En realidad esto es casi meramente teórico, ya que en la realidad estos operadores prácticamente nunca son intercambiables, y los casos en los que los son, seguramente el compilador los optimizará de cualquier manera.

No hay nada de malo en preguntar. C++ es un lenguaje muy complejo, y creo que muy pocas cosas en él se podrían considerar "simples". Cosas como la de este tema, no lo son, por supuesto, y encontrar la respuesta tampoco. El estándar es muy complicado, independientemente de cuánta experiencia tengamos. Realmente está dirigido, sobre todo, a creadores de compiladores. No me gusta consultarlo, ya que en realidad no siempre lo entiendo, pero a veces no hay opción, ya que es la única fuente 100% confiable. Por ejemplo, en un vistazo rápido al artículo Order of evaluation de cppreference, no encuentro nada que resuelva el asunto concreto de este hilo. Y por ejemplo, esto:


es, como mínimo incompleto, al menos en C++17, ya que la parte en negrita (que no aparece en la especificación del estándar) implica que es posible que la asignación suceda antes que los efectos colaterales del lado derecho, lo cual no es cierto. Si lo fuera, el resultado de esto:

int n = 5;
numeros[n] = n++;

seguiría indefinido. Sería posible que termináramos modificando numeros[5], ya que, si al momento de la asignación no se ha producido el efecto colateral del operando derecho, por definición, n sigue valiendo 5. Esto no es así. En C++17, siempre modificaremos numeros[6].

Con lo que está en negrita, quieres decir que tanto si se usa el postincremento como el preincremento, el compilador lo optimizará al mismo nivel? Es decir, que daría igual usar uno que otro? Lo digo porque yo era de los que empezó a programar y a hacer los for con i++ hasta que me dijeron que era mejor usar ++i, pero claro, eso me ha chocado con el tema de que el preincremento sí es mejor pero cuando se trata de objetos y no de tipos primitivos.

Cierto. Sí que se me ocurrió añadir las opciones -O1 y -O2 y se ve eso que dices. En el primer caso lo que se obtiene es esto:

mov     eax, 0
ret 

Y en el segundo caso lo que se obtiene es:

xor     eax, eax
ret 

Por lo que es cierto que el compilador ve que no se usan las variables para nada y entonces omite las sentencias.

En general los compiladores reescriben tu código como les place, la única restricción es que se preserve el "observable behavior"; o sea: el compilador es libre de pasarse tu código por donde le plazca y poner en su lugar otra cosa, sólo está obligado a generar un ejecutable que haga lo mismo. Aprovechando que ya tuve la delicadeza de poder el link al docuemento del Estándar C++17, puedes consultar: parágrafo 4.6 Program execution - Nota 5.

De modo que aunque el compilador no esté obligado, casi seguro que lo hará, eso o algo diferente, a su criterio.

Con los tipos nativos no sólo es más fácil sino que además es muy difícil que notemos la diferencia, normalmente no suele haber un cuello de botella en i++ cuando i es un int. Ahora, si i es de tipo "Clase_con_copy_constructor_vicioso", la diferencia será notable, a no dudarlo.

Ah, ¿por qué la diferencia va a estar en el copy_constructor_vicioso? Por lo dicho, el postincremento devuelve una copia del objeto original sin incrementar.