572394 - cache links within hypertext accessible

Status: VERIFIED FIXED

(Core :: Disability Access APIs, defect)

Description

[alexander :surkov (:asurkov)]

This should help much for sites containing lot of hyperlinks like blindcooltech.com running under screen readers who uses IAccessibleHyperText actively like NVDA. I think at the quick glance it should help blindcooltech.com be faster in 2 times with NVDA. As well it must help ATK screen readers like Orca.

Comment 1

[alexander :surkov (:asurkov)]

Attachment: patch

Comment 2

[Marco Zehe (:MarcoZ)]

Comment on attachment 451567 [details] [diff] [review]
patch

>+      var linkAcc = gParagraphAcc.getLinkAt(aExpectedLinkIndex);

Why did you remove the try...catch block here?

Comment 3

[alexander :surkov (:asurkov)]

because they do not fail on wrong argument, only if it's defunct but it's not happen.

Comment 4

[Marco Zehe (:MarcoZ)]

Ah OK. I'll wait with the r+ until I've seen a try-server build. But everything else in the test part is totally obvious stuff :)

Comment 5

[alexander :surkov (:asurkov)]

(In reply to comment #4)
> Ah OK. I'll wait with the r+ until I've seen a try-server build. But everything
> else in the test part is totally obvious stuff :)

I hope to get it soon. Thank you!

Comment 6

[alexander :surkov (:asurkov)]

try server build will be available here - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-d0df62afae0e/

Comment 7

[alexander :surkov (:asurkov)]

Attachment: patch2

fix style nits and linux failure

Comment 8

[Marco Zehe (:MarcoZ)]

Comment on attachment 451592 [details] [diff] [review]
patch2

blindcooltech.com is no longer being fully loaded by NVDA with this build, a regular nightly of yesterday is fine. Basically, only the first navigation links up to "Archive" are loaded into the virtual buffer, the rest, although in principle available in the accessible tree, is not being loaded into the buffer, not even after a refresh or similar. The next thing that should be following is the iframe with the ads.

Comment 9

[alexander :surkov (:asurkov)]

Attachment: patch3

the problem is fixed

Comment 10

[Marco Zehe (:MarcoZ)]

Comment on attachment 451897 [details] [diff] [review]
patch3

>+  <p id="p2"><a href="http://mozilla.org">mozilla.org</p>

Is it intentional that there is no closing </a> here? If not, provide a closing </a> before the </p> please.

Comment 11

[alexander :surkov (:asurkov)]

try server build - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-3a6a4c829afb/

Comment 12

[[e-mail]]

Comment on attachment 451897 [details] [diff] [review]
patch3

[Why does touching CAccessible*.h cause so much to rebuild?]

>+    nsAccessible* accChild  = hyperText ? hyperText->GetLinkAt(aChildIndex) :
>+                                          accWrap->GetChildAt(aChildIndex);
Nit: doubled space before =

>+  a11yFilters.cpp \
>+  nsAccCollector.cpp \
I'm confused that you're adding new files with what is presumably a "new" naming convention, but also still adding files with the "old" nsAcc prefix.

>+PRInt32
>+nsAccCollector::GetIndexAt(nsAccessible *aAccessible)
>+{
>+  EnsureObjects(-1);
>+
>+  PRUint32 collIdx = 0;
>+  return mIndexes.Get(aAccessible, &collIdx) ? collIdx : -1;
Nit: could check whether the accessible is already indexed first, i.e.

PRUint32 collIdx = 0;
if (mIndexes.Get(aAccessible, &collIndex))
  return collIdx;

EnsureObjects(-1);
return mIndexes.Get(aAccessible, &collIdx) ? collIdx : -1;

Alternatively, do you actually need to use a hashtable? You could just use indexOf on the nsTArray like this:

PRUint32 collIdx = mObjects.IndexOf(aAccessible);
if (collIdx != mObjects.NoIndex)
  return collIdx;

collIdx = mObjects.Length();
EnsureObjects(-1);
return mObjects.IndexOf(aAccessible, collIdx);

>+  if (aIndex != -1 && aIndex < static_cast<PRInt32>(mObjects.Length()))
>+    return;
Could use

if (static_cast<PRUint32>(aIndex) < mObjects.Length())
  return;

Or PRUint32 aIndex and pass in mObjects.NoIndex perhaps?

>+    mObjects.AppendElement(child);
>+    PRUint32 collIdx = mObjects.Length() - 1;
>+    mIndexes.Put(child, collIdx);
Why not reverse the order:

mIndexes.Put(child, mObjects.Length());
mObjects.AppendElement(child);

>+  nsRefPtr<nsHyperTextAccessible> hyperText =
>+    do_QueryObject(static_cast<nsISupports*>(this));
Although you inherit from nsISupports, the compiler has completely forgotten about it because you implement IUnknown, so it assumes you're uninterested in nsISupports. Add the following to the class declaration to remind it:

NS_IMETHOD QueryInterface(const nsIID & uuid, void * *result) = 0;

In theory you could s/do_QueryInterface/do_QueryObject/ on all the CAccessible*.cpp files. This would then allow you to remove nsISupports from all the CAccessible*.h files, instead you would just declare QueryInterface, although the *Wrap files would still need to re-declare AddRef and Release (maybe add macros for that in nsAccessibleWrap.h).

Comment 13

[alexander :surkov (:asurkov)]

(In reply to comment #12)
> >+  a11yFilters.cpp \
> >+  nsAccCollector.cpp \
> I'm confused that you're adding new files with what is presumably a "new"
> naming convention, but also still adding files with the "old" nsAcc prefix.

a habit :) What name would you suggest? and sorry where can I refer to new naming convention?

> Alternatively, do you actually need to use a hashtable? You could just use
> indexOf on the nsTArray like this:
> 
> PRUint32 collIdx = mObjects.IndexOf(aAccessible);

I hoped to be much faster with hashtable. IndexOf is about o(n) right?

Comment 14

[[e-mail]]

(In reply to comment #12)
> In theory you could s/do_QueryInterface/do_QueryObject/ on all the
> CAccessible*.cpp files. This would then allow you to remove nsISupports from
> all the CAccessible*.h files, instead you would just declare QueryInterface,
> although the *Wrap files would still need to re-declare AddRef and Release
> (maybe add macros for that in nsAccessibleWrap.h).
The point being that removing nsISupports from the CAccessible classes saves 4
bytes per object.

(In reply to comment #13)
> (In reply to comment #12)
> > >+  a11yFilters.cpp \
> > >+  nsAccCollector.cpp \
> > I'm confused that you're adding new files with what is presumably a "new"
> > naming convention, but also still adding files with the "old" nsAcc prefix.
> a habit :) What name would you suggest? and sorry where can I refer to new
> naming convention?
I'm not actaully sure, but I know that people are starting to drop the "ns" prefix. Which reminds me, all of your namespaces should be inside namespace mozilla. IIRC the .cpp files need something like "using namespace mozilla;"

> I hoped to be much faster with hashtable. IndexOf is about o(n) right?
Right. I wasn't sure how big N was likely to be.

Comment 15

[David Bolter [:davidb] (NeedInfo me for attention)]

(In reply to comment #14)
> (In reply to comment #12)
> > In theory you could s/do_QueryInterface/do_QueryObject/ on all the
> > CAccessible*.cpp files. This would then allow you to remove nsISupports from
> > all the CAccessible*.h files, instead you would just declare QueryInterface,
> > although the *Wrap files would still need to re-declare AddRef and Release
> > (maybe add macros for that in nsAccessibleWrap.h).
> The point being that removing nsISupports from the CAccessible classes saves 4
> bytes per object.

Nice.

> prefix. Which reminds me, all of your namespaces should be inside namespace
> mozilla. IIRC the .cpp files need something like "using namespace mozilla;"

Yeah we should start doing this.

Comment 16

[alexander :surkov (:asurkov)]

(In reply to comment #14)
> > I hoped to be much faster with hashtable. IndexOf is about o(n) right?
> Right. I wasn't sure how big N was likely to be.

You're right. Long arrays is quite rare thing, for example, document accessible of blindcooltech.com has about 4 thousands objects. But usually it's few children. Perhaps it makes sense to distinguish these cases.

What n is IndexOf faster than hash for? What n IndexOf is better than hash (speed vs memory)? I know these may not have answers but just a hint please?

Comment 17

[Marco Zehe (:MarcoZ)]

Alex, the try-server build for Win32 release didn't complete. Could you spin another so I can review it first thing on Monday when I return?

Comment 18

[alexander :surkov (:asurkov)]

Sure, I will do.

Comment 19

[alexander :surkov (:asurkov)]

Attachment: patch4

Use indexOf until there's a lot of children.

Comment 20

[alexander :surkov (:asurkov)]

Attachment: testcase

Comment 21

[[e-mail]]

(In reply to comment #16)
> What n is IndexOf faster than hash for? What n IndexOf is better than hash
> (speed vs memory)? I know these may not have answers but just a hint please?
Well, you pay 8 words (32/64 bytes) simply for having a hash table. As far as I can work out, each entry also costs you 24/32 bytes.
As for speed, hash of course uses nearly constant speed. But even then IndexOf will blow it away for small values of n, since hashing has to spend time computing the hash, which involves a function call, while IndexOf only needs to compare pointers; strings hash well because they're so slow to compare.
And of course IndexOf will always be much faster than having no cache at all.

Comment 22

[[e-mail]]

Comment on attachment 452221 [details] [diff] [review]
patch4

>+bool
>+filters::GetSelected(nsAccessible* aAccessible)

If you want to use namespaces within mozilla correctly, this should be

namespace mozilla {
namespace accessibility {
namespace filters {

bool GetSelected(nsAccessible* aAccessible)
{
  return nsAccUtils::State(aAccessible) & nsIAccessibleStates::STATE_SELECTED;
}

bool
GetSelectable(nsAccessible* aAccessible)

etc.

} // namespace filters
} // namespace accessibility
} // namespace mozilla

>+namespace filters {
And similarly here. Accessibility code that users filters will in the interim have a using namespace mozilla::accessibility; statement but eventually will all live inside the accessibility namespace.

Comment 23

[[e-mail]]

Comment on attachment 452221 [details] [diff] [review]
patch4

>+AccCollector::~AccCollector()
>+{
>+  mObjects.Clear();
Doesn't the TArray already do this?

>+  AccCollector.cpp \
>+  AccIterator.cpp \
>+  filters.cpp \
AccFilters.cpp perhaps?

Comment 24

[alexander :surkov (:asurkov)]

try-server build - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-914b2c1d576b/tryserver-win32/, blindcooltech.com with NVDA is faster in three times than Firefox 3.6 (6 seconds vs 2).

Comment 25

[alexander :surkov (:asurkov)]

(In reply to comment #22)
> (From update of attachment 452221 [details] [diff] [review])
> >+bool
> >+filters::GetSelected(nsAccessible* aAccessible)
> 
> If you want to use namespaces within mozilla correctly, this should be
> 
> namespace mozilla {
> namespace accessibility {
> namespace filters {

these headers aren't exported, it sounds it doesn't make sense to define namespace to add using namespace. I agree we should do this for exported headers. Though I think I would prefer a11y than accessibility, it's shorter :)

> >+  AccCollector.cpp \
> >+  AccIterator.cpp \
> >+  filters.cpp \
> AccFilters.cpp perhaps?

I really like to keep namespace names shorter and keep file name in sync with its content. I'm not sure what's the best way here. David, Marco?

Comment 26

[alexander :surkov (:asurkov)]

Though probably it doesn't make sense to calculate index hash until we were asked, at least on windows since it isn't used there. I think we should go with IndexOf approach only for now and get back to index hashing later.

Comment 27

[alexander :surkov (:asurkov)]

Attachment: patch5

remove indexes hashing, at least for now.

Comment 28

[alexander :surkov (:asurkov)]

Attachment: patch6

nits fixed

Comment 29

[alexander :surkov (:asurkov)]

try-server build - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-003d75865f73/ - makes faster in 1.5 times, trunk takes about 3 sec, try server build takes about 2 secs to load blindcooltech.com with NVDA.

Comment 30

[Marco Zehe (:MarcoZ)]

Comment on attachment 452462 [details] [diff] [review]
patch6

r=me. Thanks, this is a very good speed booster! I'm esp impressed with the perf win between 3.6 and this try-server, but also with the win for the current nightlies.

Comment 31

[David Bolter [:davidb] (NeedInfo me for attention)]

Comment on attachment 452462 [details] [diff] [review]
patch6

r=me! Sorry for the delay. I looked at this on the weekend and forgot to r+.

Comment 32

[David Bolter [:davidb] (NeedInfo me for attention)]

Comment on attachment 452462 [details] [diff] [review]
patch6

The only thing I'm not sure about is the namespacing... should probably take neil's advice here.

Comment 33

[alexander :surkov (:asurkov)]

(In reply to comment #32)
> (From update of attachment 452462 [details] [diff] [review])
> The only thing I'm not sure about is the namespacing... should probably take
> neil's advice here.

I'm sure it makes sense for exported things but since it's intended for internal usage only then I don't see a point. Do you?

Comment 34

[alexander :surkov (:asurkov)]

landed on 1.9.3 - http://hg.mozilla.org/mozilla-central/rev/abb7ee444c31.

Comment 35

[Marco Zehe (:MarcoZ)]

Verified fixed in Mozilla/5.0 (Windows; U; Windows NT 6.1; WOW64; de; rv:1.9.3a6pre) Gecko/20100622 Minefield/3.7a6pre (.NET CLR 3.5.30729)