Bug 261968 – AX: AXIsolatedObject::m_propertyMap is not sparse

• Component: Accessibility
• Status: RESOLVED FIXED

[Joshua Hoffman]

AXIsolatedObject::m_propertyMap stores properties, regardless of whether or not they are the default value. Make this sparse to reduce memory footprint.

[Radar WebKit Bug Importer]

<rdar://problem/115907545>

[Joshua Hoffman]

Created attachment 467830 [details]
Patch

[Joshua Hoffman]

Created attachment 467832 [details]
Patch

[Tyler Wilcock]

Comment on attachment 467832 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=467832&action=review

> Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:56
> +    // Allocates a capacity based on the average of node properties stored in the sparse map.
> +    m_propertyMap.reserveInitialCapacity(27);

I know sizing this based on the average number of properties each object has was my idea. But I wonder if it makes more sense to size based on the minimum number of properties any object has, because right now we size at 27, which is over provisioned for objects that have less than that. Ideally we would just shrink the hash map after initializeProperties below, but I don't think there's a shrinkToFit function on WTF::HashMap like exists on WTF::Vector. Might be worth measuring if there's any difference in sizing based on the minimum vs. average so we know?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:396
> +            [](String& typedValue) { return typedValue == emptyString(); },

What about typedValue.isEmpty()? That checks for both null and zero-length strings.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.h:158
> +    std::pair<unsigned, unsigned> rowIndexRange() const override { return indexRangePairAttributeValue(AXPropertyName::RowIndexRange); }

Let's make this final rather than override since we're changing this line anyways. Same for columnIndexRange.

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #4)
> Comment on attachment 467832 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=467832&action=review
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:56
> > +    // Allocates a capacity based on the average of node properties stored in the sparse map.
> > +    m_propertyMap.reserveInitialCapacity(27);
> 
> I know sizing this based on the average number of properties each object has
> was my idea. But I wonder if it makes more sense to size based on the
> minimum number of properties any object has, because right now we size at
> 27, which is over provisioned for objects that have less than that. Ideally
> we would just shrink the hash map after initializeProperties below, but I
> don't think there's a shrinkToFit function on WTF::HashMap like exists on
> WTF::Vector. Might be worth measuring if there's any difference in sizing
> based on the minimum vs. average so we know?
> 

The definitely makes sense, I can investigate this and grab some numbers. 

> > Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:396
> > +            [](String& typedValue) { return typedValue == emptyString(); },
> 
> What about typedValue.isEmpty()? That checks for both null and zero-length
> strings.

Some of our tests were written to expect null strings, so we need to store them. But, maybe this is the wrong behavior, depending on what ATs are expecting?

[Tyler Wilcock]

> > > Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:396
> > > +            [](String& typedValue) { return typedValue == emptyString(); },
> > 
> > What about typedValue.isEmpty()? That checks for both null and zero-length
> > strings.
> 
> Some of our tests were written to expect null strings, so we need to store
> them. But, maybe this is the wrong behavior, depending on what ATs are
> expecting?
I can't imagine there's a difference for an AT between null and empty string (but I could be wrong). But also maybe stringAttributeValue should return `nullString()` rather than `emptyString()` for things that aren't in the property map? Would that resolve the test failures without introducing new ones?

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #6)
> > > > Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:396
> > > > +            [](String& typedValue) { return typedValue == emptyString(); },
> > > 
> > > What about typedValue.isEmpty()? That checks for both null and zero-length
> > > strings.
> > 
> > Some of our tests were written to expect null strings, so we need to store
> > them. But, maybe this is the wrong behavior, depending on what ATs are
> > expecting?
> I can't imagine there's a difference for an AT between null and empty string
> (but I could be wrong). But also maybe stringAttributeValue should return
> `nullString()` rather than `emptyString()` for things that aren't in the
> property map? Would that resolve the test failures without introducing new
> ones?

Unfortunately, we need to store the null string in the map so we know when to use the platform string instead (which checks the property map to see if a property is stored).

(In reply to Tyler Wilcock from comment #4)
> Comment on attachment 467832 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=467832&action=review
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:56
> > +    // Allocates a capacity based on the average of node properties stored in the sparse map.
> > +    m_propertyMap.reserveInitialCapacity(27);
> 
> I know sizing this based on the average number of properties each object has
> was my idea. But I wonder if it makes more sense to size based on the
> minimum number of properties any object has, because right now we size at
> 27, which is over provisioned for objects that have less than that. Ideally
> we would just shrink the hash map after initializeProperties below, but I
> don't think there's a shrinkToFit function on WTF::HashMap like exists on
> WTF::Vector. Might be worth measuring if there's any difference in sizing
> based on the minimum vs. average so we know?

The minimum I calculated to be 22 properties, but that did have an average of a 3% greater decrease in the memory footprint over using the average, so definitely seems worthwhile.

[Joshua Hoffman]

Created attachment 467844 [details]
Patch

[Tyler Wilcock]

Comment on attachment 467844 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=467844&action=review

Big improvement!

> Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:55
> +    // Allocates a capacity based on the minimum of node properties stored in the sparse map.

Minor nit — the term "sparse map" makes sense in the context of this patch, but we don't explain that term anywhere, so it might be a bit confusing in the future. Since our behavior will now inherently be to only insert "sparsely" into the property map, maybe the comment should be something like:

// Allocate a capacity based on the minimum properties an object has (based on measurements from a real webpage).

Re-word as you please if you have a better idea.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:422
> +            [](auto&) { return false; }

Might be nice to have an ASSERT_NOT_REACHED() here in case we forget to update this after updating the variant. I also wonder if we should have a comment next to the definition of AXPropertyValueVariant mentioning that if anything is added or removed from the variant, we must update this function.

[Andres Gonzalez]

(In reply to Joshua Hoffman from comment #8)
> Created attachment 467844 [details]
> Patch

From e17ff9444a804f3d6eb050003c0c64386a6f5d1a Mon Sep 17 00:00:00 2001
From: Joshua Hoffman <[e-mail]>
Date: Fri, 22 Sep 2023 13:51:48 -0700
Subject: [PATCH] AX: AXIsolatedObject::m_propertyMap is not sparse
 https://bugs.webkit.org/show_bug.cgi?id=261968 rdar://115907545

Reviewed by NOBODY (OOPS!).

This patch makes the AXIsolatedObject::m_propertyMap, where AXIsolatedObject properties are cached,
sparse. This is accomplished though conditionally adding properties to the map, based on whether

AG: Typo ? though -> through

their values are the default for their given type. If a value is the default, we don't add it to
the map (or if it changes to be the default, we remove it). Our existing logic handles these cases
by returning the type's default value when it does not exist in the property map.

The inital size allocation for the propertyMap was brought down to 22 from 92 after running

AG: Typo: inital -> initial

this change on several sites and finding the minimum number of properties stored.

With this patch applied, on average it reduces the memory footprint of the web process (with AX
enabled) by ~33%. This analysis was performed using VoiceOver on an academic journal page.

* Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:
(WebCore::AXIsolatedObject::AXIsolatedObject):
(WebCore::AXIsolatedObject::setProperty):
(WebCore::AXIsolatedObject::indexRangePairAttributeValue const):
(WebCore::AXIsolatedObject::pairAttributeValue const): Deleted.
* Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.h:
---
 .../isolatedtree/AXIsolatedObject.cpp         | 52 +++++++++++++++----
 .../isolatedtree/AXIsolatedObject.h           |  6 +--
 2 files changed, 45 insertions(+), 13 deletions(-)

diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp b/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
index 78bfc19927aa..ac513206d3c8 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
@@ -52,10 +52,8 @@ AXIsolatedObject::AXIsolatedObject(const Ref<AccessibilityObject>& axObject, AXI
     auto* axParent = axObject->parentObjectUnignored();
     m_parentID = axParent ? axParent->objectID() : AXID();

-    // Every object will have at least this many properties. We can shrink this number
-    // to some estimated average once we implement sparse property storage (i.e. only storing
-    // a property if it's not the default value for its type).
-    m_propertyMap.reserveInitialCapacity(92);
+    // Allocates a capacity based on the minimum of node properties stored in the sparse map.
+    m_propertyMap.reserveInitialCapacity(22);

     initializeProperties(axObject);
 }
@@ -391,8 +389,43 @@ void AXIsolatedObject::setProperty(AXPropertyName propertyName, AXPropertyValueV
 {
     if (shouldRemove)
         m_propertyMap.remove(propertyName);
-    else
-        m_propertyMap.set(propertyName, value);
+    else {
+        bool isDefaultValue = WTF::switchOn(value,
+            [](std::nullptr_t&) { return true; },
+            [](AXID typedValue) { return typedValue == AXID(); },

AG: return !typedValue.isValid();

+            [](String& typedValue) { return typedValue == emptyString(); },
+            [](bool typedValue) { return !typedValue; },
+            [](int typedValue) { return !typedValue; },
+            [](unsigned typedValue) { return !typedValue; },
+            [](double typedValue) { return typedValue == 0.0; },
+            [](float typedValue) { return typedValue == 0.0; },
+            [](uint64_t typedValue) { return !typedValue; },
+            [](AccessibilityButtonState& typedValue) { return typedValue == AccessibilityButtonState::Off; },
+            [](Color& typedValue) { return typedValue == Color(); },
+            [](URL& typedValue) { return typedValue == URL(); },
+            [](LayoutRect& typedValue) { return typedValue == LayoutRect(); },
+            [](IntPoint& typedValue) { return typedValue == IntPoint(); },
+            [](std::pair<unsigned, unsigned>& typedValue) { return typedValue == std::pair<unsigned, unsigned>(0, 1); },

AG: maybe worth a comment, why not (0, 0)?

+            [](Vector<AccessibilityText>& typedValue) { return typedValue.isEmpty(); },
+            [](Vector<AXID>& typedValue) { return typedValue.isEmpty(); },
+            [](Vector<std::pair<AXID, AXID>>& typedValue) { return typedValue.isEmpty(); },
+            [](Vector<String>& typedValue) { return typedValue.isEmpty(); },
+            [](Path& typedValue) { return typedValue == Path(); },
+            [](OptionSet<AXAncestorFlag>& typedValue) { return typedValue.isEmpty(); },
+            [](RetainPtr<NSAttributedString>& typedValue) { return !typedValue.get(); },

AG: COCOA only. I think !typedValue; is enough.

+            [](InsideLink& typedValue) { return typedValue == InsideLink(); },
+            [](Vector<Vector<AXID>>& typedValue) { return typedValue.isEmpty(); },
+            [](CharacterRange& typedValue) { return !typedValue.location && !typedValue.length; },
+            [](std::pair<AXID, CharacterRange>& typedValue) {
+                return typedValue.first == AXID() && !typedValue.second.location && !typedValue.second.length;

AG: !typedValue.first.isValid() || ...

+            },
+            [](auto&) { return false; }
+        );
+        if (isDefaultValue)
+            m_propertyMap.remove(propertyName);
+        else
+            m_propertyMap.set(propertyName, value);
+    }
 }

 void AXIsolatedObject::detachRemoteParts(AccessibilityDetachmentType)
@@ -758,13 +791,12 @@ OptionSet<T> AXIsolatedObject::optionSetAttributeValue(AXPropertyName propertyNa
     );
 }

-template<typename T>
-std::pair<T, T> AXIsolatedObject::pairAttributeValue(AXPropertyName propertyName) const
+std::pair<unsigned, unsigned> AXIsolatedObject::indexRangePairAttributeValue(AXPropertyName propertyName) const
 {
     auto value = m_propertyMap.get(propertyName);
     return WTF::switchOn(value,
-        [] (std::pair<T, T>& typedValue) -> std::pair<T, T> { return typedValue; },
-        [] (auto&) { return std::pair<T, T>(0, 1); }
+        [] (std::pair<unsigned, unsigned>& typedValue) -> std::pair<unsigned, unsigned> { return typedValue; },
+        [] (auto&) { return std::pair<unsigned, unsigned>(0, 1); }
     );
 }

[Joshua Hoffman]

Comment on attachment 467844 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=467844&action=review

>> Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp:422
>> +            [](auto&) { return false; }
> 
> Might be nice to have an ASSERT_NOT_REACHED() here in case we forget to update this after updating the variant. I also wonder if we should have a comment next to the definition of AXPropertyValueVariant mentioning that if anything is added or removed from the variant, we must update this function.

Good call—I'll add a comment there.

[Joshua Hoffman]

(In reply to Andres Gonzalez from comment #10)
> (In reply to Joshua Hoffman from comment #8)
> > Created attachment 467844 [details]
> > Patch
> 
> +            [](String& typedValue) { return typedValue == emptyString(); },
> +            [](bool typedValue) { return !typedValue; },
> +            [](int typedValue) { return !typedValue; },
> +            [](unsigned typedValue) { return !typedValue; },
> +            [](double typedValue) { return typedValue == 0.0; },
> +            [](float typedValue) { return typedValue == 0.0; },
> +            [](uint64_t typedValue) { return !typedValue; },
> +            [](AccessibilityButtonState& typedValue) { return typedValue ==
> AccessibilityButtonState::Off; },
> +            [](Color& typedValue) { return typedValue == Color(); },
> +            [](URL& typedValue) { return typedValue == URL(); },
> +            [](LayoutRect& typedValue) { return typedValue == LayoutRect();
> },
> +            [](IntPoint& typedValue) { return typedValue == IntPoint(); },
> +            [](std::pair<unsigned, unsigned>& typedValue) { return
> typedValue == std::pair<unsigned, unsigned>(0, 1); },
> 
> AG: maybe worth a comment, why not (0, 0)?
> 
(0, 1) is the default for an index range, but I will add that comment in to clarify.

[Joshua Hoffman]

(In reply to Andres Gonzalez from comment #10)
> (In reply to Joshua Hoffman from comment #8)
> > Created attachment 467844 [details]
> > Patch

> 
> +            [](Vector<AccessibilityText>& typedValue) { return
> typedValue.isEmpty(); },
> +            [](Vector<AXID>& typedValue) { return typedValue.isEmpty(); },
> +            [](Vector<std::pair<AXID, AXID>>& typedValue) { return
> typedValue.isEmpty(); },
> +            [](Vector<String>& typedValue) { return typedValue.isEmpty(); },
> +            [](Path& typedValue) { return typedValue == Path(); },
> +            [](OptionSet<AXAncestorFlag>& typedValue) { return
> typedValue.isEmpty(); },
> +            [](RetainPtr<NSAttributedString>& typedValue) { return
> !typedValue.get(); },
> 
> AG: COCOA only. I think !typedValue; is enough.

Is it necessary to put build flags around this? We define the variant type on all platforms already and that includes RetainPtr<NSAttributedString>.

[Andres Gonzalez]

(In reply to Joshua Hoffman from comment #13)
> (In reply to Andres Gonzalez from comment #10)
> > (In reply to Joshua Hoffman from comment #8)
> > > Created attachment 467844 [details]
> > > Patch
> 
> > 
> > +            [](Vector<AccessibilityText>& typedValue) { return
> > typedValue.isEmpty(); },
> > +            [](Vector<AXID>& typedValue) { return typedValue.isEmpty(); },
> > +            [](Vector<std::pair<AXID, AXID>>& typedValue) { return
> > typedValue.isEmpty(); },
> > +            [](Vector<String>& typedValue) { return typedValue.isEmpty(); },
> > +            [](Path& typedValue) { return typedValue == Path(); },
> > +            [](OptionSet<AXAncestorFlag>& typedValue) { return
> > typedValue.isEmpty(); },
> > +            [](RetainPtr<NSAttributedString>& typedValue) { return
> > !typedValue.get(); },
> > 
> > AG: COCOA only. I think !typedValue; is enough.
> 
> Is it necessary to put build flags around this? We define the variant type
> on all platforms already and that includes RetainPtr<NSAttributedString>.

We should. If we didn't in the variant declaration, that was an oversight that we should fix as well. The reason it builds is because ACCESSIBILITY_ISOLATED_TREE is enabled only on Mac at the moment, but that could change.

[Andres Gonzalez]

Also forgot to mention than in the switchOn call, I think that the WebKit style standard ask for a space in between [] and the (...) for all the lambdas.

[Joshua Hoffman]

(In reply to Andres Gonzalez from comment #15)
> Also forgot to mention than in the switchOn call, I think that the WebKit
> style standard ask for a space in between [] and the (...) for all the
> lambdas.

For lamdas, WebKit style wants the space after the parentheses, but not after the square brackets: https://webkit.org/code-style-guidelines/#spacing-lambda-paren.

[Joshua Hoffman]

Created attachment 467847 [details]
Patch

[EWS]

Committed 268449@main (8a06d352a4ab): <https://commits.webkit.org/268449@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 467847 [details].