Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

Quadratic performance of h2.connection.H2Connection._open_streams

Đang mở
  • Có gì không ổn?
#1,184 5 bình luận 3 reaction 0 người được giao Xem trên GitHub

@kahuang đang làm issue này rồi.

Từ ngày 17/2/2019.

  • #1185 của @kahuang — đang mở

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
42/100
Loại issue
Lỗi
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
python
Lĩnh vực
networking

Hướng nghiên cứu

Bắt đầu với H2Connection._open_streams trong connection.py và đường dẫn open() của stream.py, sau đó theo dõi cách send_headers gọi kiểm tra giới hạn stream. Thay việc đếm toàn bộ stream lặp đi lặp lại bằng các cập nhật khi trạng thái thay đổi, đồng thời vẫn giữ việc dọn dẹp các stream đã đóng; benchmark các stream đồng thời để xác nhận hành vi bậc hai đã được loại bỏ.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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 :) )

Ngôn ngữ chính
Python
Star
1k
Fork
199
Không có pull request nào được merge trong 30 ngày

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của python-hyper/h2

Tất cả issue của python-hyper/h2

Issue tương tự

Thêm issue về Python

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.