From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 13042 invoked by alias); 17 Jul 2009 14:55:59 -0000 Received: (qmail 13033 invoked by uid 22791); 17 Jul 2009 14:55:58 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL,BAYES_00,SARE_MSGID_LONG40,SPF_PASS X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.33.17) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 17 Jul 2009 14:55:50 +0000 Received: from wpaz21.hot.corp.google.com (wpaz21.hot.corp.google.com [172.24.198.85]) by smtp-out.google.com with ESMTP id n6HEtjx8029049 for ; Fri, 17 Jul 2009 15:55:46 +0100 Received: from qyk17 (qyk17.prod.google.com [10.241.83.145]) by wpaz21.hot.corp.google.com with ESMTP id n6HEthMu018365 for ; Fri, 17 Jul 2009 07:55:43 -0700 Received: by qyk17 with SMTP id 17so782620qyk.9 for ; Fri, 17 Jul 2009 07:55:43 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.91.13 with SMTP id k13mr195050qcm.98.1247842543401; Fri, 17 Jul 2009 07:55:43 -0700 (PDT) In-Reply-To: <8ac60eac0907161724v40e5bd8bg7877d8901b8d7b6e@mail.gmail.com> References: <8ac60eac0907161724v40e5bd8bg7877d8901b8d7b6e@mail.gmail.com> Date: Fri, 17 Jul 2009 15:59:00 -0000 Message-ID: <8ac60eac0907170755k78f1a647qcba096d81980de3@mail.gmail.com> Subject: Re: [patch] Speed up find_pc_section From: Paul Pluzhnikov To: gdb-patches ml Cc: Paul Pluzhnikov Content-Type: multipart/mixed; boundary=0016361e813488fd9b046ee7fbd3 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/msg00428.txt.bz2 --0016361e813488fd9b046ee7fbd3 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 478 On Thu, Jul 16, 2009 at 5:24 PM, Paul Pluzhnikov wrote: > Attached patch turns linear search into binary search, speeding up > find_pc_section drastically :-) A cleaner patch, with ChangeLog this time. Thanks, -- Paul Pluzhnikov 2009-07-17 Paul Pluzhnikov * objfiles.c (objfiles_updated_p): New variable. (qsort_cmp, bsearch_cmp, update_section_map): New function. (find_pc_section): Use bsearch. --0016361e813488fd9b046ee7fbd3 Content-Type: text/plain; charset=US-ASCII; name="gdb-find_pc_section-20090717.txt" Content-Disposition: attachment; filename="gdb-find_pc_section-20090717.txt" Content-Transfer-Encoding: base64 X-Attachment-Id: f_fx916w383 Content-length: 5922 SW5kZXg6IG9iamZpbGVzLmMKPT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQpSQ1Mg ZmlsZTogL2N2cy9zcmMvc3JjL2dkYi9vYmpmaWxlcy5jLHYKcmV0cmlldmlu ZyByZXZpc2lvbiAxLjg1CmRpZmYgLXUgLXAgLXUgLXIxLjg1IG9iamZpbGVz LmMKLS0tIG9iamZpbGVzLmMJMTQgSnVsIDIwMDkgMTQ6NTU6MDYgLTAwMDAJ MS44NQorKysgb2JqZmlsZXMuYwkxNyBKdWwgMjAwOSAxNDo1Mjo0NyAtMDAw MApAQCAtNjQsNiArNjQsMTEgQEAgc3RydWN0IG9iamZpbGUgKmN1cnJlbnRf b2JqZmlsZTsJLyogRm9yIAogc3RydWN0IG9iamZpbGUgKnN5bWZpbGVfb2Jq ZmlsZTsJLyogTWFpbiBzeW1ib2wgdGFibGUgbG9hZGVkIGZyb20gKi8KIHN0 cnVjdCBvYmpmaWxlICpydF9jb21tb25fb2JqZmlsZTsJLyogRm9yIHJ1bnRp bWUgY29tbW9uIHN5bWJvbHMgKi8KIAorLyogUmVjb3JkcyB3aGV0aGVyIGFu eSBvYmpmaWxlcyBhcHBlYXJlZCBvciBkaXNhcHBlYXJlZCBzaW5jZSB3ZSBs YXN0IHVwZGF0ZWQKKyAgIGFkZHJlc3MgdG8gb2JqIHNlY3Rpb24gbWFwLiAg Ki8KKworc3RhdGljIGludCBvYmpmaWxlc191cGRhdGVkX3A7CisKIC8qIExv Y2F0ZSBhbGwgbWFwcGFibGUgc2VjdGlvbnMgb2YgYSBCRkQgZmlsZS4gCiAg ICBvYmpmaWxlX3BfY2hhciBpcyBhIGNoYXIgKiB0byBnZXQgaXQgdGhyb3Vn aAogICAgYmZkX21hcF9vdmVyX3NlY3Rpb25zOyB3ZSBjYXN0IGl0IGJhY2sg dG8gaXRzIHByb3BlciB0eXBlLiAgKi8KQEAgLTk0LDYgKzk5LDcgQEAgYWRk X3RvX29iamZpbGVfc2VjdGlvbnMgKHN0cnVjdCBiZmQgKmFiZgogICBvYnN0 YWNrX2dyb3cgKCZvYmpmaWxlLT5vYmpmaWxlX29ic3RhY2ssIChjaGFyICop ICZzZWN0aW9uLCBzaXplb2YgKHNlY3Rpb24pKTsKICAgb2JqZmlsZS0+c2Vj dGlvbnNfZW5kCiAgICAgPSAoc3RydWN0IG9ial9zZWN0aW9uICopICgoKHNp emVfdCkgb2JqZmlsZS0+c2VjdGlvbnNfZW5kKSArIDEpOworICBvYmpmaWxl c191cGRhdGVkX3AgKz0gMTsgIC8qIFJlYnVpbGQgc2VjdGlvbiBtYXAgbmV4 dCB0aW1lIHdlIG5lZWQgaXQuICAqLwogfQogCiAvKiBCdWlsZHMgYSBzZWN0 aW9uIHRhYmxlIGZvciBPQkpGSUxFLgpAQCAtMzk0LDYgKzQwMCw3IEBAIHVu bGlua19vYmpmaWxlIChzdHJ1Y3Qgb2JqZmlsZSAqb2JqZmlsZSkKIHZvaWQK IGZyZWVfb2JqZmlsZSAoc3RydWN0IG9iamZpbGUgKm9iamZpbGUpCiB7Cisg IG9iamZpbGVzX3VwZGF0ZWRfcCArPSAxOyAgLyogUmVidWlsZCBzZWN0aW9u IG1hcCBuZXh0IHRpbWUgd2UgbmVlZCBpdC4gICovCiAgIGlmIChvYmpmaWxl LT5zZXBhcmF0ZV9kZWJ1Z19vYmpmaWxlKQogICAgIHsKICAgICAgIGZyZWVf b2JqZmlsZSAob2JqZmlsZS0+c2VwYXJhdGVfZGVidWdfb2JqZmlsZSk7CkBA IC03NTcsMjMgKzc2NCwxMTMgQEAgaGF2ZV9taW5pbWFsX3N5bWJvbHMgKHZv aWQpCiAgIHJldHVybiAwOwogfQogCisvKiBRc29ydCBjb21wYXJpc29uIGZ1 bmN0aW9uLiAgKi8KKworc3RhdGljIGludAorcXNvcnRfY21wIChjb25zdCB2 b2lkICphLCBjb25zdCB2b2lkICpiKQoreworICBjb25zdCBzdHJ1Y3Qgb2Jq X3NlY3Rpb24gKnNlY3QxID0gKihjb25zdCBzdHJ1Y3Qgb2JqX3NlY3Rpb24g KiopIGE7CisgIGNvbnN0IHN0cnVjdCBvYmpfc2VjdGlvbiAqc2VjdDIgPSAq KGNvbnN0IHN0cnVjdCBvYmpfc2VjdGlvbiAqKikgYjsKKyAgY29uc3QgQ09S RV9BRERSIHNlY3QxX2FkZHIgPSBvYmpfc2VjdGlvbl9hZGRyIChzZWN0MSk7 CisgIGNvbnN0IENPUkVfQUREUiBzZWN0Ml9hZGRyID0gb2JqX3NlY3Rpb25f YWRkciAoc2VjdDIpOworCisgIGlmIChzZWN0MV9hZGRyIDwgc2VjdDJfYWRk cikKKyAgICB7CisgICAgICBnZGJfYXNzZXJ0IChvYmpfc2VjdGlvbl9lbmRh ZGRyIChzZWN0MSkgPD0gc2VjdDJfYWRkcik7CisgICAgICByZXR1cm4gLTE7 CisgICAgfQorICBlbHNlIGlmIChzZWN0MV9hZGRyID4gc2VjdDJfYWRkcikK KyAgICB7CisgICAgICBnZGJfYXNzZXJ0IChzZWN0MV9hZGRyID49IG9ial9z ZWN0aW9uX2VuZGFkZHIgKHNlY3QyKSk7CisgICAgICByZXR1cm4gMTsKKyAg ICB9CisgIC8qIFRoaXMgY2FuIGhhcHBlbiBmb3Igc2VwYXJhdGUgZGVidWct aW5mbyBmaWxlcy4gICovCisgIGdkYl9hc3NlcnQgKG9ial9zZWN0aW9uX2Vu ZGFkZHIgKHNlY3QxKSA9PSBvYmpfc2VjdGlvbl9lbmRhZGRyIChzZWN0Mikp OworCisgIHJldHVybiAwOworfQorCisvKiBVcGRhdGUgUE1BUCwgUE1BUF9T SVpFIHdpdGggbm9uLVRMUyBzZWN0aW9ucyBmcm9tIGFsbCBvYmpmaWxlcy4g ICovCisKK3N0YXRpYyB2b2lkCit1cGRhdGVfc2VjdGlvbl9tYXAgKHN0cnVj dCBvYmpfc2VjdGlvbiAqKipwbWFwLCBpbnQgKnBtYXBfc2l6ZSkKK3sKKyAg aW50IG1hcF9zaXplLCBpZHg7CisgIHN0cnVjdCBvYmpfc2VjdGlvbiAqcywg KiptYXA7CisgIHN0cnVjdCBvYmpmaWxlICpvYmpmaWxlOworCisgIGdkYl9h c3NlcnQgKG9iamZpbGVzX3VwZGF0ZWRfcCAhPSAwKTsKKworICBtYXAgPSAq cG1hcDsKKyAgeGZyZWUgKG1hcCk7CisKKyNkZWZpbmUgaW5zZXJ0X3Aob2Jq Ziwgc2VjKSBcCisgICgoYmZkX2dldF9zZWN0aW9uX2ZsYWdzICgob2JqZikt Pm9iZmQsIChzZWMpLT50aGVfYmZkX3NlY3Rpb24pIFwKKyAgICAmIFNFQ19U SFJFQURfTE9DQUwpID09IDApCisKKyAgbWFwX3NpemUgPSAwOworICBBTExf T0JKU0VDVElPTlMgKG9iamZpbGUsIHMpCisgICAgaWYgKGluc2VydF9wIChv YmpmaWxlLCBzKSkKKyAgICAgIG1hcF9zaXplICs9IDE7CisKKyAgbWFwID0g eG1hbGxvYyAobWFwX3NpemUgKiBzaXplb2YgKCptYXApKTsKKworICBpZHgg PSAwOworICBBTExfT0JKU0VDVElPTlMgKG9iamZpbGUsIHMpCisgICAgaWYg KGluc2VydF9wIChvYmpmaWxlLCBzKSkKKyAgICAgIG1hcFtpZHgrK10gPSBz OworCisjdW5kZWYgaW5zZXJ0X3AKKworICBxc29ydCAobWFwLCBtYXBfc2l6 ZSwgc2l6ZW9mICgqbWFwKSwgcXNvcnRfY21wKTsKKworICAqcG1hcCA9IG1h cDsKKyAgKnBtYXBfc2l6ZSA9IG1hcF9zaXplOworfQorCisvKiBCc2VhcmNo IGNvbXBhcmlzb24gZnVuY3Rpb24uICovCisKK3N0YXRpYyBpbnQKK2JzZWFy Y2hfY21wIChjb25zdCB2b2lkICprZXksIGNvbnN0IHZvaWQgKmVsdCkKK3sK KyAgY29uc3QgQ09SRV9BRERSIHBjID0gKihDT1JFX0FERFIgKikga2V5Owor ICBjb25zdCBzdHJ1Y3Qgb2JqX3NlY3Rpb24gKnNlY3Rpb24gPSAqKGNvbnN0 IHN0cnVjdCBvYmpfc2VjdGlvbiAqKikgZWx0OworCisgIGlmIChwYyA8IG9i al9zZWN0aW9uX2FkZHIgKHNlY3Rpb24pKQorICAgIHJldHVybiAtMTsKKyAg aWYgKHBjIDwgb2JqX3NlY3Rpb25fZW5kYWRkciAoc2VjdGlvbikpCisgICAg cmV0dXJuIDA7CisgIHJldHVybiAxOworfQorCiAvKiBSZXR1cm5zIGEgc2Vj dGlvbiB3aG9zZSByYW5nZSBpbmNsdWRlcyBQQyBvciBOVUxMIGlmIG5vbmUg Zm91bmQuICAgKi8KIAogc3RydWN0IG9ial9zZWN0aW9uICoKIGZpbmRfcGNf c2VjdGlvbiAoQ09SRV9BRERSIHBjKQogewotICBzdHJ1Y3Qgb2JqX3NlY3Rp b24gKnM7Ci0gIHN0cnVjdCBvYmpmaWxlICpvYmpmaWxlOworICBzdGF0aWMg c3RydWN0IG9ial9zZWN0aW9uICoqc2VjdGlvbnM7CisgIHN0YXRpYyBpbnQg bnVtX3NlY3Rpb25zOworCisgIHN0cnVjdCBvYmpfc2VjdGlvbiAqcywgKipz cDsKIAogICAvKiBDaGVjayBmb3IgbWFwcGVkIG92ZXJsYXkgc2VjdGlvbiBm aXJzdC4gICovCiAgIHMgPSBmaW5kX3BjX21hcHBlZF9zZWN0aW9uIChwYyk7 CiAgIGlmIChzKQogICAgIHJldHVybiBzOwogCi0gIEFMTF9PQkpTRUNUSU9O UyAob2JqZmlsZSwgcykKLSAgICBpZiAob2JqX3NlY3Rpb25fYWRkciAocykg PD0gcGMgJiYgcGMgPCBvYmpfc2VjdGlvbl9lbmRhZGRyIChzKSkKLSAgICAg IHJldHVybiBzOworICBpZiAob2JqZmlsZXNfdXBkYXRlZF9wICE9IDApCisg ICAgeworICAgICAgdXBkYXRlX3NlY3Rpb25fbWFwICgmc2VjdGlvbnMsICZu dW1fc2VjdGlvbnMpOworCisgICAgICAvKiBEb24ndCBuZWVkIHVwZGF0ZXMg dG8gc2VjdGlvbiBtYXAgdW50aWwgb2JqZmlsZXMgYXJlIGFkZGVkCisgICAg ICAgICBvciByZW1vdmVkLiAgKi8KKyAgICAgIG9iamZpbGVzX3VwZGF0ZWRf cCA9IDA7CisgICAgfQogCisgIHNwID0gKHN0cnVjdCBvYmpfc2VjdGlvbiAq KikgYnNlYXJjaCAoJnBjLCBzZWN0aW9ucywgbnVtX3NlY3Rpb25zLAorCQkJ CQlzaXplb2YgKCpzZWN0aW9ucyksIGJzZWFyY2hfY21wKTsKKyAgaWYgKHNw ICE9IE5VTEwpCisgICAgcmV0dXJuICpzcDsKICAgcmV0dXJuIE5VTEw7CiB9 CiAK --0016361e813488fd9b046ee7fbd3--