From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9612 invoked by alias); 10 Sep 2009 15:48:00 -0000 Received: (qmail 9578 invoked by uid 22791); 10 Sep 2009 15:47:56 -0000 X-SWARE-Spam-Status: No, hits=-1.1 required=5.0 tests=AWL,BAYES_00,J_CHICKENPOX_44,J_CHICKENPOX_47,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; Thu, 10 Sep 2009 15:47:50 +0000 Received: from wpaz33.hot.corp.google.com (wpaz33.hot.corp.google.com [172.24.198.97]) by smtp-out.google.com with ESMTP id n8AFlmK2024042 for ; Thu, 10 Sep 2009 08:47:49 -0700 Received: from qyk33 (qyk33.prod.google.com [10.241.83.161]) by wpaz33.hot.corp.google.com with ESMTP id n8AFlkuH026770 for ; Thu, 10 Sep 2009 08:47:46 -0700 Received: by qyk33 with SMTP id 33so126043qyk.14 for ; Thu, 10 Sep 2009 08:47:46 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.40.130 with SMTP id k2mr1502231qae.69.1252597664028; Thu, 10 Sep 2009 08:47:44 -0700 (PDT) In-Reply-To: References: From: Martin Thuresson Date: Thu, 10 Sep 2009 15:48:00 -0000 Message-ID: Subject: Fwd: Patch to improve assemble time for files with large number of sections and section groups. To: binutils Content-Type: multipart/mixed; boundary=000feaf10951d054a204733b1e0e X-System-Of-Record: true X-IsSubscribed: yes Mailing-List: contact binutils-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sourceware.org X-SW-Source: 2009-09/txt/msg00301.txt.bz2 --000feaf10951d054a204733b1e0e Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-length: 885 Resending after subscribing, as I never saw the email appear on the list. Thanks, Martin ---------- Forwarded message ---------- From: Martin Thuresson Date: Wed, Sep 9, 2009 at 6:06 PM Subject: Patch to improve assemble time for files with large number of sections and section groups. To: binutils This patch adds two hashmaps to avoid the N^2 complexity of scanning lists to find object. In obj-elf.c, group names are mapped to indexes into an array, and in dwarf2dbg.c segment names are mapped to segments. For inputs with ~40k sections, this patch reduces the assembly time from 3min to 15s on builds with debug information. It does this at the expense of increase memory usage. =A0In my example, it increased from 405MB to 640MB. Tested with x86_64-linux arm-eabi with no regressions seen on check, check-gas. Thanks, Martin --000feaf10951d054a204733b1e0e Content-Type: text/x-patch; charset=US-ASCII; name="hash.patch" Content-Disposition: attachment; filename="hash.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_fzespiq50 Content-length: 7447 T25seSBpbiBzcmMuaGVhZC9DVlM6IEVudHJpZXMuTG9nCmRpZmYgLXVycCBz cmMuaGVhZC9nYXMvYXMuYyBzcmMuaGFzaC9nYXMvYXMuYwotLS0gc3JjLmhl YWQvZ2FzL2FzLmMJMjAwOS0wOS0wNyAxMzoyMToyMi41MDk1OTUwMDAgLTA3 MDAKKysrIHNyYy5oYXNoL2dhcy9hcy5jCTIwMDktMDktMDkgMTY6NDU6Mjgu MjQ4NTQ0MDAwIC0wNzAwCkBAIC0xMTU4LDYgKzExNTgsOCBAQCBtYWluIChp bnQgYXJnYywgY2hhciAqKiBhcmd2KQogCiAgIGl0YmxfaW5pdCAoKTsKIAor ICBkd2FyZjJfaW5pdCAoKTsKKwogICAvKiBOb3cgdGhhdCB3ZSBoYXZlIGZ1 bGx5IGluaXRpYWxpemVkLCBhbmQgaGF2ZSBjcmVhdGVkIHRoZSBvdXRwdXQK ICAgICAgZmlsZSwgZGVmaW5lIGFueSBzeW1ib2xzIHJlcXVlc3RlZCBieSAt LWRlZnN5bSBjb21tYW5kIGxpbmUKICAgICAgYXJndW1lbnRzLiAgKi8KT25s eSBpbiBzcmMuaGFzaC9nYXM6IGFzLmMub3JpZwpkaWZmIC11cnAgc3JjLmhl YWQvZ2FzL2NvbmZpZy9vYmotZWxmLmMgc3JjLmhhc2gvZ2FzL2NvbmZpZy9v YmotZWxmLmMKLS0tIHNyYy5oZWFkL2dhcy9jb25maWcvb2JqLWVsZi5jCTIw MDktMDktMDcgMTM6MjE6MjMuOTIzMzE1MDAwIC0wNzAwCisrKyBzcmMuaGFz aC9nYXMvY29uZmlnL29iai1lbGYuYwkyMDA5LTA5LTA5IDE2OjQ1OjI4LjY2 MTU1NzAwMCAtMDcwMApAQCAtMjAwNiw2ICsyMDA2LDcgQEAgc3RydWN0IGdy b3VwX2xpc3QKICAgYXNlY3Rpb24gKipoZWFkOwkJLyogU2VjdGlvbiBsaXN0 cy4gICovCiAgIHVuc2lnbmVkIGludCAqZWx0X2NvdW50OwkvKiBOdW1iZXIg b2Ygc2VjdGlvbnMgaW4gZWFjaCBsaXN0LiAgKi8KICAgdW5zaWduZWQgaW50 IG51bV9ncm91cDsJLyogTnVtYmVyIG9mIGxpc3RzLiAgKi8KKyAgc3RydWN0 IGhhc2hfY29udHJvbCAqaW5kZXhlczsgLyogTWFwcyBncm91cCBuYW1lIHRv IGluZGV4IGluIGhlYWQgYXJyYXkuICAqLwogfTsKIAogLyogQ2FsbGVkIHZp YSBiZmRfbWFwX292ZXJfc2VjdGlvbnMuICBJZiBTRUMgaXMgYSBtZW1iZXIg b2YgYSBncm91cCwKQEAgLTIwMTksMjEgKzIwMjAsMjEgQEAgYnVpbGRfZ3Jv dXBfbGlzdHMgKGJmZCAqYWJmZCBBVFRSSUJVVEVfVQogICBzdHJ1Y3QgZ3Jv dXBfbGlzdCAqbGlzdCA9IGluZjsKICAgY29uc3QgY2hhciAqZ3JvdXBfbmFt ZSA9IGVsZl9ncm91cF9uYW1lIChzZWMpOwogICB1bnNpZ25lZCBpbnQgaTsK KyAgdW5zaWduZWQgaW50ICplbGVtX2lkeDsKKyAgdW5zaWduZWQgaW50ICpp ZHhfcHRyOwogCiAgIGlmIChncm91cF9uYW1lID09IE5VTEwpCiAgICAgcmV0 dXJuOwogCiAgIC8qIElmIHRoaXMgZ3JvdXAgYWxyZWFkeSBoYXMgYSBsaXN0 LCBhZGQgdGhlIHNlY3Rpb24gdG8gdGhlIGhlYWQgb2YKICAgICAgdGhlIGxp c3QuICAqLwotICBmb3IgKGkgPSAwOyBpIDwgbGlzdC0+bnVtX2dyb3VwOyBp KyspCisgIGVsZW1faWR4ID0gKHVuc2lnbmVkIGludCAqKSBoYXNoX2ZpbmQg KGxpc3QtPmluZGV4ZXMsIGdyb3VwX25hbWUpOworICBpZiAoZWxlbV9pZHgg IT0gTlVMTCkKICAgICB7Ci0gICAgICBpZiAoc3RyY21wIChncm91cF9uYW1l LCBlbGZfZ3JvdXBfbmFtZSAobGlzdC0+aGVhZFtpXSkpID09IDApCi0Jewot CSAgZWxmX25leHRfaW5fZ3JvdXAgKHNlYykgPSBsaXN0LT5oZWFkW2ldOwot CSAgbGlzdC0+aGVhZFtpXSA9IHNlYzsKLQkgIGxpc3QtPmVsdF9jb3VudFtp XSArPSAxOwotCSAgcmV0dXJuOwotCX0KKyAgICAgIGVsZl9uZXh0X2luX2dy b3VwIChzZWMpID0gbGlzdC0+aGVhZFsqZWxlbV9pZHhdOworICAgICAgbGlz dC0+aGVhZFsqZWxlbV9pZHhdID0gc2VjOworICAgICAgbGlzdC0+ZWx0X2Nv dW50WyplbGVtX2lkeF0gKz0gMTsKKyAgICAgIHJldHVybjsKICAgICB9CiAK ICAgLyogTmV3IGdyb3VwLiAgTWFrZSB0aGUgYXJyYXlzIGJpZ2dlciBpbiBj aHVua3MgdG8gbWluaW1pemUgY2FsbHMgdG8KQEAgLTIwNDksNiArMjA1MCwx NiBAQCBidWlsZF9ncm91cF9saXN0cyAoYmZkICphYmZkIEFUVFJJQlVURV9V CiAgIGxpc3QtPmhlYWRbaV0gPSBzZWM7CiAgIGxpc3QtPmVsdF9jb3VudFtp XSA9IDE7CiAgIGxpc3QtPm51bV9ncm91cCArPSAxOworCisgIC8qIEFkZCBp bmRleCB0byBoYXNoLiAgKi8KKyAgaWR4X3B0ciA9IHhtYWxsb2MgKHNpemVv ZiAodW5zaWduZWQgaW50KSk7CisgICppZHhfcHRyID0gaTsKKyAgaGFzaF9p bnNlcnQgKGxpc3QtPmluZGV4ZXMsIGdyb3VwX25hbWUsIGlkeF9wdHIpOwor fQorCitzdGF0aWMgdm9pZCBmcmVlX3NlY3Rpb25faWR4IChjb25zdCBjaGFy ICprZXkgQVRUUklCVVRFX1VOVVNFRCwgdm9pZCAqdmFsKQoreworICBmcmVl ICgodW5zaWduZWQgaW50ICopIHZhbCk7CiB9CiAKIHZvaWQKQEAgLTIwNjMs NiArMjA3NCw3IEBAIGVsZl9mcm9iX2ZpbGUgKHZvaWQpCiAgIGxpc3QubnVt X2dyb3VwID0gMDsKICAgbGlzdC5oZWFkID0gTlVMTDsKICAgbGlzdC5lbHRf Y291bnQgPSBOVUxMOworICBsaXN0LmluZGV4ZXMgID0gaGFzaF9uZXcgKCk7 CiAgIGJmZF9tYXBfb3Zlcl9zZWN0aW9ucyAoc3Rkb3V0cHV0LCBidWlsZF9n cm91cF9saXN0cywgJmxpc3QpOwogCiAgIC8qIE1ha2UgdGhlIFNIVF9HUk9V UCBzZWN0aW9ucyB0aGF0IGRlc2NyaWJlIGVhY2ggc2VjdGlvbiBncm91cC4g IFdlCkBAIC0yMTI4LDYgKzIxNDAsMTAgQEAgZWxmX2Zyb2JfZmlsZSAodm9p ZCkKICNpZmRlZiBlbGZfdGNfZmluYWxfcHJvY2Vzc2luZwogICBlbGZfdGNf ZmluYWxfcHJvY2Vzc2luZyAoKTsKICNlbmRpZgorCisgIC8qIENsZWFudXAg aGFzaC4gICovCisgIGhhc2hfdHJhdmVyc2UgKGxpc3QuaW5kZXhlcywgZnJl ZV9zZWN0aW9uX2lkeCk7CisgIGhhc2hfZGllIChsaXN0LmluZGV4ZXMpOwog fQogCiAvKiBJdCByZW1vdmVzIGFueSB1bm5lZWRlZCB2ZXJzaW9uZWQgc3lt Ym9scyBmcm9tIHRoZSBzeW1ib2wgdGFibGUuICAqLwpPbmx5IGluIHNyYy5o YXNoL2dhcy9jb25maWc6IG9iai1lbGYuYy5vcmlnCmRpZmYgLXVycCBzcmMu aGVhZC9nYXMvZHdhcmYyZGJnLmMgc3JjLmhhc2gvZ2FzL2R3YXJmMmRiZy5j Ci0tLSBzcmMuaGVhZC9nYXMvZHdhcmYyZGJnLmMJMjAwOS0wOS0wNyAxMzoy MToyMi43Nzc1MDgwMDAgLTA3MDAKKysrIHNyYy5oYXNoL2dhcy9kd2FyZjJk YmcuYwkyMDA5LTA5LTA5IDE2OjQ1OjI4Ljc4NzUyODAwMCAtMDcwMApAQCAt MTY4LDYgKzE2OCwxMCBAQCBzdHJ1Y3QgbGluZV9zZWcgewogCiAvKiBDb2xs ZWN0cyBkYXRhIGZvciBhbGwgbGluZSB0YWJsZSBlbnRyaWVzIGR1cmluZyBh c3NlbWJseS4gICovCiBzdGF0aWMgc3RydWN0IGxpbmVfc2VnICphbGxfc2Vn czsKKy8qIEhhc2ggdXNlZCB0byBxdWlja2x5IGxvb2t1cCBhIHNlZ21lbnQg YnkgbmFtZSwgYXZvaWRpbmcgdGhlIG5lZWQgdG8gc2VhcmNoCisgICB0aHJv dWdoIHRoZSBhbGxfc2VncyBsaXN0LiAgKi8KK3N0YXRpYyBzdHJ1Y3QgaGFz aF9jb250cm9sICphbGxfc2Vnc19oYXNoOworc3RhdGljIHN0cnVjdCBsaW5l X3NlZyAqKmxhc3Rfc2VnX3B0cjsKIAogc3RydWN0IGZpbGVfZW50cnkgewog ICBjb25zdCBjaGFyICpmaWxlbmFtZTsKQEAgLTIzMCwyMyArMjM0LDI1IEBA IGdldF9saW5lX3N1YnNlZyAoc2VnVCBzZWcsIHN1YnNlZ1Qgc3Vic2UKICAg c3RhdGljIHN1YnNlZ1QgbGFzdF9zdWJzZWc7CiAgIHN0YXRpYyBzdHJ1Y3Qg bGluZV9zdWJzZWcgKmxhc3RfbGluZV9zdWJzZWc7CiAKLSAgc3RydWN0IGxp bmVfc2VnICoqcHMsICpzOworICBzdHJ1Y3QgbGluZV9zZWcgKnM7CiAgIHN0 cnVjdCBsaW5lX3N1YnNlZyAqKnBzcywgKnNzOwogCiAgIGlmIChzZWcgPT0g bGFzdF9zZWcgJiYgc3Vic2VnID09IGxhc3Rfc3Vic2VnKQogICAgIHJldHVy biBsYXN0X2xpbmVfc3Vic2VnOwogCi0gIGZvciAocHMgPSAmYWxsX3NlZ3M7 IChzID0gKnBzKSAhPSBOVUxMOyBwcyA9ICZzLT5uZXh0KQotICAgIGlmIChz LT5zZWcgPT0gc2VnKQotICAgICAgZ290byBmb3VuZF9zZWc7Ci0KLSAgcyA9 IChzdHJ1Y3QgbGluZV9zZWcgKikgeG1hbGxvYyAoc2l6ZW9mICgqcykpOwot ICBzLT5uZXh0ID0gTlVMTDsKLSAgcy0+c2VnID0gc2VnOwotICBzLT5oZWFk ID0gTlVMTDsKLSAgKnBzID0gczsKKyAgcyA9IChzdHJ1Y3QgbGluZV9zZWcg KikgaGFzaF9maW5kIChhbGxfc2Vnc19oYXNoLCBzZWctPm5hbWUpOworICBp ZiAocyA9PSBOVUxMKQorICAgIHsKKyAgICAgIHMgPSAoc3RydWN0IGxpbmVf c2VnICopIHhtYWxsb2MgKHNpemVvZiAoKnMpKTsKKyAgICAgIHMtPm5leHQg PSBOVUxMOworICAgICAgcy0+c2VnID0gc2VnOworICAgICAgcy0+aGVhZCA9 IE5VTEw7CisgICAgICAqbGFzdF9zZWdfcHRyID0gczsKKyAgICAgIGxhc3Rf c2VnX3B0ciA9ICZzLT5uZXh0OworICAgICAgaGFzaF9pbnNlcnQgKGFsbF9z ZWdzX2hhc2gsIHNlZy0+bmFtZSwgcyk7CisgICAgfQorICBnYXNfYXNzZXJ0 IChzZWcgPT0gcy0+c2VnKTsKIAotIGZvdW5kX3NlZzoKICAgZm9yIChwc3Mg PSAmcy0+aGVhZDsgKHNzID0gKnBzcykgIT0gTlVMTCA7IHBzcyA9ICZzcy0+ bmV4dCkKICAgICB7CiAgICAgICBpZiAoc3MtPnN1YnNlZyA9PSBzdWJzZWcp CkBAIC0xNzAyLDYgKzE3MDgsMTQgQEAgb3V0X2RlYnVnX2luZm8gKHNlZ1Qg aW5mb19zZWcsIHNlZ1QgYWJicgogICBzeW1ib2xfc2V0X3ZhbHVlX25vdyAo aW5mb19lbmQpOwogfQogCit2b2lkCitkd2FyZjJfaW5pdCAodm9pZCkKK3sK KyAgYWxsX3NlZ3NfaGFzaCA9IGhhc2hfbmV3ICgpOworICBsYXN0X3NlZ19w dHIgPSAmYWxsX3NlZ3M7Cit9CisKKwogLyogRmluaXNoIHRoZSBkd2FyZjIg ZGVidWcgc2VjdGlvbnMuICBXZSBlbWl0IC5kZWJ1Zy5saW5lIGlmIHRoZXJl CiAgICB3ZXJlIGFueSAuZmlsZS8ubG9jIGRpcmVjdGl2ZXMsIG9yIC0tZ2R3 YXJmMiB3YXMgZ2l2ZW4sIG9yIGlmIHRoZQogICAgZmlsZSBoYXMgYSBub24t ZW1wdHkgLmRlYnVnX2luZm8gc2VjdGlvbi4gIElmIHdlIGVtaXQgLmRlYnVn X2xpbmUsCk9ubHkgaW4gc3JjLmhhc2gvZ2FzOiBkd2FyZjJkYmcuYy5vcmln CmRpZmYgLXVycCBzcmMuaGVhZC9nYXMvZHdhcmYyZGJnLmggc3JjLmhhc2gv Z2FzL2R3YXJmMmRiZy5oCi0tLSBzcmMuaGVhZC9nYXMvZHdhcmYyZGJnLmgJ MjAwOS0wOS0wNyAxMzoyMToyMi43OTc0NzgwMDAgLTA3MDAKKysrIHNyYy5o YXNoL2dhcy9kd2FyZjJkYmcuaAkyMDA5LTA5LTA5IDE2OjQ1OjI4Ljg4MzU2 NjAwMCAtMDcwMApAQCAtOTAsNiArOTAsOCBAQCBiZmRfYm9vbGVhbiBkd2Fy ZjJfbG9jX2RpcmVjdGl2ZV9zZWVuOwogICAgZHdhcmYyX2VtaXRfbGFiZWwu ICAqLwogZXh0ZXJuIGJmZF9ib29sZWFuIGR3YXJmMl9sb2NfbWFya19sYWJl bHM7CiAKK2V4dGVybiB2b2lkIGR3YXJmMl9pbml0ICh2b2lkKTsKKwogZXh0 ZXJuIHZvaWQgZHdhcmYyX2ZpbmlzaCAodm9pZCk7CiAKIGV4dGVybiBpbnQg ZHdhcmYyZGJnX2VzdGltYXRlX3NpemVfYmVmb3JlX3JlbGF4IChmcmFnUyAq KTsK --000feaf10951d054a204733b1e0e Content-Type: application/octet-stream; name="hash.changelog" Content-Disposition: attachment; filename="hash.changelog" Content-Transfer-Encoding: base64 X-Attachment-Id: f_fzespsj31 Content-length: 570 MjAwOS0wOS0wOSAgTWFydGluIFRodXJlc3NvbiAgPG1hcnRpbnRAZ29vZ2xl LmNvbT4KCgkqIGdhcy9hcy5jIChtYWluKTogQ2FsbCBkd2FyZjJfaW5pdC4K CSogZ2FzL2NvbmZpZy9vYmotZWxmLmMgKHN0cnVjdCBncm91cF9saXN0KTog TmV3IGZpZWxkLgoJKGJ1aWxkX2dyb3VwX2xpc3RzKTogVXNlIGhhc2ggbG9v a3VwLgoJKGZyZWVfc2VjdGlvbl9pZHgpOiBOZXcgZnVuY3Rpb24uCgkoZWxm X2Zyb2JfZmlsZSk6IEFkanVzdC4KCSogZ2FzL2R3YXJmMmRiZy5jIChhbGxf c2Vnc19oYXNoLCBsYXN0X3NlZ19wdHIpOiBOZXcgdmFyaWFibGVzLgoJKGdl dF9saW5lX3N1YnNlZyk6IEFkanVzdC4KCShkd2FyZjJfaW5pdCk6IE5ldyBm dW5jdGlvbi4KCSogZ2FzL2R3YXJmMmRiZy5oIChkd2FyZjJfaW5pdCk6IE5l dyBkZWNsYXJhdGlvbi4K --000feaf10951d054a204733b1e0e--