Improve `SequenceSet` memory use and performance

Aberta
  • Algo errado?
#484 0 comentários 0 reações 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
5/5
Tempo estimado
Mais de uma semana
Facilidade para iniciantes
25/100
Tipo de issue
Refatoração
Clareza
Precisa de esclarecimento
Status de atividade
Estagnada
Stack de tecnologia
ruby
Domínio
backend

Direção de pesquisa

Comece localizando a implementação Ruby de SequenceSet e inspecione como funcionam o armazenamento de intervalos e as operações de conjuntos. Estabeleça benchmarks para o uso de memória e o desempenho de AND/XOR em escalas realistas de caixas de correio; considera-se concluído quando as evidências dos benchmarks sustentarem qualquer complexidade resultante e as metas documentadas forem atingidas.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

performance sequence-set

SequenceSet is very useful for managing mailbox state. But I've known since first implementing it that, even though it uses binary searches for O(lg n) in many places, the current naive implementation of SequenceSet has some serious performance issues, especially at larger scales (e.g: when a set holds millions of members, which is very common for "All Mail" type mailboxes). For many scenarios, it performs worse than simply keeping a sorted array of integers (using Array#bsearch, etc).

Most notably: by storing each element as a [min, max] range/run tuple, we create a 8-byte pointer to 40-byte array for each uint32x2 run. We could easily use 1/3rd as much memory, either by storing a flat array (runs represented by flat.each_cons(2)) or two "columnar" arrays (runs represented by mins.zip(lens). And that could be cut in half by storing the uint32 values in a packed string or by merging each uint32x2 run into a single uint64 Integer—in practice this will almost always be less than UINT62_MAX and thus stored as a FIXNUM.

So we're basically using 6x more memory than needed, and that memory isn't even in a contiguous block.

And that's all before we get into more advanced tricks, for example: splitting large sets into UInt16 chunks, allowing runs to be stored as uint16x2. And once that's done, we can dynamically encode each chunk as either run length encoded, a bitset, or simple array of numbers. I've tested the encoding of real-life mailbox UID sets, and this last step provides enormous memory savings. (While working on this, I accidentally re-invented a naive version of Roaring Bitmaps... and when I started searching for prior art, I discovered roaring bitmaps!)

Additionally, I'd also like to add less naive versions of specific set operations. Most set operations are implemented as simply dup.mutating_version!(other). In my benchmarks, some fairly straightforward tricks can be employed to make AND and XOR operations 20% to 300% faster for real-world scenarios (i.e: my own production code).

And, of course, none of this should be done without good benchmarks to justify any significant jump in complexity.

  • #486
  • #485
Linguagem predominante
Ruby
Estrelas
121
Forks
47
Merge médio
19h 25min
PRs com merge (30d)
3

Preparar o ambiente

Este projeto não oferece contêiner de desenvolvimento, Dockerfile nem guia de contribuição, então a configuração fica por sua conta: comece pelo README e veja nosso guia da primeira contribuição para os passos gerais.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de ruby/net-imap

Todas as issues de ruby/net-imap

Issues semelhantes

Mais issues de Ruby

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.