CPU: pipeline, cache L1/L2/L3, branch prediction

# Impacto do pipeline na prática — medindo com timeit
import timeit

# Acesso sequencial vs aleatório (cache-friendly vs cache-unfriendly)
import random

SIZE = 10_000_000
dados_sequenciais = list(range(SIZE))
dados_aleatorios = dados_sequenciais.copy()
random.shuffle(dados_aleatorios)

# Criar índices para acesso
indices_seq = list(range(SIZE))
indices_rand = list(range(SIZE))
random.shuffle(indices_rand)

def acesso_sequencial():
    total = 0
    for i in indices_seq:
        total += dados_sequenciais[i]
    return total

def acesso_aleatorio():
    total = 0
    for i in indices_rand:
        total += dados_aleatorios[i]
    return total

# Resultado típico:
# sequencial: ~0.8s
# aleatório:  ~1.5s (2x mais lento — cache misses)

# Melhor em numpy (acesso vetorizado + SIMD):
import numpy as np
arr = np.arange(SIZE, dtype=np.int64)
# np.sum(arr) → ~5ms  (vs 800ms Python puro — 160x mais rápido)

# Demonstrando cache miss em Python
# (números são relativos — Python tem overhead grande de intérprete)
import timeit

# Lista de listas — péssimo para cache (pointer chasing)
matriz_ruim = [[i * 1000 + j for j in range(1000)] for i in range(1000)]

# Numpy array — contíguo na memória (cache-friendly)
import numpy as np
matriz_boa = np.zeros((1000, 1000), dtype=np.int64)

# Row-major (C order, NumPy default) — acesso por linhas é rápido
t1 = timeit.timeit(lambda: np.sum(matriz_boa[0, :]), number=10000)  # linha
t2 = timeit.timeit(lambda: np.sum(matriz_boa[:, 0]), number=10000)  # coluna
# t1 << t2 (acesso por coluna pula 1000 elementos na memória — mais cache misses)

# Linha de cache tem 64 bytes = 8 × int64
# Carregar um elemento de numpy float64 carrega os 7 vizinhos na mesma linha de cache

import timeit
import random

# Branch prediction favorece padrões previsíveis
dados = list(range(10_000))

def com_branch_previsivel():
    # loop sem if imprevisível — quase sempre mesmo caminho
    total = 0
    for x in dados:
        total += x  # sem branch aqui
    return total

dados_aleatorios = [random.randint(0, 100) for _ in range(10_000)]

def com_branch_imprevisivel():
    # condição depende de dados aleatórios — preditor erra ~50%
    total = 0
    for x in dados_aleatorios:
        if x > 50:    # ← branch imprevisível
            total += x
    return total

def sem_branch():
    # elimina o branch com operação vetorizada
    return sum(x for x in dados_aleatorios if x > 50)

# Numpy elimina branches com operações vetorizadas:
import numpy as np
arr = np.array(dados_aleatorios)
# np.sum(arr[arr > 50]) — sem Python branch, operação SIMD na CPU

# Estratégias para código cache/branch-friendly:
# 1. Prefira loops sobre arrays contíguos (numpy, bytearray) vs listas de objetos
# 2. Estruture condições para o caso comum primeiro (profiling ajuda)
# 3. Use numpy/pandas para operações vetorizadas que evitam Python branching
# 4. Evite linked lists para dados que serão iterados — use arrays
# 5. Prefira struct-of-arrays vs array-of-structs para SIMD efficiency