Title: [266513] trunk/Source/WebCore
- Revision
- 266513
- Author
- wenson_hs...@apple.com
- Date
- 2020-09-03 07:20:25 -0700 (Thu, 03 Sep 2020)
Log Message
Make TransformationMatrix::inverse() faster in the case of affine transformation matrices
https://bugs.webkit.org/show_bug.cgi?id=216101
Reviewed by Tim Horton.
The Multiply subtest of MotionMark places a large number of elements that are all rotated by some angle; when
painting these, we currently spend about 7% of the time under `RenderLayer::paintLayerByApplyingTransform` just
inverting the transformation matrix (underneath `TransformationMatrix::inverse()`) so that we can map the bounds
of the dirty rect through this inverse.
`TransformationMatrix::inverse()` currently has a fast path for identity and translation matrices that avoids
having to fall back to the generalized 4-by-4 matrix inverse equation; this generalized algorithm works by
dividing the entire adjoint matrix by the determinant, a process that involves nearly 1000 floating point
additions and multiplications.
However, in this case, all of the matrices are a combination of translations and rotations, which all result in
affine transformations. As such, there's no need to fall back to the generalized algorithm for computing the
inverse; instead, we can bail early with simpler strategy that only requires 15 floating point additions and
multiplications.
We can also take advantange of the fact that we currently go through most of the entries in the 4x4 matrix to
determine whether the matrix is an identity or translation matrix, by introducing a new helper method that
returns not only whether the matrix is the identity matrix or translation, but also whether the matrix is affine
(by the definition of `TransformationMatrix::isAffine()`). Since most of the entries that need to be 1 or 0 in
order for a matrix to be a translation matrix vs. just an affine transformation matrix are the same, this helps
avoid some redundant checks in `TransformationMatrix::inverse()`.
We also apply a similar optimization to `TransformationMatrix::isInvertible()`, reducing the multiplications and
additions from roughly 200 to just 3.
I measured this locally to be a (statistically significant) 2% improvement on Multiply.
* platform/graphics/transforms/TransformationMatrix.cpp:
(WebCore::TransformationMatrix::isInvertible const):
(WebCore::TransformationMatrix::inverse const):
* platform/graphics/transforms/TransformationMatrix.h:
(WebCore::TransformationMatrix::type const):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (266512 => 266513)
--- trunk/Source/WebCore/ChangeLog 2020-09-03 14:19:37 UTC (rev 266512)
+++ trunk/Source/WebCore/ChangeLog 2020-09-03 14:20:25 UTC (rev 266513)
@@ -1,3 +1,43 @@
+2020-09-03 Wenson Hsieh <wenson_hs...@apple.com>
+
+ Make TransformationMatrix::inverse() faster in the case of affine transformation matrices
+ https://bugs.webkit.org/show_bug.cgi?id=216101
+
+ Reviewed by Tim Horton.
+
+ The Multiply subtest of MotionMark places a large number of elements that are all rotated by some angle; when
+ painting these, we currently spend about 7% of the time under `RenderLayer::paintLayerByApplyingTransform` just
+ inverting the transformation matrix (underneath `TransformationMatrix::inverse()`) so that we can map the bounds
+ of the dirty rect through this inverse.
+
+ `TransformationMatrix::inverse()` currently has a fast path for identity and translation matrices that avoids
+ having to fall back to the generalized 4-by-4 matrix inverse equation; this generalized algorithm works by
+ dividing the entire adjoint matrix by the determinant, a process that involves nearly 1000 floating point
+ additions and multiplications.
+
+ However, in this case, all of the matrices are a combination of translations and rotations, which all result in
+ affine transformations. As such, there's no need to fall back to the generalized algorithm for computing the
+ inverse; instead, we can bail early with simpler strategy that only requires 15 floating point additions and
+ multiplications.
+
+ We can also take advantange of the fact that we currently go through most of the entries in the 4x4 matrix to
+ determine whether the matrix is an identity or translation matrix, by introducing a new helper method that
+ returns not only whether the matrix is the identity matrix or translation, but also whether the matrix is affine
+ (by the definition of `TransformationMatrix::isAffine()`). Since most of the entries that need to be 1 or 0 in
+ order for a matrix to be a translation matrix vs. just an affine transformation matrix are the same, this helps
+ avoid some redundant checks in `TransformationMatrix::inverse()`.
+
+ We also apply a similar optimization to `TransformationMatrix::isInvertible()`, reducing the multiplications and
+ additions from roughly 200 to just 3.
+
+ I measured this locally to be a (statistically significant) 2% improvement on Multiply.
+
+ * platform/graphics/transforms/TransformationMatrix.cpp:
+ (WebCore::TransformationMatrix::isInvertible const):
+ (WebCore::TransformationMatrix::inverse const):
+ * platform/graphics/transforms/TransformationMatrix.h:
+ (WebCore::TransformationMatrix::type const):
+
2020-09-03 Youenn Fablet <you...@apple.com>
Expose RTCPeerConnection.restartIce
Modified: trunk/Source/WebCore/platform/graphics/transforms/TransformationMatrix.cpp (266512 => 266513)
--- trunk/Source/WebCore/platform/graphics/transforms/TransformationMatrix.cpp 2020-09-03 14:19:37 UTC (rev 266512)
+++ trunk/Source/WebCore/platform/graphics/transforms/TransformationMatrix.cpp 2020-09-03 14:20:25 UTC (rev 266513)
@@ -1459,20 +1459,17 @@
bool TransformationMatrix::isInvertible() const
{
- if (isIdentityOrTranslation())
+ auto type = this->type();
+ if (type == Type::IdentityOrTranslation)
return true;
- double det = WebCore::determinant4x4(m_matrix);
-
- if (fabs(det) < SMALL_NUMBER)
- return false;
-
- return true;
+ return fabs(type == Type::Affine ? (m11() * m22() - m12() * m21()) : WebCore::determinant4x4(m_matrix)) >= SMALL_NUMBER;
}
Optional<TransformationMatrix> TransformationMatrix::inverse() const
{
- if (isIdentityOrTranslation()) {
+ auto type = this->type();
+ if (type == Type::IdentityOrTranslation) {
// identity matrix
if (m_matrix[3][0] == 0 && m_matrix[3][1] == 0 && m_matrix[3][2] == 0)
return TransformationMatrix();
@@ -1484,6 +1481,28 @@
-m_matrix[3][0], -m_matrix[3][1], -m_matrix[3][2], 1);
}
+ if (type == Type::Affine) {
+ double a = m11();
+ double b = m12();
+ double c = m21();
+ double d = m22();
+ double e = m41();
+ double f = m42();
+ double determinant = a * d - b * c;
+ if (fabs(determinant) < SMALL_NUMBER)
+ return WTF::nullopt;
+
+ double inverseDeterminant = 1 / determinant;
+ return {{
+ d * inverseDeterminant,
+ -b * inverseDeterminant,
+ -c * inverseDeterminant,
+ a * inverseDeterminant,
+ (c * f - d * e) * inverseDeterminant,
+ (b * e - a * f) * inverseDeterminant
+ }};
+ }
+
TransformationMatrix invMat;
// FIXME: Use LU decomposition to apply the inverse instead of calculating the inverse explicitly.
// Calculating the inverse of a 4x4 matrix using cofactors is numerically unstable and unnecessary to apply the inverse transformation to a point.
Modified: trunk/Source/WebCore/platform/graphics/transforms/TransformationMatrix.h (266512 => 266513)
--- trunk/Source/WebCore/platform/graphics/transforms/TransformationMatrix.h 2020-09-03 14:19:37 UTC (rev 266512)
+++ trunk/Source/WebCore/platform/graphics/transforms/TransformationMatrix.h 2020-09-03 14:20:25 UTC (rev 266513)
@@ -435,6 +435,23 @@
return FloatPoint3D(static_cast<float>(resultX), static_cast<float>(resultY), static_cast<float>(resultZ));
}
+ enum class Type : uint8_t {
+ IdentityOrTranslation,
+ Affine,
+ Other
+ };
+
+ Type type() const
+ {
+ if (!m13() && !m14() && !m23() && !m24() && !m34() && !m31() && !m32() && m33() == 1 && m44() == 1) {
+ if (!m12() && !m21() && m11() == 1 && m22() == 1)
+ return Type::IdentityOrTranslation;
+ if (!m43())
+ return Type::Affine;
+ }
+ return Type::Other;
+ }
+
Matrix4 m_matrix;
};
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
