WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
RESOLVED FIXED
261968
AX: AXIsolatedObject::m_propertyMap is not sparse
https://bugs.webkit.org/show_bug.cgi?id=261968
Summary
AX: AXIsolatedObject::m_propertyMap is not sparse
Joshua Hoffman
Reported
2023-09-22 13:27:12 PDT
AXIsolatedObject::m_propertyMap stores properties, regardless of whether or not they are the default value. Make this sparse to reduce memory footprint.
Attachments
Patch
(8.29 KB, patch)
2023-09-22 14:18 PDT
,
Joshua Hoffman
no flags
Details
Formatted Diff
Diff
Patch
(8.18 KB, patch)
2023-09-22 14:30 PDT
,
Joshua Hoffman
no flags
Details
Formatted Diff
Diff
Patch
(8.19 KB, patch)
2023-09-24 18:52 PDT
,
Joshua Hoffman
no flags
Details
Formatted Diff
Diff
Patch
(10.14 KB, patch)
2023-09-25 11:34 PDT
,
Joshua Hoffman
no flags
Details
Formatted Diff
Diff
Show Obsolete
(3)
View All
Add attachment
proposed patch, testcase, etc.
Radar WebKit Bug Importer
Comment 1
2023-09-22 13:27:28 PDT
<
rdar://problem/115907545
>
Joshua Hoffman
Comment 2
2023-09-22 14:18:55 PDT
Created
attachment 467830
[details]
Patch
Joshua Hoffman
Comment 3
2023-09-22 14:30:12 PDT
Created
attachment 467832
[details]
Patch
Tyler Wilcock
Comment 4
2023-09-22 14:45:43 PDT
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
Comment 5
2023-09-22 14:51:24 PDT
(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
Comment 6
2023-09-22 15:18:04 PDT
> > > 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
Comment 7
2023-09-24 18:50:29 PDT
(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
Comment 8
2023-09-24 18:52:41 PDT
Created
attachment 467844
[details]
Patch
Tyler Wilcock
Comment 9
2023-09-24 19:46:29 PDT
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
Comment 10
2023-09-25 07:07:15 PDT
(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 <
jhoffman23@apple.com
> 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 11
2023-09-25 09:29:46 PDT
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
Comment 12
2023-09-25 09:31:08 PDT
(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
Comment 13
2023-09-25 09:51:21 PDT
(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
Comment 14
2023-09-25 10:56:03 PDT
(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
Comment 15
2023-09-25 11:02:50 PDT
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
Comment 16
2023-09-25 11:07:44 PDT
(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
Comment 17
2023-09-25 11:34:48 PDT
Created
attachment 467847
[details]
Patch
EWS
Comment 18
2023-09-26 07:06:52 PDT
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]
.
Note
You need to
log in
before you can comment on or make changes to this bug.
Top of Page
Format For Printing
XML
Clone This Bug