Quadratic performance of h2.connection.H2Connection._open_streams

Offen
  • Stimmt etwas nicht?
#1,184 5 Kommentare 3 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

@kahuang arbeitet bereits daran.

Seit 17.2.2019.

  • #1185 von @kahuang — offen

Bewertung

Schwierigkeit
4/5
Geschätzter Aufwand
3-5 Tage
Anfängerfreundlichkeit
42/100
Issue-Typ
Bug
Klarheit
Größtenteils klar
Aktivitätsstatus
Veraltet
Tech-Stack
python
Bereich
networking

Rechercherichtung

Beginne mit H2Connection._open_streams in connection.py und dem open()-Pfad in stream.py. Verfolge anschließend, wie send_headers die Prüfung des Stream-Limits aufruft. Ersetze wiederholtes vollständiges Zählen der Streams durch Aktualisierungen bei Zustandsänderungen, wobei die Bereinigung geschlossener Streams erhalten bleibt; benchmarke gleichzeitige Streams, um zu bestätigen, dass das quadratische Verhalten beseitigt wurde.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

First let me say this is an excellent library! Thanks for taking the time to maintain/update it.

While writing an http2 client library for tornado (I can hopefully share it soon ;) ), I ran into very poor performance while benchmarking the client with many concurrently open streams (5000+). Here's a cProfile output for starting/finishing 5000 concurrent requests:

19128647 function calls (19069074 primitive calls) in 18.635 seconds
   Ordered by: internal time
11113314    4.002    0.000    4.002    0.000 stream.py:826(open)
5101    3.571    0.001    9.150    0.002 connection.py:392(_open_streams)
21279    1.580    0.000    1.580    0.000 {method 'items' of 'dict' objects}
34357    0.464    0.000    0.464    0.000 {method 'write' of '_ssl._SSLSocket' objects}
    ...

As you can see, almost half of the run time is spent in _open_streams

Here's the function code for reference:

def _open_streams(self, remainder):
      """
      A common method of counting number of open streams. Returns the number
      of streams that are open *and* that have (stream ID % 2) == remainder.
      While it iterates, also deletes any closed streams.
      """
      count = 0
      to_delete = []

      for stream_id, stream in self.streams.items():
          if stream.open and (stream_id % 2 == remainder):
              count += 1
          elif stream.closed:
              to_delete.append(stream_id)

      for stream_id in to_delete:
          stream = self.streams.pop(stream_id)
          self._closed_streams[stream_id] = stream.closed_by

      return count

The function loops through all streams, and returns the count of all open remote/local streams. As self.max_outbound_streams is called on each stream open in send_headers, the performance of this function is quadratic in the number of concurrently open streams over the lifetime of the program.

And to check the numbers, stream.py's open() is called per element in self.streams. It was called 11,113,314 times. The benchmark was run with 5000 concurrent streams, and since open() is called on opening a stream, the runtime is O(1 + 2 + ... + n) =~ (n * (n-1)) / 2 in the worst case if all streams remain open during this time. If we insert 5000 into that formula we get 12,497,500 which is within 10% of the function calls we got from the cProfile output.

Proposal: Update H2Connection to incrementally update the count of open local/remote streams, to make the function call O(1).

The logic here being that we are processing all events, so we know when we're processing the event if the stream should be closed/open, and can update counts incrementally when there is a state change. I'm not super familiar with the code base, but we should also be able to clean up closed streams on state change as well, or else make some other process for cleaning up close streams from self.streams.

I'm happy to implement the change, just let me know if this is a path you'd be willing to go down, or if there is anything that makes this infeasible (totally possible! Started using this library two days ago :) )

Vorherrschende Sprache
Python
Sterne
1k
Forks
199
Keine gemergten PRs in 30 T.

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 python-hyper/h2

Alle Issues in python-hyper/h2

Ähnliche Issues

Weitere Issues zu Python

Neue Issues direkt in Ihr Postfach

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