Improve `SequenceSet` memory use and performance

Offen
  • Stimmt etwas nicht?
#484 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
25/100
Issue-Typ
Refactoring
Klarheit
Muss geklärt werden
Aktivitätsstatus
Veraltet
Tech-Stack
ruby
Bereich
backend

Rechercherichtung

Beginne damit, die Ruby-Implementierung von SequenceSet zu finden und zu untersuchen, wie ihre Bereichsspeicherung und Mengenoperationen funktionieren. Erstelle Benchmarks für den Speicherverbrauch sowie die AND/XOR-Leistung bei realistischen Mailbox-Größen; als erledigt gilt die Aufgabe, wenn Benchmark-Ergebnisse jede daraus resultierende Komplexität stützen und die dokumentierten Ziele erreicht sind.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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
Vorherrschende Sprache
Ruby
Sterne
121
Forks
47
Ø Merge
19 Std. 25 Min.
Gemergte PRs (30 T.)
3

Entwicklungsumgebung

Dieses Projekt bietet weder Dev-Container noch Dockerfile noch Beitragsleitfaden – die Einrichtung liegt bei Ihnen. Beginnen Sie mit der README; die allgemeinen Schritte stehen in unserem Leitfaden für den ersten Beitrag.

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus ruby/net-imap

Alle Issues in ruby/net-imap

Ähnliche Issues

Weitere Issues zu Ruby

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.