Pesquisa de graduando derruba limite de busca em tabelas hash
(quantamagazine.org)- Andrew Krapivin, então graduando na Rutgers, concebeu uma nova tabela hash a partir do artigo Tiny Pointers e mostrou que é possível superar o que era visto como um limite de desempenho para busca e inserção
- Em um artigo de janeiro de 2025, Krapivin, Martín Farach-Colton e William Kuszmaul refutaram a conjectura de 40 anos de Yao sobre uma determinada categoria de tabelas hash
- A conjectura existente sustentava que, para x, que representa o quão cheia a tabela está, o pior tempo de busca/inserção não poderia ser melhor que x, mas a nova estrutura alcança tempo proporcional a (log x)²
- Os pesquisadores também mostraram que (log x)² é um limite ótimo que não pode ser reduzido nessa popular categoria de tabelas hash tratada por Yao, e que em tabelas hash não gananciosas o tempo médio de busca pode chegar a uma constante independente de x
- Mesmo que não leve a aplicações imediatas, o trabalho fornece uma base teórica que reorganiza os limites de desempenho da antiga estrutura de dados tabela hash e abre caminho para melhorias práticas futuras
Uma nova tabela hash que começou com Tiny Pointers
- Andrew Krapivin conheceu o artigo Tiny Pointers no outono de 2021, quando era graduando na Rutgers University, e dois anos depois, ao lê-lo com mais atenção, teve a ideia de como criar ponteiros menores
- Como era necessário organizar melhor os dados apontados pelos ponteiros, a tabela hash, um método comum de armazenamento de dados, virou objeto da pesquisa
- Durante os experimentos, Krapivin criou uma nova tabela hash que não depende de sondagem uniforme (uniform probing) e percebeu que o tempo e o número de etapas para encontrar um elemento específico eram menores do que o esperado
- Martín Farach-Colton inicialmente desconfiou do projeto, mas William Kuszmaul concluiu que a estrutura de Krapivin não era apenas uma tabela hash interessante, e sim um resultado que derrubava uma conjectura de 40 anos
O problema dos limites de desempenho das tabelas hash
- Tabelas hash são estruturas de dados para armazenar e acessar informações e, em essência, dão suporte a três operações
- Buscar (query) um elemento
- Excluir um elemento
- Inserir um elemento em um slot vazio
- As primeiras tabelas hash remontam ao início dos anos 1950, e desde então essa antiga estrutura de dados segue sendo estudada e usada na ciência da computação
- O limite de velocidade de buscas ou inserções costuma estar ligado ao tempo necessário para encontrar um espaço vazio na tabela hash
- O quão cheia a tabela hash está pode ser expresso como uma proporção total, mas os pesquisadores usam o valor x ao tratar de tabelas quase cheias
- Se x for 100, a tabela está 99% cheia
- Se x for 1.000, a tabela está 99,9% cheia
- Em certas tabelas hash gerais, sabia-se que o tempo esperado da pior inserção, como colocar um elemento no último espaço vazio restante, era proporcional a x
A conjectura de Yao de 1985 e sua refutação
- Em um artigo de 1985, Andrew Yao considerou que, em tabelas hash com certas propriedades, a melhor forma de encontrar um elemento individual ou um espaço vazio seria a sondagem uniforme, que percorre aleatoriamente as posições possíveis
- No pior caso, isto é, ao procurar o último espaço vazio restante, a conjectura de que não seria possível fazer melhor que x foi amplamente aceita como verdadeira por 40 anos
- Sem conhecer a conjectura de Yao, Krapivin deu continuidade à investigação relacionada a Tiny Pointers e criou uma nova tabela hash que não depende de sondagem uniforme
- O artigo de janeiro de 2025 de Krapivin, Farach-Colton e Kuszmaul mostra que, nessa nova tabela hash, o pior tempo de busca e inserção é proporcional a (log x)²
- O resultado entra em conflito direto com a conjectura de Yao, e os pesquisadores também provaram que (log x)² é um limite ótimo que não pode ser reduzido na popular categoria de tabelas hash tratada por Yao
Um resultado ainda mais surpreendente sobre tempo médio de busca
- Em 1985, Yao tratou não apenas do pior tempo de busca, mas também do tempo médio considerando todas as buscas possíveis
- Ele provou que, em tabelas hash com certas propriedades, especialmente tabelas hash gananciosas (greedy), nas quais novos elementos devem ser colocados na primeira posição possível, o tempo médio não pode ser melhor que log x
- Farach-Colton, Krapivin e Kuszmaul quiseram verificar se o mesmo limite se aplicava também a tabelas hash não gananciosas, e mostraram por meio de um contraexemplo que isso não é verdade
- Nessa tabela hash não gananciosa usada como contraexemplo, o tempo médio de busca é muito melhor que log x e, na prática, não depende de x de forma alguma
- O fato de ser possível alcançar tempo médio de busca constante independentemente do quão cheia a tabela hash esteja foi um resultado inesperado até para os próprios pesquisadores
Atualização teórica de uma antiga estrutura de dados
- Alex Conway avaliou que a tabela hash, embora seja uma das estruturas de dados mais antigas, continua sendo uma das formas mais eficientes de armazenar dados
- Guy Blelloch considerou o resultado belo por lidar com um problema clássico e resolvê-lo
- Sepehr Assadi avaliou que os pesquisadores não apenas refutaram a conjectura de Yao, mas também encontraram a melhor resposta para a pergunta dele
- Conway considera importante compreender melhor esse tipo de estrutura de dados, mesmo que o resultado não leve a aplicações imediatas
- Ao reorganizar os limites teóricos das tabelas hash, este resultado cria uma base que pode mais tarde levar a melhorias reais de desempenho
1 comentários
Opiniões no Hacker News
Acho que Krapivin chegou a esse avanço porque não conhecia a conjectura de Yao, e que o desenvolvedor de Balatro também criou um jogo premiado porque não conhecia muito bem os deck builders existentes
Fico pensando se a melhor forma de abordar um problema talvez seja não conhecer, ou ignorar, a maioria das tentativas semelhantes anteriores
O mundo hoje é tão conectado que ficou raro ver uma originalidade que não caia nos modelos mentais de quem veio antes; a internet é ótima, mas é uma pena que ela também homogeneíze o pensamento
Na maioria das vezes, ignorar sucessos do passado faz você voltar a semear um terreno que já era infértil
Se você lê os trabalhos anteriores cedo demais, fica preso à forma de pensar existente; se não lê nada, perde coisas importantes que não teria pensado sozinho
Mesmo que sua abordagem seja pior do que o estado da arte, a comparação pode render insights importantes sobre por que a abordagem de ponta é melhor
Segundo uma citação direta do desenvolvedor, a maior influência em Balatro foi Luck be a Landlord; depois de ver alguns vídeos do Northernlion jogando, ele gostou da ideia de um roguelike de ataque de pontuação com tema não fantástico e transformou o jogo de cartas que estava fazendo na época em um roguelike
A partir desse ponto, ele se distanciou intencionalmente do gênero e disse que queria explorar o espaço de design de forma ingênua, cometendo seus próprios erros
Ele ouve muitas comparações com Slay the Spire, mas, quando estava projetando Balatro, nunca tinha jogado nem visto vídeos desse jogo, e só foi conhecê-lo muito mais tarde
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
“Mas eu jamais teria conseguido sem a ajuda de todos”, retrucou [Milo]
“Talvez.” Reason falou solenemente. “Mas você teve a coragem de tentar, e o que você consegue fazer geralmente depende do que você se dispõe a fazer.”
King Azaz disse: “Por isso havia uma coisa muito importante sobre a sua aventura que não podíamos contar antes de você voltar.”
“Eu me lembro”, disse Milo, ansioso. “Agora me contem.”
“Era impossível”, disse o rei, olhando para o Mathemagician
“Completamente impossível”, disse o Mathemagician, olhando para o rei
“Então….” disse o inseto, ficando subitamente tonto
“Sim, exatamente”, disseram os dois juntos. “Mas, se tivéssemos lhe contado na época, talvez você não tivesse ido… e, como você descobriu, muitas coisas são possíveis desde que você não saiba que são impossíveis.”
— The Phantom Tollbooth (1961)
Por vários motivos, acabei reprovando nessa disciplina e a fiz de novo, e percebi um hábito dele
Em todo semestre, em uma das listas de exercícios da segunda metade do curso, entre cerca de 30 problemas, ele incluía um que na verdade era um problema em aberto e, um ou dois dias antes do prazo, enviava uma versão corrigida dizendo “ah, foi um engano”
Como isso sempre acontecia exatamente uma vez, não acho que fosse coincidência
O link do vídeo [1] enviado por monort [0] ajudou bastante
É um resumo rápido com base em ter assistido ao vídeo uma vez; o nome é Funnel Hashing
A ideia é dividir um array em subarrays exponencialmente menores. O primeiro bloco é n/m, o segundo vai diminuindo como n/(m^2), até chegar a um único elemento. Chamando-os de A0, A1 etc., |A0| = n/m, |A1| = n/(m^2), e há um total de k etapas
Tenta-se inserir c vezes em A0 e, se falhar, tenta-se c vezes em A1. Se isso também falhar, desce-se pelo “funil” até encontrar um slot vazio
\delta é chamado de proporção de slots vazios, mas não sei bem se esse valor é um parâmetro definido na criação da tabela hash ou um valor atualizado dinamicamente. Se definirmos c = log(1/d), k = log(1/d), a complexidade de tempo no pior caso fica O(log^2(1/d))
Entendi que esse método contorna o resultado de Yao por não ser guloso. O resultado de Yao vale para políticas gulosas de inserção e busca, e o método acima não é guloso porque desce em cadeia pelo funil
Deve haver muitos detalhes complicados, mas a ideia que entendi é mais ou menos essa. Se eu estiver completamente enganado, seria bom me avisarem
Lembra bastante a ideia de “Distinct Elements in Streams”, de Chakraborty, Vinodchandran e Meel [2]
[0] https://news.ycombinator.com/item?id=43007860
[1] https://www.youtube.com/watch?v=ArQNyOU1hyE
[2] https://arxiv.org/pdf/2301.10191
Funnel Hashing é “guloso” e quebra a conjectura de Yao sobre mecanismos de hash gulosos
Elastic Hashing é “não guloso” e oferece tempo amortizado melhor que algoritmos gulosos
Não sei se o artigo está errado ou se a compreensão do paper está equivocada, mas fico curioso se o autor do artigo apontou algo que não sabe
Parece ter relação com o “estágio final especial para capturar algumas chaves” por volta de 14:41 no vídeo, mas, se isso também tiver de ter tamanho fixo, pode encher. O que se faz nesse caso?
[propaganda descarada]: se você se interessa por tabelas hash, vale dar uma olhada também no Dandelion Hashtable [0]
Usamos no nosso banco de dados de próxima geração, foi apresentado no HPDC'24 e atualmente é a tabela hash em memória mais rápida em uso real
Ele melhora o endereçamento fechado com encadeamento limitado a linhas de cache e processa mais de 1 bilhão de requisições em memória por segundo em servidores comuns
[0] https://dandelion-datastore.com/#dlht
Apresentação do inventor: https://www.youtube.com/watch?v=ArQNyOU1hyE
Parece um daqueles macetes de gestão de recursos que você usa quando está espremido por restrições e com poucos recursos
Dividir por prioridade é uma abordagem comum em alocação de recursos, e isto é uma variação disso
Fico imaginando quantos outros “macetes de trincheira” que as pessoas já usavam na prática, e que nem o próprio inventor sabia que eram importantes, poderiam derrubar algo amplamente aceito. Algo como “quando tenho muitas entregas, descobri um jeito esperto de traçar normalmente a rota mais rápida...”
Claro que reconhecer isso, formalizar, trabalhar e publicar como paper exige muito esforço. Não quero diminuir esse mérito
Acho que papers simplesmente deveriam incluir uma apresentação em vídeo
Ainda assim, essa abordagem também aloca mais memória por meio de arrays auxiliares, então me parece um pouco estranho em que ela é melhor do que simplesmente fazer superalocação para reduzir a chance de colisões de chaves e tornar o pior caso menos ruim
Ao passar os olhos pelo paper [1], a diferença central parece ser que o algoritmo de inserção na tabela hash não preenche gulosamente o primeiro slot vazio encontrado, mas procura mais adiante
Combinado a uma ordem de sondagem inteligente, ele prova que consegue encontrar slots vazios com eficiência mesmo quando a tabela está muito cheia
Ou seja, as inserções ficam mais lentas quando a tabela está menos cheia, mas evitam a pior situação de procurar sem saber onde estão os últimos poucos slots vazios restantes
[1]: https://arxiv.org/pdf/2501.02305
É um resultado teórico interessante, mas, na prática, imagino que o “macete” atual de alocar uma tabela maior do que o necessário seja uma solução melhor
Por exemplo, o hashbrown do Rust deixa intencionalmente 1/8 da tabela, ou 12,5%, vazio; isso usa um pouco mais de memória, mas torna inserções e consultas muito rápidas com alta probabilidade
Esse método aumenta o número médio de posições sondadas mesmo quando a tabela está menos cheia
Ainda assim, dentro dessa estratégia, o item é colocado no primeiro slot vazio encontrado
“Pular slots” tem a ver com saltar para frente na ordem do hash
Alguém tem uma implementação simples de ‘Tiny pointers’? Meu cérebro prefere ver código ou pseudocódigo antes de provas
Legal. Sempre me perguntei se haveria um jeito de conteinerizar tabelas desse tipo
Uma tabela comum parece um navio graneleiro em que se enfia tudo de qualquer jeito. Se desse para organizá-la melhor, como um porta-contêineres, acho que daria para carregar muito mais coisa com mais eficiência e também descarregar mais rápido
Converta as linhas da tabela para algo como uma string ou JSON e aplique base16 a essa variável; isso vira a string base16 desses dados
Crie uma tabela hash e defina um valor de chave para essa string base16, e você terá um contêiner com os dados
Agora é só decodificar a string hexadecimal para obter os dados em base32
As propriedades teóricas das tabelas hash sempre foram impressionantes, quase mágicas, e este resultado as amplia ainda mais
O que me parecia estranho era como tabelas hash podiam ser tão melhores do que árvores, que intuitivamente pareciam a forma mais eficiente de armazenar dados
O que percebi é que a teoria de tabelas hash lida com um conjunto de objetos de tamanho fixo. Para esse conjunto fixo, cria-se uma função hash e ela é usada como um índice de vetor para armazenar em um vetor pré-alocado. Daí sai a receita para inserção, remoção e consulta em algo próximo de O(1). Já várias estruturas de árvore não assumem um tamanho específico
O problema é que é preciso definir o tamanho antecipadamente e, quando o vetor fica quase cheio, processos como inserção podem ficar lentos
Pelo que vi rapidamente no artigo, este resultado parece resolver essa parte que fica lenta e permitir inserções rápidas mesmo em tabelas quase cheias
É interessante e engenhoso, mas não acho que seja um grande avanço prático. Na prática, em vez de se preocupar com uma forma inteligente de preencher a tabela, basta aumentar o tamanho assumido
Estou escrevendo para checar se entendi corretamente; se estiver errado, podem me corrigir
Na inserção em que ocorre o redimensionamento, há um custo muito maior, linear no tamanho da tabela, mas esse tempo é amortizado por todas as inserções já realizadas
Se você aumenta a tabela o suficiente sempre que ela começa a ficar cheia demais, isso acontece com frequência cada vez menor, então na média continua sendo tempo constante
No mundo funcional, árvores provavelmente continuam sendo mais adequadas
Não tive tempo de entender o paper por completo, mas eles afirmam que, com esse método, as inserções são consistentemente rápidas. Entendo até 75% da capacidade total, mas não sei se há outro modo quando todas as linhas chegam a 75%
Eles também afirmam que as consultas são rápidas, mas não li o suficiente para entender como a consulta funciona ou por que é rápida
Há muitas situações em que seria muito bom uma tabela hash quase cheia ainda funcionar bem. Nem sempre dá para redimensionar durante a execução de um programa, e em alguns ambientes a memória é extremamente importante
Ainda assim, gostaria de ver a implementação e mexer nela eu mesmo. Não tenho certeza se, no caso geral, isso “vale a pena”
A eficiência de cache provavelmente também não é boa. Isso vale para a maioria das tabelas hash, embora uma exceção seja ler com sondagem linear em uma tabela bem cheia, em que dá para buscar e verificar dados contíguos na memória
Ainda não está claro se isso tem valor do ponto de vista de desempenho, mas é uma nova ideia interessante e quero entendê-la completamente
Não entendi a parte que diz que “nessa nova tabela hash, o tempo necessário para a pior consulta e inserção é proporcional a (log x)2, muito mais rápido que x”, mas também que “o resultado da equipe pode não levar a aplicações imediatas”
Por que não levaria a aplicações imediatas? Quer dizer que, por meio de uma análise de casos de uso reais, é possível ajustar melhor a implementação de hash do que com uma abordagem puramente matemática?
Em alguns casos, o conjunto de dados precisa ser irrealisticamente grande para que se veja ganho de velocidade
Assim, x não passa de 4; portanto, melhorar O(x) para O((log x)^2) não significa muito quando x é tão pequeno
Em algumas aplicações especiais com restrição de memória, x seria maior, mas pessoalmente nunca encontrei esse caso
Sempre que precisei de uma taxa de ocupação muito alta, por exemplo acima de 90%, cuckoo hashing foi suficiente; em 70% a 80% ou menos, a sondagem linear era muito rápida e boa o bastante
O novo resultado também tem o custo de tornar mais lentas as inserções do “caso bom”
Não vejo no paper nada que vá impactar a prática
Este resultado parece importante apenas quando a tabela hash está quase cheia
Então não bastaria dimensionar a tabela 10% maior ou, se o redimensionamento for possível, fazer o resize mais cedo?
Quando a probabilidade de colisões de hash fica alta demais, elas se redimensionam sozinhas
Se a tabela fica cheia demais, simplesmente aloca-se o dobro da memória, ou algum múltiplo fixo, e copiam-se os itens existentes
A maioria das tabelas com sondagem não linear, como cuckoo hashing, é prejudicada pelo fato de a RAM não ser nem um pouco “aleatória”
Alguém conhece um repositório no GitHub com esta implementação?