A falha no trecho de código mais copiado da história do Stack Overflow (2019)

 (programming.guide)
3 pontos por GN⁺ 2023-09-28 | 1 comentários | Compartilhar no WhatsApp
  • A resposta em Java humanReadableByteCount, escrita em 2010, foi identificada em um estudo de 2018 como o trecho de código do Stack Overflow mais copiado, mas produzia resultados incorretos em valores de fronteira na formatação de tamanhos em bytes
  • Esse código usava o fato de que prefixos como kB, MB e GB são potências de 1000 ou 1024 e, em vez de um loop, escolhia a unidade por meio de cálculo logarítmico
  • O bug principal era um problema de limite de arredondamento em que 999,999 bytes era exibido como "1000.0 kB" no modo SI, embora pela especificação, se a parte numérica deve ficar entre 1 e 999.9, o correto fosse "1.0 MB"
  • Em valores maiores, somava-se ainda a limitação de precisão de ponto flutuante do double, fazendo com que a entrada 999,949,999,999,999,999 aparecesse como 1000.0 PB; a correção exigiu cálculo de limiar, redução de escala, ajuste de padrão de bits e strictfp
  • O código final passou a tratar números negativos e até Long.MIN_VALUE, mas perdeu a simplicidade original, e copiar código do Stack Overflow exige testes de casos extremos e atribuição de origem

A simplificação que a resposta de 2010 buscava

  • O problema era formatar uma quantidade de bytes em uma string legível para humanos
    • Ex.: 123,456,789 bytes exibido como "123.5 MB"
    • A especificação implícita era que a parte numérica da string resultante ficasse entre 1 e 999.9, com o sufixo de tamanho apropriado
  • A resposta anterior usava uma abordagem baseada em loop, percorrendo EB, PB, TB, GB, MB, kB e B da maior para a menor unidade e escolhendo a primeira menor que a quantidade de bytes
  • A nova resposta usava Math.log e Math.pow para reduzir loops e ramificações
    • No modo SI, a unidade é 1000
    • Na notação binária, a unidade é 1024
    • O valor exp = log(bytes) / log(unit) era convertido em inteiro e usado como índice do prefixo
    • Os prefixos eram "kMGTPE" em SI e "KMGTPE" em binário, adicionando "i" no caso binário

A cópia em massa e o episódio do OpenJDK

  • O artigo de Sebastian Baltes Usage and Attribution of Stack Overflow Code Snippets in GitHub Projects analisa como trechos de código do Stack Overflow são usados em projetos no GitHub e como a origem é atribuída
  • O método de análise consistia em extrair trechos de código do dump de dados do Stack Overflow e compará-los com código em repositórios públicos do GitHub
    • A pergunta central era se a atribuição exigida pela licença CC BY-SA 3.0 do Stack Overflow estava sendo respeitada
    • No fim, a maioria dos usuários não incluía a atribuição adequada
  • A resposta de ID 3758880 aparecia no topo da tabela do artigo, com centenas de milhares de visualizações e mais de 1.000 upvotes na época
  • Ao buscar humanReadableByteCount no GitHub, aparecem milhares de usos, e em um repositório local isso pode ser verificado com o comando a seguir
git grep humanReadableByteCount
  • Um caso correspondente também foi encontrado no repositório do OpenJDK
    • O código não tinha atribuição de origem, e a licença do OpenJDK não era compatível com a CC BY-SA 3.0
    • Sebastian Baltes perguntou na lista de discussão de desenvolvimento do OpenJDK se o código havia sido copiado do Stack Overflow para o OpenJDK, ou o contrário
    • O autor da resposta ainda não trabalhava na Oracle antes de aquele commit ser mesclado e também não contribuiu para esse patch
    • Depois disso, uma issue foi registrada e o código foi removido

O primeiro bug: valores de fronteira com 999 em sequência

  • Os problemas que pareciam suspeitos à primeira vista não eram a causa real
    • O valor máximo de long é 2^63 - 1, cerca de 9.2 × 10^18, então ele não chega a passar da unidade EB
    • Quando bytes < unit, o primeiro if trata o caso, então exp não vira 0 a ponto de fazer charAt(exp - 1) falhar
  • O problema real era o limite de arredondamento
    • A entrada 999,999 bytes virava "1000.0 kB" no modo SI
    • Pela especificação de que a parte numérica deve ficar entre 1 e 999.9, o resultado correto é "1.0 MB"
  • Na data em que o texto foi escrito, todas as 22 respostas publicadas, incluindo as que usavam Apache Commons e bibliotecas do Android, tinham esse bug ou alguma variação dele
  • A chave da correção era o limiar que determina quando o expoente exp deve subir para a próxima unidade
    • O ponto de troca de k para M é quando o valor fica mais próximo de 1 MB do que de 999.9 k, isto é, 999,950
    • O ponto de troca de M para G é 999,950,000
    • No modo binário, como o limiar não é inteiro, é preciso usar ceil
if (bytes >= Math.ceil(Math.pow(unit, exp) * (unit - 0.05)))
    exp++;

O segundo bug: o limite de precisão do double

  • Mesmo com a correção acima, a entrada 999,949,999,999,999,999 era exibida como 1000.0 PB, quando o correto seria 999.9 PB
  • A causa não era a fórmula em si, mas o limite de precisão do double
    • Na representação IEEE 754, valores de ponto flutuante próximos de 0 são densos, mas valores grandes ficam muito espaçados
    • Em um double muito grande, até subtrair Long.MAX_VALUE pode não alterar o valor
double a = Double.MAX_VALUE;
double b = a - Long.MAX_VALUE;
System.err.println(a == b); // prints true
  • O cálculo problemático aparecia em dois pontos
    • Na divisão feita no argumento de String.format
    • No cálculo do limiar que decide se exp deve subir
  • O primeiro problema foi tratado reduzindo o valor intermediário de bytes para uma faixa com melhor precisão e ajustando exp
    • A ideia era que, como o resultado final de qualquer forma seria arredondado, os dígitos menos significativos poderiam ser descartados
if (exp > 4) {
    bytes /= unit;
    exp--;
}
  • No segundo problema, os bits menos significativos importavam
    • 999,949,99…9 e 999,950,00…0 precisavam ser classificados com expoentes diferentes
    • Havia 12 limiares possíveis, somando SI e binário, e apenas um deles produzia resultado incorreto
    • O erro foi identificado e corrigido por meio de um padrão de bits terminando em D00
    • Como a correção dependia do padrão de bits de um resultado específico em ponto flutuante, foi usado strictfp

Entradas negativas e o código final

  • Como o Java não tem long sem sinal, também foi adicionado tratamento para quantidades negativas de bytes
    • Antes, a entrada -10,000 era exibida como -10000 B
    • Foi introduzido absBytes, e os cálculos ligados a exp passaram a ser feitos com base no valor absoluto
  • Long.MIN_VALUE exigia tratamento especial
    • Porque -Long.MIN_VALUE == Long.MIN_VALUE
    • Portanto, quando bytes == Long.MIN_VALUE, usa-se Long.MAX_VALUE; nos demais casos, Math.abs(bytes)
  • A versão final incluía strictfp, correção de limiar, tratamento de Long.MIN_VALUE e redução de escala em expoentes grandes
  • O código que pretendia evitar loops e ramificações excessivas acabou, após tratar todos os corner cases, ficando mais difícil de ler do que a versão original
  • Para um código moderno com qualidade de produção, há outro texto: Formatting byte size to human readable format

Lições práticas que ficam

  • Trechos de código do Stack Overflow podem ter bugs, mesmo com milhares de upvotes
  • Código copiado precisa especialmente de testes de casos extremos
  • Aritmética de ponto flutuante é difícil de lidar em valores de fronteira e números grandes
  • Ao copiar código, é necessário fazer a atribuição de origem adequada; caso contrário, isso pode se tornar um problema real

Leituras relacionadas

1 comentários

 
GN⁺ 2023-09-28
Comentários do Hacker News

  • É interessante que tanto as respostas com valores hardcoded quanto as que usam if (ou while) façam no máximo 5 comparações.
    Se as unidades forem apenas B, KiB, MiB, GiB, TiB e EiB, dá para resolver com no máximo 3 instruções if. Ao verificar se é GiB ou maior, você já sabe que não é B/KiB/MiB, então a busca binária vence.
    Mesmo estendendo até ZiB e YiB, no máximo 3 comparações bastam, enquanto a abordagem hardcoded chega a até 7. Se eu fosse escrever isso, não usaria log/pow/ponto flutuante porque a chance de erro é grande demais; provavelmente hardcodaria os if, mas usando busca binária.

    • A abordagem de busca binária pode ser mais lenta do que simplesmente fazer 6 verificações. Nesta última, há boa chance de seguir apenas uma ramificação, e ramificações são muito lentas, então é melhor manter o código o mais linear possível.
    • Depende da distribuição das entradas. Se valores pequenos forem muito comuns, uma busca linear pode ser melhor.
    • Vejo isso como um péssimo julgamento de engenharia. Uma solução simples é fácil para colegas revisarem, deixa as condições de contorno claramente visíveis e facilita verificar se os testes as cobrem.
      Com esse tipo de código, você está trabalhando muito para escrever um código mais lento, mais complexo e também mais difícil de testar e revisar.

  • (2019) Discussões anteriores:
    https://news.ycombinator.com/item?id=21693431
    https://news.ycombinator.com/item?id=21698619
    https://news.ycombinator.com/item?id=27533684

  • Não entendo. Se há 7 sufixos, basta escolher o correto com busca binária, e 3 comparações são suficientes. Ou, mantendo tudo simples, são só 6 comparações.
    Não vejo por que usar log() duas vezes, pow() uma vez e ceil() seria melhor do que a abordagem simples. O bug descrito aqui é um exemplo perfeito de algo que surgiu por tentar ser esperto demais.

    • Parece que o autor reconheceu que a legibilidade era ruim e voltou para uma abordagem com loop: https://programming.guide/java/formatting-byte-size-to-human...
      Ainda assim, por levar em conta o bug de arredondamento, é um pouco melhor do que o primeiro exemplo de código do texto original.
    • O próprio autor também diz no início que isso, na prática, não é melhor do que um loop.
      Além disso, 6 comparações só ocorre no valor máximo, e isso parece improvável no uso real. Se a maioria dos valores estiver na faixa de B ou KB, a abordagem linear pode ser melhor.

  • É uma divulgação descarada, mas, em vez de copiar do S/O, para formatar tamanhos de forma rápida e correta em um formato legível por humanos, você também pode usar nossa biblioteca open source PrettySize. Há uma versão para Rust [0] e outra para .NET [1], e ela também torna operações lógicas type-safe sobre tamanhos de arquivo seguras e fáceis.
    O trecho do S/O tem 4 linhas, mas essas bibliotecas são muito mais abrangentes e incluem testes, opções de formato de saída, conversões de tamanho etc.
    [0]: https://github.com/neosmart/prettysize-rs
    [1]: https://github.com/neosmart/PrettySize.net

    • A cultura de substituir uma solução de 4 linhas por uma biblioteca enorme foi o que gerou o left-pad.

  • É uma curiosidade genuína: há muitos desenvolvedores que simplesmente copiam código não confiável do Stack Overflow e colam em aplicações?
    A ideia de que as pessoas simplesmente copiam do Stack Overflow é famosa, mas eu achava que era mais uma piada até ver alguém fazendo isso de fato. Eu também uso o Stack Overflow como ponto de partida quando estou resolvendo um problema em uma área com a qual não tenho familiaridade, mas nunca copiei código literalmente
    Normalmente, um trecho de código não faz exatamente só aquilo de que preciso, então preciso olhar a API e construir minha própria solução com base na abordagem explicada. Especialmente em Python, o Stack Overflow muitas vezes me apontou na direção de APIs de nicho úteis

    • Já trabalhei com um desenvolvedor que, no instante em que via uma resposta, ninguém conseguia impedi-lo de copiar o código. Ele nem lia a pergunta para verificar se era o mesmo problema que estava enfrentando, e também não lia a resposta
      Era literalmente Google → clicar no primeiro link do Stack Overflow que aparecia → copiar/colar o primeiro bloco de código que aparecia; às vezes, até a linguagem era outra. Durante programação em par, eu tinha que tomar fisicamente o dispositivo de entrada dele. Se eu dissesse que estava errado, antes mesmo de eu terminar a frase ele já estava colando o segundo trecho de código da página, e era estranhamente rápido
      É um caso extremo, mas há muitos desenvolvedores com a mentalidade “preciso de código; há código no Stack Overflow; resolvido!”, sem pensar nem um pouco se é uma solução adequada
    • Isso acontece de verdade, e quanto mais algo parece estar fora do escopo da parte do programa que me interessa, mais frequentemente acontece
      De qualquer forma, estamos sempre usando código de bibliotecas feito por estranhos para partes de encanamento com as quais não nos importamos muito. Se eu quiser me aprofundar e entender, provavelmente vou escrever eu mesmo; mas, se nessa parte eu só quero que “funcione” para continuar o projeto, vira desenvolvimento guiado por erros do compilador
    • Pelos motivos que o autor menciona, quase nunca copio/colo literalmente. Em vez disso, tento entender a solução e, se necessário, copio à mão linha por linha até entender direito, para então refatorar a partir dali
      Também mudo os nomes das variáveis. Muitas vezes há foo, bar, baz demais, dificultando a leitura por humanos. Se eu reencontrar o mesmo problema, também é mais fácil lembrar o que fiz do que se tivesse copiado às cegas
    • As pessoas realmente fazem isso. Depois de ver uma quantidade absurda de código e configurações TLS incorretos do Stack Overflow, fiquei bastante convencido de que a maioria dos sistemas roda sem validar certificados corretamente
    • Talvez você ainda não tenha tido o prazer de trabalhar em uma base de código criada por jovens de 23 anos tomando Adderall

  • Não entendo por que usar logaritmo em ponto flutuante quando se precisa de log 2
    Se não estou deixando nada passar, a expressão abaixo dá exatamente floor(log2(value)) para positivos menores que 2^63 bytes e é muito mais rápida:
    Long.bitCount( (Long.highestOneBit(value) << 1) - 1) - 1

    • As unidades “normais” são potências de 10, então esse método não está correto

  • Assim que vi o trecho de código, apareceram uma operação log em ponto flutuante e uma divisão sobre inteiros; considerei imediatamente, na minha cabeça, que era um código esperto demais e, por natureza, propenso a bugs, então descartei

    • Esse é basicamente o ponto do texto

  • A cadeia do conhecimento vai até o fundo. Mostra como é difícil guardar de volta até mesmo um conhecimento minúsculo depois que ele é tirado
    Com o Stack Exchange perdendo rapidamente contribuidores ativos, fico me perguntando o que será necessário para corrigir respostas de gatilho rápido que depois se mostram desviadas. E também o que significará para nosso conhecimento coletivo quando essas respostas “ligeiramente erradas” ficarem cada vez mais cristalizadas no histórico de buscas e, cada vez mais, na história dos LLMs

  • Isso me lembra o treinamento militar básico. Os instrutores às vezes davam aos recrutas, de propósito, uma tarefa que ninguém sabia fazer, sem instruções, e iam embora
    Aí alguém sempre começava do jeito errado, e todos os demais seguiam essa pessoa

    • Fico me perguntando se isso é agravado pela tendência humana de não querer parecer pior que os outros. Isso pode levar até pessoas inteligentes a resultados tolos, seguindo ideias ruins ou apressadas
      Algo parecido acontece em previsões econômicas públicas. Quem erra sozinho quando os outros acertam é tratado com muito mais dureza do que quem erra junto com todo mundo
    • Qual era o objetivo desse treinamento?

  • Eu não necessariamente consideraria erros de ponto flutuante como “defeitos” nesse tipo de algoritmo. Se o código define uma solução lógica e matematicamente correta, então, em si, eu o considero “certo”
    Lidar com erros de ponto flutuante é um nível acima disso, e só é feito quando realmente importa. Posso imaginar uma linguagem de programação futura perfeita em que erros de ponto flutuante não existam e nem precisem ser considerados; 99% dos meus algoritmos, de certa forma, têm essa linguagem como alvo