After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 640518 - GMainLoop has quadratic complexity when all pollfd's have the same priority
GMainLoop has quadratic complexity when all pollfd's have the same priority
Status: RESOLVED FIXED
Product: glib
Classification: Platform
Component: mainloop
unspecified
Other Linux
: Normal normal
: ---
Assigned To: gtkdev
gtkdev
Depends on:
Blocks:
 
 
Reported: 2011-01-25 10:39 UTC by Paolo Bonzini
Modified: 2011-06-04 04:06 UTC
See Also:
GNOME target: ---
GNOME version: ---

Attachments
patch to convert to doubly-linked list (2.91 KB, patch)
2011-01-25 10:49 UTC, Paolo Bonzini 		committed Details | Review
avoid quadratic behavior of GMainLoop when all fd's have the same priority (2.96 KB, patch)
2011-06-04 04:06 UTC, Matthias Clasen 		committed Details | Review

Description Paolo Bonzini 2011-01-25 10:39:34 UTC 
The worst-case cannot really be avoided, but the attached patch makes the common operations O(1) in the simple case of all pollfd's having the same priority.
Comment 1 Paolo Bonzini 2011-01-25 10:49:13 UTC 
Created attachment 179277 [details] [review]
patch to convert to doubly-linked list
Comment 2 Matthias Clasen 2011-01-29 02:07:34 UTC 
Lets hold this until 2.29, at this point
Comment 3 Matthias Clasen 2011-06-04 04:06:27 UTC 
The following fix has been pushed:
c5d9a46 avoid quadratic behavior of GMainLoop when all fd's have the same priority
Comment 4 Matthias Clasen 2011-06-04 04:06:33 UTC 
Created attachment 189199 [details] [review]
avoid quadratic behavior of GMainLoop when all fd's have the same priority