72523 2011-11-16 10:38:23 -0800 AX: Searching mechanism is too slow when finding the element. 2011-11-30 16:58:54 -0800 1 1 1 Unclassified WebKit Accessibility 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 cfleizach cfleizach bdakin oldest_to_newest 504036 0 cfleizach 2011-11-16 10:38:23 -0800 Right now the searching mechanism goes through every item starting at the first one in order to find where to start the search Instead, it should start with the immediate parent chain of the element and start searching from there 504037 1 cfleizach 2011-11-16 10:38:56 -0800 First patch will be too clean up this method... Second patch will change the implementation 505999 2 cfleizach 2011-11-18 13:15:57 -0800 So in summary, in the old approach, it literally went through every element, looking for the start element before, "starting" the search In the new way, we only go through the elements that need to be searched. This happens by going up the start object parent chain. at each level we do a DFS. as we go up the parent chain, we only check the elements before or after the current element. This reduces element comparison times significantly. In the old way, if you were on the last page of a link, you'd have to go through pretty much every element in the page. now, it's just a few elements. 506003 3 115858 cfleizach 2011-11-18 13:18:33 -0800 Created attachment 115858 patch 512139 4 115858 bdakin 2011-11-30 14:36:07 -0800 Comment on attachment 115858 patch View in context: https://bugs.webkit.org/attachment.cgi?id=115858&action=review > Source/WebCore/accessibility/AccessibilityObject.cpp:373 > + for (size_t i = startIndex; isForward ? i > endIndex : i < endIndex; isForward ? i-- : i++) { This line is hard to read with all of the isForward craziness. I can't think of any obvious way to simplify it, but if you can, I encourage it. 512249 5 cfleizach 2011-11-30 16:58:54 -0800 http://trac.webkit.org/changeset/101570 115858 2011-11-18 13:18:33 -0800 2011-11-30 14:36:07 -0800 patch patch.txt text/plain 5892 cfleizach SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDEwMDgwNCkKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDIxIEBACisyMDExLTExLTE4ICBDaHJpcyBG bGVpemFjaCAgPGNmbGVpemFjaEBhcHBsZS5jb20+CisKKyAgICAgICAgQVg6IFNlYXJjaGluZyBt ZWNoYW5pc20gaXMgdG9vIHNsb3cgd2hlbiBmaW5kaW5nIHRoZSBlbGVtZW50LgorICAgICAgICBo dHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9NzI1MjMKKworICAgICAgICBS ZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBUaGlzIG1ha2VzIHRoZSBlbGVt ZW50IHNlYXJjaGluZyBtZWNoYW5pc20gbXVjaCBmYXN0ZXIuIFByZXZpb3VzbHksIHNlYXJjaGlu ZyBsaXRlcmFsbHkgd2VudCAKKyAgICAgICAgdGhyb3VnaCBldmVyeSBlbGVtZW50LCBsb29raW5n IGZvciB0aGUgc3RhcnQgZWxlbWVudCBiZWZvcmUgInN0YXJ0aW5nIiB0aGUgc2VhcmNoLgorCisg ICAgICAgIE5vdyB3ZSBvbmx5IGdvIHRocm91Z2ggdGhlIGVsZW1lbnRzIHRoYXQgbmVlZCB0byBi ZSBzZWFyY2hlZC4gVGhpcyBpcyBkb25lIGJ5IGdvaW5nIHVwIHRoZSAKKyAgICAgICAgc3RhcnQg b2JqZWN0IHBhcmVudCBjaGFpbi4gQXQgZWFjaCBsZXZlbCwgYSBERlMgaXMgZG9uZS4gQXMgd2Ug Z28gdXAgdGhlIHBhcmVudCBjaGFpbiwgCisgICAgICAgIG9ubHkgdGhlIGVsZW1lbnRzIGJlZm9y ZS9hZnRlciB0aGUgY3VycmVudCBlbGVtZW50IGFyZSBleGFtaW5lZC4KKworICAgICAgICAqIGFj Y2Vzc2liaWxpdHkvQWNjZXNzaWJpbGl0eU9iamVjdC5jcHA6CisgICAgICAgIChXZWJDb3JlOjph cHBlbmRDaGlsZHJlblRvQXJyYXkpOgorICAgICAgICAoV2ViQ29yZTo6QWNjZXNzaWJpbGl0eU9i amVjdDo6ZmluZE1hdGNoaW5nT2JqZWN0cyk6CisKIDIwMTEtMTEtMTggIFNpbW9uIEZyYXNlciAg PHNpbW9uLmZyYXNlckBhcHBsZS5jb20+CiAKICAgICAgICAgQXBwZWFyYW5jZSBvZiBjb21wb3Vu ZCB0cmFuc2Zvcm0gYW5pbWF0aW9ucyB1bmRlciBhcHBzIGxpbmtlZCBvbiBTbm93TGVvcGFyZCBp cyBpbmNvcnJlY3QKSW5kZXg6IFNvdXJjZS9XZWJDb3JlL2FjY2Vzc2liaWxpdHkvQWNjZXNzaWJp bGl0eU9iamVjdC5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNlL1dlYkNvcmUvYWNjZXNzaWJpbGl0 eS9BY2Nlc3NpYmlsaXR5T2JqZWN0LmNwcAkocmV2aXNpb24gMTAwNjYyKQorKysgU291cmNlL1dl YkNvcmUvYWNjZXNzaWJpbGl0eS9BY2Nlc3NpYmlsaXR5T2JqZWN0LmNwcAkod29ya2luZyBjb3B5 KQpAQCAtMzU0LDQyICszNTQsODEgQEAKICAgICByZXR1cm4gYWNjZXNzaWJsZU9iamVjdDsKIH0K IAorc3RhdGljIHZvaWQgYXBwZW5kQ2hpbGRyZW5Ub0FycmF5KEFjY2Vzc2liaWxpdHlPYmplY3Qq IG9iamVjdCwgYm9vbCBpc0ZvcndhcmQsIEFjY2Vzc2liaWxpdHlPYmplY3QqIHN0YXJ0T2JqZWN0 LCBBY2Nlc3NpYmlsaXR5T2JqZWN0OjpBY2Nlc3NpYmlsaXR5Q2hpbGRyZW5WZWN0b3ImIHJlc3Vs dHMpCit7CisgICAgQWNjZXNzaWJpbGl0eU9iamVjdDo6QWNjZXNzaWJpbGl0eUNoaWxkcmVuVmVj dG9yIHNlYXJjaENoaWxkcmVuID0gb2JqZWN0LT5jaGlsZHJlbigpOworICAgIHNpemVfdCBjaGls ZHJlblNpemUgPSBzZWFyY2hDaGlsZHJlbi5zaXplKCk7CisKKyAgICBzaXplX3Qgc3RhcnRJbmRl eCA9IGlzRm9yd2FyZCA/IGNoaWxkcmVuU2l6ZSA6IDA7CisgICAgc2l6ZV90IGVuZEluZGV4ID0g aXNGb3J3YXJkID8gMCA6IGNoaWxkcmVuU2l6ZTsKKworICAgIHNpemVfdCBzZWFyY2hQb3NpdGlv biA9IHN0YXJ0T2JqZWN0ID8gc2VhcmNoQ2hpbGRyZW4uZmluZChzdGFydE9iamVjdCkgOiBXVEY6 Om5vdEZvdW5kOworICAgIGlmIChzZWFyY2hQb3NpdGlvbiAhPSBXVEY6Om5vdEZvdW5kKSB7Cisg ICAgICAgIGlmIChpc0ZvcndhcmQpCisgICAgICAgICAgICBlbmRJbmRleCA9IHNlYXJjaFBvc2l0 aW9uICsgMTsKKyAgICAgICAgZWxzZQorICAgICAgICAgICAgZW5kSW5kZXggPSBzZWFyY2hQb3Np dGlvbjsKKyAgICB9CisgICAgCisgICAgZm9yIChzaXplX3QgaSA9IHN0YXJ0SW5kZXg7IGlzRm9y d2FyZCA/IGkgPiBlbmRJbmRleCA6IGkgPCBlbmRJbmRleDsgaXNGb3J3YXJkID8gaS0tIDogaSsr KSB7CisgICAgICAgIC8vIEZJWE1FOiBIYW5kbGUgYXR0YWNobWVudHMuCisgICAgICAgIHJlc3Vs dHMuYXBwZW5kKHNlYXJjaENoaWxkcmVuLmF0KGlzRm9yd2FyZCA/IGkgLSAxIDogaSkuZ2V0KCkp OworICAgIH0KK30KKyAgICAKIHZvaWQgQWNjZXNzaWJpbGl0eU9iamVjdDo6ZmluZE1hdGNoaW5n T2JqZWN0cyhBY2Nlc3NpYmlsaXR5U2VhcmNoQ3JpdGVyaWEqIGNyaXRlcmlhLCBBY2Nlc3NpYmls aXR5Q2hpbGRyZW5WZWN0b3ImIHJlc3VsdHMpCiB7CiAgICAgQVNTRVJUKGNyaXRlcmlhKTsKICAg ICAKICAgICBpZiAoIWNyaXRlcmlhKQogICAgICAgICByZXR1cm47CisKKyAgICAvLyBUaGlzIHNl YXJjaCBtZWNoYW5pc20gb25seSBzZWFyY2hlcyB0aGUgZWxlbWVudHMgYmVmb3JlL2FmdGVyIHRo ZSBzdGFydGluZyBvYmplY3QuCisgICAgLy8gSXQgZG9lcyB0aGlzIGJ5IHN0ZXBwaW5nIHVwIHRo ZSBwYXJlbnQgY2hhaW4gYW5kIGF0IGVhY2ggbGV2ZWwgZG9pbmcgYSBERlMuCiAgICAgCisgICAg Ly8gSWYgdGhlcmUncyBubyBzdGFydCBvYmplY3QsIGl0IG1lYW5zIHdlIHdhbnQgdG8gc2VhcmNo IGV2ZXJ5dGhpbmcuCiAgICAgQWNjZXNzaWJpbGl0eU9iamVjdCogc3RhcnRPYmplY3QgPSBjcml0 ZXJpYS0+c3RhcnRPYmplY3Q7Ci0gICAgQWNjZXNzaWJpbGl0eUNoaWxkcmVuVmVjdG9yIHNlYXJj aFN0YWNrOwotICAgIHNlYXJjaFN0YWNrLmFwcGVuZCh0aGlzKTsKKyAgICBpZiAoIXN0YXJ0T2Jq ZWN0KQorICAgICAgICBzdGFydE9iamVjdCA9IHRoaXM7CiAgICAgCiAgICAgYm9vbCBpc0Zvcndh cmQgPSBjcml0ZXJpYS0+c2VhcmNoRGlyZWN0aW9uID09IFNlYXJjaERpcmVjdGlvbk5leHQ7Ci0g ICAgYm9vbCBkaWRGaW5kU3RhcnRPYmplY3QgPSAhY3JpdGVyaWEtPnN0YXJ0T2JqZWN0OwogICAg IAotICAgIC8vIEZJWE1FOiBJdGVyYXRlIHRoZSBBY2Nlc3NpYmlsaXR5T2JqZWN0IGNhY2hlIGNy ZWF0aW5nIGFuZCBhZGRpbmcgb2JqZWN0cyBpZiBuZXNzZXNhcnkuCi0gICAgd2hpbGUgKCFzZWFy Y2hTdGFjay5pc0VtcHR5KCkpIHsKLSAgICAgICAgQWNjZXNzaWJpbGl0eU9iamVjdCogc2VhcmNo T2JqZWN0ID0gc2VhcmNoU3RhY2subGFzdCgpLmdldCgpOwotICAgICAgICBzZWFyY2hTdGFjay5y ZW1vdmVMYXN0KCk7Ci0gICAgICAgIAotICAgICAgICBpZiAoZGlkRmluZFN0YXJ0T2JqZWN0KSB7 CisgICAgLy8gSW4gdGhlIGZpcnN0IGl0ZXJhdGlvbiBvZiB0aGUgbG9vcCwgaXQgd2lsbCBleGFt aW5lIHRoZSBjaGlsZHJlbiBvZiB0aGUgc3RhcnQgb2JqZWN0IGZvciBtYXRjaGVzLgorICAgIC8v IEhvd2V2ZXIsIHdoZW4gZ29pbmcgYmFja3dhcmRzLCB0aG9zZSBjaGlsZHJlbiBzaG91bGQgbm90 IGJlIGNvbnNpZGVyZWQsIHNvIHRoZSBsb29wIGlzIHNraXBwZWQgYWhlYWQuCisgICAgQWNjZXNz aWJpbGl0eU9iamVjdCogcHJldmlvdXNPYmplY3QgPSAwOworICAgIGlmICghaXNGb3J3YXJkKSB7 CisgICAgICAgIHByZXZpb3VzT2JqZWN0ID0gc3RhcnRPYmplY3Q7CisgICAgICAgIHN0YXJ0T2Jq ZWN0ID0gc3RhcnRPYmplY3QtPnBhcmVudE9iamVjdFVuaWdub3JlZCgpOworICAgIH0KKyAgICAK KyAgICAvLyBUaGUgb3V0ZXIgbG9vcCBzdGVwcyB1cCB0aGUgcGFyZW50IGNoYWluIGVhY2ggdGlt ZSAodW5pZ25vcmVkIGlzIGltcG9ydGFudCBoZXJlIGJlY2F1c2Ugb3RoZXJ3aXNlIGVsZW1lbnRz IHdvdWxkIGJlIHNlYXJjaGVkIHR3aWNlKQorICAgIGZvciAoQWNjZXNzaWJpbGl0eU9iamVjdCog c3RvcFNlYXJjaEVsZW1lbnQgPSBwYXJlbnRPYmplY3RVbmlnbm9yZWQoKTsgc3RhcnRPYmplY3Qg IT0gc3RvcFNlYXJjaEVsZW1lbnQ7IHN0YXJ0T2JqZWN0ID0gc3RhcnRPYmplY3QtPnBhcmVudE9i amVjdFVuaWdub3JlZCgpKSB7CisKKyAgICAgICAgLy8gT25seSBhcHBlbmQgdGhlIGNoaWxkcmVu IGFmdGVyL2JlZm9yZSB0aGUgcHJldmlvdXMgZWxlbWVudCwgc28gdGhhdCB0aGUgc2VhcmNoIGRv ZXMgbm90IGNoZWNrIGVsZW1lbnRzIHRoYXQgYXJlIAorICAgICAgICAvLyBhbHJlYWR5IGJlaGlu ZC9haGVhZCBvZiBzdGFydCBlbGVtZW50LgorICAgICAgICBBY2Nlc3NpYmlsaXR5Q2hpbGRyZW5W ZWN0b3Igc2VhcmNoU3RhY2s7CisgICAgICAgIGFwcGVuZENoaWxkcmVuVG9BcnJheShzdGFydE9i amVjdCwgaXNGb3J3YXJkLCBwcmV2aW91c09iamVjdCwgc2VhcmNoU3RhY2spOworCisgICAgICAg IC8vIFRoaXMgbm93IGRvZXMgYSBERlMgYXQgdGhlIGN1cnJlbnQgbGV2ZWwgb2YgdGhlIHBhcmVu dC4KKyAgICAgICAgd2hpbGUgKCFzZWFyY2hTdGFjay5pc0VtcHR5KCkpIHsKKyAgICAgICAgICAg IEFjY2Vzc2liaWxpdHlPYmplY3QqIHNlYXJjaE9iamVjdCA9IHNlYXJjaFN0YWNrLmxhc3QoKS5n ZXQoKTsKKyAgICAgICAgICAgIHNlYXJjaFN0YWNrLnJlbW92ZUxhc3QoKTsKKyAgICAgICAgICAg IAogICAgICAgICAgICAgaWYgKGlzQWNjZXNzaWJpbGl0eU9iamVjdFNlYXJjaE1hdGNoKHNlYXJj aE9iamVjdCwgY3JpdGVyaWEpICYmIGlzQWNjZXNzaWJpbGl0eVRleHRTZWFyY2hNYXRjaChzZWFy Y2hPYmplY3QsIGNyaXRlcmlhKSkgewogICAgICAgICAgICAgICAgIHJlc3VsdHMuYXBwZW5kKHNl YXJjaE9iamVjdCk7Ci0gICAgICAgICAgICAgCisgICAgICAgICAgICAgICAgCiAgICAgICAgICAg ICAgICAgLy8gRW5vdWdoIHJlc3VsdHMgd2VyZSBmb3VuZCB0byBzdG9wIHNlYXJjaGluZy4KICAg ICAgICAgICAgICAgICBpZiAocmVzdWx0cy5zaXplKCkgPj0gY3JpdGVyaWEtPnJlc3VsdHNMaW1p dCkKICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICB9Ci0gICAgICAgIH0g ZWxzZSBpZiAoc2VhcmNoT2JqZWN0ID09IHN0YXJ0T2JqZWN0KQotICAgICAgICAgICAgZGlkRmlu ZFN0YXJ0T2JqZWN0ID0gdHJ1ZTsKKyAgICAgICAgICAgIAorICAgICAgICAgICAgYXBwZW5kQ2hp bGRyZW5Ub0FycmF5KHNlYXJjaE9iamVjdCwgaXNGb3J3YXJkLCAwLCBzZWFyY2hTdGFjayk7Cisg ICAgICAgIH0KICAgICAgICAgCi0gICAgICAgIEFjY2Vzc2liaWxpdHlDaGlsZHJlblZlY3RvciBz ZWFyY2hDaGlsZHJlbiA9IHNlYXJjaE9iamVjdC0+Y2hpbGRyZW4oKTsKLSAgICAgICAgc2l6ZV90 IGNoaWxkcmVuU2l6ZSA9IHNlYXJjaENoaWxkcmVuLnNpemUoKTsKLSAgICAgICAgZm9yIChzaXpl X3QgaSA9IGlzRm9yd2FyZCA/IGNoaWxkcmVuU2l6ZSA6IDA7IGlzRm9yd2FyZCA/IGkgPiAwIDog aSA8IGNoaWxkcmVuU2l6ZTsgaXNGb3J3YXJkID8gaS0tIDogaSsrKSB7Ci0gICAgICAgICAgICAv LyBGSVhNRTogSGFuZGxlIGF0dGFjaG1lbnRzLgotICAgICAgICAgICAgc2VhcmNoU3RhY2suYXBw ZW5kKHNlYXJjaENoaWxkcmVuLmF0KGlzRm9yd2FyZCA/IGkgLSAxIDogaSkuZ2V0KCkpOwotICAg ICAgICB9CisgICAgICAgIGlmIChyZXN1bHRzLnNpemUoKSA+PSBjcml0ZXJpYS0+cmVzdWx0c0xp bWl0KQorICAgICAgICAgICAgYnJlYWs7CisKKyAgICAgICAgcHJldmlvdXNPYmplY3QgPSBzdGFy dE9iamVjdDsKICAgICB9CiB9CiAK