54376 2011-02-13 23:28:48 -0800 Make sorting of matched rules faster 2011-02-14 00:05:44 -0800 1 1 1 Unclassified WebKit CSS 528+ (Nightly build) PC OS X 10.5 RESOLVED FIXED P2 Normal --- 1 koivisto webkit-unassigned oldest_to_newest 350531 0 koivisto 2011-02-13 23:28:48 -0800 Make sorting of matched rules faster 350534 1 82289 koivisto 2011-02-13 23:33:27 -0800 Created attachment 82289 patch - use std::sort - cache specificity, it is slow to compute - inline compare function 350544 2 koivisto 2011-02-14 00:05:44 -0800 http://trac.webkit.org/changeset/78457 82289 2011-02-13 23:33:27 -0800 2011-02-13 23:45:16 -0800 patch rule-sort.patch text/plain 6629 koivisto SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDc4NDU1KQorKysgU291cmNlL1dlYkNvcmUvQ2hhbmdl TG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMjMgQEAKKzIwMTEtMDItMTMgIEFudHRpIEtv aXZpc3RvICA8YW50dGlAYXBwbGUuY29tPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAo T09QUyEpLgorCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9p ZD01NDM3NgorICAgICAgICBNYWtlIHNvcnRpbmcgb2YgbWF0Y2hlZCBydWxlcyBmYXN0ZXIKKyAg ICAgICAgCisgICAgICAgIC0gdXNlIHN0ZDo6c29ydAorICAgICAgICAtIGNhY2hlIHNwZWNpZmlj aXR5LCBpdCBpcyBzbG93IHRvIGNvbXB1dGUKKyAgICAgICAgLSBpbmxpbmUgY29tcGFyZSBmdW5j dGlvbgorCisgICAgICAgICogY3NzL0NTU1N0eWxlU2VsZWN0b3IuY3BwOgorICAgICAgICAoV2Vi Q29yZTo6UnVsZURhdGE6OnNwZWNpZmljaXR5KToKKyAgICAgICAgKFdlYkNvcmU6OkNTU1N0eWxl U2VsZWN0b3I6Om1hdGNoUnVsZXMpOgorICAgICAgICAoV2ViQ29yZTo6Y29tcGFyZVJ1bGVzKToK KyAgICAgICAgKFdlYkNvcmU6OkNTU1N0eWxlU2VsZWN0b3I6OnNvcnRNYXRjaGVkUnVsZXMpOgor ICAgICAgICAoV2ViQ29yZTo6UnVsZURhdGE6OlJ1bGVEYXRhKToKKyAgICAgICAgKFdlYkNvcmU6 OkNTU1N0eWxlU2VsZWN0b3I6Om1hdGNoUGFnZVJ1bGVzKToKKyAgICAgICAgKiBjc3MvQ1NTU3R5 bGVTZWxlY3Rvci5oOgorCiAyMDExLTAyLTEyICBEYXJpbiBBZGxlciAgPGRhcmluQGFwcGxlLmNv bT4KIAogICAgICAgICBSZXZpZXdlZCBieSBBbGV4ZXkgUHJvc2t1cnlha292LgpJbmRleDogU291 cmNlL1dlYkNvcmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuY3BwCj09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJj ZS9XZWJDb3JlL2Nzcy9DU1NTdHlsZVNlbGVjdG9yLmNwcAkocmV2aXNpb24gNzgzMjIpCisrKyBT b3VyY2UvV2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHAJKHdvcmtpbmcgY29weSkKQEAg LTM2Myw2ICszNjMsNyBAQCBwdWJsaWM6CiAgICAgYm9vbCBoYXNGYXN0Q2hlY2thYmxlU2VsZWN0 b3IoKSBjb25zdCB7IHJldHVybiBtX2hhc0Zhc3RDaGVja2FibGVTZWxlY3RvcjsgfQogICAgIGJv b2wgaGFzTXVsdGlwYXJ0U2VsZWN0b3IoKSBjb25zdCB7IHJldHVybiBtX2hhc011bHRpcGFydFNl bGVjdG9yOyB9CiAgICAgYm9vbCBoYXNUb3BTZWxlY3Rvck1hdGNoaW5nSFRNTEJhc2VkT25SdWxl SGFzaCgpIGNvbnN0IHsgcmV0dXJuIG1faGFzVG9wU2VsZWN0b3JNYXRjaGluZ0hUTUxCYXNlZE9u UnVsZUhhc2g7IH0KKyAgICB1bnNpZ25lZCBzcGVjaWZpY2l0eSgpIGNvbnN0IHsgcmV0dXJuIG1f c3BlY2lmaWNpdHk7IH0KICAgICAKICAgICAvLyBUcnkgdG8gYmFsYW5jZSBiZXR3ZWVuIG1lbW9y eSB1c2FnZSAodGhlcmUgY2FuIGJlIGxvdHMgb2YgUnVsZURhdGEgb2JqZWN0cykgYW5kIGdvb2Qg ZmlsdGVyaW5nIHBlcmZvcm1hbmNlLgogICAgIHN0YXRpYyBjb25zdCB1bnNpZ25lZCBtYXhpbXVt SWRlbnRpZmllckNvdW50ID0gNDsKQEAgLTM3NCw2ICszNzUsNyBAQCBwcml2YXRlOgogICAgIAog ICAgIENTU1N0eWxlUnVsZSogbV9ydWxlOwogICAgIENTU1NlbGVjdG9yKiBtX3NlbGVjdG9yOwor ICAgIHVuc2lnbmVkIG1fc3BlY2lmaWNpdHk7CiAgICAgdW5zaWduZWQgbV9wb3NpdGlvbiA6IDI5 OwogICAgIGJvb2wgbV9oYXNGYXN0Q2hlY2thYmxlU2VsZWN0b3IgOiAxOwogICAgIGJvb2wgbV9o YXNNdWx0aXBhcnRTZWxlY3RvciA6IDE7CkBAIC03NzIsNyArNzc0LDcgQEAgdm9pZCBDU1NTdHls ZVNlbGVjdG9yOjptYXRjaFJ1bGVzKFJ1bGVTZQogICAgICAgICByZXR1cm47CiAgICAgCiAgICAg Ly8gU29ydCB0aGUgc2V0IG9mIG1hdGNoZWQgcnVsZXMuCi0gICAgc29ydE1hdGNoZWRSdWxlcygw LCBtX21hdGNoZWRSdWxlcy5zaXplKCkpOworICAgIHNvcnRNYXRjaGVkUnVsZXMoKTsKICAgICAK ICAgICAvLyBOb3cgdHJhbnNmZXIgdGhlIHNldCBvZiBtYXRjaGVkIHJ1bGVzIG92ZXIgdG8gb3Vy IGxpc3Qgb2YgZGVjbHMuCiAgICAgaWYgKCFtX2NoZWNrZXIubV9jb2xsZWN0UnVsZXNPbmx5KSB7 CkBAIC04MzksODAgKzg0MSwxNiBAQCB2b2lkIENTU1N0eWxlU2VsZWN0b3I6Om1hdGNoUnVsZXNG b3JMaXN0CiAgICAgfQogfQogCi1zdGF0aWMgYm9vbCBvcGVyYXRvciA+KGNvbnN0IFJ1bGVEYXRh JiByMSwgY29uc3QgUnVsZURhdGEmIHIyKQorc3RhdGljIGlubGluZSBib29sIGNvbXBhcmVSdWxl cyhjb25zdCBSdWxlRGF0YSogcjEsIGNvbnN0IFJ1bGVEYXRhKiByMikKIHsKLSAgICBpbnQgc3Bl YzEgPSByMS5zZWxlY3RvcigpLT5zcGVjaWZpY2l0eSgpOwotICAgIGludCBzcGVjMiA9IHIyLnNl bGVjdG9yKCktPnNwZWNpZmljaXR5KCk7Ci0gICAgcmV0dXJuIChzcGVjMSA9PSBzcGVjMikgPyBy MS5wb3NpdGlvbigpID4gcjIucG9zaXRpb24oKSA6IHNwZWMxID4gc3BlYzI7IAotfQotICAgIAot c3RhdGljIGJvb2wgb3BlcmF0b3IgPD0oY29uc3QgUnVsZURhdGEmIHIxLCBjb25zdCBSdWxlRGF0 YSYgcjIpCi17Ci0gICAgcmV0dXJuICEocjEgPiByMik7CisgICAgdW5zaWduZWQgc3BlY2lmaWNp dHkxID0gcjEtPnNwZWNpZmljaXR5KCk7CisgICAgdW5zaWduZWQgc3BlY2lmaWNpdHkyID0gcjIt PnNwZWNpZmljaXR5KCk7CisgICAgcmV0dXJuIChzcGVjaWZpY2l0eTEgPT0gc3BlY2lmaWNpdHky KSA/IHIxLT5wb3NpdGlvbigpIDwgcjItPnBvc2l0aW9uKCkgOiBzcGVjaWZpY2l0eTEgPCBzcGVj aWZpY2l0eTI7IAogfQogCi12b2lkIENTU1N0eWxlU2VsZWN0b3I6OnNvcnRNYXRjaGVkUnVsZXMo dW5zaWduZWQgc3RhcnQsIHVuc2lnbmVkIGVuZCkKK3ZvaWQgQ1NTU3R5bGVTZWxlY3Rvcjo6c29y dE1hdGNoZWRSdWxlcygpCiB7Ci0gICAgaWYgKHN0YXJ0ID49IGVuZCB8fCAoZW5kIC0gc3RhcnQg PT0gMSkpCi0gICAgICAgIHJldHVybjsgLy8gU2FuaXR5IGNoZWNrLgotCi0gICAgaWYgKGVuZCAt IHN0YXJ0IDw9IDYpIHsKLSAgICAgICAgLy8gQXBwbHkgYSBidWJibGUgc29ydCBmb3Igc21hbGxl ciBsaXN0cy4KLSAgICAgICAgZm9yICh1bnNpZ25lZCBpID0gZW5kIC0gMTsgaSA+IHN0YXJ0OyBp LS0pIHsKLSAgICAgICAgICAgIGJvb2wgc29ydGVkID0gdHJ1ZTsKLSAgICAgICAgICAgIGZvciAo dW5zaWduZWQgaiA9IHN0YXJ0OyBqIDwgaTsgaisrKSB7Ci0gICAgICAgICAgICAgICAgY29uc3Qg UnVsZURhdGEqIGVsdCA9IG1fbWF0Y2hlZFJ1bGVzW2pdOwotICAgICAgICAgICAgICAgIGNvbnN0 IFJ1bGVEYXRhKiBlbHQyID0gbV9tYXRjaGVkUnVsZXNbaiArIDFdOwotICAgICAgICAgICAgICAg IGlmICgqZWx0ID4gKmVsdDIpIHsKLSAgICAgICAgICAgICAgICAgICAgc29ydGVkID0gZmFsc2U7 Ci0gICAgICAgICAgICAgICAgICAgIG1fbWF0Y2hlZFJ1bGVzW2pdID0gZWx0MjsKLSAgICAgICAg ICAgICAgICAgICAgbV9tYXRjaGVkUnVsZXNbaiArIDFdID0gZWx0OwotICAgICAgICAgICAgICAg IH0KLSAgICAgICAgICAgIH0KLSAgICAgICAgICAgIGlmIChzb3J0ZWQpCi0gICAgICAgICAgICAg ICAgcmV0dXJuOwotICAgICAgICB9Ci0gICAgICAgIHJldHVybjsKLSAgICB9Ci0KLSAgICAvLyBQ ZXJmb3JtIGEgbWVyZ2Ugc29ydCBmb3IgbGFyZ2VyIGxpc3RzLgotICAgIHVuc2lnbmVkIG1pZCA9 IChzdGFydCArIGVuZCkgLyAyOwotICAgIHNvcnRNYXRjaGVkUnVsZXMoc3RhcnQsIG1pZCk7Ci0g ICAgc29ydE1hdGNoZWRSdWxlcyhtaWQsIGVuZCk7Ci0gICAgCi0gICAgY29uc3QgUnVsZURhdGEq IGVsdCA9IG1fbWF0Y2hlZFJ1bGVzW21pZCAtIDFdOwotICAgIGNvbnN0IFJ1bGVEYXRhKiBlbHQy ID0gbV9tYXRjaGVkUnVsZXNbbWlkXTsKLSAgICAKLSAgICAvLyBIYW5kbGUgdGhlIGZhc3QgY29t bW9uIGNhc2UgKG9mIGVxdWFsIHNwZWNpZmljaXR5KS4gIFRoZSBsaXN0IG1heSBhbHJlYWR5Ci0g ICAgLy8gYmUgY29tcGxldGVseSBzb3J0ZWQuCi0gICAgaWYgKCplbHQgPD0gKmVsdDIpCi0gICAg ICAgIHJldHVybjsKLSAgICAKLSAgICAvLyBXZSBoYXZlIHRvIG1lcmdlIHNvcnQuICBFbnN1cmUg b3VyIG1lcmdlIGJ1ZmZlciBpcyBiaWcgZW5vdWdoIHRvIGhvbGQKLSAgICAvLyBhbGwgdGhlIGl0 ZW1zLgotICAgIFZlY3Rvcjxjb25zdCBSdWxlRGF0YSo+IHJ1bGVzTWVyZ2VCdWZmZXI7Ci0gICAg cnVsZXNNZXJnZUJ1ZmZlci5yZXNlcnZlSW5pdGlhbENhcGFjaXR5KGVuZCAtIHN0YXJ0KTsgCi0K LSAgICB1bnNpZ25lZCBpMSA9IHN0YXJ0OwotICAgIHVuc2lnbmVkIGkyID0gbWlkOwotICAgIAot ICAgIGVsdCA9IG1fbWF0Y2hlZFJ1bGVzW2kxXTsKLSAgICBlbHQyID0gbV9tYXRjaGVkUnVsZXNb aTJdOwotICAgIAotICAgIHdoaWxlIChpMSA8IG1pZCB8fCBpMiA8IGVuZCkgewotICAgICAgICBp ZiAoaTEgPCBtaWQgJiYgKGkyID09IGVuZCB8fCAqZWx0IDw9ICplbHQyKSkgewotICAgICAgICAg ICAgcnVsZXNNZXJnZUJ1ZmZlci5hcHBlbmQoZWx0KTsKLSAgICAgICAgICAgIGlmICgrK2kxIDwg bWlkKQotICAgICAgICAgICAgICAgIGVsdCA9IG1fbWF0Y2hlZFJ1bGVzW2kxXTsKLSAgICAgICAg fSBlbHNlIHsKLSAgICAgICAgICAgIHJ1bGVzTWVyZ2VCdWZmZXIuYXBwZW5kKGVsdDIpOwotICAg ICAgICAgICAgaWYgKCsraTIgPCBlbmQpCi0gICAgICAgICAgICAgICAgZWx0MiA9IG1fbWF0Y2hl ZFJ1bGVzW2kyXTsKLSAgICAgICAgfQotICAgIH0KLSAgICAKLSAgICBmb3IgKHVuc2lnbmVkIGkg PSBzdGFydDsgaSA8IGVuZDsgaSsrKQotICAgICAgICBtX21hdGNoZWRSdWxlc1tpXSA9IHJ1bGVz TWVyZ2VCdWZmZXJbaSAtIHN0YXJ0XTsKKyAgICBzdGQ6OnNvcnQobV9tYXRjaGVkUnVsZXMuYmVn aW4oKSwgbV9tYXRjaGVkUnVsZXMuZW5kKCksIGNvbXBhcmVSdWxlcyk7CiB9CiAKIGlubGluZSBF SW5zaWRlTGluayBDU1NTdHlsZVNlbGVjdG9yOjpTZWxlY3RvckNoZWNrZXI6OmRldGVybWluZUxp bmtTdGF0ZShFbGVtZW50KiBlbGVtZW50KSBjb25zdApAQCAtMzA1Miw2ICsyOTkwLDcgQEAgc3Rh dGljIGlubGluZSBib29sIGlzU2VsZWN0b3JNYXRjaGluZ0hUTQogUnVsZURhdGE6OlJ1bGVEYXRh KENTU1N0eWxlUnVsZSogcnVsZSwgQ1NTU2VsZWN0b3IqIHNlbGVjdG9yLCB1bnNpZ25lZCBwb3Np dGlvbikKICAgICA6IG1fcnVsZShydWxlKQogICAgICwgbV9zZWxlY3RvcihzZWxlY3RvcikKKyAg ICAsIG1fc3BlY2lmaWNpdHkoc2VsZWN0b3ItPnNwZWNpZmljaXR5KCkpCiAgICAgLCBtX3Bvc2l0 aW9uKHBvc2l0aW9uKQogICAgICwgbV9oYXNGYXN0Q2hlY2thYmxlU2VsZWN0b3IoaXNGYXN0Q2hl Y2thYmxlU2VsZWN0b3Ioc2VsZWN0b3IpKQogICAgICwgbV9oYXNNdWx0aXBhcnRTZWxlY3Rvcihz ZWxlY3Rvci0+dGFnSGlzdG9yeSgpKQpAQCAtMzM2Myw3ICszMzAyLDcgQEAgdm9pZCBDU1NTdHls ZVNlbGVjdG9yOjptYXRjaFBhZ2VSdWxlcyhSdQogICAgICAgICByZXR1cm47CiAKICAgICAvLyBT b3J0IHRoZSBzZXQgb2YgbWF0Y2hlZCBydWxlcy4KLSAgICBzb3J0TWF0Y2hlZFJ1bGVzKDAsIG1f bWF0Y2hlZFJ1bGVzLnNpemUoKSk7CisgICAgc29ydE1hdGNoZWRSdWxlcygpOwogCiAgICAgLy8g Tm93IHRyYW5zZmVyIHRoZSBzZXQgb2YgbWF0Y2hlZCBydWxlcyBvdmVyIHRvIG91ciBsaXN0IG9m IGRlY2xzLgogICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBtX21hdGNoZWRSdWxlcy5zaXpl KCk7IGkrKykKSW5kZXg6IFNvdXJjZS9XZWJDb3JlL2Nzcy9DU1NTdHlsZVNlbGVjdG9yLmgKPT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PQotLS0gU291cmNlL1dlYkNvcmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuaAkocmV2aXNp b24gNzgzMjIpCisrKyBTb3VyY2UvV2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5oCSh3b3Jr aW5nIGNvcHkpCkBAIC0xOTIsNyArMTkyLDcgQEAgcHVibGljOgogICAgICAgICB2b2lkIG1hdGNo UnVsZXMoUnVsZVNldCosIGludCYgZmlyc3RSdWxlSW5kZXgsIGludCYgbGFzdFJ1bGVJbmRleCwg Ym9vbCBpbmNsdWRlRW1wdHlSdWxlcyk7CiAgICAgICAgIHZvaWQgbWF0Y2hSdWxlc0Zvckxpc3Qo Y29uc3QgVmVjdG9yPFJ1bGVEYXRhPiosIGludCYgZmlyc3RSdWxlSW5kZXgsIGludCYgbGFzdFJ1 bGVJbmRleCwgYm9vbCBpbmNsdWRlRW1wdHlSdWxlcyk7CiAgICAgICAgIGJvb2wgZmFzdFJlamVj dFNlbGVjdG9yKGNvbnN0IFJ1bGVEYXRhJikgY29uc3Q7Ci0gICAgICAgIHZvaWQgc29ydE1hdGNo ZWRSdWxlcyh1bnNpZ25lZCBzdGFydCwgdW5zaWduZWQgZW5kKTsKKyAgICAgICAgdm9pZCBzb3J0 TWF0Y2hlZFJ1bGVzKCk7CiAgICAgICAgIAogICAgICAgICBib29sIGNoZWNrU2VsZWN0b3IoY29u c3QgUnVsZURhdGEmKTsKIAo=