Sobre stackalloc, o (mejor) Homenaje a John Horton Conway

El pasado fin de semana estaba empezando a escribir este artículo al mismo tiempo que miraba las noticias, que últimamente no traen nada bueno. Ahora que se me van acabando las novedades recientes de C# de las que no he hablado todavía, y que no me atrevo a decir nada sobre aquella de la que no me siento preparado para hablar – léase los tipos-referencia anulables (nullable reference types), el artículo iba a estar dedicado al operador stackalloc, que con la última versión del lenguaje ha salido del oscuro nicho del código no seguro (unsafe code) para pasar a poder ser utilizado en escenarios más comunes.

Esencialmente, al utilizar stackalloc en lugar de new al inicializar un array local dentro de un método, se le está indicando al compilador que reserve la memoria para ese array en la pila de ejecución en lugar de crear un objeto heredero de Array en la memoria dinámica, como ocurriría al usar new. En C# 8.0, ese vector en la pila debe manipularse (fuera de un contexto no seguro) a través de la clase Span<T> de la que ya hablamos hace un tiempo aquí. En muy diversas situaciones, el alojamiento en la pila podría producir mejoras en el rendimiento, ya sea debido a la mayor velocidad de adquisición de la memoria (que en el caso de la pila se reduce a mover un puntero), a la localidad de los datos que el método manipula, o a la disminución en las necesidades de ejecución del recolector de basura.

Una vez claros los fundamentos teóricos en los que se basa la característica, tocaba lo más difícil: encontrar un buen ejemplo que hiciera evidente esas ventajas. Y entonces levanté los ojos para mirar las noticias, donde presentaban a personajes más o menos conocidos que perdieron la vida recientemente a causa del brutal COVID-19. Entre ellos estaba John Horton Conway, el genial matemático británico que creó esa maravilla de máquina universal de Turing que es el Juego de la vida (Game of Life). El Juego de la vida forma parte indeleble de mis memorias de juventud: aún recuerdo el brillo en los ojos de nuestros alumnos de Programación en la Universidad de La Habana cuando les explicábamos1 en qué consiste el juego y luego los veíamos pasarse horas implementándolo en aquellos IBM PC originales (para los que la fecha inicial siempre era el 1 de enero de 1980), utilizando esa otra maravilla de la tecnología de su tiempo que era Turbo PASCAL 3.0 (¿alguien recuerda el número 39671?).

El fichero que se adjunta al final del artículo contiene una implementación en C# del Juego de la vida, adaptada de la que se ofrece en Rosetta Code. El método que crea una nueva generación a partir de la actual es el siguiente:

private void UpdateBoard()
{
    // A temp variable to hold the next state while it's being calculated.
    Span<bool> newBoard = new bool[Width * Height];

    for (var y = 0; y < Height; y++)
    {
        for (var x = 0; x < Width; x++)
        {
            var n = CountLiveNeighbors(x, y);
            var c = board[x + y * Width];

            // A live cell dies unless it has exactly 2 or 3 live neighbors.
            // A dead cell remains dead unless it has exactly 3 live neighbors.
            newBoard[x + y * Width] = c && (n == 2 || n == 3) || !c && n == 3;
        }
    }

    // Set the board to its new state.
    board = newBoard.ToArray();
}

Para adaptarme a las limitaciones de stackalloc, he introducido a Span<T>, he convertido a posta la estructura de datos newBoard (originalmente una matriz) en un array, y me he echado encima el cálculo de la posición en memoria de los elementos. Todo eso hace posible pasar de una versión que usa new para reservar la memoria a una que utiliza stackalloc cambiando sólo la primera línea de código del método:

    Span<bool> newBoard = stackalloc bool[Width * Height];

Con el objetivo de comparar el rendimiento de ambas variantes, el programa de ejemplo ejecuta bajo condiciones repetibles 250 juegos sobre un tablero de 100*100 celdas. Invito al lector a que repita el experimento y vea si obtiene resultados diferentes al mío. En mi viejo Mac, con la optimización de código activada y ejecutando sin depuración, la variante que usa new requirió 694 segundos, mientras que la variante basada en stackalloc consumió 676. No puedo asegurar que estos números den una respuesta concluyente sobre las ventajas de usar stackalloc, pero eso lo dejo también al análisis del lector interesado. A fin de cuentas, el objetivo de este artículo no era tanto hablar de programación como servir como modesto homenaje a la vida y obra de John Horton Conway. God rest his soul!


1 Me refiero aquí a los miembros del equipo docente dirigido por mentor y amigo Miguel Katrib.

Código fuente:

using System;

namespace Conway
{
    // Plays Conway's Game of Life with a random initial state.
    public class GameOfLifeBoard
    {
        // The dimensions of the board in cells.
        private const int Width = 100;
        private const int Height = 100;

        // Holds the current state of the board.
        private bool[] board;

        // Creates the initial board with a random state.
        public GameOfLifeBoard(int randomSeed = 0)
        {
            var random = randomSeed == 0 ? new Random() : new Random(randomSeed);

            board = new bool[Width * Height];
            for (var y = 0; y < Height; y++)
            {
                for (var x = 0; x < Width; x++)
                {
                    // Equal probability of being true or false.
                    board[x + y * Width] = random.Next(2) == 0;
                }
            }
        }

        // Play the game until the colony extinguishes or maximum iterations is reached
        public bool Run(int maxIterations)
        {
            int i = 0;
            while (i < maxIterations & !IsEmpty)
            {
                UpdateBoard();
                i++;
            }
            return !IsEmpty;
        }

        // Return whether the colony has no live cells
        public bool IsEmpty
        {
            get
            {
                for (var y = 0; y < Height; y++)
                {
                    for (var x = 0; x < Width; x++)
                    {
                        if (board[x + y * Width])
                        {
                            return false;
                        }
                    }
                }
                return true;
            }
        }

        // Moves the board to the next state based on Conway's rules.
        private void UpdateBoard()
        {
            // A temp variable to hold the next state while it's being calculated.
            Span newBoard = new bool[Width * Height];

            for (var y = 0; y < Height; y++)
            {
                for (var x = 0; x < Width; x++)
                {
                    var n = CountLiveNeighbors(x, y);
                    var c = board[x + y * Width];

                    // A live cell dies unless it has exactly 2 or 3 live neighbors.
                    // A dead cell remains dead unless it has exactly 3 live neighbors.
                    newBoard[x + y * Width] = c && (n == 2 || n == 3) || !c && n == 3;
                }
            }

            // Set the board to its new state.
            board = newBoard.ToArray();
        }

        // Returns the number of live neighbors around the cell at position (x,y).
        private int CountLiveNeighbors(int x, int y)
        {
            // The number of live neighbors.
            int value = 0;

            // This nested loop enumerates the 9 cells in the specified cells neighborhood.
            for (var j = -1; j <= 1; j++)
            {
                // If y+j is off the board, continue.
                if (y + j < 0 || y + j >= Height)
                {
                    continue;
                }

                for (var i = -1; i <= 1; i++)
                {
                    // If x+i is off the board, continue.
                    if (x + i < 0 || x + i >= Width)
                    {
                        continue;
                    }

                    // Count the neighbor cell at (h,k) if it is alive.
                    value += board[x + i + (y + j) * Width] ? 1 : 0;
                }
            }

            // Subtract 1 if (x,y) is alive since we counted it as a neighbor.
            return value - (board[x + y * Width] ? 1 : 0);
        }

        static void Main(string[] args)
        {
            const int MaxGames = 250;
            const int MaxIterations = 10000;

            DateTime start = DateTime.Now;
            int survived = 0, extinguished = 0;
            for (int i = 0; i < MaxGames; i++)
            {
                Console.WriteLine(i);
                var board = new GameOfLifeBoard(i);
                if (board.Run(MaxIterations))
                {
                    survived++;
                }
                else
                {
                    extinguished++;
                }
            }
            DateTime end = DateTime.Now;

            Console.WriteLine($"Survived:     {survived,6:d}");
            Console.WriteLine($"Extinguished: {extinguished,6:d}");
            Console.WriteLine($"Total time:   {(int)(end - start).TotalSeconds,6:d}");
        }
    }
}

Octavio Hernandez

Desarrollador y consultor en tecnologías .NET. Microsoft C# MVP entre 2004 y 2010.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *