DEV Community: Jônatas A.

Resolvendo o desafio de um bilhão de linhas em Go (de 1m40s para 8,4s)

Jônatas A. — Sat, 03 Aug 2024 00:58:26 +0000

Há um tempo atrás, um amigo comentou comigo sobre um desafio que envolvia ler um arquivo com 1 bilhão de linhas. Achei a ideia muito interessante, mas como estava em semana de provas na faculdade, acabei deixando para ver isso depois. Meses depois, vi um vídeo do Theo sobre o desafio e resolvi dar uma olhada mais de perto.

O objetivo do One Billion Row Challenge é calcular a temperatura mínima, máxima e média de uma lista de cidades - o detalhe é que são 1 bilhão de itens nessa lista, onde cada item consiste do nome de uma cidade e uma temperatura, sendo que cada cidade pode aparecer mais de uma vez. or fim, o programa deve exibir esses valores em ordem alfabética pelo nome da cidade.

Achei que seria divertido tentar resolver o desafio, mesmo que não houvesse uma recompensa. Enfim, fiz este texto descrevendo o meu processo.

Primeira tentativa: fazendo o código funcionar

Sempre que preciso resolver um problema mais complicado, minha primeira meta é fazer o programa funcionar. Pode não ser o código mais rápido e nem o mais limpo, mas é um código que funciona.

Basicamente, criei a estrutura Location para representar cada cidade da lista, contendo a temperatura mínima, máxima, a soma das temperaturas e quantas vezes a cidade aparece na lista (esses dois últimos são necessários para calcular a média). Sei que existe uma maneira de calcular a média diretamente, sem precisar armazenar a quantidade de temperaturas e a soma delas. Mas, como mencionei anteriormente, o objetivo era fazer o código funcionar.

A lista de dados é formada pelo nome da cidade seguido pela temperatura, separados por um ponto e vírgula. Por exemplo:

Antananarivo;15.6
Iqaluit;-20.7
Dolisie;25.8
Kuopio;-6.8

O jeito mais simples para ler os dados é utilizando o Scan, que permite ler uma linha de cada vez. Com a linha, é possível dividi-la em duas partes: os valores antes e após o ponto e vírgula. Para obter a temperatura, é possível usar o strconv.ParseFloat, que converte uma string em um float. O código completo da primeira implementação pode ser visto abaixo:

package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "sort"
    "strconv"
    "strings"
)

type Location struct {
    min   float64
    max   float64
    sum   float64
    count int
}

func NewLocation() *Location {
    return &Location{
        min:   math.MaxInt16,
        max:   math.MinInt16,
        sum:   0,
        count: 0,
    }
}

func (loc *Location) Add(temp float64) {
    if temp < loc.min {
        loc.min = temp
    } else if temp > loc.max {
        loc.max = temp
    }

    loc.sum += temp
    loc.count += 1
}

var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")

func main() {
    flag.Parse()
    if *cpuprofile != "" {
        f, err := os.Create(*cpuprofile)
        if err != nil {
            log.Fatal(err)
        }
        pprof.StartCPUProfile(f)
        defer pprof.StopCPUProfile()
    }

    file, _ := os.Open("./measurements.txt")
    defer file.Close()

    m := map[string]*Location{}

    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        line := scanner.Text()
        name, tempStr, _ := strings.Cut(line, ";")
        temp, _ := strconv.ParseFloat(tempStr, 32)

        loc, ok := m[name]
        if !ok {
            loc = NewLocation()
            m[name] = loc
        }
        loc.Add(temp)
    }

    keys := make([]string, 0, len(m))
    for k := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)

    for _, name := range keys {
        loc := m[name]
        mean := loc.sum / float64(loc.count)
        fmt.Printf("%s: %.1f/%.1f/%.1f\n", name, loc.min, mean, loc.max)
    }
}

Essa versão mais simples levou aproximadamente 97 segundos para rodar.

Otimizando a conversão de strings para floats

Analisando o profile da execução, percebi que um dos maiores gargalos era a função strconv.ParseFloat. Basicamente, tempo total de execução dela foi de 23 segundos (aproximadamente 23% do tempo total).

O problema dessa função é que ela é genérica, ou seja, é feita para funcionar com qualquer float válido. Porém, nossos dados têm um formato de temperatura bem específico. Veja o exemplo abaixo:

Antananarivo;15.6
Iqaluit;-20.7
Dolisie;5.8
Kuopio;-6.8

O formato da temperatura é sempre o mesmo: um ou dois dígitos antes do ponto e um dígito após o ponto, podendo incluir um sinal de menos no inicio. Assim, podemos criar uma função que converte os valores de forma específica, otimizando o processo sem a necessidade de realizar todas as verificações genéricas do ParseFloat.

func bytesToTemp(b []byte) float64 {
    var v int16
    var isNeg int16 = 1

    for i := 0; i < len(b)-1; i++ {
        char := b[i]
        if char == '-' {
            isNeg = -1
        } else if char == '.' {
            digit := int16(b[i+1] - '0')
            v = v*10 + digit
        } else {
            digit := int16(char - '0')
            v = v*10 + digit
        }
    }

    return float64(v*isNeg) / 10
}

Para ler os dados em formato de bytes em vez de string, alterei o retorno do Scanner de string para bytes

line := scanner.Bytes()
before, after, _ := bytes.Cut(line, []byte{';'})
name := string(before)
temp := bytesToTemp(after)

Essas pequenas mudanças fizeram o tempo de execução cair para 75 segundos.

Lendo pedaços maiores de dados

A maior vantagem de usar o Scan é que o programa não precisa carregar todo o arquivo de uma só vez na memória. Em vez disso, permite ler linha por linha, trocando desempenho por memória.

É importante ressaltar que existe um meio-termo entre ler uma linha por vez e carregar os 14 GB de dados de uma só vez. Esse meio termo é a leitura de chunks, que são pedaços de memória. Dessa forma, ao invés de ler todo o arquivo de uma vez, podemos ler blocos de 128 MB.

buf := make([]byte, chunkSize)
reader := bufio.NewReader(file)
var leftData []byte
for {
    n, err := reader.Read(buf)
    if err != nil {
        if err == io.EOF {
            break
        }
        panic(err)
    }

    chunk := append(leftData, buf[:n]...)
    lastIndex := bytes.LastIndex(chunk, []byte{'\n'})
    leftData = chunk[lastIndex+1:]

    lines := bytes.Split(chunk[:lastIndex], []byte{'\n'})

    for _, line := range lines {
        before, after, _ := bytes.Cut(line, []byte{';'})
        name := string(before)
        temp := bytesToTemp(after)

        loc, ok := m[name]
        if !ok {
            loc = NewLocation()
            m[name] = loc
        }
        loc.Add(temp)
    }
}

Com isso, o tempo de execução caiu para 70 segundos. Melhor que antes, mas ainda da para melhorar.

Alterando os tipos dos dados

É fato que todo o desafio gira em torno de números com casas decimais. Porém, lidar com pontos flutuantes é sempre um grande desafio (vide IEEE-754). Nesse caso, por que não usar inteiros para representar a temperatura?

type Location struct {
    min   int16
    max   int16
    sum   int32
    count int32
}

Como definido anteriormente, uma temperatura é sempre representada por até três dígitos. Logo, removendo a vírgula, os valores podem variar entre -999 e 999, de modo que int16 é o suficiente para representá-los. Para a soma e a contagem, int32 é mais que o suficiente, visto que esse tipo pode variar entre -2147483648 e 2147483647.

Dado que agora esperamos um valor inteiro de 16 bits para a temperatura, precisamos modificar a função bytesToTemp. Para isso, mudamos o retorno para int16 e removemos a divisão no final. Assim, a função vai sempre vai retornar um número inteiro.

func bytesToTemp(b []byte) int16 {
    var v int16
    var isNeg int16 = 1

    for i := 0; i < len(b)-1; i++ {
        char := b[i]
        if char == '-' {
            isNeg = -1
        } else if char == '.' {
            digit := int16(b[i+1] - '0')
            v = v*10 + digit
        } else {
            digit := int16(char - '0')
            v = v*10 + digit
        }
    }

    return v * isNeg
}

Para finalizar, modifiquei a função Add para aceitar os valores inteiros e ajustei o print para dividir os valores antes de mostrá-los na tela. Com isso, o tempo caiu três segundos, indo para 60 segundos. Não é muito, mas uma vitória é uma vitória.

Melhorando a Performance da Conversão de Bytes para String

Novamente analisando o profile, vi que tinha uma certa função chamada slicebytetostring que custava 13,5 segundos de tempo de execução. Analisando, descobri que essa função é a responsável por converter um conjunto de bytes em uma string (o próprio nome da função deixa claro isso). No caso, essa é a função chamada internamente quando se usa a função string(bytes).

Em Go, assim como na maioria das linguagens, strings são imutáveis, o que significa que não podem ser modificadas após serem criadas (normalmente, quando se faz isso, uma nova string é criada). Por outro lado, listas são mutáveis. Ou seja, quando se faz uma conversão de uma lista de bytes para string, é preciso criar uma cópia da lista para garantir que a string não mude se a lista mudar.

Para evitar o custo adicional de alocação de memória nessas conversões, podemos utilizar a biblioteca unsafe para realizar a conversão de bytes para string (Nota: ela é chamada de unsafe por um motivo).

name := unsafe.String(unsafe.SliceData(before), len(before))

Diferente do caso anterior, a função acima reutiliza os bytes passados para gerar a string. O problema disso é que, se a lista original mudar, a string resultante também será afetada. Embora possamos garantir que isso não ocorrerá neste contexto específico, em aplicações maiores e mais complexas, o uso de unsafe pode se tornar bem inseguro.

Com essa mudança, reduzimos o tempo de execução para 51 segundos. Nada mal.

Reimplementando `bytes.Cut`

Lembra que eu mencionei que as temperaturas sempre tinham formatos específicos? Então, segundo o profile da execução, que separa a linha em duas partes (nome da cidade e temperatura), custa 5.38 segundos para rodar. E refizermos ela na mão?

Para separar os dois valores, precisamos encontrar onde está o ";". Como a gente já sabe, os valores da temperatura podem ter entre três e cinco caracteres. Assim, precisamos verificar se o caractere anterior aos dígitos é um ";". Simples, não?

idx := 0
if line[len(line)-4] == ';' {
    idx = len(line) - 4
} else if line[len(line)-5] == ';' {
    idx = len(line) - 5
} else {
    idx = len(line) - 6
}

before := line[:idx]
after := line[idx+1:]

Com isso, o tempo de execução foi para 46 segundos, cerca de 5 segundos a menos que antes (quem diria, não é?).

Paralelismo para acelerar o processamento

Todo esse tempo, nosso objetivo foi tornar o código o mais rápido possível em um núcleo. Mudando coisas aqui e ali, diminuímos o tempo de 97 segundos para 46 segundos. Claro, ainda daria para melhorar o tempo sem ter que lidar com paralelismo, mas a vida é curta demais para se preocupar com isso, não é?

Para poder rodar o código em vários núcleos, decidi usar a estrutura de canais nativa do Go. Além disso, também criei um grupo de espera que vai indicar quando o processamento dos dados terminaram.

Vale destacar que workers, nesse caso, é uma constante que define quantas goroutines serão criadas para processar os dados. No meu caso, são 12, visto que eu tenho um processador com 6 núcleos e 12 threads.

chunkChan := make(chan []byte, workers)
var wg sync.WaitGroup
wg.Add(workers)

O próximo passo foi criar as goroutines que serão responsável por receber os dados do canal e processá-los. A lógica de processamento dos dados é semelhante ao modelo single thread.

for i := 0; i < workers; i++ {
    go func() {
        for chunk := range chunkChan {
            lines := bytes.Split(chunk, []byte{'\n'})
            for _, line := range lines {
                before, after := parseLine(line)
                name := unsafe.String(unsafe.SliceData(before), len(before))
                temp := bytesToTemp(after)

                loc, ok := m[name]
                if !ok {
                    loc = NewLocation()
                    m[name] = loc
                }
                loc.Add(temp)
            }
        }
        wg.Done()
    }()
}

Por fim, o código responsável por ler os dados do disco e enviá-los ao canal:

for {
    n, err := reader.Read(buf)
    if err != nil {
        if err == io.EOF {
            break
        }
        panic(err)
    }

    chunk := append(leftData, buf[:n]...)
    lastIndex := bytes.LastIndex(chunk, []byte{'\n'})
    leftData = chunk[lastIndex+1:]
    chunkChan <- chunk[:lastIndex]
}
close(chunkChan)
wg.Wait()

Vale ressaltar que os mapas em Go não são thread-safe. Isso significa que acessar ou alterar dados no mesmo mapa de forma concorrente pode levar a problemas de consistência ou erros. Embora não tenha observado problemas durante meus testes, vale a pena tratar esse problema.

Uma das maneiras de resolver esse problema seria criar um mecanismo de trava para o mapa, permitindo que somente uma goroutine consiga utilizá-lo por vez. Isso, claro, poderia tornar a execução um pouco mais lenta.

A segunda alternativa consiste em criar um mapa para cada uma das goroutines, de modo que não vai existir concorrência entre elas. Por fim, os mapas são colocados em um novo canal e os valores do mapa principal calculados a partir deles. Essa solução ainda vai ter um custo, mas vai ser menor que a anterior.

close(chunkChan)

go func() {
    wg.Wait()
    close(mapChan)
}()

keys := make([]string, 0, 825)

m := map[string]*Location{}
for lm := range mapChan {
    for lk, lLoc := range lm {
        loc, ok := m[lk]
        if !ok {
            keys = append(keys, lk)
            m[lk] = lLoc
            continue
        }

        if lLoc.min < loc.min {
            loc.min = lLoc.min
        }
        if lLoc.max > loc.max {
            loc.max = lLoc.max
        }
        loc.sum += lLoc.sum
        loc.count += lLoc.count
    }
}

Além disso, como o processamento passou a ser distribuído entre diferentes núcleos, diminui o tamanho do chunk de 128 MB para 2 MB. Cheguei nesse número testando vários valores, tendo entre 1 MB e 5 MB os melhores resultando. Na média, 2 MB obteve o melhor desempenho.

Enfim, o nosso tempo de processamento caiu de 46 segundos para... 12 segundos.

Otimizando a quebra de linhas no chunk

Todas as vezes que eu analisava o profile, a função bytes.Split chamava a minha atenção. O tempo de execução dela era de 16 segundos (tempo total, considerando todas as goroutines), o que parece justo, visto que ela é responsável por quebrar um chunk em linhas. No entanto, parecia um trabalho dobrado, dado que ela primeiro quebra as linhas para, em seguida, as linhas serem lidas uma a uma. Por que não fazer ambos ao mesmo tempo?

Minha abordagem foi percorrer o chunk e verificar se o byte atual correspondia a um \n. Dessa forma, consegui percorrer todas as linhas ao mesmo tempo em que as quebrava, processando em seguida.

start := 0
start := 0
for end, b := range chunk {
    if b != '\n' {
        continue
    }
    before, after := parseLine(chunk[start:end])
    // ...
    start = end + 1
}

Com essa simples mudança, o tempo de execução caiu para aproximadamente 9 segundos.

Executed in    8.45 secs    fish           external
   usr time   58.47 secs  152.00 micros   58.47 secs
   sys time    4.52 secs  136.00 micros    4.52 secs

Próximos passos

Atualmente, o maior gargalo da aplicação é o mapa. Somando todas as operações de leitura e escrita, são 32 segundos (de longe, o tempo mais alto). Talvez criar um algoritmo de hash mais eficiente resolva? Fica como ideia para o futuro.

No mais, conseguimos diminuir o tempo de 1 minuto e 40 segundos para quase 8 segundos, sem usar qualquer biblioteca externa. Além disso, tentando fazer a aplicação ficar cada vez mais rápida, me fez aprender muita coisa.

Como eu criei em algumas horas um site que busca propostas de freelas

Jônatas A. — Sun, 19 Jun 2022 23:35:32 +0000

Conteúdo originalmente publicado em: https://jnaraujo.com/blog/como-eu-criei-em-algumas-horas-um-site-que-busca-propostas-de-freelas

Há um tempo atrás, eu estava conversando com um amigo sobre como pegar trabalhos na internet. Ele me contou que usava o Reddit para isso - basicamente, existem comunidades em que pessoas que precisam de alguém pra fazer um trabalho postam sua proposta, falando o que querem, pra quando querem e (o mais importante) quanto querem pagar.

Eu achei isso incrível - um lugar onde as pessoas anunciavam o que queriam e ainda pagavam em dólar.

Claro que existem plataformas parecidas - como o 99freelas ou o Workana. Mas esses sites normalmente ficam com uma parte do dinheiro e a concorrência é muito - mas muito - grande. Além disso, nem todos pagam em dólar.

Só que nem tudo são flores

Dando uma olhada nessas comunidades, eu achei alguns "problemas".

Primeiro que nem todos os posts ali eram de gente querendo contratar - boa parte era de gente mostrando seus próprios serviços.

Além disso, tinha muito trabalho que não me interessava - tinha gente postando todo tipo de coisa, desde trabalho full-time de marketing até gente que queria fazer uma planilha no Excel.

Agora, junte tudo isso e multiplique por 5.

Eu, como todo programador que se preze, achei que ficar entrando nesses subreddits e analisando os freelas era trabalho demais. Então resolvi criar um script para fazer o trabalho que eu, definitivamente, não queria fazer.

Deixando o trabalho repetitivo pra outro trouxa
Minha primeira ideia foi checar como funcionava a API do Reddit - se precisava de autenticação, criar um token, fazer um pacto ou alguma coisa parecida.

Pra ser sincero, eu achei o site deles muito feio e bagunçado. Além disso, não estava com muita vontade de ficar vasculhando para ver se achava o que eu queria. Por isso, resolvi procurar um outro jeito.

Dando uma olhadinha nas profundezas da internet eu descobri que colocando .json no final do link do subReddit ele retorna o site em json.

Por exemplo a URL https://www.reddit.com/r/memes/new que vira https://www.reddit.com/r/memes/new.json

Simplesmente incrível.

Então criei um código simples e cheio de gambiarras em Javascript com Node que entrava no site e retornava os últimos freelas pra mim.

Bem... a ideia tava certa. Só que nada é tão simples assim.

Dando uma limpadinha nos dados

Pois é, quem diria que os dados estariam sujos, não é mesmo?

Na verdade, eu já esperava isso. Foi um dos motivos de eu querer fazer esse script - limpar as postagens de gente procurando trabalho e tentar filtrar os freelas.

Além disso, eu queria remover aquelas propostas que já tinham sido atendidas por outras pessoas.

Resolver a primeira parte foi simples: quando os dados eram retornados em uma lista, eu adicionei um filtro que tirava posts com tags que eu não queria (como a tag “For Hire”). Além disso, adicionei alguns filtros de segurança, como remover posts de usuários banidos etc.

async function mountPosts(limitPerPost=20){
  let finalPosts = [];

  for (let index = 0; index < subReddits.length; index++) {
    const subReddit = subReddits[index];
    let res = await getReddit.getLastPostsFromSubreddit(subReddit, 30);
    let posts = res.filter(getReddit.isPostValid);

    finalPosts.push(...posts.slice(0,limitPerPost));
  }

  return finalPosts.sort(sortFunction).reverse();;
}
async function mountPosts(limitPerPost=20){
  let finalPosts = [];

  for (let index = 0; index < subReddits.length; index++) {
    const subReddit = subReddits[index];
    let res = await getReddit.getLastPostsFromSubreddit(subReddit, 30);
    let posts = res.filter(getReddit.isPostValid);

    finalPosts.push(...posts.slice(0,limitPerPost));
  }

  return finalPosts.sort(sortFunction).reverse();;
}

Feito isso, a coisa parecia estar indo bem.

Cria um site logo, amigo

Depois de ter feito a base, eu comentei com um amigo sobre o que eu tinha feito.

E se isso fosse um site? - ele perguntou.

A ideia parecia boa.

Eu também achei que seria muito melhor ver tudo isso de uma forma mais visualmente agradável - como um site - que em um terminal de comandos.

Eu também queria treinar meu ReactJS com NextJS.

Então eu juntei as coisas e foi isso - decidi criar o site.

Calma! Já tô criando.

Não deve ser tãoooo difícil fazer esse site - pensei, antes de perceber que eu estava muito enganado.

Brincadeiras à parte, a primeira coisa que eu fiz foi fazer o design do site no Figma.

Não me considero um UI Designer, mas tento me virar.

Primeiro eu criei um esqueleto simples dos cards de trabalho, já pensando o que ia aparecer nele, onde iam ficar, etc.

Depois, fiz o design com mais detalhes, pensando nas cores e arrumando as posições do conteúdo com mais cuidado.

Além disso, fui fazendo o esboço do site como um todo - os textos, cores etc.

O resultado ficou assim.

Ainda não estava como eu queria, mas já era um começo.

Tudo isso durou menos de 2 horas.

Eu não estava afim de perder muito tempo com o design, então fui logo para o código.

Transformando palavras em bugs

Para começar, criei o componente que seria a proposta de freela.

Para essa parte, não tinha muito segredo - fui colocando as tags do título da proposta, descrição, botão que leva para o post no Reddit, etc.

Depois de criar o código do site, implementei meu código de buscas por freelas.

Até que funcionou bem.

Na verdade, a parte mais chata foi descobrir um jeito de carregar automaticamente mais freelas - o famoso infinite scroll.

Pra mim, essa foi a parte mais complicada, tanto por que eu nunca tinha feito algo assim em React com Next quanto porque meu código inicial de buscas não foi feito pra isso.

E foi bug atrás de bug.

Também criei o esboço de um sistema de buscas por palavras chaves no posts para tentar filtrar trabalhos que me interessavam - outra coisa que não tinha no código original.

E mais bugs apareciam.

Outro problema foi que muitas vezes eu pegava mais de 100 postagens do Reddit e só duas passavam pelo filtro. Isso quando alguma passava.

Nessa brincadeira, o usuário baixava quase 100kb de dados do Reddit para ver duas ou três propostas. Não estava legal.

Foi aí que eu pensei em criar uma API.

AH, e rolou mais bugs 😷

Tentando resolver meus problemas com uma API

Criar a API foi a parte mais legal de tudo isso. Achei que seria mais complicado, mas não foi.

O NextJS permite criar uma API no mesmo projeto, simplesmente criando uma pasta chamada “api” na pasta de “pages”.

Então, criei o endereço /tag/ que retornava as postagens já filtradas e tratadas do site do Reddit. Além disso, também cacheava para futuras requisições.

Com isso, o usuário deixava de baixar 100kb de dados para algo próximo de 5kb - que podia ser mais ou menos a depender de quantas postagens a API tinha encontrado.

Com essa API, ficou mais fácil e rápido juntar e mostrar as informações pro usuário.

Ainda tentando melhorar tudo

Bom, essa foi a história de como eu criei o básico do projeto.

Se quiser dar uma olhada em como o site está, pode acessar clicando aqui.

Eu fiz tudo isso em mais ou menos 6 horas.

Na verdade, depois de terminar esse post eu ainda trabalhei mais nele - mas o básico do site foi realmente feito nesse tempo.

Como dito, ele ainda não está 100% funcional, mas eu achei divertido de fazer.

No fim das contas deu pra aprender muita coisa sobre React, NextJS, APIs, Reddit e bugs.