GNOME Bugzilla – Bug 594650
Implement constant-time interface lookups
Last modified: 2009-12-01 09:22:05 UTC
Created attachment 142793 [details] [review] O(1) interface lookups Currently interface lookups are do a binary search over all the interfaces an object implements. Its possible to do this lookup in constant time using for instance the gcj algorighm described at: http://gcc.gnu.org/ml/java/1999-q3/msg00377.html I'm attaching a patch that uses some infrastructure from bug 594525 to implement this.
Running the test from bug 594525, here's the results. Numers are: - row 1: git master - row 2: patch from bug 594525 - row 3: patches from both bug 594525 and above Running the test single-threaded without g_type_init(): Running test "liststore-is-a" 2175 runs, min/avg/max = 0.818/0.916/4.115 ms 2542 runs, min/avg/max = 0.718/0.783/1.538 ms 3393 runs, min/avg/max = 0.560/0.586/3.736 ms Running test "liststore-interface-peek" 4169 runs, min/avg/max = 0.474/0.476/1.286 ms 4702 runs, min/avg/max = 0.396/0.422/7.459 ms 5068 runs, min/avg/max = 0.387/0.391/3.038 ms Running test "liststore-interface-peek-same" 5019 runs, min/avg/max = 0.372/0.395/0.487 ms 5790 runs, min/avg/max = 0.337/0.342/1.742 ms 5017 runs, min/avg/max = 0.387/0.395/2.378 ms For one thread running after g_type_init(): Running test "liststore-is-a" 979 runs, min/avg/max = 1.913/2.040/3.817 ms 2500 runs, min/avg/max = 0.657/0.795/6.723 ms 3357 runs, min/avg/max = 0.560/0.591/2.464 ms Running test "liststore-interface-peek" 1293 runs, min/avg/max = 1.475/1.542/4.159 ms 4460 runs, min/avg/max = 0.431/0.444/3.722 ms 4988 runs, min/avg/max = 0.387/0.396/0.485 ms Running test "liststore-interface-peek-same" 1557 runs, min/avg/max = 1.265/1.280/3.870 ms 4664 runs, min/avg/max = 0.415/0.424/4.485 ms 4889 runs, min/avg/max = 0.387/0.404/3.113 ms For two threads running concurrently on a dual core machine: Running test "liststore-is-a" 443 runs, min/avg/max = 1.941/9.037/39.310 ms 5067 runs, min/avg/max = 0.719/0.785/18.201 ms 6664 runs, min/avg/max = 0.556/0.595/26.311 ms Running test "liststore-interface-peek" 545 runs, min/avg/max = 1.495/7.337/15.112 ms 8987 runs, min/avg/max = 0.417/0.440/14.300 ms 9946 runs, min/avg/max = 0.387/0.398/13.414 ms Running test "liststore-interface-peek-same" 583 runs, min/avg/max = 1.236/6.859/20.641 ms 9924 runs, min/avg/max = 0.381/0.398/16.410 ms 9967 runs, min/avg/max = 0.387/0.397/14.164 ms
All these patches are now in the gobject-performance branch in git
The gobject-performance branch is now rebased onto the gobject-performance-2 branch based on glib 2.18, with some stuff merged.
now in master