From debbugs-submit-bounces@debbugs.gnu.org Mon Aug 26 02:57:18 2013 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-- 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 debbugs-submit-bounces@debbugs.gnu.org Tue May 06 10:35:08 2014 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 To: Ivan Yanikov Subject: bug#15191: faster DFA.C state merge 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-Debbugs-Envelope-To: 15191 Cc: Paul Eggert , 15191@debbugs.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: -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 debbugs-submit-bounces@debbugs.gnu.org Wed May 07 10:51:30 2014 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 To: 15191@debbugs.gnu.org Subject: bug#15191: faster DFA.C state merge 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-Debbugs-Envelope-To: 15191 Cc: Paul Eggert 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 debbugs-submit-bounces@debbugs.gnu.org Fri May 16 22:03:26 2014 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 To: 15191@debbugs.gnu.org Subject: Re: bug#15191: faster DFA.C state merge 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-Debbugs-Envelope-To: 15191 Cc: Paul Eggert , 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: -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 debbugs-submit-bounces@debbugs.gnu.org Fri May 16 23:25:13 2014 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. From unknown Mon Jun 23 07:47:49 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sat, 14 Jun 2014 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator