{"id":1505,"date":"2023-10-12T15:10:05","date_gmt":"2023-10-12T13:10:05","guid":{"rendered":"https:\/\/intsight.com\/?p=1505"},"modified":"2023-10-13T08:01:34","modified_gmt":"2023-10-13T06:01:34","slug":"smart-boys-optimizations","status":"publish","type":"post","link":"https:\/\/intsight.com\/index.php\/2023\/10\/12\/smart-boys-optimizations\/","title":{"rendered":"Smart boy&#8217;s optimizations"},"content":{"rendered":"<p><span style=\"font-variant:small-caps;font-size:107%\">Dec\u00eda el gran Donald<\/span> Knuth algo as\u00ed como que <em>premature optimization is the root of all evil<\/em>. Santificado sea su nombre&#8230;<\/p>\n<h4>Calidad de c\u00f3digo<\/h4>\n<p>Una vez citadas las sagradas escrituras, debo reconocer que mi lado hereje cumple otros mandamientos:<\/p>\n<ul style=\"list-style-type:square\">\n<li>Peor que la optimizaci\u00f3n prematura, es no optimizar nunca. Una vez escuch\u00e9 una mala excusa sobre un programa que tardaba 25 horas en cargar un fichero: \u00abes que nadie me dijo que ten\u00eda que ser r\u00e1pido\u00bb. Los ordenadores existen, precisamente, para hacer las cosas m\u00e1s r\u00e1pidamente. No s\u00f3lo porque es inter\u00e9s directo del usuario del programa que \u00e9ste termine antes, sino que, adem\u00e1s, le interesa el ahorro en electricidad y en el desgaste del propio aparato.<\/li>\n<li>Si est\u00e1s escribiendo una aplicaci\u00f3n, te puedes permitir el lujo de esperar a que funcione para buscar los puntos cr\u00edticos de eficiencia. Pero si est\u00e1s escribiendo una librer\u00eda, que se va a utilizar en formas que a\u00fan no sospechas&#8230; mejor que todo vaya como la seda desde el principio.<\/li>\n<li>La mayor\u00eda de las optimizaciones (yo dir\u00eda m\u00e1s bien mejoras) caen en una categor\u00eda que yo llamo \u00abmejoras de chico listo\u00bb, y tienen que ver con la calidad del c\u00f3digo que cada programador puede generar sin esfuerzo adicional.<\/li>\n<\/ul>\n<p>Las optimizaciones de chico listo, por supuesto, dependen de la experiencia del programador, de lo bien que le funcione la memoria y de lo bien que se le d\u00e9 la detecci\u00f3n de patrones, por lo que se trata de una categor\u00eda dif\u00edcil de delimitar. Programar es un arte.<\/p>\n<h4>Un ejemplo<\/h4>\n<p>En cualquier caso, el prop\u00f3sito de esta entrada es mostrarle algunas de las optimizaciones que he aprendido mirando el c\u00f3digo fuente de .NET. Yo las tengo ya en mi memoria de trabajo: las aplico autom\u00e1ticamente cuando detecto que son aplicables.<\/p>\n<p>Trabajando con una implementaci\u00f3n de la funci\u00f3n <a href=\"https:\/\/en.wikipedia.org\/wiki\/Error_function\" rel=\"noopener\" target=\"_blank\">erf<\/a>, tropec\u00e9 con este c\u00f3digo, que eval\u00faa un polinomio en un punto, usando los coeficientes de una tabla:<\/p>\n<pre class=\"EnlighterJSRAW\">\nprivate static double Evaluate(double z, double[] coefficients)\n{\n    if (coefficients == null)\n        throw new ArgumentNullException(nameof(coefficients));\n    int n = coefficients.Length;\n    if (n == 0)\n        return 0;\n    double sum = coefficients[n - 1];\n    for (int i = n - 2; i >= 0; --i)\n    {\n        sum *= z;\n        sum += coefficients[i];\n    }\n    return sum;\n}\n<\/pre>\n<p>Esta funci\u00f3n se ejecuta varias veces, con distintos coeficientes. Un ejemplo de tabla de coeficientes es \u00e9sta:<\/p>\n<pre class=\"EnlighterJSRAW\">\nstatic readonly double[] ErvInvImpAn =\n{\n    -0.000508781949658280665617, -0.00836874819741736770379,\n    0.0334806625409744615033, -0.0126926147662974029034,\n    -0.0365637971411762664006, 0.0219878681111168899165,\n    0.00822687874676915743155, -0.00538772965071242932965\n};\n<\/pre>\n<p>Este m\u00e9todo es un m\u00e9todo privado de una clase, y una r\u00e1pida ojeada me confirm\u00f3 que las tablas que se le pasan son siempre no nulas, y con longitud mayor que cero. \u00bfA qu\u00e9 vienen las dos comprobaciones iniciales? Respuesta: es uno de los problemas que causa la \u00abmodularidad\u00bb. Escribes software que no sabes c\u00f3mo se puede usar, y lo proteges de las cosas m\u00e1s inveros\u00edmiles. Pero si es un m\u00e9todo privado, tanta precauci\u00f3n sobra. Empezamos por esta simplificaci\u00f3n, para ir haciendo boca y verlo todo m\u00e1s claro:<\/p>\n<pre class=\"EnlighterJSRAW\">\nprivate static double Evaluate(double z, double[] coefficients)\n{\n    int n = coefficients.Length;\n    double sum = coefficients[n - 1];\n    for (int i = n - 2; i >= 0; --i)\n    {\n        sum *= z;\n        sum += coefficients[i];\n    }\n    return sum;\n}\n<\/pre>\n<p>El siguiente paso seguramente le sorprender\u00e1: sustituyo la tabla de coeficientes, que ahora es un campo est\u00e1tico de s\u00f3lo lectura, por esto:<\/p>\n<pre class=\"EnlighterJSRAW\">\nstatic ReadOnlySpan&lt;double&gt; ErvInvImpAn => new[]\n{\n    -0.000508781949658280665617, -0.00836874819741736770379,\n    0.0334806625409744615033, -0.0126926147662974029034,\n    -0.0365637971411762664006, 0.0219878681111168899165,\n    0.00822687874676915743155, -0.00538772965071242932965\n};\n<\/pre>\n<p>Sorprendente, \u00bfverdad? Es un truco poco conocido, pero que Microsoft usa a diestra y siniestra en el <a href=\"https:\/\/source.dot.net\" rel=\"noopener\" target=\"_blank\">c\u00f3digo de .NET Core<\/a>. Por razones que en parte se me escapan, el compilador de C# y el JIT transforman esta construcci\u00f3n en una zona de datos dentro de los metadatos del c\u00f3digo IL. Y el JIT lo maneja m\u00e1s eficientemente. No hay mucha l\u00f3gica en que tengamos que usar precisamente un <code>ReadOnlySpan&lt;double&gt;<\/code>, o que haya que convertir el campo en una propiedad de s\u00f3lo lectura. Se trata de una marca, o un gui\u00f1o de complicidad, que utilizan el JIT y el compilador para generar c\u00f3digo m\u00e1s eficiente.<\/p>\n<p>Esto me obliga a crear una nueva versi\u00f3n del amigo <code>Evaluate<\/code> que acepte un <code>ReadOnlySpan&lt;double&gt;<\/code> como origen de sus coeficientes. Esta es la nueva versi\u00f3n, con dos optimizaciones adicionales:<\/p>\n<pre class=\"EnlighterJSRAW\">\nprivate static double Evaluate(\n    double z, ReadOnlySpan&lt;double&gt; coeffs)\n{\n    int n = coeffs.Length;\n    ref double rd = ref MemoryMarshal.GetReference(coeffs);\n    double sum = Unsafe.Add(ref rd, n - 1);\n    for (int i = n - 2; i >= 0; --i)\n        sum = Math.FusedMultiplyAdd(\n            z, sum, Unsafe.Add(ref rd, i));\n    return sum;\n}\n<\/pre>\n<p>De las dos nuevas mejoras, la m\u00e1s sencilla es el uso de <code>Math.FusedMultiplyAdd<\/code>: un m\u00e9todo de la clase <code>Math<\/code> que combina la multiplicaci\u00f3n y la suma en una sola instrucci\u00f3n de la CPU, y puede darnos m\u00e1s velocidad y precisi\u00f3n. En este caso, adem\u00e1s, he medido que realmente sea ventajosa, porque no siempre lo es.<\/p>\n<p>El segundo cambio tiene dos partes. Como el bucle <code>for<\/code> utilizado no es un bucle convencional, el JIT actual no puede deducir que no habr\u00e1n referencias fuera de rango para eliminar las comprobaciones de los \u00edndices en tiempo de ejecuci\u00f3n. El bucle es descendente, y ni siquiera comienza por el \u00faltimo elemento. No le podemos exigir tanto al JIT.<\/p>\n<p>Lo primero que hago es pedir una <em>managed reference<\/em> a la primera celda de la tabla de coeficientes:<\/p>\n<pre class=\"EnlighterJSRAW\">\n    ref double rd = ref MemoryMarshal.GetReference(coeffs);\n    \/\/ Equivalente a:\n    \/\/ ref double rd = ref coeffs[0];\n<\/pre>\n<p>Esto es m\u00e1s o menos parecido a pedir un puntero al inicio de la tabla. En realidad, C# nos permitir\u00eda pedir un puntero al inicio de la tabla, pero el precio ser\u00eda \u00abfijar\u00bb la tabla en memoria para que el recolector de basura no vaya a pensar que no la estamos usando. El puntero que conseguimos con esta t\u00e9cnica es uno que el recolector de basura puede identificar y tener en cuenta. Y la forma normal de pedirlo es la que muestro en los comentarios del fragmento. \u00bfPor qu\u00e9 no la he usado? Pues porque implicar\u00eda una comprobaci\u00f3n de rango innecesaria: el JIT generar\u00eda una comparaci\u00f3n y un salto para verificar si la tabla no est\u00e1 vac\u00eda. Para evitarlo, uso <code>MemoryMarshal.GetReference<\/code>, que es otro truco sucio de Microsoft, para conseguir un puntero al inicio de un array sin costes ocultos.<\/p>\n<p>Lo que sigue es m\u00e1s sencillo: utilizo el m\u00e9todo <code>Add<\/code> de la clase <code>Unsafe<\/code> para llegar a cada una de las celdas que contienen los coeficientes. S\u00ed, todo es un poco enrevesado, pero una vez que te lo aprendes, no te cuesta nada escribir estas cosas de carrerilla. Me siento en el deber de cont\u00e1rselas. Ya usted decidir\u00e1 si merece la pena o no usarlas en su propio c\u00f3digo cuando lo crea necesario. No son cosas para usar en una aplicaci\u00f3n que tienes que escribir en tres meses. Pero creo que tienen un lugar en una librer\u00eda de c\u00f3digo.<\/p>\n<h4>Y hay m\u00e1s, claro<\/h4>\n<p>Hay montones de trucos similares en el c\u00f3digo fuente de .NET. Por ejemplo, imagine que hay que tiene que hacer una comprobaci\u00f3n de rango de un \u00edndice:<\/p>\n<pre class=\"EnlighterJSRAW\">\nif (0 <= index &#038;&#038; index < length) ...\n<\/pre>\n<p>Dos comparaciones, y dos saltos. Las comparaciones son lo de menos. Los dos saltos ralentizan todo. \u00bfQu\u00e9 hace Microsoft en estos casos?<\/p>\n<pre class=\"EnlighterJSRAW\">\nif ((uint)index < length) ...\n<\/pre>\n<p>La variable <code>index<\/code> suele ser un entero con signo. No cuesta nada pedir que el compilador la trate, moment\u00e1neamente, como un entero del mismo tama\u00f1o, pero sin signo. Si el \u00edndice fuese negativo, al tratarlo como un entero sin signo, el valor ser\u00eda inevitablemente superior al de <code>length<\/code>. Una sola comparaci\u00f3n, y un \u00fanico salto potencial.<\/p>\n<p>Veamos una variante derivada de este truco. El analizador lexical de Austra tiene que comprobar muchas veces si un car\u00e1cter es un d\u00edgito decimal:<\/p>\n<pre class=\"EnlighterJSRAW\">\nif ('0' <= ch &#038;&#038; ch <= '9') ...\n<\/pre>\n<p>La forma m\u00e1s eficiente, sin embargo, es la siguiente:<\/p>\n<pre class=\"EnlighterJSRAW\">\nif ((uint)(ch - '0') < 10u) ...\n<\/pre>\n<p>He introducido una resta, que se ejecuta eficientemente, y he quitado un salto potencial.<\/p>\n<p>De todas maneras, una de mis optimizaciones de chico listo preferidas es muy sencilla. En vez de escribir:<\/p>\n<pre class=\"EnlighterJSRAW\">\nx * x - y * y\n<\/pre>\n<p>un servidor prefiere:<\/p>\n<pre class=\"EnlighterJSRAW\">\n(x + y) * (x - y)\n<\/pre>\n<p>Y es que en la segunda expresi\u00f3n hay una suma de m\u00e1s, pero una multiplicaci\u00f3n de menos.<\/p>\n<p>Es agradable tener un cerebro cargado, y estar dispuestos a usarlo.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dec\u00eda el gran Donald Knuth algo as\u00ed como que premature optimization is the root of all evil. Santificado sea su nombre&#8230; Calidad de c\u00f3digo Una vez citadas las sagradas escrituras, debo reconocer que mi lado hereje cumple otros mandamientos: Peor que la optimizaci\u00f3n prematura, es no optimizar nunca. Una vez escuch\u00e9 una mala excusa sobre [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1515,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4,3],"tags":[65,87,86,10,85],"class_list":["post-1505","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c","category-insights","tag-net","tag-fma","tag-horner","tag-optimization","tag-spans"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/intsight.com\/wp-content\/uploads\/2023\/10\/smartboy.png?fit=494%2C494&ssl=1","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/1505","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/comments?post=1505"}],"version-history":[{"count":39,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/1505\/revisions"}],"predecessor-version":[{"id":1570,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/1505\/revisions\/1570"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/media\/1515"}],"wp:attachment":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/media?parent=1505"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/categories?post=1505"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/tags?post=1505"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}