From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 28145 invoked by alias); 17 Jul 2009 00:24:39 -0000 Received: (qmail 28136 invoked by uid 22791); 17 Jul 2009 00:24:38 -0000 X-SWARE-Spam-Status: No, hits=-1.5 required=5.0 tests=AWL,BAYES_00,J_CHICKENPOX_31,SARE_MSGID_LONG40,SPF_PASS X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.45.13) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 17 Jul 2009 00:24:32 +0000 Received: from zps19.corp.google.com (zps19.corp.google.com [172.25.146.19]) by smtp-out.google.com with ESMTP id n6H0OU6x025857 for ; Thu, 16 Jul 2009 17:24:30 -0700 Received: from qyk41 (qyk41.prod.google.com [10.241.83.169]) by zps19.corp.google.com with ESMTP id n6H0OR44030042 for ; Thu, 16 Jul 2009 17:24:28 -0700 Received: by qyk41 with SMTP id 41so483716qyk.29 for ; Thu, 16 Jul 2009 17:24:27 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.89.146 with SMTP id e18mr86013qcm.23.1247790267427; Thu, 16 Jul 2009 17:24:27 -0700 (PDT) Date: Fri, 17 Jul 2009 07:34:00 -0000 Message-ID: <8ac60eac0907161724v40e5bd8bg7877d8901b8d7b6e@mail.gmail.com> Subject: [patch] Speed up find_pc_section From: Paul Pluzhnikov To: gdb-patches ml Cc: Paul Pluzhnikov Content-Type: multipart/mixed; boundary=0016364ee4e6a4ecb0046edbcf6b X-System-Of-Record: true X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2009-07/txt/msg00419.txt.bz2 --0016364ee4e6a4ecb0046edbcf6b Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 988 Greetings, While working on something else, I noticed find_pc_section consuming 90%+ of CPU in my GDB profiles :-( It is called from quite a number of places, and is surprisingly inefficient. Further, it exhibits yet another quadratic slowdown on number of objfiles, as the attached test case demonstrates. Running "perl gen.pl NNN" generates NNN shared libs, and a main executable, which crashes with NNN+C levels in stack trace, crossing all shared libs. I then collected timing like this: time gdb64-cvs -ex run -ex where -ex quit ./a.out > /dev/null Here are user-time results before the patch (clearly showing non-linear slowdown): 32: 0m0.426s 64: 0m1.344s 128: 0m5.254s 256: 0m35.792s 512: 4m55.999s Attached patch turns linear search into binary search, speeding up find_pc_section drastically :-) Here are the same user-time results after the patch: 128: 0m1.064s 256: 0m3.062s 512: 0m10.675s Tested on Linux/x86_64 with no regressions. Comments? -- Paul Pluzhnikov --0016364ee4e6a4ecb0046edbcf6b Content-Type: text/plain; charset=US-ASCII; name="gdb-find_pc_section-20090716.txt" Content-Disposition: attachment; filename="gdb-find_pc_section-20090716.txt" Content-Transfer-Encoding: base64 X-Attachment-Id: f_fx85jw1c1 Content-length: 6198 SW5kZXg6IG9iamZpbGVzLmMKPT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQpSQ1Mg ZmlsZTogL2N2cy9zcmMvc3JjL2dkYi9vYmpmaWxlcy5jLHYKcmV0cmlldmlu ZyByZXZpc2lvbiAxLjg1CmRpZmYgLXUgLXAgLXUgLXIxLjg1IG9iamZpbGVz LmMKLS0tIG9iamZpbGVzLmMJMTQgSnVsIDIwMDkgMTQ6NTU6MDYgLTAwMDAJ MS44NQorKysgb2JqZmlsZXMuYwkxNyBKdWwgMjAwOSAwMDoyMToxMyAtMDAw MApAQCAtNjQsNiArNjQsMTggQEAgc3RydWN0IG9iamZpbGUgKmN1cnJlbnRf b2JqZmlsZTsJLyogRm9yIAogc3RydWN0IG9iamZpbGUgKnN5bWZpbGVfb2Jq ZmlsZTsJLyogTWFpbiBzeW1ib2wgdGFibGUgbG9hZGVkIGZyb20gKi8KIHN0 cnVjdCBvYmpmaWxlICpydF9jb21tb25fb2JqZmlsZTsJLyogRm9yIHJ1bnRp bWUgY29tbW9uIHN5bWJvbHMgKi8KIAorc3RydWN0IGFkZHJlc3NfdG9fb2Jq X3NlY3Rpb24KK3sKKyAgQ09SRV9BRERSIGFkZHI7CisgIENPUkVfQUREUiBl bmRhZGRyOworICBzdHJ1Y3Qgb2JqX3NlY3Rpb24gKnNlY3Rpb247Cit9Owor CisvKiBSZWNvcmRzIHdoZXRoZXIgYW55IG9iamZpbGVzIGFwcGVhcmVkIG9y IGRpc2FwcGVhcmVkIHNpbmNlIHdlIGxhc3QgdXBkYXRlZAorICAgYWRkcmVz cyB0byBvYmogc2VjdGlvbiBtYXAuICAqLworCitzdGF0aWMgaW50IG9iamZp bGVzX3VwZGF0ZWRfcDsKKwogLyogTG9jYXRlIGFsbCBtYXBwYWJsZSBzZWN0 aW9ucyBvZiBhIEJGRCBmaWxlLiAKICAgIG9iamZpbGVfcF9jaGFyIGlzIGEg Y2hhciAqIHRvIGdldCBpdCB0aHJvdWdoCiAgICBiZmRfbWFwX292ZXJfc2Vj dGlvbnM7IHdlIGNhc3QgaXQgYmFjayB0byBpdHMgcHJvcGVyIHR5cGUuICAq LwpAQCAtOTQsNiArMTA2LDcgQEAgYWRkX3RvX29iamZpbGVfc2VjdGlvbnMg KHN0cnVjdCBiZmQgKmFiZgogICBvYnN0YWNrX2dyb3cgKCZvYmpmaWxlLT5v YmpmaWxlX29ic3RhY2ssIChjaGFyICopICZzZWN0aW9uLCBzaXplb2YgKHNl Y3Rpb24pKTsKICAgb2JqZmlsZS0+c2VjdGlvbnNfZW5kCiAgICAgPSAoc3Ry dWN0IG9ial9zZWN0aW9uICopICgoKHNpemVfdCkgb2JqZmlsZS0+c2VjdGlv bnNfZW5kKSArIDEpOworICBvYmpmaWxlc191cGRhdGVkX3AgKz0gMTsgIC8q IFJlYnVpbGQgc2VjdGlvbiBtYXAgbmV4dCB0aW1lIHdlIG5lZWQgaXQuICAq LwogfQogCiAvKiBCdWlsZHMgYSBzZWN0aW9uIHRhYmxlIGZvciBPQkpGSUxF LgpAQCAtMzk0LDYgKzQwNyw3IEBAIHVubGlua19vYmpmaWxlIChzdHJ1Y3Qg b2JqZmlsZSAqb2JqZmlsZSkKIHZvaWQKIGZyZWVfb2JqZmlsZSAoc3RydWN0 IG9iamZpbGUgKm9iamZpbGUpCiB7CisgIG9iamZpbGVzX3VwZGF0ZWRfcCAr PSAxOyAgLyogUmVidWlsZCBzZWN0aW9uIG1hcCBuZXh0IHRpbWUgd2UgbmVl ZCBpdC4gICovCiAgIGlmIChvYmpmaWxlLT5zZXBhcmF0ZV9kZWJ1Z19vYmpm aWxlKQogICAgIHsKICAgICAgIGZyZWVfb2JqZmlsZSAob2JqZmlsZS0+c2Vw YXJhdGVfZGVidWdfb2JqZmlsZSk7CkBAIC03NTcsMjIgKzc3MSwxMjEgQEAg aGF2ZV9taW5pbWFsX3N5bWJvbHMgKHZvaWQpCiAgIHJldHVybiAwOwogfQog CisvKiBRc29ydCBjb21wYXJpc29uIGZ1bmN0aW9uLiAgKi8KK3N0YXRpYyBp bnQKK3NlY3Rpb25fbWFwX2NvbXBhcmUgKGNvbnN0IHZvaWQgKmEsIGNvbnN0 IHZvaWQgKmIpCit7CisgIGNvbnN0IHN0cnVjdCBhZGRyZXNzX3RvX29ial9z ZWN0aW9uICphYSA9CisgICAgICAoY29uc3Qgc3RydWN0IGFkZHJlc3NfdG9f b2JqX3NlY3Rpb24gKikgYTsKKyAgY29uc3Qgc3RydWN0IGFkZHJlc3NfdG9f b2JqX3NlY3Rpb24gKmJiID0KKyAgICAgIChjb25zdCBzdHJ1Y3QgYWRkcmVz c190b19vYmpfc2VjdGlvbiAqKSBiOworCisgIGlmIChhYS0+YWRkciA8IGJi LT5hZGRyKQorICAgIHsKKyAgICAgIGdkYl9hc3NlcnQgKGFhLT5lbmRhZGRy IDw9IGJiLT5hZGRyKTsKKyAgICAgIHJldHVybiAtMTsKKyAgICB9CisgIGVs c2UgaWYgKGFhLT5hZGRyID4gYmItPmFkZHIpCisgICAgeworICAgICAgZ2Ri X2Fzc2VydCAoYWEtPmFkZHIgPj0gYmItPmVuZGFkZHIpOworICAgICAgcmV0 dXJuIDE7CisgICAgfQorICAvKiBUaGlzIGNhbiBoYXBwZW4gZm9yIHNlcGFy YXRlIGRlYnVnLWluZm8gZmlsZXMuICAqLworICBnZGJfYXNzZXJ0IChhYS0+ ZW5kYWRkciA9PSBiYi0+ZW5kYWRkcik7CisKKyAgcmV0dXJuIDA7Cit9CisK Ky8qIFVwZGF0ZSBQTUFQLCBQTUFQX1NJWkUgd2l0aCBub24tVExTIHNlY3Rp b25zIGZyb20gYWxsIG9iamZpbGVzLiAgKi8KKworc3RhdGljIHZvaWQKK3Vw ZGF0ZV9zZWN0aW9uX21hcCAoc3RydWN0IGFkZHJlc3NfdG9fb2JqX3NlY3Rp b24gKipwbWFwLAorICAgICAgICAgICAgICAgICAgICBpbnQgKnBtYXBfc2l6 ZSkKK3sKKyAgaW50IG1hcF9zaXplLCBpZHg7CisgIHN0cnVjdCBvYmpfc2Vj dGlvbiAqczsKKyAgc3RydWN0IG9iamZpbGUgKm9iamZpbGU7CisgIHN0cnVj dCBhZGRyZXNzX3RvX29ial9zZWN0aW9uICptYXA7CisKKyAgZ2RiX2Fzc2Vy dCAob2JqZmlsZXNfdXBkYXRlZF9wICE9IDApOworCisgIG1hcCA9ICpwbWFw OworICB4ZnJlZSAobWFwKTsKKworI2RlZmluZSBpbnNlcnRfcChvYmpmLCBz ZWMpIFwKKyAgKChiZmRfZ2V0X3NlY3Rpb25fZmxhZ3MgKChvYmpmKS0+b2Jm ZCwgKHNlYyktPnRoZV9iZmRfc2VjdGlvbikgXAorICAgICYgU0VDX1RIUkVB RF9MT0NBTCkgPT0gMCkKKworICBtYXBfc2l6ZSA9IDA7CisgIEFMTF9PQkpT RUNUSU9OUyAob2JqZmlsZSwgcykKKyAgICBpZiAoaW5zZXJ0X3AgKG9iamZp bGUsIHMpKQorICAgICAgbWFwX3NpemUgKz0gMTsKKworICBtYXAgPSB4bWFs bG9jIChtYXBfc2l6ZSAqIHNpemVvZiAoKm1hcCkpOworCisgIGlkeCA9IDA7 CisgIEFMTF9PQkpTRUNUSU9OUyAob2JqZmlsZSwgcykKKyAgICBpZiAoaW5z ZXJ0X3AgKG9iamZpbGUsIHMpKQorICAgICAgeworICAgICAgICBtYXBbaWR4 XS5zZWN0aW9uID0gczsKKyAgICAgICAgbWFwW2lkeF0uYWRkciA9IG9ial9z ZWN0aW9uX2FkZHIgKHMpOworICAgICAgICBtYXBbaWR4XS5lbmRhZGRyID0g b2JqX3NlY3Rpb25fZW5kYWRkciAocyk7CisgICAgICAgIGlkeCArPSAxOwor ICAgICAgfQorCisjdW5kZWYgaW5zZXJ0X3AKKworICBxc29ydCAobWFwLCBt YXBfc2l6ZSwgc2l6ZW9mICgqbWFwKSwgc2VjdGlvbl9tYXBfY29tcGFyZSk7 CisKKyAgKnBtYXAgPSBtYXA7CisgICpwbWFwX3NpemUgPSBtYXBfc2l6ZTsK K30KKworLyogQnNlYXJjaCBjb21wYXJpc29uIGZ1bmN0aW9uLiAqLworCitp bnQKK2ZpbmRfcGNfc2VjdGlvbl9jbXAgKGNvbnN0IHZvaWQgKmtleSwgY29u c3Qgdm9pZCAqZWx0KQoreworICBDT1JFX0FERFIgcGMgPSAqKENPUkVfQURE UiAqKSBrZXk7CisgIGNvbnN0IHN0cnVjdCBhZGRyZXNzX3RvX29ial9zZWN0 aW9uICplbnRyeSA9CisgICAgICAoY29uc3Qgc3RydWN0IGFkZHJlc3NfdG9f b2JqX3NlY3Rpb24gKikgZWx0OworCisgIGlmIChwYyA8IGVudHJ5LT5hZGRy KQorICAgIHJldHVybiAtMTsKKyAgaWYgKHBjIDwgZW50cnktPmVuZGFkZHIp CisgICAgcmV0dXJuIDA7CisgIHJldHVybiAxOworfQorCiAvKiBSZXR1cm5z IGEgc2VjdGlvbiB3aG9zZSByYW5nZSBpbmNsdWRlcyBQQyBvciBOVUxMIGlm IG5vbmUgZm91bmQuICAgKi8KIAogc3RydWN0IG9ial9zZWN0aW9uICoKIGZp bmRfcGNfc2VjdGlvbiAoQ09SRV9BRERSIHBjKQogeworICBzdGF0aWMgc3Ry dWN0IGFkZHJlc3NfdG9fb2JqX3NlY3Rpb24gKnNlY3Rpb25zOworICBzdGF0 aWMgaW50IG51bV9zZWN0aW9uczsKKwogICBzdHJ1Y3Qgb2JqX3NlY3Rpb24g KnM7Ci0gIHN0cnVjdCBvYmpmaWxlICpvYmpmaWxlOworICBzdHJ1Y3QgYWRk cmVzc190b19vYmpfc2VjdGlvbiAqYW9zOwogCiAgIC8qIENoZWNrIGZvciBt YXBwZWQgb3ZlcmxheSBzZWN0aW9uIGZpcnN0LiAgKi8KICAgcyA9IGZpbmRf cGNfbWFwcGVkX3NlY3Rpb24gKHBjKTsKICAgaWYgKHMpCiAgICAgcmV0dXJu IHM7CiAKLSAgQUxMX09CSlNFQ1RJT05TIChvYmpmaWxlLCBzKQotICAgIGlm IChvYmpfc2VjdGlvbl9hZGRyIChzKSA8PSBwYyAmJiBwYyA8IG9ial9zZWN0 aW9uX2VuZGFkZHIgKHMpKQotICAgICAgcmV0dXJuIHM7CisgIGlmIChvYmpm aWxlc191cGRhdGVkX3AgIT0gMCkKKyAgICB7CisgICAgICB1cGRhdGVfc2Vj dGlvbl9tYXAgKCZzZWN0aW9ucywgJm51bV9zZWN0aW9ucyk7CisKKyAgICAg IC8qIERvbid0IG5lZWQgdXBkYXRlcyB0byBzZWN0aW9uIG1hcCB1bnRpbCBv YmpmaWxlcyBhcmUgYWRkZWQKKyAgICAgICAgIG9yIHJlbW92ZWQuICAqLwor ICAgICAgb2JqZmlsZXNfdXBkYXRlZF9wID0gMDsKKyAgICB9CisKKyAgYW9z ID0gYnNlYXJjaCAoJnBjLCBzZWN0aW9ucywgbnVtX3NlY3Rpb25zLCBzaXpl b2YgKCpzZWN0aW9ucyksCisgICAgICAgICAgICAgICAgIGZpbmRfcGNfc2Vj dGlvbl9jbXApOworICBpZiAoYW9zKQorICAgIHJldHVybiBhb3MtPnNlY3Rp b247CiAKICAgcmV0dXJuIE5VTEw7CiB9Cg== --0016364ee4e6a4ecb0046edbcf6b Content-Type: application/x-perl; name="gen.pl" Content-Disposition: attachment; filename="gen.pl" Content-Transfer-Encoding: base64 X-Attachment-Id: f_fx85hb7o0 Content-length: 859 IyEvdXNyL2Jpbi9wZXJsCgokbGltaXQgPSAoJEFSR1ZbMF0gfHwgMTAwMCk7 CgpAbGlicyA9ICgpOwpmb3IgJGkgKDEgLi4gJGxpbWl0KSB7CiAgbXkgJG5h bWUgPSBzcHJpbnRmKCJmb29fJTA0ZCIsICRpKTsKICBteSAkc3RtdCA9ICgk aSA9PSAkbGltaXQpID8gImFib3J0KCkiIDogc3ByaW50ZigicmV0dXJuIGZv b18lMDRkKCkiLCAkaSsxKTsKICBvcGVuKE9VVCwgIj4gJG5hbWUuYyIpIHx8 IGRpZTsKICBwcmludCBPVVQgImludCAkbmFtZSgpIHsgJHN0bXQ7IH1cbiI7 CiAgZm9yIG15ICRqICgxIC4uIDEwMDApIHsKICAgIG15ICRuID0gc3ByaW50 ZiAiJXNfJTA0ZCIsICRuYW1lLCAkajsKICAgIHByaW50IE9VVCAiaW50ICRu KCkgeyByZXR1cm4gJGo7IH1cbiI7CiAgfQogIGNsb3NlKE9VVCk7CiAgc3lz dGVtKCJnY2MgLWZQSUMgLXNoYXJlZCAtbyAkbmFtZS5zbyAkbmFtZS5jIDI+ L2Rldi9udWxsIikgJiYgZGllOwogIHB1c2goQGxpYnMsICIuLyRuYW1lLnNv Iik7Cn0KCm9wZW4oT1VULCAiPiBtYWluLmMiKSB8fCBkaWU7CnByaW50IE9V VCAiaW50IG1haW4oKSB7IHJldHVybiBmb29fMDAwMSgpOyB9XG4iOwpjbG9z ZShPVVQpOwoKc3lzdGVtKCJnY2MiLCAibWFpbi5jIiwgQGxpYnMpICYmIGRp ZTsK --0016364ee4e6a4ecb0046edbcf6b--