From unknown Mon Jun 23 07:48:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15191: faster DFA.C state merge Resent-From: Ivan Yanikov Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Mon, 26 Aug 2013 06:58:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 15191 X-GNU-PR-Package: grep X-GNU-PR-Keywords: To: Paul Eggert Cc: 15191@debbugs.gnu.org X-Debbugs-Original-Cc: bug-grep@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.137750023911692 (code B ref -1); Mon, 26 Aug 2013 06:58:03 +0000 Received: (at submit) by debbugs.gnu.org; 26 Aug 2013 06:57:19 +0000 Received: from localhost ([127.0.0.1]:56084 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VDqjj-00032M-CV for submit@debbugs.gnu.org; Mon, 26 Aug 2013 02:57:16 -0400 Received: from eggs.gnu.org ([208.118.235.92]:45702) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VDlZh-0002Ut-Im for submit@debbugs.gnu.org; Sun, 25 Aug 2013 21:26:35 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VDlZc-0007hG-JU for submit@debbugs.gnu.org; Sun, 25 Aug 2013 21:26:33 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50,FREEMAIL_FROM, T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:49871) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VDlZc-0007hC-Fl for submit@debbugs.gnu.org; Sun, 25 Aug 2013 21:26:28 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47417) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VDlZX-0002ob-Md for bug-grep@gnu.org; Sun, 25 Aug 2013 21:26:28 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VDlZR-0007g0-6Y for bug-grep@gnu.org; Sun, 25 Aug 2013 21:26:23 -0400 Received: from mail-la0-x232.google.com ([2a00:1450:4010:c03::232]:48471) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VDlZQ-0007fk-RO for bug-grep@gnu.org; Sun, 25 Aug 2013 21:26:17 -0400 Received: by mail-la0-f50.google.com with SMTP id es20so1787036lab.37 for ; Sun, 25 Aug 2013 18:26:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type; bh=k/92xJo/xBy5sizD8IKUY1kXlUa/yCKixJi6fMkCiAU=; b=L9XtSTX+5q0sCCZ7KlG8iefSnGNE7ER1jndaZnLUo6XUlqTlqhiYkTkxRkpZ7vJQku jPOS0ssvh3lzXmh9NXyat3Wa5JqV1ZIg812fGhVI8Lyk/Qae/demtFrR13nPqEbLuduv eoSLZbvZ4Y6ps2si2sbHKYhLXuuhPbq5NLO9nQQzbKkha+TGfg50AiVAgr/olgWxYIYR 1KY0ECfPSEW2gg7KB2CwD88AVtjWsUu5b/AfFco6SjOzLdk5rW+os78fT8CZSUoiNnQf H3YnCMxXlsZfislUm2DsFlkty2ePNJ5I9RBz3k8B97HQpOhxW5CKRXzumB9jWPECVbXx j+CQ== X-Received: by 10.112.51.166 with SMTP id l6mr10556562lbo.5.1377480375328; Sun, 25 Aug 2013 18:26:15 -0700 (PDT) Received: from [192.168.1.4] (ppp91-76-191-147.pppoe.mtu-net.ru. [91.76.191.147]) by mx.google.com with ESMTPSA id ap7sm4579513lac.10.1969.12.31.16.00.00 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 25 Aug 2013 18:26:14 -0700 (PDT) Message-ID: <521AAEB3.70909@gmail.com> Date: Mon, 26 Aug 2013 05:26:11 +0400 From: Ivan Yanikov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 MIME-Version: 1.0 References: <52195675.6030606@gmail.com> <5219AC0D.7040806@cs.ucla.edu> In-Reply-To: <5219AC0D.7040806@cs.ucla.edu> Content-Type: multipart/mixed; boundary="------------010006080605040308050001" X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -2.4 (--) X-Mailman-Approved-At: Mon, 26 Aug 2013 02:57:13 -0400 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.4 (--) This is a multi-part message in MIME format. --------------010006080605040308050001 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit I have polished the patch ( faster code for simple cases of merging 2 or 1 sets, fixes of code style, like fancy 2+2 indentation, important fix: memory leaks under valgrind - I improperly returned array from a function ) New patch available on URL https://gist.github.com/dobrokot/6337339 and included as attach > One thing that'd help would be a test case that illustrates the need for the patch. Not sure how to properly to send test-case, and how to reference grep compiled old/new binary. I had put it on URL http://dobrokot.ru/dump/slow_dfa_merge.2013-08-26.tar.gz I can send it in a attach for a "history", if binary/large attaches are allowed in maillists. Real regex contains sensitive private data, and it's huge. So I had little obfuscated it and reduce to kilobytes. The runtime difference is not so great as in real example (1 to 100), but still large ( 2-3 times faster ). Times for new/old version: 2.3sec / 8.7sec > I assume you're willing to assign copyright to the FSF for the change? (I can send you copies of the paperwork, if so.) You mean, I should somewhere explicitly state, that I am agree with GPL and give FSF rights to distribute and use the code from patch? If so, I am surely agree with the license, and (proudly) give the permission to use/distribute code from my patch :) Or you mean some modification of authorship lines in the AUTHORS/THANKS and beginning of dfa.c, which should contain my name now ? Which paperwork do you mean? Real paper which I should sign with pen and ink? Thanks for attention, Ivan Yanikov. On 25.08.2013 11:02, Paul Eggert wrote: > Ivan Yanikov wrote: >> How I can properly send/commit it for review? > You've already done that, sort of, with the pointers > to the patch. One thing that'd help would be a test > case that illustrates the need for the patch. Also, > I assume you're willing to assign copyright to the > FSF for the change? (I can send you copies of the > paperwork, if so.) > --------------010006080605040308050001 Content-Type: text/plain; charset=windows-1251; name="grep-2.14-faster-dfa-merger.diff" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="grep-2.14-faster-dfa-merger.diff" SW5kZXg6IGRmYS5jDQo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09DQotLS0gZGZhLmMJKHJldmlzaW9uIGdyZXAt Mi4xNC1mYXN0ZXItZGZhKQ0KKysrIGRmYS5jCShyZXZpc2lvbiBncmVwLTIuMTQpDQpAQCAt MTk5Miw2ICsxOTkyLDEzMyBAQA0KICAgICAgIHMtPmVsZW1zW2ldID0gcy0+ZWxlbXNbaSAr IDFdOw0KIH0NCiANCisvKiBNZXJnZSBpbXBsZW1lbnRhdGlvbiBvZiBzb3J0ZWQgc2V0cywg dGhlbiBudW1iZXIgb2Ygc2V0cyBzbW9yZSB0aGFuIDIuDQorICAgUHJpb3JpdHkgcXVldWUg YWthICdoZWFwJyBkYXRhIHN0cnVjdHVyZSB1c2VkIHRvIHNlbGVjdCBtYXhpbXVtIG9mDQor ICAgbWFueSBlbGVtZW50cyAqLw0KKw0KK3R5cGVkZWYgc3RydWN0IHsNCisgIHBvc2l0aW9u IHA7DQorICBzaXplX3Qgc2V0X2luZGV4OyAvKiBSZW1lbWJlciB3aGljaCBzZXQgdGhpcyBl bGVtZW50IHdhcyB0YWtlbiBmcm9tICovDQorfSBoZWFwX2VsZW07DQorDQorDQorc3RhdGlj IHZvaWQNCitoZWFwX2FkZCAoaGVhcF9lbGVtICpoZWFwLCBzaXplX3QgKmhlYXBfc2l6ZSwg aGVhcF9lbGVtIGUpDQorew0KKyAgc2l6ZV90IGkgPSAqaGVhcF9zaXplOw0KKyAgd2hpbGUg KGkpDQorICAgIHsNCisgICAgICBzaXplX3QgcGFyZW50ID0gKGktMSkgLyAyOw0KKyAgICAg IGlmIChlLnAuaW5kZXggPCBoZWFwW3BhcmVudF0ucC5pbmRleCkNCisgICAgICAgIGJyZWFr Ow0KKw0KKyAgICAgIGhlYXBbaV0gPSBoZWFwW3BhcmVudF07DQorICAgICAgaSA9IHBhcmVu dDsNCisgICAgfQ0KKyAgaGVhcFtpXSA9IGU7DQorICAqaGVhcF9zaXplICs9IDE7DQorfQ0K Kw0KK3N0YXRpYyB2b2lkDQoraGVhcF9yZW1vdmVfdG9wX2FuZF9hZGQgKGhlYXBfZWxlbSAq aGVhcCwgc2l6ZV90IGhlYXBfc2l6ZSwgaGVhcF9lbGVtIGUpDQorew0KKyAgc2l6ZV90IGkg PSAwOw0KKyAgc2l6ZV90IGxjaGlsZCAgPSAyKmkgKyAxOw0KKyAgc2l6ZV90IG4gPSBoZWFw X3NpemU7DQorICB3aGlsZSAobGNoaWxkIDwgbikNCisgICAgew0KKyAgICAgIHNpemVfdCBy Y2hpbGQgPSBsY2hpbGQgKyAxOw0KKyAgICAgIHNpemVfdCBuZXh0Y2hpbGQgPSBsY2hpbGQ7 DQorICAgICAgaWYgKHJjaGlsZCA8IG4gJiYgaGVhcFtsY2hpbGRdLnAuaW5kZXggPCBoZWFw W3JjaGlsZF0ucC5pbmRleCkNCisgICAgICAgIG5leHRjaGlsZCA9IHJjaGlsZDsNCisgICAg ICBpZiAoZS5wLmluZGV4ID49IGhlYXBbbmV4dGNoaWxkXS5wLmluZGV4KQ0KKyAgICAgICAg YnJlYWs7DQorICAgICAgaGVhcFtpXSA9IGhlYXBbbmV4dGNoaWxkXTsNCisgICAgICBpID0g bmV4dGNoaWxkOw0KKyAgICAgIGxjaGlsZCA9IDIqaSArIDE7DQorICAgIH0NCisgIGhlYXBb aV0gPSBlOw0KK30NCisNCisNCitzdGF0aWMgdm9pZA0KK2hlYXBfcmVtb3ZlX3RvcCAoaGVh cF9lbGVtICpoZWFwLCBzaXplX3QgKmhlYXBfc2l6ZSkNCit7DQorICAqaGVhcF9zaXplIC09 IDE7DQorICBpZiAoKmhlYXBfc2l6ZSA9PSAwKQ0KKyAgICByZXR1cm47DQorICBoZWFwX3Jl bW92ZV90b3BfYW5kX2FkZCAoaGVhcCwgKmhlYXBfc2l6ZSwgaGVhcFsqaGVhcF9zaXplXSk7 DQorfQ0KKw0KK3N0YXRpYyB2b2lkDQoraGVhcF9tZXJnZV9tYW55X3NldHMgKHBvc2l0aW9u X3NldCAqc2V0cywgc2l6ZV90IG4sIHBvc2l0aW9uX3NldCAqcmVzdWx0KQ0KK3sNCisgIHNp emVfdCBoZWFwX3NpemUgPSAwOw0KKyAgcG9zaXRpb25fc2V0IHI7IC8qIGZhc3RlciBhY2Nl c3MgdG8gbG9jYWwgdmFyaWFibGVzICovDQorICBoZWFwX2VsZW0gKmhlYXAgPSBYTk1BTExP QyAobiwgaGVhcF9lbGVtKTsNCisgIHNpemVfdCAqaWRzID0gWE5NQUxMT0MgKG4sIHNpemVf dCk7DQorICBzaXplX3Qgc3VtX29mX3NpemVzID0gMDsNCisgIHNpemVfdCBpOw0KKw0KKyAg Zm9yIChpID0gMDsgaSA8IG47ICsraSkNCisgICAgew0KKyAgICAgIHN1bV9vZl9zaXplcyAr PSBzZXRzW2ldLm5lbGVtOw0KKyAgICAgIC8qIHNwZWNpYWwgdmFsdWUgZm9yICJlbmQgb2Yg c2V0IiwgdG8gcmVkdWNlDQorICAgICAgICAgZGVwZW5kZW50IG1lbW9yeSByZWFkcyAqLw0K KyAgICAgIGlkc1tpXSA9IH4oc2l6ZV90KTA7DQorICAgICAgaWYgKHNldHNbaV0ubmVsZW0p DQorICAgICAgICB7DQorICAgICAgICAgIGhlYXBfZWxlbSBlID0geyBzZXRzW2ldLmVsZW1z WzBdLCBpIH07DQorICAgICAgICAgIGhlYXBfYWRkIChoZWFwLCAmaGVhcF9zaXplLCBlKTsN CisgICAgICAgICAgaWYgKHNldHNbaV0ubmVsZW0gPiAxKQ0KKyAgICAgICAgICAgIGlkc1tp XSA9IDE7DQorICAgICAgICB9DQorICAgIH0NCisNCisgIFJFQUxMT0NfSUZfTkVDRVNTQVJZ KHJlc3VsdC0+ZWxlbXMsIHJlc3VsdC0+YWxsb2MsIHN1bV9vZl9zaXplcyk7DQorICByID0g KnJlc3VsdDsNCisgIHIubmVsZW0gPSAwOw0KKw0KKyAgd2hpbGUgKGhlYXBfc2l6ZSkNCisg ICAgew0KKyAgICAgIGhlYXBfZWxlbSBlID0gaGVhcFswXTsNCisgICAgICBpZiAoci5uZWxl bSAmJiByLmVsZW1zW3IubmVsZW0tMV0uaW5kZXggPT0gZS5wLmluZGV4KQ0KKyAgICAgICAg ci5lbGVtc1tyLm5lbGVtLTFdLmNvbnN0cmFpbnQgfD0gZS5wLmNvbnN0cmFpbnQ7DQorICAg ICAgZWxzZQ0KKyAgICAgICAgci5lbGVtc1tyLm5lbGVtKytdID0gZS5wOw0KKyAgICAgIGkg PSBlLnNldF9pbmRleDsNCisgICAgICBpZiAoaWRzW2ldICE9IH4oc2l6ZV90KTApDQorICAg ICAgICB7DQorICAgICAgICAgIGhlYXBfZWxlbSBlMiA9IHsgc2V0c1tpXS5lbGVtc1tpZHNb aV1dLCBpIH07DQorICAgICAgICAgIGhlYXBfcmVtb3ZlX3RvcF9hbmRfYWRkIChoZWFwLCBo ZWFwX3NpemUsIGUyKTsNCisgICAgICAgICAgKytpZHNbaV07DQorICAgICAgICAgIGlmIChp ZHNbaV0gPT0gc2V0c1tpXS5uZWxlbSkNCisgICAgICAgICAgICBpZHNbaV0gPSB+KHNpemVf dCkwOw0KKyAgICAgICAgfQ0KKyAgICAgIGVsc2UNCisgICAgICAgIHsNCisgICAgICAgICAg aGVhcF9yZW1vdmVfdG9wIChoZWFwLCAmaGVhcF9zaXplKTsNCisgICAgICAgIH0NCisgICAg fQ0KKyAgKnJlc3VsdCA9IHI7DQorICBmcmVlIChpZHMpOw0KKyAgZnJlZSAoaGVhcCk7DQor fQ0KKw0KK3N0YXRpYyB2b2lkDQorbWVyZ2VfbWFueV9zZXRzIChwb3NpdGlvbl9zZXQgKnNl dHMsIHNpemVfdCBuLCBwb3NpdGlvbl9zZXQgKnJlc3VsdCkNCit7DQorICAvKiBvcHRpbWl6 ZWQgc29sdXRpb25zIGZvciBzcGVjaWFsL3RyaXZpYWwgY2FzZXMgKi8NCisgIGlmIChuID09 IDApDQorICAgIHJlc3VsdC0+bmVsZW0gPSAwOw0KKyAgZWxzZSBpZiAobiA9PSAxKQ0KKyAg ICBjb3B5ICgmc2V0c1swXSwgcmVzdWx0KTsNCisgIGVsc2UgaWYgKG4gPT0gMikNCisgICAg bWVyZ2UgKCZzZXRzWzBdLCAmc2V0c1sxXSwgcmVzdWx0KTsNCisgIGVsc2UNCisgICAgaGVh cF9tZXJnZV9tYW55X3NldHMoc2V0cywgbiwgcmVzdWx0KTsNCit9DQorDQogLyogRmluZCB0 aGUgaW5kZXggb2YgdGhlIHN0YXRlIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGdpdmVuIHBvc2l0 aW9uIHNldCB3aXRoDQogICAgdGhlIGdpdmVuIHByZWNlZGluZyBjb250ZXh0LCBvciBjcmVh dGUgYSBuZXcgc3RhdGUgaWYgdGhlcmUgaXMgbm8gc3VjaA0KICAgIHN0YXRlLiAgQ29udGV4 dCB0ZWxscyB3aGV0aGVyIHdlIGdvdCBoZXJlIG9uIGEgbmV3bGluZSBvciBsZXR0ZXIuICov DQpAQCAtMjQ4MiwxMyArMjYwOSwxNiBAQA0KICAgY2hhcmNsYXNzIGxlZnRvdmVyczsgICAg ICAgICAgLyogU3R1ZmYgaW4gdGhlIGxhYmVsIHRoYXQgZGlkbid0IG1hdGNoLiAqLw0KICAg aW50IGxlZnRvdmVyc2Y7ICAgICAgICAgICAgICAgLyogVHJ1ZSBpZiBsZWZ0b3ZlcnMgaXMg bm9uZW1wdHkuICovDQogICBwb3NpdGlvbl9zZXQgZm9sbG93czsgICAgICAgICAvKiBVbmlv biBvZiB0aGUgZm9sbG93cyBvZiBzb21lIGdyb3VwLiAqLw0KLSAgcG9zaXRpb25fc2V0IHRt cDsgICAgICAgICAgICAgLyogVGVtcG9yYXJ5IHNwYWNlIGZvciBtZXJnaW5nIHNldHMuICov DQorICBwb3NpdGlvbl9zZXQgZm9sbG93c190bXA7ICAgICAvKiBUZW1wb3Jhcnkgc3BhY2Ug Zm9yIG1lcmdpbmcgc2V0cy4gKi8NCiAgIGludCBwb3NzaWJsZV9jb250ZXh0czsgICAgICAg IC8qIENvbnRleHRzIHRoYXQgdGhpcyBncm91cCBjYW4gbWF0Y2guICovDQogICBpbnQgc2Vw YXJhdGVfY29udGV4dHM7ICAgICAgICAvKiBDb250ZXh0IHRoYXQgbmV3IHN0YXRlIHdhbnRz IHRvIGtub3cuICovDQogICBzdGF0ZV9udW0gc3RhdGU7ICAgICAgICAgICAgICAvKiBOZXcg c3RhdGUuICovDQogICBzdGF0ZV9udW0gc3RhdGVfbmV3bGluZTsgICAgICAvKiBOZXcgc3Rh dGUgb24gYSBuZXdsaW5lIHRyYW5zaXRpb24uICovDQogICBzdGF0ZV9udW0gc3RhdGVfbGV0 dGVyOyAgICAgICAvKiBOZXcgc3RhdGUgb24gYSBsZXR0ZXIgdHJhbnNpdGlvbi4gKi8NCiAg IGludCBuZXh0X2lzbnRfMXN0X2J5dGUgPSAwOyAgIC8qIEZsYWcgaWYgd2UgY2FuJ3QgYWRk IHN0YXRlMC4gICovDQorICBwb3NpdGlvbl9zZXQgKnNldHMgPSAwOyAgICAgICAvKiBUZW1w b3JhcnkgYXJyYXkgb2Ygc2V0cywgdG8gcGFzcyBtYW55IHNldHMgdG8gbWVyZ2UgZnVuY3Rp b24gKi8NCisgIHNpemVfdCBzZXRzX24gPSAwOyAgICAgICAgICAgIC8qIFNldHMgYXJyYXkg c2l6ZSAqLw0KKyAgc2l6ZV90IHNldHNfYWxsb2MgPSAwOyAgICAgICAgLyogU2V0cyBhcnJh eSBjYXBhY2l0eSAgICovDQogICBzaXplX3QgaSwgaiwgazsNCiANCiAgIE1BTExPQyAoZ3Jw cywgTk9UQ0hBUik7DQpAQCAtMjYwNyw3ICsyNzM3LDcgQEANCiAgICAgfQ0KIA0KICAgYWxs b2NfcG9zaXRpb25fc2V0ICgmZm9sbG93cywgZC0+bmxlYXZlcyk7DQotICBhbGxvY19wb3Np dGlvbl9zZXQgKCZ0bXAsIGQtPm5sZWF2ZXMpOw0KKyAgYWxsb2NfcG9zaXRpb25fc2V0ICgm Zm9sbG93c190bXAsIGQtPm5sZWF2ZXMpOw0KIA0KICAgLyogSWYgd2UgYXJlIGEgc2VhcmNo aW5nIG1hdGNoZXIsIHRoZSBkZWZhdWx0IHRyYW5zaXRpb24gaXMgdG8gYSBzdGF0ZQ0KICAg ICAgY29udGFpbmluZyB0aGUgcG9zaXRpb25zIG9mIHN0YXRlIDAsIG90aGVyd2lzZSB0aGUg ZGVmYXVsdCB0cmFuc2l0aW9uDQpAQCAtMjYzNywxMyArMjc2NywxMiBAQA0KIA0KICAgZm9y IChpID0gMDsgaSA8IG5ncnBzOyArK2kpDQogICAgIHsNCi0gICAgICBmb2xsb3dzLm5lbGVt ID0gMDsNCi0NCi0gICAgICAvKiBGaW5kIHRoZSB1bmlvbiBvZiB0aGUgZm9sbG93cyBvZiB0 aGUgcG9zaXRpb25zIG9mIHRoZSBncm91cC4NCi0gICAgICAgICBUaGlzIGlzIGEgaGlkZW91 c2x5IGluZWZmaWNpZW50IGxvb3AuICBGaXggaXQgc29tZWRheS4gKi8NCisgICAgICAvKiBG aW5kIHRoZSB1bmlvbiBvZiB0aGUgZm9sbG93cyBvZiB0aGUgcG9zaXRpb25zIG9mIHRoZSBn cm91cC4gICovDQorICAgICAgc2V0c19uID0gZ3Jwc1tpXS5uZWxlbTsNCisgICAgICBSRUFM TE9DX0lGX05FQ0VTU0FSWShzZXRzLCBzZXRzX2FsbG9jLCBzZXRzX24pOw0KICAgICAgIGZv ciAoaiA9IDA7IGogPCBncnBzW2ldLm5lbGVtOyArK2opDQotICAgICAgICBmb3IgKGsgPSAw OyBrIDwgZC0+Zm9sbG93c1tncnBzW2ldLmVsZW1zW2pdXS5uZWxlbTsgKytrKQ0KLSAgICAg ICAgICBpbnNlcnQgKGQtPmZvbGxvd3NbZ3Jwc1tpXS5lbGVtc1tqXV0uZWxlbXNba10sICZm b2xsb3dzKTsNCisgICAgICAgIHNldHNbal0gPSBkLT5mb2xsb3dzW2dycHNbaV0uZWxlbXNb al1dOw0KKyAgICAgIG1lcmdlX21hbnlfc2V0cyAoc2V0cywgc2V0c19uLCAmZm9sbG93c190 bXApOw0KIA0KICAgICAgIGlmIChkLT5tYl9jdXJfbWF4ID4gMSkNCiAgICAgICAgIHsNCkBA IC0yNjY2LDkgKzI3OTUsOSBAQA0KICAgICAgICAgICAgICA8bWIgQT4sIHNvIHdlIGNhbm5v dCBhZGQgc3RhdGVbMF0uICAqLw0KIA0KICAgICAgICAgICBuZXh0X2lzbnRfMXN0X2J5dGUg PSAwOw0KLSAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgZm9sbG93cy5uZWxlbTsgKytqKQ0K KyAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgZm9sbG93c190bXAubmVsZW07ICsraikNCiAg ICAgICAgICAgICB7DQotICAgICAgICAgICAgICBpZiAoIShkLT5tdWx0aWJ5dGVfcHJvcFtm b2xsb3dzLmVsZW1zW2pdLmluZGV4XSAmIDEpKQ0KKyAgICAgICAgICAgICAgaWYgKCEoZC0+ bXVsdGlieXRlX3Byb3BbZm9sbG93c190bXAuZWxlbXNbal0uaW5kZXhdICYgMSkpDQogICAg ICAgICAgICAgICAgIHsNCiAgICAgICAgICAgICAgICAgICBuZXh0X2lzbnRfMXN0X2J5dGUg PSAxOw0KICAgICAgICAgICAgICAgICAgIGJyZWFrOw0KQEAgLTI2ODAsOCArMjgwOSw3IEBA DQogICAgICAgICAgb2Ygc3RhdGUgMCBhcyB3ZWxsLiAqLw0KICAgICAgIGlmIChkLT5zZWFy Y2hmbGFnDQogICAgICAgICAgICYmICghTUJTX1NVUFBPUlQgfHwgKGQtPm1iX2N1cl9tYXgg PT0gMSB8fCAhbmV4dF9pc250XzFzdF9ieXRlKSkpDQotICAgICAgICBmb3IgKGogPSAwOyBq IDwgZC0+c3RhdGVzWzBdLmVsZW1zLm5lbGVtOyArK2opDQotICAgICAgICAgIGluc2VydCAo ZC0+c3RhdGVzWzBdLmVsZW1zLmVsZW1zW2pdLCAmZm9sbG93cyk7DQorICAgICAgICBtZXJn ZSAoJmZvbGxvd3NfdG1wLCAmZC0+c3RhdGVzWzBdLmVsZW1zLCAmZm9sbG93cyk7DQogDQog ICAgICAgLyogRmluZCBvdXQgaWYgdGhlIG5ldyBzdGF0ZSB3aWxsIHdhbnQgYW55IGNvbnRl eHQgaW5mb3JtYXRpb24uICovDQogICAgICAgcG9zc2libGVfY29udGV4dHMgPSBjaGFyY2xh c3NfY29udGV4dCAobGFiZWxzW2ldKTsNCkBAIC0yNzIwLDcgKzI4NDgsOCBAQA0KICAgZm9y IChpID0gMDsgaSA8IG5ncnBzOyArK2kpDQogICAgIGZyZWUgKGdycHNbaV0uZWxlbXMpOw0K ICAgZnJlZSAoZm9sbG93cy5lbGVtcyk7DQotICBmcmVlICh0bXAuZWxlbXMpOw0KKyAgZnJl ZSAoc2V0cyk7DQorICBmcmVlIChmb2xsb3dzX3RtcC5lbGVtcyk7DQogICBmcmVlIChncnBz KTsNCiAgIGZyZWUgKGxhYmVscyk7DQogfQ0K --------------010006080605040308050001-- From debbugs-submit-bounces@debbugs.gnu.org Sat Mar 08 12:51:14 2014 Received: (at control) by debbugs.gnu.org; 8 Mar 2014 17:51:14 +0000 Received: from localhost ([127.0.0.1]:56830 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WMLOz-0001Nb-Ip for submit@debbugs.gnu.org; Sat, 08 Mar 2014 12:51:13 -0500 Received: from smtp.cs.ucla.edu ([131.179.128.62]:38611) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WMLOw-0001NQ-1k for control@debbugs.gnu.org; Sat, 08 Mar 2014 12:51:10 -0500 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 2B15439E8018 for ; Sat, 8 Mar 2014 09:51:09 -0800 (PST) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kEXmnDi-K-yC for ; Sat, 8 Mar 2014 09:51:08 -0800 (PST) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id DA93C39E8013 for ; Sat, 8 Mar 2014 09:51:08 -0800 (PST) Message-ID: <531B588C.30603@cs.ucla.edu> Date: Sat, 08 Mar 2014 09:51:08 -0800 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0 MIME-Version: 1.0 To: control@debbugs.gnu.org Subject: 15191 has a patch Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) tags 15191 patch From debbugs-submit-bounces@debbugs.gnu.org Sun Apr 06 11:18:05 2014 Received: (at control) by debbugs.gnu.org; 6 Apr 2014 15:18:05 +0000 Received: from localhost ([127.0.0.1]:38211 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WWopg-0000Xv-Qi for submit@debbugs.gnu.org; Sun, 06 Apr 2014 11:18:05 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:33162) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WWopf-0000Xn-8W for control@debbugs.gnu.org; Sun, 06 Apr 2014 11:18:03 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id BF89339E8018 for ; Sun, 6 Apr 2014 08:18:02 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GwRCXc-iXICH for ; Sun, 6 Apr 2014 08:17:54 -0700 (PDT) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 4995439E8015 for ; Sun, 6 Apr 2014 08:17:54 -0700 (PDT) Message-ID: <53417022.7010907@cs.ucla.edu> Date: Sun, 06 Apr 2014 08:17:54 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: control@debbugs.gnu.org Subject: 15191 waiting on paperwork Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.6 (--) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.6 (--) tags 15191 + moreinfo thanks This one is waiting for paperwork. From unknown Mon Jun 23 07:48:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15191: faster DFA.C state merge Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Tue, 06 May 2014 14:36:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 15191 X-GNU-PR-Package: grep X-GNU-PR-Keywords: moreinfo patch To: Ivan Yanikov Cc: Paul Eggert , 15191@debbugs.gnu.org Received: via spool by 15191-submit@debbugs.gnu.org id=B15191.139938690932598 (code B ref 15191); Tue, 06 May 2014 14:36:01 +0000 Received: (at 15191) by debbugs.gnu.org; 6 May 2014 14:35:09 +0000 Received: from localhost ([127.0.0.1]:52945 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WhgSa-0008Ti-4k for submit@debbugs.gnu.org; Tue, 06 May 2014 10:35:08 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:49806) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WhgSV-0008T7-Uu for 15191@debbugs.gnu.org; Tue, 06 May 2014 10:35:05 -0400 Received: from imp03 (mailgw7.kcn.ne.jp [61.86.15.238]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 0F2DBE80669 for <15191@debbugs.gnu.org>; Tue, 6 May 2014 23:34:55 +0900 (JST) Received: from mail03.kcn.ne.jp ([61.86.6.182]) by imp03 with bizsmtp id yeau1n00F3veGq501eauks; Tue, 06 May 2014 23:34:54 +0900 X-OrgRCPT: 15191@debbugs.gnu.org Received: from [10.120.1.76] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail03.kcn.ne.jp (Postfix) with ESMTPA id 677F41410025; Tue, 6 May 2014 23:34:54 +0900 (JST) Date: Tue, 06 May 2014 23:34:53 +0900 From: Norihiro Tanaka In-Reply-To: <521AAEB3.70909@gmail.com> References: <5219AC0D.7040806@cs.ucla.edu> <521AAEB3.70909@gmail.com> Message-Id: <20140506233412.289F.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5368F0910000000028BF_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_5368F0910000000028BF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I tested below on CentOS 5.10 Intel(R) Core(TM)2 Duo CPU E7500 @ 2.93GHz GCC 4.1.2. $ env LANG=C time -p src/grep -f regex.re input_lines.txt Command exited with non-zero status 1 real 4.81 user 4.40 sys 0.09 I apply an attachment, and tested again. $ env LANG=C time -p src/grep -f regex.re input_lines.txt Command exited with non-zero status 1 real 4.63 user 4.46 sys 0.10 Therefore, I don't think that the patch is effective. --------_5368F0910000000028BF_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8"; name="diff.txt" Content-Disposition: attachment; filename="diff.txt" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9kZmEuYyBiL3NyYy9kZmEuYwppbmRleCAyNzNkM2QxLi4zODlmYzU5 IDEwMDY0NAotLS0gYS9zcmMvZGZhLmMKKysrIGIvc3JjL2RmYS5jCkBAIC0yMDcyLDYgKzIwNzIs MTI4IEBAIGRlbGV0ZSAocG9zaXRpb24gcCwgcG9zaXRpb25fc2V0ICogcykKICAgICAgIHMtPmVs ZW1zW2ldID0gcy0+ZWxlbXNbaSArIDFdOwogfQogCisvKiBNZXJnZSBpbXBsZW1lbnRhdGlvbiBv ZiBzb3J0ZWQgc2V0cywgdGhlbiBudW1iZXIgb2Ygc2V0cyBzbW9yZSB0aGFuIDIuCisgICBQcmlv cml0eSBxdWV1ZSBha2EgJ2hlYXAnIGRhdGEgc3RydWN0dXJlIHVzZWQgdG8gc2VsZWN0IG1heGlt dW0gb2YKKyAgIG1hbnkgZWxlbWVudHMgKi8KKwordHlwZWRlZiBzdHJ1Y3QgeworICBwb3NpdGlv biBwOworICBzaXplX3Qgc2V0X2luZGV4OyAgICAgLyogUmVtZW1iZXIgd2hpY2ggc2V0IHRoaXMg ZWxlbWVudCB3YXMgdGFrZW4gZnJvbSAqLworfSBoZWFwX2VsZW07CisKK3N0YXRpYyB2b2lkCito ZWFwX2FkZCAoaGVhcF9lbGVtICpoZWFwLCBzaXplX3QgKmhlYXBfc2l6ZSwgaGVhcF9lbGVtIGUp Cit7CisgIHNpemVfdCBpID0gKmhlYXBfc2l6ZTsKKyAgd2hpbGUgKGkpCisgICAgeworICAgICAg c2l6ZV90IHBhcmVudCA9IChpIC0gMSkgLyAyOworICAgICAgaWYgKGUucC5pbmRleCA8IGhlYXBb cGFyZW50XS5wLmluZGV4KQorICAgICAgICBicmVhazsKKyAgICAgIGhlYXBbaV0gPSBoZWFwW3Bh cmVudF07CisgICAgICBpID0gcGFyZW50OworICAgIH0KKyAgaGVhcFtpXSA9IGU7CisgICgqaGVh cF9zaXplKSsrOworfQorCitzdGF0aWMgdm9pZAoraGVhcF9yZW1vdmVfdG9wX2FuZF9hZGQgKGhl YXBfZWxlbSAqaGVhcCwgc2l6ZV90IGhlYXBfc2l6ZSwgaGVhcF9lbGVtIGUpCit7CisgIHNpemVf dCBpID0gMDsKKyAgc2l6ZV90IGxjaGlsZCAgPSAyICogaSArIDE7CisgIHNpemVfdCBuID0gaGVh cF9zaXplOworICB3aGlsZSAobGNoaWxkIDwgbikKKyAgICB7CisgICAgICBzaXplX3QgcmNoaWxk ID0gbGNoaWxkICsgMTsKKyAgICAgIHNpemVfdCBuZXh0Y2hpbGQgPSBsY2hpbGQ7CisgICAgICBp ZiAocmNoaWxkIDwgbiAmJiBoZWFwW2xjaGlsZF0ucC5pbmRleCA8IGhlYXBbcmNoaWxkXS5wLmlu ZGV4KQorICAgICAgICBuZXh0Y2hpbGQgPSByY2hpbGQ7CisgICAgICBpZiAoZS5wLmluZGV4ID49 IGhlYXBbbmV4dGNoaWxkXS5wLmluZGV4KQorICAgICAgICBicmVhazsKKyAgICAgIGhlYXBbaV0g PSBoZWFwW25leHRjaGlsZF07CisgICAgICBpID0gbmV4dGNoaWxkOworICAgICAgbGNoaWxkID0g MiAqIGkgKyAxOworICAgIH0KKyAgaGVhcFtpXSA9IGU7Cit9CisKK3N0YXRpYyB2b2lkCitoZWFw X3JlbW92ZV90b3AgKGhlYXBfZWxlbSAqaGVhcCwgc2l6ZV90ICpoZWFwX3NpemUpCit7CisgIGlm ICgtLSgqaGVhcF9zaXplKSA9PSAwKQorICAgIHJldHVybjsKKyAgaGVhcF9yZW1vdmVfdG9wX2Fu ZF9hZGQgKGhlYXAsICpoZWFwX3NpemUsIGhlYXBbKmhlYXBfc2l6ZV0pOworfQorCitzdGF0aWMg dm9pZAoraGVhcF9tZXJnZV9tYW55X3NldHMgKHBvc2l0aW9uX3NldCAqc2V0cywgc2l6ZV90IG4s IHBvc2l0aW9uX3NldCAqcmVzdWx0KQoreworICBzaXplX3QgaGVhcF9zaXplID0gMDsKKyAgcG9z aXRpb25fc2V0IHI7CisgIGhlYXBfZWxlbSAqaGVhcCA9IHhubWFsbG9jIChuLCBzaXplb2YgKmhl YXApOworICBzaXplX3QgKmlkcyA9IHhubWFsbG9jIChuLCBzaXplb2YgKmlkcyk7CisgIHNpemVf dCBzdW1fb2Zfc2l6ZXMgPSAwOworICBzaXplX3QgaTsKKworICBmb3IgKGkgPSAwOyBpIDwgbjsg KytpKQorICAgIHsKKyAgICAgIHN1bV9vZl9zaXplcyArPSBzZXRzW2ldLm5lbGVtOworICAgICAg aWRzW2ldID0gKHNpemVfdCkgLTE7CisgICAgICBpZiAoc2V0c1tpXS5uZWxlbSkKKyAgICAgICAg eworICAgICAgICAgIGhlYXBfZWxlbSBlID0geyBzZXRzW2ldLmVsZW1zWzBdLCBpIH07CisgICAg ICAgICAgaGVhcF9hZGQgKGhlYXAsICZoZWFwX3NpemUsIGUpOworICAgICAgICAgIGlmIChzZXRz W2ldLm5lbGVtID4gMSkKKyAgICAgICAgICAgIGlkc1tpXSA9IDE7CisgICAgICAgIH0KKyAgICB9 CisKKyAgcmVzdWx0LT5lbGVtcyA9IG1heWJlX3JlYWxsb2MgKHJlc3VsdC0+ZWxlbXMsIHJlc3Vs dC0+bmVsZW0sCisgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAmcmVzdWx0LT5hbGxv Yywgc2l6ZW9mICpyZXN1bHQtPmVsZW1zKTsKKyAgciA9ICpyZXN1bHQ7CisgIHIubmVsZW0gPSAw OworCisgIHdoaWxlIChoZWFwX3NpemUpCisgICAgeworICAgICAgaGVhcF9lbGVtIGUgPSBoZWFw WzBdOworICAgICAgaWYgKHIubmVsZW0gJiYgci5lbGVtc1tyLm5lbGVtLTFdLmluZGV4ID09IGUu cC5pbmRleCkKKyAgICAgICAgci5lbGVtc1tyLm5lbGVtLTFdLmNvbnN0cmFpbnQgfD0gZS5wLmNv bnN0cmFpbnQ7CisgICAgICBlbHNlCisgICAgICAgIHIuZWxlbXNbci5uZWxlbSsrXSA9IGUucDsK KyAgICAgIGkgPSBlLnNldF9pbmRleDsKKyAgICAgIGlmIChpZHNbaV0gIT0gKHNpemVfdCkgLTEp CisgICAgICAgIHsKKyAgICAgICAgICBoZWFwX2VsZW0gZTIgPSB7IHNldHNbaV0uZWxlbXNbaWRz W2ldXSwgaSB9OworICAgICAgICAgIGhlYXBfcmVtb3ZlX3RvcF9hbmRfYWRkIChoZWFwLCBoZWFw X3NpemUsIGUyKTsKKyAgICAgICAgICArK2lkc1tpXTsKKyAgICAgICAgICBpZiAoaWRzW2ldID09 IHNldHNbaV0ubmVsZW0pCisgICAgICAgICAgICBpZHNbaV0gPSAoc2l6ZV90KSAtMTsKKyAgICAg ICAgfQorICAgICAgZWxzZQorICAgICAgICB7CisgICAgICAgICAgaGVhcF9yZW1vdmVfdG9wICho ZWFwLCAmaGVhcF9zaXplKTsKKyAgICAgICAgfQorICAgIH0KKyAgKnJlc3VsdCA9IHI7CisgIGZy ZWUgKGlkcyk7CisgIGZyZWUgKGhlYXApOworfQorCitzdGF0aWMgdm9pZAorbWVyZ2VfbWFueV9z ZXRzIChwb3NpdGlvbl9zZXQgKnNldHMsIHNpemVfdCBuLCBwb3NpdGlvbl9zZXQgKnJlc3VsdCkK K3sKKyAgLyogb3B0aW1pemVkIHNvbHV0aW9ucyBmb3Igc3BlY2lhbC90cml2aWFsIGNhc2VzICov CisgIGlmIChuID09IDApCisgICAgcmVzdWx0LT5uZWxlbSA9IDA7CisgIGVsc2UgaWYgKG4gPT0g MSkKKyAgICBjb3B5ICgmc2V0c1swXSwgcmVzdWx0KTsKKyAgZWxzZSBpZiAobiA9PSAyKQorICAg IG1lcmdlICgmc2V0c1swXSwgJnNldHNbMV0sIHJlc3VsdCk7CisgIGVsc2UKKyAgICBoZWFwX21l cmdlX21hbnlfc2V0cyAoc2V0cywgbiwgcmVzdWx0KTsKK30KKwogLyogRmluZCB0aGUgaW5kZXgg b2YgdGhlIHN0YXRlIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGdpdmVuIHBvc2l0aW9uIHNldCB3aXRo CiAgICB0aGUgZ2l2ZW4gcHJlY2VkaW5nIGNvbnRleHQsIG9yIGNyZWF0ZSBhIG5ldyBzdGF0ZSBp ZiB0aGVyZSBpcyBubyBzdWNoCiAgICBzdGF0ZS4gIENvbnRleHQgdGVsbHMgd2hldGhlciB3ZSBn b3QgaGVyZSBvbiBhIG5ld2xpbmUgb3IgbGV0dGVyLiAgKi8KQEAgLTI1NTgsNiArMjY4MCw4IEBA IGRmYXN0YXRlIChzdGF0ZV9udW0gcywgc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHRyYW5zW10p CiAgIHN0YXRlX251bSBzdGF0ZV9uZXdsaW5lOyAgICAgIC8qIE5ldyBzdGF0ZSBvbiBhIG5ld2xp bmUgdHJhbnNpdGlvbi4gICovCiAgIHN0YXRlX251bSBzdGF0ZV9sZXR0ZXI7ICAgICAgIC8qIE5l dyBzdGF0ZSBvbiBhIGxldHRlciB0cmFuc2l0aW9uLiAgKi8KICAgYm9vbCBuZXh0X2lzbnRfMXN0 X2J5dGUgPSBmYWxzZTsgLyogRmxhZyBpZiB3ZSBjYW4ndCBhZGQgc3RhdGUwLiAgKi8KKyAgcG9z aXRpb25fc2V0ICpzZXRzID0gMDsgICAgICAgLyogVGVtcG9yYXJ5IGFycmF5IG9mIHNldHMsIHRv IHBhc3MgbWFueSBzZXRzIHRvIG1lcmdlIGZ1bmN0aW9uICovCisgIHNpemVfdCBzZXRzX2FsbG9j ID0gMDsgICAgICAgIC8qIFNldHMgYXJyYXkgY2FwYWNpdHkgICAqLwogICBzaXplX3QgaSwgaiwg azsKIAogICB6ZXJvc2V0IChtYXRjaGVzKTsKQEAgLTI3MDYsMTMgKzI4MzAsMTEgQEAgZGZhc3Rh dGUgKHN0YXRlX251bSBzLCBzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNbXSkKIAogICBm b3IgKGkgPSAwOyBpIDwgbmdycHM7ICsraSkKICAgICB7Ci0gICAgICBmb2xsb3dzLm5lbGVtID0g MDsKLQotICAgICAgLyogRmluZCB0aGUgdW5pb24gb2YgdGhlIGZvbGxvd3Mgb2YgdGhlIHBvc2l0 aW9ucyBvZiB0aGUgZ3JvdXAuCi0gICAgICAgICBUaGlzIGlzIGEgaGlkZW91c2x5IGluZWZmaWNp ZW50IGxvb3AuICBGaXggaXQgc29tZWRheS4gICovCisgICAgICAvKiBGaW5kIHRoZSB1bmlvbiBv ZiB0aGUgZm9sbG93cyBvZiB0aGUgcG9zaXRpb25zIG9mIHRoZSBncm91cC4gICovCisgICAgICBz ZXRzID0gbWF5YmVfcmVhbGxvYyAoc2V0cywgZ3Jwc1tpXS5uZWxlbSwgJnNldHNfYWxsb2MsIHNp emVvZiAqc2V0cyk7CiAgICAgICBmb3IgKGogPSAwOyBqIDwgZ3Jwc1tpXS5uZWxlbTsgKytqKQot ICAgICAgICBmb3IgKGsgPSAwOyBrIDwgZC0+Zm9sbG93c1tncnBzW2ldLmVsZW1zW2pdXS5uZWxl bTsgKytrKQotICAgICAgICAgIGluc2VydCAoZC0+Zm9sbG93c1tncnBzW2ldLmVsZW1zW2pdXS5l bGVtc1trXSwgJmZvbGxvd3MpOworICAgICAgICBzZXRzW2pdID0gZC0+Zm9sbG93c1tncnBzW2ld LmVsZW1zW2pdXTsKKyAgICAgIG1lcmdlX21hbnlfc2V0cyAoc2V0cywgZ3Jwc1tpXS5uZWxlbSwg JmZvbGxvd3MpOwogCiAgICAgICBpZiAoZC0+bXVsdGlieXRlKQogICAgICAgICB7Cg== --------_5368F0910000000028BF_MULTIPART_MIXED_-- From unknown Mon Jun 23 07:48:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15191: faster DFA.C state merge Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Wed, 07 May 2014 14:52:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 15191 X-GNU-PR-Package: grep X-GNU-PR-Keywords: moreinfo patch To: 15191@debbugs.gnu.org Cc: Paul Eggert Received: via spool by 15191-submit@debbugs.gnu.org id=B15191.139947429018077 (code B ref 15191); Wed, 07 May 2014 14:52:02 +0000 Received: (at 15191) by debbugs.gnu.org; 7 May 2014 14:51:30 +0000 Received: from localhost ([127.0.0.1]:54646 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wi3Bx-0004hU-Ro for submit@debbugs.gnu.org; Wed, 07 May 2014 10:51:30 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:54488) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wi3Bs-0004hC-S4 for 15191@debbugs.gnu.org; Wed, 07 May 2014 10:51:26 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id 58BB3802C1 for <15191@debbugs.gnu.org>; Wed, 7 May 2014 23:51:22 +0900 (JST) Received: from mail05.kcn.ne.jp ([61.86.6.184]) by imp01 with bizsmtp id z2rN1n0093yDdWd012rNVm; Wed, 07 May 2014 23:51:22 +0900 X-OrgRCPT: 15191@debbugs.gnu.org Received: from [10.120.1.62] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail05.kcn.ne.jp (Postfix) with ESMTPA id DD7447D009F; Wed, 7 May 2014 23:51:21 +0900 (JST) Date: Wed, 07 May 2014 23:51:20 +0900 From: Norihiro Tanaka In-Reply-To: <20140506233412.289F.27F6AC2D@kcn.ne.jp> References: <521AAEB3.70909@gmail.com> <20140506233412.289F.27F6AC2D@kcn.ne.jp> Message-Id: <20140507235113.2E18.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_536A443A000000002E14_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_536A443A000000002E14_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit As far as I examined a cause of slowness, it seems that it's caused by not state merge but dfamust. Although I'm suspicious of memory allocations in dfamust, I don't still have any ideas to fix them. I tried an attachment, but it became more and more slowdown. --------_536A443A000000002E14_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8"; name="0001-dfa-efficient-memory-allocation.patch" Content-Disposition: attachment; filename="0001-dfa-efficient-memory-allocation.patch" Content-Transfer-Encoding: base64 RnJvbSA3ZjlmNTY4NDllMWJhYjhkMGYzNzEwNjM4YWRjMTExZTNjY2VmM2ZmIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBXZWQsIDcgTWF5IDIwMTQgMTQ6MTU6MDEgKzA5MDAKU3ViamVjdDogW1BBVENIXSBkZmE6 IGVmZmljaWVudCBtZW1vcnkgYWxsb2NhdGlvbgoKKiBzcmMvZGZhLmMgKHN0cnVjdCBtdXN0KTog RGVmaW5lIG5ldyBtZW1iZXIgYG5leHQnLgooYWxsb2NtdXN0KTogQ29uc2lkZXIgdGhlIHJldXNl IG9mIG11c3QuCihkZmFtdXN0KTogRG9uJ3QgZGVhbGxvY2F0ZSBtdXN0IHdpdGggQ0FUIG9yIE9S LgotLS0KIHNyYy9kZmEuYyB8IDUzICsrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysr KystLS0tLS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMzcgaW5zZXJ0aW9ucygrKSwgMTYg ZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2RmYS5jIGIvc3JjL2RmYS5jCmluZGV4IGZj MmFjZGMuLmRlZTNmZWQgMTAwNjQ0Ci0tLSBhL3NyYy9kZmEuYworKysgYi9zcmMvZGZhLmMKQEAg LTM4NTIsMTIgKzM4NTIsMjkgQEAgc3RydWN0IG11c3QKICAgYm9vbCBiZWdsaW5lOwogICBib29s IGVuZGxpbmU7CiAgIG11c3QgKnByZXY7CisgIG11c3QgKm5leHQ7CiB9OwogCitzdGF0aWMgdm9p ZAorcmVzZXRtdXN0IChtdXN0ICptcCkKK3sKKyAgZnJlZWxpc3QgKG1wLT5pbik7CisgIG1wLT5p blswXSA9IE5VTEw7CisgIG1wLT5sZWZ0WzBdID0gbXAtPnJpZ2h0WzBdID0gbXAtPmlzWzBdID0g J1wwJzsKKyAgbXAtPmJlZ2xpbmUgPSBmYWxzZTsKKyAgbXAtPmVuZGxpbmUgPSBmYWxzZTsKK30K Kwogc3RhdGljIG11c3QgKgogYWxsb2NtdXN0IChtdXN0ICptcCkKIHsKLSAgbXVzdCAqbmV3X21w ID0geG1hbGxvYyAoc2l6ZW9mICpuZXdfbXApOworICBtdXN0ICpuZXdfbXA7CisgIGlmIChtcCAm JiBtcC0+bmV4dCkKKyAgICB7CisgICAgICByZXNldG11c3QgKG1wLT5uZXh0KTsKKyAgICAgIHJl dHVybiBtcC0+bmV4dDsKKyAgICB9CisgIG5ld19tcCA9IHhtYWxsb2MgKHNpemVvZiAqbmV3X21w KTsKICAgbmV3X21wLT5pbiA9IHh6YWxsb2MgKHNpemVvZiAqbmV3X21wLT5pbik7CiAgIG5ld19t cC0+bGVmdCA9IHh6YWxsb2MgKDIpOwogICBuZXdfbXAtPnJpZ2h0ID0geHphbGxvYyAoMik7CkBA IC0zODY1LDIwICszODgyLDEzIEBAIGFsbG9jbXVzdCAobXVzdCAqbXApCiAgIG5ld19tcC0+YmVn bGluZSA9IGZhbHNlOwogICBuZXdfbXAtPmVuZGxpbmUgPSBmYWxzZTsKICAgbmV3X21wLT5wcmV2 ID0gbXA7CisgIG5ld19tcC0+bmV4dCA9IE5VTEw7CisgIGlmIChtcCkKKyAgICBtcC0+bmV4dCA9 IG5ld19tcDsKICAgcmV0dXJuIG5ld19tcDsKIH0KIAogc3RhdGljIHZvaWQKLXJlc2V0bXVzdCAo bXVzdCAqbXApCi17Ci0gIGZyZWVsaXN0IChtcC0+aW4pOwotICBtcC0+aW5bMF0gPSBOVUxMOwot ICBtcC0+bGVmdFswXSA9IG1wLT5yaWdodFswXSA9IG1wLT5pc1swXSA9ICdcMCc7Ci0gIG1wLT5i ZWdsaW5lID0gZmFsc2U7Ci0gIG1wLT5lbmRsaW5lID0gZmFsc2U7Ci19Ci0KLXN0YXRpYyB2b2lk CiBmcmVlbXVzdCAobXVzdCAqbXApCiB7CiAgIGZyZWVsaXN0IChtcC0+aW4pOwpAQCAtMzk2Nyw3 ICszOTc3LDYgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkKICAgICAgICAgICAgIGZyZWVsaXN0 IChsbXAtPmluKTsKICAgICAgICAgICAgIGZyZWUgKGxtcC0+aW4pOwogICAgICAgICAgICAgbG1w LT5pbiA9IG5ldzsKLSAgICAgICAgICAgIGZyZWVtdXN0IChybXApOwogICAgICAgICAgIH0KICAg ICAgICAgICBicmVhazsKIApAQCAtNDAyNyw3ICs0MDM2LDYgQEAgZGZhbXVzdCAoc3RydWN0IGRm YSAqZCkKICAgICAgICAgICAgICAgICBsbXAtPmJlZ2xpbmUgPSBmYWxzZTsKICAgICAgICAgICAg ICAgICBsbXAtPmVuZGxpbmUgPSBmYWxzZTsKICAgICAgICAgICAgICAgfQotICAgICAgICAgICAg ZnJlZW11c3QgKHJtcCk7CiAgICAgICAgICAgfQogICAgICAgICAgIGJyZWFrOwogCkBAIC00MDc4 LDExICs0MDg2LDI0IEBAIGRvbmU6CiAgICAgICBkLT5tdXN0cyA9IGRtOwogICAgIH0KIAotICB3 aGlsZSAobXApCisgIGlmIChtcCkKICAgICB7Ci0gICAgICBtdXN0ICpwcmV2ID0gbXAtPnByZXY7 CisgICAgICBtdXN0ICptcF90bXA7CisgICAgICBtcF90bXAgPSBtcC0+cHJldjsKKyAgICAgIHdo aWxlIChtcF90bXApCisgICAgICAgIHsKKyAgICAgICAgICBtdXN0ICpwcmV2ID0gbXBfdG1wLT5w cmV2OworICAgICAgICAgIGZyZWVtdXN0IChtcF90bXApOworICAgICAgICAgIG1wX3RtcCA9IHBy ZXY7CisgICAgICAgIH0KKyAgICAgIG1wX3RtcCA9IG1wLT5uZXh0OworICAgICAgd2hpbGUgKG1w X3RtcCkKKyAgICAgICAgeworICAgICAgICAgIG11c3QgKm5leHQgPSBtcF90bXAtPm5leHQ7Cisg ICAgICAgICAgZnJlZW11c3QgKG1wX3RtcCk7CisgICAgICAgICAgbXBfdG1wID0gbmV4dDsKKyAg ICAgICAgfQogICAgICAgZnJlZW11c3QgKG1wKTsKLSAgICAgIG1wID0gcHJldjsKICAgICB9CiB9 CiAKLS0gCjEuOS4yCgo= --------_536A443A000000002E14_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Sat May 10 16:48:06 2014 Received: (at control) by debbugs.gnu.org; 10 May 2014 20:48:06 +0000 Received: from localhost ([127.0.0.1]:58415 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WjEBh-0008Ju-IF for submit@debbugs.gnu.org; Sat, 10 May 2014 16:48:05 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:33151) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WjEBe-0008JL-Al for control@debbugs.gnu.org; Sat, 10 May 2014 16:48:03 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id B3AD539E8013 for ; Sat, 10 May 2014 13:47:56 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GDFcIZszzwXI for ; Sat, 10 May 2014 13:47:48 -0700 (PDT) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 3BA88A6000C for ; Sat, 10 May 2014 13:47:48 -0700 (PDT) Message-ID: <536E9073.4090906@cs.ucla.edu> Date: Sat, 10 May 2014 13:47:47 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: control@debbugs.gnu.org Subject: mark some grep bug reports as wishlist items Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.0 (---) severity 15191 wishlist severity 17381 wishlist thanks These reports aren't about bugs in grep, just potential improvements and/or better collaboration with gawk. From unknown Mon Jun 23 07:48:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15191: faster DFA.C state merge Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 17 May 2014 02:04:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 15191 X-GNU-PR-Package: grep X-GNU-PR-Keywords: moreinfo patch To: 15191@debbugs.gnu.org Cc: Paul Eggert , Ivan Yanikov Received: via spool by 15191-submit@debbugs.gnu.org id=B15191.140029220631393 (code B ref 15191); Sat, 17 May 2014 02:04:02 +0000 Received: (at 15191) by debbugs.gnu.org; 17 May 2014 02:03:26 +0000 Received: from localhost ([127.0.0.1]:50997 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WlTy9-0008AE-CI for submit@debbugs.gnu.org; Fri, 16 May 2014 22:03:26 -0400 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:53101) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WlTy5-00089u-8I for 15191@debbugs.gnu.org; Fri, 16 May 2014 22:03:22 -0400 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id 0C8036E110 for <15191@debbugs.gnu.org>; Sat, 17 May 2014 11:03:15 +0900 (JST) Received: from mail09.kcn.ne.jp ([61.86.6.188]) by imp02 with bizsmtp id 2q3F1o00743QJrh01q3FEX; Sat, 17 May 2014 11:03:15 +0900 X-OrgRCPT: 15191@debbugs.gnu.org Received: from [10.120.1.33] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail09.kcn.ne.jp (Postfix) with ESMTPA id B49361BD00C8; Sat, 17 May 2014 11:03:14 +0900 (JST) Date: Sat, 17 May 2014 11:03:13 +0900 From: Norihiro Tanaka In-Reply-To: <20140506233412.289F.27F6AC2D@kcn.ne.jp> References: <521AAEB3.70909@gmail.com> <20140506233412.289F.27F6AC2D@kcn.ne.jp> Message-Id: <20140517110302.6755.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5376BF92000000006797_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_5376BF92000000006797_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I tried it on grep-2.14, and I confirmed that the patch is effective certainly. However, I see that it's fixed in bug#17377. $ env LC_ALL=C time -p ../grep-2.19/src/grep -E -f regex.re input_lines.txt grep-2.14 before: real 7.66 user 7.56 sys 0.09 after : real 2.06 user 1.96 sys 0.09 grep-2.18.146-ebf3 before: real 1.59 user 1.50 sys 0.08 after : real 1.99 user 1.86 sys 0.12 If my rewriting of the patch is right, it causes slowdown rather by building heap. Norihiro --------_5376BF92000000006797_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="dfa_faster_state_merge.diff" Content-Disposition: attachment; filename="dfa_faster_state_merge.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9kZmEuYyBiL3NyYy9kZmEuYwppbmRleCAzYzljYjc1Li45OTFiMTc2 IDEwMDY0NAotLS0gYS9zcmMvZGZhLmMKKysrIGIvc3JjL2RmYS5jCkBAIC0yMDczLDYgKzIwNzMs MTMzIEBAIG1lcmdlIChwb3NpdGlvbl9zZXQgY29uc3QgKnMxLCBwb3NpdGlvbl9zZXQgY29uc3Qg KnMyLCBwb3NpdGlvbl9zZXQgKiBtKQogICAgIG0tPmVsZW1zW20tPm5lbGVtKytdID0gczItPmVs ZW1zW2orK107CiB9CiAKKy8qIE1lcmdlIGltcGxlbWVudGF0aW9uIG9mIHNvcnRlZCBzZXRzLCB0 aGVuIG51bWJlciBvZiBzZXRzIHNtb3JlIHRoYW4gMi4KKyAqIFByaW9yaXR5IHF1ZXVlIGFrYSAn aGVhcCcgZGF0YSBzdHJ1Y3R1cmUgdXNlZCB0byBzZWxlY3QgbWF4aW11bSBvZgorICogbWFueSBl bGVtZW50cyAqLworCit0eXBlZGVmIHN0cnVjdCB7CisgIHBvc2l0aW9uIHA7CisgIHNpemVfdCBz ZXRfaW5kZXg7ICAgLyogUmVtZW1iZXIgd2hpY2ggc2V0IHRoaXMgZWxlbWVudCB3YXMgdGFrZW4g ZnJvbS4gICovCit9IGhlYXBfZWxlbTsKKworc3RhdGljIHZvaWQKK2hlYXBfYWRkIChoZWFwX2Vs ZW0gKmhlYXAsIHNpemVfdCAqaGVhcF9zaXplLCBoZWFwX2VsZW0gZSkKK3sKKyAgc2l6ZV90IGkg PSAqaGVhcF9zaXplOworICB3aGlsZSAoaSkKKyAgICB7CisgICAgICBzaXplX3QgcGFyZW50ID0g KGktMSkgLyAyOworICAgICAgaWYgKGUucC5pbmRleCA8IGhlYXBbcGFyZW50XS5wLmluZGV4KQor ICAgICAgICBicmVhazsKKworICAgICAgaGVhcFtpXSA9IGhlYXBbcGFyZW50XTsKKyAgICAgIGkg PSBwYXJlbnQ7CisgICAgfQorICBoZWFwW2ldID0gZTsKKyAgKmhlYXBfc2l6ZSArPSAxOworfQor CitzdGF0aWMgdm9pZAoraGVhcF9yZW1vdmVfdG9wX2FuZF9hZGQgKGhlYXBfZWxlbSAqaGVhcCwg c2l6ZV90IGhlYXBfc2l6ZSwgaGVhcF9lbGVtIGUpCit7CisgIHNpemVfdCBpID0gMDsKKyAgc2l6 ZV90IGxjaGlsZCAgPSAyKmkgKyAxOworICBzaXplX3QgbiA9IGhlYXBfc2l6ZTsKKyAgd2hpbGUg KGxjaGlsZCA8IG4pCisgICAgeworICAgICAgc2l6ZV90IHJjaGlsZCA9IGxjaGlsZCArIDE7Cisg ICAgICBzaXplX3QgbmV4dGNoaWxkID0gbGNoaWxkOworICAgICAgaWYgKHJjaGlsZCA8IG4gJiYg aGVhcFtsY2hpbGRdLnAuaW5kZXggPCBoZWFwW3JjaGlsZF0ucC5pbmRleCkKKyAgICAgICAgbmV4 dGNoaWxkID0gcmNoaWxkOworICAgICAgaWYgKGUucC5pbmRleCA+PSBoZWFwW25leHRjaGlsZF0u cC5pbmRleCkKKyAgICAgICAgYnJlYWs7CisgICAgICBoZWFwW2ldID0gaGVhcFtuZXh0Y2hpbGRd OworICAgICAgaSA9IG5leHRjaGlsZDsKKyAgICAgIGxjaGlsZCA9IDIqaSArIDE7CisgICAgfQor ICBoZWFwW2ldID0gZTsKK30KKworCitzdGF0aWMgdm9pZAoraGVhcF9yZW1vdmVfdG9wIChoZWFw X2VsZW0gKmhlYXAsIHNpemVfdCAqaGVhcF9zaXplKQoreworICAqaGVhcF9zaXplIC09IDE7Cisg IGlmICgqaGVhcF9zaXplID09IDApCisgICAgcmV0dXJuOworICBoZWFwX3JlbW92ZV90b3BfYW5k X2FkZCAoaGVhcCwgKmhlYXBfc2l6ZSwgaGVhcFsqaGVhcF9zaXplXSk7Cit9CisKK3N0YXRpYyB2 b2lkCitoZWFwX21lcmdlX21hbnlfc2V0cyAocG9zaXRpb25fc2V0ICpzZXRzLCBzaXplX3Qgbiwg cG9zaXRpb25fc2V0ICpyZXN1bHQpCit7CisgIHNpemVfdCBoZWFwX3NpemUgPSAwOworICBwb3Np dGlvbl9zZXQgcjsgLyogZmFzdGVyIGFjY2VzcyB0byBsb2NhbCB2YXJpYWJsZXMgKi8KKyAgaGVh cF9lbGVtICpoZWFwID0gWE5NQUxMT0MgKG4sIGhlYXBfZWxlbSk7CisgIHNpemVfdCAqaWRzID0g WE5NQUxMT0MgKG4sIHNpemVfdCk7CisgIHNpemVfdCBzdW1fb2Zfc2l6ZXMgPSAwOworICBzaXpl X3QgaTsKKworICBmb3IgKGkgPSAwOyBpIDwgbjsgKytpKQorICAgIHsKKyAgICAgIHN1bV9vZl9z aXplcyArPSBzZXRzW2ldLm5lbGVtOworICAgICAgLyogc3BlY2lhbCB2YWx1ZSBmb3IgImVuZCBv ZiBzZXQiLCB0byByZWR1Y2UgZGVwZW5kZW50IG1lbW9yeQorICAgICAgICAgcmVhZHMuICAqLwor ICAgICAgaWRzW2ldID0gfihzaXplX3QpMDsKKyAgICAgIGlmIChzZXRzW2ldLm5lbGVtKQorICAg ICAgICB7CisgICAgICAgICAgaGVhcF9lbGVtIGUgPSB7IHNldHNbaV0uZWxlbXNbMF0sIGkgfTsK KyAgICAgICAgICBoZWFwX2FkZCAoaGVhcCwgJmhlYXBfc2l6ZSwgZSk7CisgICAgICAgICAgaWYg KHNldHNbaV0ubmVsZW0gPiAxKQorICAgICAgICAgICAgaWRzW2ldID0gMTsKKyAgICAgICAgfQor ICAgIH0KKworICBtYXliZV9yZWFsbG9jIChyZXN1bHQtPmVsZW1zLCBzdW1fb2Zfc2l6ZXMsICZy ZXN1bHQtPmFsbG9jLAorICAgICAgICAgICAgICAgICBzaXplb2YgKnJlc3VsdC0+ZWxlbXMpOyAK KyAgciA9ICpyZXN1bHQ7CisgIHIubmVsZW0gPSAwOworCisgIHdoaWxlIChoZWFwX3NpemUpCisg ICAgeworICAgICAgaGVhcF9lbGVtIGUgPSBoZWFwWzBdOworICAgICAgaWYgKHIubmVsZW0gJiYg ci5lbGVtc1tyLm5lbGVtLTFdLmluZGV4ID09IGUucC5pbmRleCkKKyAgICAgICAgci5lbGVtc1ty Lm5lbGVtLTFdLmNvbnN0cmFpbnQgfD0gZS5wLmNvbnN0cmFpbnQ7CisgICAgICBlbHNlCisgICAg ICAgIHIuZWxlbXNbci5uZWxlbSsrXSA9IGUucDsKKyAgICAgIGkgPSBlLnNldF9pbmRleDsKKyAg ICAgIGlmIChpZHNbaV0gIT0gfihzaXplX3QpMCkKKyAgICAgICAgeworICAgICAgICAgIGhlYXBf ZWxlbSBlMiA9IHsgc2V0c1tpXS5lbGVtc1tpZHNbaV1dLCBpIH07CisgICAgICAgICAgaGVhcF9y ZW1vdmVfdG9wX2FuZF9hZGQgKGhlYXAsIGhlYXBfc2l6ZSwgZTIpOworICAgICAgICAgICsraWRz W2ldOworICAgICAgICAgIGlmIChpZHNbaV0gPT0gc2V0c1tpXS5uZWxlbSkKKyAgICAgICAgICAg IGlkc1tpXSA9IH4oc2l6ZV90KTA7CisgICAgICAgIH0KKyAgICAgIGVsc2UKKyAgICAgICAgewor ICAgICAgICAgIGhlYXBfcmVtb3ZlX3RvcCAoaGVhcCwgJmhlYXBfc2l6ZSk7CisgICAgICAgIH0K KyAgICB9CisgICpyZXN1bHQgPSByOworICBmcmVlIChpZHMpOworICBmcmVlIChoZWFwKTsKK30K Kworc3RhdGljIHZvaWQKK21lcmdlX21hbnlfc2V0cyAocG9zaXRpb25fc2V0ICpzZXRzLCBzaXpl X3QgbiwgcG9zaXRpb25fc2V0ICpyZXN1bHQpCit7CisgIC8qIG9wdGltaXplZCBzb2x1dGlvbnMg Zm9yIHNwZWNpYWwvdHJpdmlhbCBjYXNlcyAqLworICBpZiAobiA9PSAwKQorICAgIHJlc3VsdC0+ bmVsZW0gPSAwOworICBlbHNlIGlmIChuID09IDEpCisgICAgY29weSAoJnNldHNbMF0sIHJlc3Vs dCk7CisgIGVsc2UgaWYgKG4gPT0gMikKKyAgICBtZXJnZSAoJnNldHNbMF0sICZzZXRzWzFdLCBy ZXN1bHQpOworICBlbHNlCisgICAgaGVhcF9tZXJnZV9tYW55X3NldHMoc2V0cywgbiwgcmVzdWx0 KTsKK30KKwogLyogRGVsZXRlIGEgcG9zaXRpb24gZnJvbSBhIHNldC4gICovCiBzdGF0aWMgdm9p ZAogZGVsZXRlIChwb3NpdGlvbiBwLCBwb3NpdGlvbl9zZXQgKiBzKQpAQCAtMjU3NCw2ICsyNzAx LDEwIEBAIGRmYXN0YXRlIChzdGF0ZV9udW0gcywgc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHRy YW5zW10pCiAgIHN0YXRlX251bSBzdGF0ZV9uZXdsaW5lOyAgICAgIC8qIE5ldyBzdGF0ZSBvbiBh IG5ld2xpbmUgdHJhbnNpdGlvbi4gICovCiAgIHN0YXRlX251bSBzdGF0ZV9sZXR0ZXI7ICAgICAg IC8qIE5ldyBzdGF0ZSBvbiBhIGxldHRlciB0cmFuc2l0aW9uLiAgKi8KICAgYm9vbCBuZXh0X2lz bnRfMXN0X2J5dGUgPSBmYWxzZTsgLyogV2UgY2FuJ3QgYWRkIHN0YXRlMC4gICovCisgIHBvc2l0 aW9uX3NldCAqc2V0cyA9IE5VTEw7ICAgIC8qIFRlbXBvcmFyeSBhcnJheSBvZiBzZXRzLCB0byBw YXNzIG1hbnkKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2V0cyB0byBtZXJn ZSBmdW5jdGlvbi4gICovCisgIHNpemVfdCBzZXRzX247ICAgICAgICAgICAgICAgIC8qIFNldHMg YXJyYXkgc2l6ZS4gICovCisgIHNpemVfdCBzZXRzX2FsbG9jID0gMDsgICAgICAgIC8qIFNldHMg YXJyYXkgY2FwYWNpdHkuICAqLwogICBzaXplX3QgaSwgaiwgazsKIAogICB6ZXJvc2V0IChtYXRj aGVzKTsKQEAgLTI3MjIsMTMgKzI4NTMsMTIgQEAgZGZhc3RhdGUgKHN0YXRlX251bSBzLCBzdHJ1 Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNbXSkKIAogICBmb3IgKGkgPSAwOyBpIDwgbmdycHM7 ICsraSkKICAgICB7Ci0gICAgICBmb2xsb3dzLm5lbGVtID0gMDsKLQotICAgICAgLyogRmluZCB0 aGUgdW5pb24gb2YgdGhlIGZvbGxvd3Mgb2YgdGhlIHBvc2l0aW9ucyBvZiB0aGUgZ3JvdXAuCi0g ICAgICAgICBUaGlzIGlzIGEgaGlkZW91c2x5IGluZWZmaWNpZW50IGxvb3AuICBGaXggaXQgc29t ZWRheS4gICovCisgICAgICAvKiBGaW5kIHRoZSB1bmlvbiBvZiB0aGUgZm9sbG93cyBvZiB0aGUg cG9zaXRpb25zIG9mIHRoZSBncm91cC4gICovCisgICAgICBzZXRzX24gPSBncnBzW2ldLm5lbGVt OworICAgICAgc2V0cyA9IG1heWJlX3JlYWxsb2MgKHNldHMsIHNldHNfbiwgJnNldHNfYWxsb2Ms IHNpemVvZiAqc2V0cyk7CiAgICAgICBmb3IgKGogPSAwOyBqIDwgZ3Jwc1tpXS5uZWxlbTsgKytq KQotICAgICAgICBmb3IgKGsgPSAwOyBrIDwgZC0+Zm9sbG93c1tncnBzW2ldLmVsZW1zW2pdXS5u ZWxlbTsgKytrKQotICAgICAgICAgIGluc2VydCAoZC0+Zm9sbG93c1tncnBzW2ldLmVsZW1zW2pd XS5lbGVtc1trXSwgJmZvbGxvd3MpOworICAgICAgICBzZXRzW2pdID0gZC0+Zm9sbG93c1tncnBz W2ldLmVsZW1zW2pdXTsKKyAgICAgIG1lcmdlX21hbnlfc2V0cyAoc2V0cywgc2V0c19uLCAmZm9s bG93cyk7CiAKICAgICAgIGlmIChkLT5tdWx0aWJ5dGUpCiAgICAgICAgIHsK --------_5376BF92000000006797_MULTIPART_MIXED_-- From unknown Mon Jun 23 07:48:42 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.503 (Entity 5.503) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Ivan Yanikov Subject: bug#15191: closed (Re: bug#15191: faster DFA.C state merge) Message-ID: References: <5376D686.3050308@cs.ucla.edu> <521AAEB3.70909@gmail.com> X-Gnu-PR-Message: they-closed 15191 X-Gnu-PR-Package: grep X-Gnu-PR-Keywords: moreinfo patch Reply-To: 15191@debbugs.gnu.org Date: Sat, 17 May 2014 03:26:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1400297162-9823-1" This is a multi-part message in MIME format... ------------=_1400297162-9823-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #15191: faster DFA.C state merge which was filed against the grep package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 15191@debbugs.gnu.org. --=20 15191: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D15191 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1400297162-9823-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 15191-done) by debbugs.gnu.org; 17 May 2014 03:25:13 +0000 Received: from localhost ([127.0.0.1]:51014 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WlVFI-0002Wk-TT for submit@debbugs.gnu.org; Fri, 16 May 2014 23:25:13 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:59171) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WlVFG-0002WO-5T for 15191-done@debbugs.gnu.org; Fri, 16 May 2014 23:25:10 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id B40B0A60063; Fri, 16 May 2014 20:25:03 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id liXKNVlWH8WP; Fri, 16 May 2014 20:24:55 -0700 (PDT) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 1390CA60001; Fri, 16 May 2014 20:24:55 -0700 (PDT) Message-ID: <5376D686.3050308@cs.ucla.edu> Date: Fri, 16 May 2014 20:24:54 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: Norihiro Tanaka , 15191-done@debbugs.gnu.org Subject: Re: bug#15191: faster DFA.C state merge References: <521AAEB3.70909@gmail.com> <20140506233412.289F.27F6AC2D@kcn.ne.jp> <20140517110302.6755.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140517110302.6755.27F6AC2D@kcn.ne.jp> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 15191-done Cc: Ivan Yanikov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.0 (---) Norihiro Tanaka wrote: > If my rewriting of the patch is right, it causes slowdown rather by > building heap. Thanks for checking it. I'll close this bug report, since it seems to have been fixed in a different way. ------------=_1400297162-9823-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 26 Aug 2013 06:57:19 +0000 Received: from localhost ([127.0.0.1]:56084 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VDqjj-00032M-CV for submit@debbugs.gnu.org; Mon, 26 Aug 2013 02:57:16 -0400 Received: from eggs.gnu.org ([208.118.235.92]:45702) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VDlZh-0002Ut-Im for submit@debbugs.gnu.org; Sun, 25 Aug 2013 21:26:35 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VDlZc-0007hG-JU for submit@debbugs.gnu.org; Sun, 25 Aug 2013 21:26:33 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50,FREEMAIL_FROM, T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:49871) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VDlZc-0007hC-Fl for submit@debbugs.gnu.org; Sun, 25 Aug 2013 21:26:28 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47417) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VDlZX-0002ob-Md for bug-grep@gnu.org; Sun, 25 Aug 2013 21:26:28 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VDlZR-0007g0-6Y for bug-grep@gnu.org; Sun, 25 Aug 2013 21:26:23 -0400 Received: from mail-la0-x232.google.com ([2a00:1450:4010:c03::232]:48471) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VDlZQ-0007fk-RO for bug-grep@gnu.org; Sun, 25 Aug 2013 21:26:17 -0400 Received: by mail-la0-f50.google.com with SMTP id es20so1787036lab.37 for ; Sun, 25 Aug 2013 18:26:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type; bh=k/92xJo/xBy5sizD8IKUY1kXlUa/yCKixJi6fMkCiAU=; b=L9XtSTX+5q0sCCZ7KlG8iefSnGNE7ER1jndaZnLUo6XUlqTlqhiYkTkxRkpZ7vJQku jPOS0ssvh3lzXmh9NXyat3Wa5JqV1ZIg812fGhVI8Lyk/Qae/demtFrR13nPqEbLuduv eoSLZbvZ4Y6ps2si2sbHKYhLXuuhPbq5NLO9nQQzbKkha+TGfg50AiVAgr/olgWxYIYR 1KY0ECfPSEW2gg7KB2CwD88AVtjWsUu5b/AfFco6SjOzLdk5rW+os78fT8CZSUoiNnQf H3YnCMxXlsZfislUm2DsFlkty2ePNJ5I9RBz3k8B97HQpOhxW5CKRXzumB9jWPECVbXx j+CQ== X-Received: by 10.112.51.166 with SMTP id l6mr10556562lbo.5.1377480375328; Sun, 25 Aug 2013 18:26:15 -0700 (PDT) Received: from [192.168.1.4] (ppp91-76-191-147.pppoe.mtu-net.ru. [91.76.191.147]) by mx.google.com with ESMTPSA id ap7sm4579513lac.10.1969.12.31.16.00.00 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 25 Aug 2013 18:26:14 -0700 (PDT) Message-ID: <521AAEB3.70909@gmail.com> Date: Mon, 26 Aug 2013 05:26:11 +0400 From: Ivan Yanikov User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 MIME-Version: 1.0 To: Paul Eggert Subject: Re: faster DFA.C state merge References: <52195675.6030606@gmail.com> <5219AC0D.7040806@cs.ucla.edu> In-Reply-To: <5219AC0D.7040806@cs.ucla.edu> Content-Type: multipart/mixed; boundary="------------010006080605040308050001" X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -2.4 (--) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Mon, 26 Aug 2013 02:57:13 -0400 Cc: bug-grep@gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.4 (--) This is a multi-part message in MIME format. --------------010006080605040308050001 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit I have polished the patch ( faster code for simple cases of merging 2 or 1 sets, fixes of code style, like fancy 2+2 indentation, important fix: memory leaks under valgrind - I improperly returned array from a function ) New patch available on URL https://gist.github.com/dobrokot/6337339 and included as attach > One thing that'd help would be a test case that illustrates the need for the patch. Not sure how to properly to send test-case, and how to reference grep compiled old/new binary. I had put it on URL http://dobrokot.ru/dump/slow_dfa_merge.2013-08-26.tar.gz I can send it in a attach for a "history", if binary/large attaches are allowed in maillists. Real regex contains sensitive private data, and it's huge. So I had little obfuscated it and reduce to kilobytes. The runtime difference is not so great as in real example (1 to 100), but still large ( 2-3 times faster ). Times for new/old version: 2.3sec / 8.7sec > I assume you're willing to assign copyright to the FSF for the change? (I can send you copies of the paperwork, if so.) You mean, I should somewhere explicitly state, that I am agree with GPL and give FSF rights to distribute and use the code from patch? If so, I am surely agree with the license, and (proudly) give the permission to use/distribute code from my patch :) Or you mean some modification of authorship lines in the AUTHORS/THANKS and beginning of dfa.c, which should contain my name now ? Which paperwork do you mean? Real paper which I should sign with pen and ink? Thanks for attention, Ivan Yanikov. On 25.08.2013 11:02, Paul Eggert wrote: > Ivan Yanikov wrote: >> How I can properly send/commit it for review? > You've already done that, sort of, with the pointers > to the patch. One thing that'd help would be a test > case that illustrates the need for the patch. Also, > I assume you're willing to assign copyright to the > FSF for the change? (I can send you copies of the > paperwork, if so.) > --------------010006080605040308050001 Content-Type: text/plain; charset=windows-1251; name="grep-2.14-faster-dfa-merger.diff" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="grep-2.14-faster-dfa-merger.diff" SW5kZXg6IGRmYS5jDQo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09DQotLS0gZGZhLmMJKHJldmlzaW9uIGdyZXAt Mi4xNC1mYXN0ZXItZGZhKQ0KKysrIGRmYS5jCShyZXZpc2lvbiBncmVwLTIuMTQpDQpAQCAt MTk5Miw2ICsxOTkyLDEzMyBAQA0KICAgICAgIHMtPmVsZW1zW2ldID0gcy0+ZWxlbXNbaSAr IDFdOw0KIH0NCiANCisvKiBNZXJnZSBpbXBsZW1lbnRhdGlvbiBvZiBzb3J0ZWQgc2V0cywg dGhlbiBudW1iZXIgb2Ygc2V0cyBzbW9yZSB0aGFuIDIuDQorICAgUHJpb3JpdHkgcXVldWUg YWthICdoZWFwJyBkYXRhIHN0cnVjdHVyZSB1c2VkIHRvIHNlbGVjdCBtYXhpbXVtIG9mDQor ICAgbWFueSBlbGVtZW50cyAqLw0KKw0KK3R5cGVkZWYgc3RydWN0IHsNCisgIHBvc2l0aW9u IHA7DQorICBzaXplX3Qgc2V0X2luZGV4OyAvKiBSZW1lbWJlciB3aGljaCBzZXQgdGhpcyBl bGVtZW50IHdhcyB0YWtlbiBmcm9tICovDQorfSBoZWFwX2VsZW07DQorDQorDQorc3RhdGlj IHZvaWQNCitoZWFwX2FkZCAoaGVhcF9lbGVtICpoZWFwLCBzaXplX3QgKmhlYXBfc2l6ZSwg aGVhcF9lbGVtIGUpDQorew0KKyAgc2l6ZV90IGkgPSAqaGVhcF9zaXplOw0KKyAgd2hpbGUg KGkpDQorICAgIHsNCisgICAgICBzaXplX3QgcGFyZW50ID0gKGktMSkgLyAyOw0KKyAgICAg IGlmIChlLnAuaW5kZXggPCBoZWFwW3BhcmVudF0ucC5pbmRleCkNCisgICAgICAgIGJyZWFr Ow0KKw0KKyAgICAgIGhlYXBbaV0gPSBoZWFwW3BhcmVudF07DQorICAgICAgaSA9IHBhcmVu dDsNCisgICAgfQ0KKyAgaGVhcFtpXSA9IGU7DQorICAqaGVhcF9zaXplICs9IDE7DQorfQ0K Kw0KK3N0YXRpYyB2b2lkDQoraGVhcF9yZW1vdmVfdG9wX2FuZF9hZGQgKGhlYXBfZWxlbSAq aGVhcCwgc2l6ZV90IGhlYXBfc2l6ZSwgaGVhcF9lbGVtIGUpDQorew0KKyAgc2l6ZV90IGkg PSAwOw0KKyAgc2l6ZV90IGxjaGlsZCAgPSAyKmkgKyAxOw0KKyAgc2l6ZV90IG4gPSBoZWFw X3NpemU7DQorICB3aGlsZSAobGNoaWxkIDwgbikNCisgICAgew0KKyAgICAgIHNpemVfdCBy Y2hpbGQgPSBsY2hpbGQgKyAxOw0KKyAgICAgIHNpemVfdCBuZXh0Y2hpbGQgPSBsY2hpbGQ7 DQorICAgICAgaWYgKHJjaGlsZCA8IG4gJiYgaGVhcFtsY2hpbGRdLnAuaW5kZXggPCBoZWFw W3JjaGlsZF0ucC5pbmRleCkNCisgICAgICAgIG5leHRjaGlsZCA9IHJjaGlsZDsNCisgICAg ICBpZiAoZS5wLmluZGV4ID49IGhlYXBbbmV4dGNoaWxkXS5wLmluZGV4KQ0KKyAgICAgICAg YnJlYWs7DQorICAgICAgaGVhcFtpXSA9IGhlYXBbbmV4dGNoaWxkXTsNCisgICAgICBpID0g bmV4dGNoaWxkOw0KKyAgICAgIGxjaGlsZCA9IDIqaSArIDE7DQorICAgIH0NCisgIGhlYXBb aV0gPSBlOw0KK30NCisNCisNCitzdGF0aWMgdm9pZA0KK2hlYXBfcmVtb3ZlX3RvcCAoaGVh cF9lbGVtICpoZWFwLCBzaXplX3QgKmhlYXBfc2l6ZSkNCit7DQorICAqaGVhcF9zaXplIC09 IDE7DQorICBpZiAoKmhlYXBfc2l6ZSA9PSAwKQ0KKyAgICByZXR1cm47DQorICBoZWFwX3Jl bW92ZV90b3BfYW5kX2FkZCAoaGVhcCwgKmhlYXBfc2l6ZSwgaGVhcFsqaGVhcF9zaXplXSk7 DQorfQ0KKw0KK3N0YXRpYyB2b2lkDQoraGVhcF9tZXJnZV9tYW55X3NldHMgKHBvc2l0aW9u X3NldCAqc2V0cywgc2l6ZV90IG4sIHBvc2l0aW9uX3NldCAqcmVzdWx0KQ0KK3sNCisgIHNp emVfdCBoZWFwX3NpemUgPSAwOw0KKyAgcG9zaXRpb25fc2V0IHI7IC8qIGZhc3RlciBhY2Nl c3MgdG8gbG9jYWwgdmFyaWFibGVzICovDQorICBoZWFwX2VsZW0gKmhlYXAgPSBYTk1BTExP QyAobiwgaGVhcF9lbGVtKTsNCisgIHNpemVfdCAqaWRzID0gWE5NQUxMT0MgKG4sIHNpemVf dCk7DQorICBzaXplX3Qgc3VtX29mX3NpemVzID0gMDsNCisgIHNpemVfdCBpOw0KKw0KKyAg Zm9yIChpID0gMDsgaSA8IG47ICsraSkNCisgICAgew0KKyAgICAgIHN1bV9vZl9zaXplcyAr PSBzZXRzW2ldLm5lbGVtOw0KKyAgICAgIC8qIHNwZWNpYWwgdmFsdWUgZm9yICJlbmQgb2Yg c2V0IiwgdG8gcmVkdWNlDQorICAgICAgICAgZGVwZW5kZW50IG1lbW9yeSByZWFkcyAqLw0K KyAgICAgIGlkc1tpXSA9IH4oc2l6ZV90KTA7DQorICAgICAgaWYgKHNldHNbaV0ubmVsZW0p DQorICAgICAgICB7DQorICAgICAgICAgIGhlYXBfZWxlbSBlID0geyBzZXRzW2ldLmVsZW1z WzBdLCBpIH07DQorICAgICAgICAgIGhlYXBfYWRkIChoZWFwLCAmaGVhcF9zaXplLCBlKTsN CisgICAgICAgICAgaWYgKHNldHNbaV0ubmVsZW0gPiAxKQ0KKyAgICAgICAgICAgIGlkc1tp XSA9IDE7DQorICAgICAgICB9DQorICAgIH0NCisNCisgIFJFQUxMT0NfSUZfTkVDRVNTQVJZ KHJlc3VsdC0+ZWxlbXMsIHJlc3VsdC0+YWxsb2MsIHN1bV9vZl9zaXplcyk7DQorICByID0g KnJlc3VsdDsNCisgIHIubmVsZW0gPSAwOw0KKw0KKyAgd2hpbGUgKGhlYXBfc2l6ZSkNCisg ICAgew0KKyAgICAgIGhlYXBfZWxlbSBlID0gaGVhcFswXTsNCisgICAgICBpZiAoci5uZWxl bSAmJiByLmVsZW1zW3IubmVsZW0tMV0uaW5kZXggPT0gZS5wLmluZGV4KQ0KKyAgICAgICAg ci5lbGVtc1tyLm5lbGVtLTFdLmNvbnN0cmFpbnQgfD0gZS5wLmNvbnN0cmFpbnQ7DQorICAg ICAgZWxzZQ0KKyAgICAgICAgci5lbGVtc1tyLm5lbGVtKytdID0gZS5wOw0KKyAgICAgIGkg PSBlLnNldF9pbmRleDsNCisgICAgICBpZiAoaWRzW2ldICE9IH4oc2l6ZV90KTApDQorICAg ICAgICB7DQorICAgICAgICAgIGhlYXBfZWxlbSBlMiA9IHsgc2V0c1tpXS5lbGVtc1tpZHNb aV1dLCBpIH07DQorICAgICAgICAgIGhlYXBfcmVtb3ZlX3RvcF9hbmRfYWRkIChoZWFwLCBo ZWFwX3NpemUsIGUyKTsNCisgICAgICAgICAgKytpZHNbaV07DQorICAgICAgICAgIGlmIChp ZHNbaV0gPT0gc2V0c1tpXS5uZWxlbSkNCisgICAgICAgICAgICBpZHNbaV0gPSB+KHNpemVf dCkwOw0KKyAgICAgICAgfQ0KKyAgICAgIGVsc2UNCisgICAgICAgIHsNCisgICAgICAgICAg aGVhcF9yZW1vdmVfdG9wIChoZWFwLCAmaGVhcF9zaXplKTsNCisgICAgICAgIH0NCisgICAg fQ0KKyAgKnJlc3VsdCA9IHI7DQorICBmcmVlIChpZHMpOw0KKyAgZnJlZSAoaGVhcCk7DQor fQ0KKw0KK3N0YXRpYyB2b2lkDQorbWVyZ2VfbWFueV9zZXRzIChwb3NpdGlvbl9zZXQgKnNl dHMsIHNpemVfdCBuLCBwb3NpdGlvbl9zZXQgKnJlc3VsdCkNCit7DQorICAvKiBvcHRpbWl6 ZWQgc29sdXRpb25zIGZvciBzcGVjaWFsL3RyaXZpYWwgY2FzZXMgKi8NCisgIGlmIChuID09 IDApDQorICAgIHJlc3VsdC0+bmVsZW0gPSAwOw0KKyAgZWxzZSBpZiAobiA9PSAxKQ0KKyAg ICBjb3B5ICgmc2V0c1swXSwgcmVzdWx0KTsNCisgIGVsc2UgaWYgKG4gPT0gMikNCisgICAg bWVyZ2UgKCZzZXRzWzBdLCAmc2V0c1sxXSwgcmVzdWx0KTsNCisgIGVsc2UNCisgICAgaGVh cF9tZXJnZV9tYW55X3NldHMoc2V0cywgbiwgcmVzdWx0KTsNCit9DQorDQogLyogRmluZCB0 aGUgaW5kZXggb2YgdGhlIHN0YXRlIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGdpdmVuIHBvc2l0 aW9uIHNldCB3aXRoDQogICAgdGhlIGdpdmVuIHByZWNlZGluZyBjb250ZXh0LCBvciBjcmVh dGUgYSBuZXcgc3RhdGUgaWYgdGhlcmUgaXMgbm8gc3VjaA0KICAgIHN0YXRlLiAgQ29udGV4 dCB0ZWxscyB3aGV0aGVyIHdlIGdvdCBoZXJlIG9uIGEgbmV3bGluZSBvciBsZXR0ZXIuICov DQpAQCAtMjQ4MiwxMyArMjYwOSwxNiBAQA0KICAgY2hhcmNsYXNzIGxlZnRvdmVyczsgICAg ICAgICAgLyogU3R1ZmYgaW4gdGhlIGxhYmVsIHRoYXQgZGlkbid0IG1hdGNoLiAqLw0KICAg aW50IGxlZnRvdmVyc2Y7ICAgICAgICAgICAgICAgLyogVHJ1ZSBpZiBsZWZ0b3ZlcnMgaXMg bm9uZW1wdHkuICovDQogICBwb3NpdGlvbl9zZXQgZm9sbG93czsgICAgICAgICAvKiBVbmlv biBvZiB0aGUgZm9sbG93cyBvZiBzb21lIGdyb3VwLiAqLw0KLSAgcG9zaXRpb25fc2V0IHRt cDsgICAgICAgICAgICAgLyogVGVtcG9yYXJ5IHNwYWNlIGZvciBtZXJnaW5nIHNldHMuICov DQorICBwb3NpdGlvbl9zZXQgZm9sbG93c190bXA7ICAgICAvKiBUZW1wb3Jhcnkgc3BhY2Ug Zm9yIG1lcmdpbmcgc2V0cy4gKi8NCiAgIGludCBwb3NzaWJsZV9jb250ZXh0czsgICAgICAg IC8qIENvbnRleHRzIHRoYXQgdGhpcyBncm91cCBjYW4gbWF0Y2guICovDQogICBpbnQgc2Vw YXJhdGVfY29udGV4dHM7ICAgICAgICAvKiBDb250ZXh0IHRoYXQgbmV3IHN0YXRlIHdhbnRz IHRvIGtub3cuICovDQogICBzdGF0ZV9udW0gc3RhdGU7ICAgICAgICAgICAgICAvKiBOZXcg c3RhdGUuICovDQogICBzdGF0ZV9udW0gc3RhdGVfbmV3bGluZTsgICAgICAvKiBOZXcgc3Rh dGUgb24gYSBuZXdsaW5lIHRyYW5zaXRpb24uICovDQogICBzdGF0ZV9udW0gc3RhdGVfbGV0 dGVyOyAgICAgICAvKiBOZXcgc3RhdGUgb24gYSBsZXR0ZXIgdHJhbnNpdGlvbi4gKi8NCiAg IGludCBuZXh0X2lzbnRfMXN0X2J5dGUgPSAwOyAgIC8qIEZsYWcgaWYgd2UgY2FuJ3QgYWRk IHN0YXRlMC4gICovDQorICBwb3NpdGlvbl9zZXQgKnNldHMgPSAwOyAgICAgICAvKiBUZW1w b3JhcnkgYXJyYXkgb2Ygc2V0cywgdG8gcGFzcyBtYW55IHNldHMgdG8gbWVyZ2UgZnVuY3Rp b24gKi8NCisgIHNpemVfdCBzZXRzX24gPSAwOyAgICAgICAgICAgIC8qIFNldHMgYXJyYXkg c2l6ZSAqLw0KKyAgc2l6ZV90IHNldHNfYWxsb2MgPSAwOyAgICAgICAgLyogU2V0cyBhcnJh eSBjYXBhY2l0eSAgICovDQogICBzaXplX3QgaSwgaiwgazsNCiANCiAgIE1BTExPQyAoZ3Jw cywgTk9UQ0hBUik7DQpAQCAtMjYwNyw3ICsyNzM3LDcgQEANCiAgICAgfQ0KIA0KICAgYWxs b2NfcG9zaXRpb25fc2V0ICgmZm9sbG93cywgZC0+bmxlYXZlcyk7DQotICBhbGxvY19wb3Np dGlvbl9zZXQgKCZ0bXAsIGQtPm5sZWF2ZXMpOw0KKyAgYWxsb2NfcG9zaXRpb25fc2V0ICgm Zm9sbG93c190bXAsIGQtPm5sZWF2ZXMpOw0KIA0KICAgLyogSWYgd2UgYXJlIGEgc2VhcmNo aW5nIG1hdGNoZXIsIHRoZSBkZWZhdWx0IHRyYW5zaXRpb24gaXMgdG8gYSBzdGF0ZQ0KICAg ICAgY29udGFpbmluZyB0aGUgcG9zaXRpb25zIG9mIHN0YXRlIDAsIG90aGVyd2lzZSB0aGUg ZGVmYXVsdCB0cmFuc2l0aW9uDQpAQCAtMjYzNywxMyArMjc2NywxMiBAQA0KIA0KICAgZm9y IChpID0gMDsgaSA8IG5ncnBzOyArK2kpDQogICAgIHsNCi0gICAgICBmb2xsb3dzLm5lbGVt ID0gMDsNCi0NCi0gICAgICAvKiBGaW5kIHRoZSB1bmlvbiBvZiB0aGUgZm9sbG93cyBvZiB0 aGUgcG9zaXRpb25zIG9mIHRoZSBncm91cC4NCi0gICAgICAgICBUaGlzIGlzIGEgaGlkZW91 c2x5IGluZWZmaWNpZW50IGxvb3AuICBGaXggaXQgc29tZWRheS4gKi8NCisgICAgICAvKiBG aW5kIHRoZSB1bmlvbiBvZiB0aGUgZm9sbG93cyBvZiB0aGUgcG9zaXRpb25zIG9mIHRoZSBn cm91cC4gICovDQorICAgICAgc2V0c19uID0gZ3Jwc1tpXS5uZWxlbTsNCisgICAgICBSRUFM TE9DX0lGX05FQ0VTU0FSWShzZXRzLCBzZXRzX2FsbG9jLCBzZXRzX24pOw0KICAgICAgIGZv ciAoaiA9IDA7IGogPCBncnBzW2ldLm5lbGVtOyArK2opDQotICAgICAgICBmb3IgKGsgPSAw OyBrIDwgZC0+Zm9sbG93c1tncnBzW2ldLmVsZW1zW2pdXS5uZWxlbTsgKytrKQ0KLSAgICAg ICAgICBpbnNlcnQgKGQtPmZvbGxvd3NbZ3Jwc1tpXS5lbGVtc1tqXV0uZWxlbXNba10sICZm b2xsb3dzKTsNCisgICAgICAgIHNldHNbal0gPSBkLT5mb2xsb3dzW2dycHNbaV0uZWxlbXNb al1dOw0KKyAgICAgIG1lcmdlX21hbnlfc2V0cyAoc2V0cywgc2V0c19uLCAmZm9sbG93c190 bXApOw0KIA0KICAgICAgIGlmIChkLT5tYl9jdXJfbWF4ID4gMSkNCiAgICAgICAgIHsNCkBA IC0yNjY2LDkgKzI3OTUsOSBAQA0KICAgICAgICAgICAgICA8bWIgQT4sIHNvIHdlIGNhbm5v dCBhZGQgc3RhdGVbMF0uICAqLw0KIA0KICAgICAgICAgICBuZXh0X2lzbnRfMXN0X2J5dGUg PSAwOw0KLSAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgZm9sbG93cy5uZWxlbTsgKytqKQ0K KyAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgZm9sbG93c190bXAubmVsZW07ICsraikNCiAg ICAgICAgICAgICB7DQotICAgICAgICAgICAgICBpZiAoIShkLT5tdWx0aWJ5dGVfcHJvcFtm b2xsb3dzLmVsZW1zW2pdLmluZGV4XSAmIDEpKQ0KKyAgICAgICAgICAgICAgaWYgKCEoZC0+ bXVsdGlieXRlX3Byb3BbZm9sbG93c190bXAuZWxlbXNbal0uaW5kZXhdICYgMSkpDQogICAg ICAgICAgICAgICAgIHsNCiAgICAgICAgICAgICAgICAgICBuZXh0X2lzbnRfMXN0X2J5dGUg PSAxOw0KICAgICAgICAgICAgICAgICAgIGJyZWFrOw0KQEAgLTI2ODAsOCArMjgwOSw3IEBA DQogICAgICAgICAgb2Ygc3RhdGUgMCBhcyB3ZWxsLiAqLw0KICAgICAgIGlmIChkLT5zZWFy Y2hmbGFnDQogICAgICAgICAgICYmICghTUJTX1NVUFBPUlQgfHwgKGQtPm1iX2N1cl9tYXgg PT0gMSB8fCAhbmV4dF9pc250XzFzdF9ieXRlKSkpDQotICAgICAgICBmb3IgKGogPSAwOyBq IDwgZC0+c3RhdGVzWzBdLmVsZW1zLm5lbGVtOyArK2opDQotICAgICAgICAgIGluc2VydCAo ZC0+c3RhdGVzWzBdLmVsZW1zLmVsZW1zW2pdLCAmZm9sbG93cyk7DQorICAgICAgICBtZXJn ZSAoJmZvbGxvd3NfdG1wLCAmZC0+c3RhdGVzWzBdLmVsZW1zLCAmZm9sbG93cyk7DQogDQog ICAgICAgLyogRmluZCBvdXQgaWYgdGhlIG5ldyBzdGF0ZSB3aWxsIHdhbnQgYW55IGNvbnRl eHQgaW5mb3JtYXRpb24uICovDQogICAgICAgcG9zc2libGVfY29udGV4dHMgPSBjaGFyY2xh c3NfY29udGV4dCAobGFiZWxzW2ldKTsNCkBAIC0yNzIwLDcgKzI4NDgsOCBAQA0KICAgZm9y IChpID0gMDsgaSA8IG5ncnBzOyArK2kpDQogICAgIGZyZWUgKGdycHNbaV0uZWxlbXMpOw0K ICAgZnJlZSAoZm9sbG93cy5lbGVtcyk7DQotICBmcmVlICh0bXAuZWxlbXMpOw0KKyAgZnJl ZSAoc2V0cyk7DQorICBmcmVlIChmb2xsb3dzX3RtcC5lbGVtcyk7DQogICBmcmVlIChncnBz KTsNCiAgIGZyZWUgKGxhYmVscyk7DQogfQ0K --------------010006080605040308050001-- ------------=_1400297162-9823-1--