Autor: Aléssio Miranda Júnior

Prática: Limites Computacionais

Este roteiro é projetado para testar e visualizar na prática como o computador e a Máquina Virtual Java (JVM) lidam com limites físicos de memória e de processamento.

Experimento 1: Memory Limit (Estouro de Heap)

Quando um programa precisa de mais memória para guardar instâncias e objetos do que o ambiente de execução tem disponível, ocorre o chamado erro de Estouro de Memória (Out of Memory - OOM). Em Java, este erro costuma aparecer como java.lang.OutOfMemoryError: Java heap space.

Sua tarefa inicial é implementar um programa que tenta alocar uma matriz quadrada cada vez maior no Heap (área da memória RAM onde os objetos do código residem) até que a memória acabe.

Estouro de Heap - Memória RAM

O que fazer: 1. Execute o código abaixo na sua máquina. 2. O programa tentará alocar matrizes preenchidas com o tipo long (que ocupa exatos 8 bytes por elemento). 3. Modifique o tamanho da matriz (variável N) e tente descobrir qual é a ordem de grandeza que fará seu ambiente estourar a memória.

public class ExperimentoMemoryLimit {
    public static void main(String[] args) {
        System.out.println("Iniciando teste de Memory Limit...");
        
        // Cada 'long' na matriz ocupa 8 bytes de memória.
        // Tente alterar o valor de N e observe quando a máquina falha!
        // Valores sugeridos: 10000, 20000, 30000, 50000...
        int N = 10000; 

        try {
            System.out.println("Tentando alocar matriz de " + N + " x " + N + "...");
            long[][] matriz = new long[N][N];
            
            // Calculando a memória aproximada exigida para guardar esses dados no hardware
            long bytes = (long) N * N * 8; // 8 bytes por long
            long megaBytes = bytes / (1024 * 1024);
            
            System.out.println("Sucesso! Memória aproximada alocada no Heap: " + megaBytes + " MB.");
        } catch (OutOfMemoryError e) {
            System.out.println("\nESTOURO DE MEMÓRIA! (OutOfMemoryError)");
            System.out.println("A JVM não conseguiu alocar espaço para N = " + N);
        }
    }
}

Marque a alternativa (X) que descreve a ordem de grandeza em que a sua máquina (ou a configuração padrão da sua JVM / SO) provocou o estouro do limite de memória:

• Aprox. \(10.000\) ~ (Consome 800 MB)
• Aprox. \(15.000\) ~ (Consome 1.8 GB)
• Aprox. \(20.000\) ~ (Consome 3.2 GB)
• Aprox. \(30.000\) ~ (Consome 7.2 GB)
• Aprox. \(50.000\) ~ (Consome 20.0 GB)

Experimento 2: Stack Overflow (Estouro da Pilha Recursiva)

Ao contrário de arrays, matrizes e objetos instanciados com o new (que ficam guardados no Heap), as camadas de chamadas de função/métodos e suas variáveis locais são gerenciadas por uma área da memória mais ágil, porém muito mais restrita, chamada Stack (Pilha de Chamadas).

Estouro da Pilha de Chamadas - Stack Overflow

Entendendo a Stack e a Recursão

A Stack funciona de acordo com a regra LIFO (Last In, First Out - O último a entrar é o primeiro a sair). Toda vez que uma função invoca outra função, a JVM pausa a execução da primeira e empilha um novo “bloco de contexto” (contendo as variáveis locais e a linha exata de retorno) no topo dessa pilha na memória RAM. Apenas quando a função no topo finaliza o seu trabalho (dando return), esse bloco é destruído e desempilhado da extremidade superior, devolvendo a execução da CPU para a função abaixo dela.

Quando utilizamos algoritmos com laços recursivos (funções que chamam a si mesmas sucessivamente), cada nova invocação exige um novo bloco empilhado sobre os anteriores. Se a condição de parada (Base Case) da recursão demorar muito para ser alcançada, esses blocos se acumulam descontroladamente. Quando a altura dessa pilha atinge o teto físico do espaço pré-alocado pelo sistema operacional para essa estrutura, ocorre o crash estrutural no processo que conhecemos como o clássico e temido java.lang.StackOverflowError.

O que fazer: 1. O código a seguir calcula o clássico fatorial de um número utilizando recursividade. 2. Teste inicializando com o número 5 e veja como o programa se divide. 3. Agora altere a entrada para um número bastante alto (numero = 200000) e verifique o comportamento da máquina.

public class ExperimentoStackOverflow {

    public static long fatorial(long n, int profundidade) {
        // A cada mil empilhamentos alcançados, imprimimos em que profundidade da Stack estamos
        if (profundidade % 1000 == 0) {
            System.out.println("Profundidade atual da recursao (Stack): " + profundidade);
        }

        // Condição de parada do fatorial
        if (n <= 1) {
            return 1;
        }
        
        // Chamada recursiva: a cada chamada interna, alocamos informações na Pilha (Stack)
        return n * fatorial(n - 1, profundidade + 1);
    }

    public static void main(String[] args) {
        System.out.println("Iniciando teste de Stack Overflow...");
        
        // Número alto que tentaremos calcular. 
        // Aumente de forma gradual caso ele tenha passado no seu teste.
        long numero = 150000; 
        
        try {
            long resultado = fatorial(numero, 1);
            System.out.println("Resultado: " + resultado);
        } catch (StackOverflowError e) {
            System.err.println("\nESTOURO DA PILHA DE CHAMADAS! (StackOverflowError)");
            System.err.println("A pilha suportou uma profundidade considerável de métodos ativos, mas excedeu seu limite de alocação da Stack antes da condição de parada.");
        }
    }
}

Reflexão: Em qual profundidade de execução aproximadamente o seu programa travou e estourou a pilha recursiva (em qual fatorial)? Pense em como contornar isso com o que estudamos até então (Ex: uso do laço iterativo for/while consome apenas escopo local e resolve o esgotamento do tamanho da Stack de processos).

Experimento 3: Time Limit (Limite de Tempo de Execução)

Neste experimento, você presenciará na prática como as diferentes Complexidades Assintóticas lidam frente ao processamento real. Veremos como o impacto algorítmico do \(O(n^2)\) em um algoritmo básico como o Bubble Sort destrói e satura o tempo de processamento quando comparado com uma implementação \(O(n \log n)\) robusta construída pela classe Arrays do Java, que implementa um algoritmo híbrido (Dual-Pivot Quicksort).

Gráfico de Complexidade de Tempo O(n²) vs O(n log n)

O que fazer: 1. O programa gera um grande vetor de números aleatórios com de tamanho inicial definido por N. Dois algoritmos correrão para organizar o Array para nós: o Bubble Sort e a ordenação embutida do Java. 2. Usamos um cronômetro milissegundo interno System.currentTimeMillis() para verificar a rapidez.

import java.util.Arrays;
import java.util.Random;

public class ExperimentoTimeLimit {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // Repare nos dois laços for aninhados (Complexidade O(n^2))
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Troca de posição dos elementos no laço interno
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        // Tamanho inicial do Array de números aleatórios.
        int N = 50000; 

        int[] arrayBubble = new int[N];
        int[] arrayQuick = new int[N];

        // Populando nosso array de maneira randômica
        Random random = new Random();
        for (int i = 0; i < N; i++) {
            int valorAleatorio = random.nextInt(N);
            arrayBubble[i] = valorAleatorio;
            arrayQuick[i] = valorAleatorio; // Corrigido a atribuição
        }

        System.out.println("Vetor gerado contendo " + N + " números prontos para processamento...\n");

        // =========== SEÇÃO 1: MEDINDO ALGORITMO BUBBLE SORT ===========
        System.out.print("Iniciando algoritmo tradicional - Bubble Sort [ O(n^2) ] ... ");
        long inicioBubble = System.currentTimeMillis();
        
        bubbleSort(arrayBubble);
        
        long fimBubble = System.currentTimeMillis();
        System.out.println("Concluído!\n» Tempo gasto pelo Bubble Sort: " + (fimBubble - inicioBubble) + " milissegundos");

        // =========== SEÇÃO 2: MEDINDO QUICKSORT PADRÃO DO JAVA ===========
        System.out.println("");
        System.out.print("Iniciando Arrays.sort() do Java [ O(n log n) ] ... ");
        long inicioQuick = System.currentTimeMillis();
        
        // Aqui o Java invoca seu Dual-Pivot Quicksort
        Arrays.sort(arrayQuick);
        
        long fimQuick = System.currentTimeMillis();
        System.out.println("Concluído!\n» Tempo gasto pela solução O(n log n): " + (fimQuick - inicioQuick) + " milissegundos");
    }
}

Tarefa: Execute o código inteiro variando os tamanhos para analisar a Time Limit em ação.

Dobre sistematicamente o tamanho da entrada alterando N. Tente com N = 25000, em seguida experimente N = 50000, avance para 100000 e possivelmente 200000.

• O que acontece com o tempo final de execução do código de Bubble Sort cada vez que dobramos N de tamanho? Quantas vezes o cronômetro aumentou sua duração base do Bubble Sort na medida em que fomos dobrando ele?
• Em contraponto, verifique a curva de tempo gasta e percorrida pela classe nativa do Java. O que é possível notar comparada visualmente com a de complexidade \(N^2\)?