¿Hay una razón técnica por la que C# no emite la "cola"?"CIL instruction? [duplicar]


Posible Duplicado:
¿Por qué. net/C# no elimina la recursión de cola?

Tome el siguiente código C#:

using System;

namespace TailTest
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Counter(0);
        }

        static void Counter(int i)
        {
            Console.WriteLine(i);
            if (i < int.MaxValue) Counter(++i);
        }
    }
}

El compilador de C # (mío de todos modos) compilará el método Contador en el siguiente CIL:

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_0019
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  call void class TailTest.MainClass::Counter(int32)
IL_0019:  ret 
}

El problema con el código anterior es que causará un desbordamiento de pila (aproximadamente i=262000 en mi hardware). Para evitar este problema, algunos idiomas hacen lo que se llama eliminación de tail-call o tail-call optimización (TCO). Esencialmente, convierten la llamada recursiva en un bucle.

Entiendo que la implementación de 64 bits del JIT.NET 4 ahora realiza TCO y evita el desbordamiento en el código como el CIL anterior. Sin embargo, el JIT de 32 bits no lo hace. La mononucleosis tampoco lo parece. Es interesante que el JIT (que está bajo presión de tiempo y recursos) hace TCO mientras que el compilador de C# no lo hace. Mi pregunta es ¿por qué el compilador de C# no es más consciente del TCO?

Hay un CIL instrucción que le dice al JIT que realice el TCO. Por ejemplo, el compilador de C# podría generar el siguiente CIL:

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_001c
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  tail.
IL_0017:  call void class TailTest.MainClass::Counter(int32)
IL_001c:  ret 
}

A diferencia del original, este código no se desbordará y se ejecutará hasta completarse incluso en el JIT de 32 bits (tanto.NET como Mono). La magia está en la instrucción CIL tail.. Compiladores como F # generarán CIL que incluye esta instrucción automáticamente.

Así que mi pregunta es, ¿hay alguna razón técnica por la que el compilador de C# no hace esto?

Consigo que históricamente tal vez no ha valido la pena. Código como Counter() no ha sido común en C# idiomático y/o en.NET framework. Puede ver fácilmente el TCO para C # como una optimización innecesaria o prematura.

Con la introducción de LINQ y otras cosas, parece que los desarrolladores de C# y C# se están moviendo en direcciones más funcionales. Por lo tanto, sería bueno si el uso de recursión no fuera una cosa tan insegura de hacer. Pero mi pregunta es realmente más técnica.

Am falta algo que hace que TCO como esta sea una mala idea (o una arriesgada) para C#. ¿O hay algo que hace que sea particularmente difícil de hacer bien? Eso es realmente lo que espero entender. ¿Alguna idea?

EDIT: Gracias por la gran información. Solo quería dejar claro que no estoy criticando la falta o incluso exigiendo esta característica. No estoy muy interesado en lo racional en torno a la priorización. Mi curiosidad es ¿qué obstáculos podría no percibir o entender que hacen de esto una cosa difícil, peligrosa o indeseable de hacer.

Tal vez un contexto diferente ayude a enfocar la conversación...

Digamos que iba a implementar mi propio lenguaje similar a C#en el CLR. ¿Por qué no incluiría (aparte del costo de oportunidad) la emisión automática y transparente de la 'cola.¿instrucción donde sea apropiado? ¿Qué desafíos encontraría o qué limitaciones introduciría al apoyar esta característica en un lenguaje muy parecido C#.

Gracias de nuevo (y de antemano) por las respuestas.

Author: Community, 2011-08-17

2 answers

Compruebe los siguientes enlaces

¿Por qué. NET/ C # no optimiza para la recursión de llamada de cola? /491463#491463
http://social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/67b6d908-8811-430f-bc84-0081f4393336?StatusCode=1
https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=166013&wa=wsignin1.0

La siguiente declaración es MS official (Luke Hoban Visual C # Compiler Program Manager) y copiada de último enlace

Gracias por la sugerencia. Hemos considerado emitir instrucciones de llamada de cola en un número de puntos en el desarrollo del compilador de C#. Sin embargo, hay algunos problemas sutiles que nos han empujado a evitar esto hasta ahora: 1) En realidad hay una sobrecarga no trivial costo para usar el.instrucción de cola en el CLR (no es solo una instrucción de salto como en última instancia, las llamadas de cola se convierten en muchos entornos menos estrictos, como los funcionales. entornos de tiempo de ejecución de idiomas donde las llamadas tail están muy optimizadas). 2) Hay pocos métodos reales de C# donde sería legal emitir llamadas tail (otros idiomas fomentar patrones de codificación que tienen más recursión de cola, y muchos que dependen en gran medida en la optimización de llamadas de cola en realidad hacer reescritura global (como el Paso de continuación transformaciones) para aumentar la cantidad de recursión de cola). 3) En parte debido a 2), casos en los que los métodos C# se desbordan debido a la recursión profunda que debería haber tenido éxito son bastante raros.

Dicho esto, seguimos mirando esto, y podemos en una futura versión de la compilador encontrar algunos patrones donde tiene sentido emitir .instrucciones de cola.

 12
Author: Yahia,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 11:45:17

Buena pregunta. No tengo una respuesta concreta, pero tengo algunas ideas que podrían encontrar interesantes. (Me han dicho antes que no debería publicar tales cosas como respuestas, pero bueno... La respuesta de Yahia parece la más definitiva que probablemente obtendrás, aunque también haré ping a Eric Lippert para ver si quiere intervenir.

Parte de la entrada del blog Hans enlazado en los comentarios probablemente cubrirá algunos de sus pensamientos, pero estoy seguro de que hay más:

Me preguntan "¿por qué C# no implementa la característica X?"todo el tiempo. La respuesta es siempre la misma: porque nadie diseñó, especificó, implementó, probó, documentó y envió esa característica. Las seis cosas son necesarias para hacer que una característica suceda. Todos ellos cuestan grandes cantidades de tiempo, esfuerzo y dinero. Las funciones no son baratas, y nos esforzamos mucho para asegurarnos de que solo enviemos las funciones que brindan los mejores beneficios posibles a nuestros usuarios, dado nuestro tiempo limitado, presupuestos de esfuerzo y dinero.


Ahora vuelvo a mis propios pensamientos:

Sospecho que nunca ha sido una prioridad, pero hay una buena razón para no estar demasiadoentusiasmado con ello: si los desarrolladores van a confiar en él, debe estar garantizado. Usted escribió:

Por lo tanto, sería bueno si el uso de recursión no fuera algo tan inseguro. Pero mi pregunta es realmente más técnica.

Ahora, mira la entrada del blog explicando cuándo se aplican optimizaciones de llamadas de cola. Eso fue en 2007, y explícitamente dice:

Tenga en cuenta que estas instrucciones se aplican a los JITs como eran cuando Grant y Fei miraron a través de la base de código, y son propensos a cambiar a capricho. No debe tomar dependencias en este comportamiento. Utilice esta información solo para su propio entretenimiento personal.

Entonces hay una larga lista de condiciones que se requieren antes de que se apliquen las llamadas tail. Un montón de esos no son triviales de adivinar desde el punto de vista de un codificador.

Tienes toda la razón en que sería bueno que el uso de recursión fuera seguro en ciertas circunstancias, pero creo que ese es solo el caso si se pudiera garantizar que sea seguro. Si fuera seguro en el 95% de los casos, pero el 5% fuera difícil de predecir, tendríamos una gran cantidad de errores de "funciona en mi máquina".

Lo que me gustaría es que el lenguaje C# me permita indicar un requisito de optimización de llamadas de cola. El compilador podría entonces verificar que es correcto, e idealmente proporcionar algo más que una pista al JIT de que este comportamiento es requerido. Básicamente, si voy a recurrir de una manera algo descontrolada, será mejor que sepa que va a funcionar. ¿Te imaginas si la recolección de basura solo estuviera habilitada en algunas configuraciones? Eek!

Así que +1 a la idea de la recursión de cola es un concepto útil, pero creo que necesitamos más apoyo del lenguaje, el JIT y el compilador antes de que realmente podría ser considerado "seguro".

 7
Author: Jon Skeet,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-17 16:31:03