Hash :
c9955641
Author :
Date :
2023-09-25T14:31:01
Avoid malloc in angle::Mat4 by using array instead of vector angle::Matrix<float>::inverse() showed up in cpu profile of "minetest" trace at ~10%. It's a gles1 trace. Multiple objects are constructed and require malloc due to the use of std::vector. Called here: https://crsrc.org/c/third_party/angle/src/libANGLE/GLES1Renderer.cpp;drc=eb0d59973d21f845b5785563f5d56b8ebb617478;l=371 This CL decouples Mat4 from angle::Matrix (some of the functionality had to be copied over) to switch from std::vector to std::array. Testing "minetest" on a phone I saw a ~20% cpu power improvement due to this CL. There is an existing unit test coverage: MatrixUtilsTest.Mat4InvTr Moved 4x4 cofactor matrix code to a helper with transposition included Bug: b/301977186 Change-Id: I1e4c2201d19759dd37c0fee44fb44f4d24a58a6b Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/4885501 Reviewed-by: Charlie Lao <cclao@google.com> Reviewed-by: Shahbaz Youssefi <syoussefi@chromium.org> Commit-Queue: Roman Lavrov <romanl@google.com>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
//
// Copyright 2015 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// Matrix:
// Utility class implementing various matrix operations.
// Supports matrices with minimum 2 and maximum 4 number of rows/columns.
//
// TODO: Check if we can merge Matrix.h in sample_util with this and replace it with this
// implementation.
// TODO: Rename this file to Matrix.h once we remove Matrix.h in sample_util.
#ifndef COMMON_MATRIX_UTILS_H_
#define COMMON_MATRIX_UTILS_H_
#include <array>
#include <vector>
#include "common/debug.h"
#include "common/mathutil.h"
#include "common/vector_utils.h"
namespace
{
template <typename T4x4>
void CofactorTransposed(const T4x4 &mat, T4x4 &coft)
{
coft(0, 0) = mat(1, 1) * mat(2, 2) * mat(3, 3) + mat(2, 1) * mat(3, 2) * mat(1, 3) +
mat(3, 1) * mat(1, 2) * mat(2, 3) - mat(1, 1) * mat(3, 2) * mat(2, 3) -
mat(2, 1) * mat(1, 2) * mat(3, 3) - mat(3, 1) * mat(2, 2) * mat(1, 3);
coft(1, 0) = -(mat(1, 0) * mat(2, 2) * mat(3, 3) + mat(2, 0) * mat(3, 2) * mat(1, 3) +
mat(3, 0) * mat(1, 2) * mat(2, 3) - mat(1, 0) * mat(3, 2) * mat(2, 3) -
mat(2, 0) * mat(1, 2) * mat(3, 3) - mat(3, 0) * mat(2, 2) * mat(1, 3));
coft(2, 0) = mat(1, 0) * mat(2, 1) * mat(3, 3) + mat(2, 0) * mat(3, 1) * mat(1, 3) +
mat(3, 0) * mat(1, 1) * mat(2, 3) - mat(1, 0) * mat(3, 1) * mat(2, 3) -
mat(2, 0) * mat(1, 1) * mat(3, 3) - mat(3, 0) * mat(2, 1) * mat(1, 3);
coft(3, 0) = -(mat(1, 0) * mat(2, 1) * mat(3, 2) + mat(2, 0) * mat(3, 1) * mat(1, 2) +
mat(3, 0) * mat(1, 1) * mat(2, 2) - mat(1, 0) * mat(3, 1) * mat(2, 2) -
mat(2, 0) * mat(1, 1) * mat(3, 2) - mat(3, 0) * mat(2, 1) * mat(1, 2));
coft(0, 1) = -(mat(0, 1) * mat(2, 2) * mat(3, 3) + mat(2, 1) * mat(3, 2) * mat(0, 3) +
mat(3, 1) * mat(0, 2) * mat(2, 3) - mat(0, 1) * mat(3, 2) * mat(2, 3) -
mat(2, 1) * mat(0, 2) * mat(3, 3) - mat(3, 1) * mat(2, 2) * mat(0, 3));
coft(1, 1) = mat(0, 0) * mat(2, 2) * mat(3, 3) + mat(2, 0) * mat(3, 2) * mat(0, 3) +
mat(3, 0) * mat(0, 2) * mat(2, 3) - mat(0, 0) * mat(3, 2) * mat(2, 3) -
mat(2, 0) * mat(0, 2) * mat(3, 3) - mat(3, 0) * mat(2, 2) * mat(0, 3);
coft(2, 1) = -(mat(0, 0) * mat(2, 1) * mat(3, 3) + mat(2, 0) * mat(3, 1) * mat(0, 3) +
mat(3, 0) * mat(0, 1) * mat(2, 3) - mat(0, 0) * mat(3, 1) * mat(2, 3) -
mat(2, 0) * mat(0, 1) * mat(3, 3) - mat(3, 0) * mat(2, 1) * mat(0, 3));
coft(3, 1) = mat(0, 0) * mat(2, 1) * mat(3, 2) + mat(2, 0) * mat(3, 1) * mat(0, 2) +
mat(3, 0) * mat(0, 1) * mat(2, 2) - mat(0, 0) * mat(3, 1) * mat(2, 2) -
mat(2, 0) * mat(0, 1) * mat(3, 2) - mat(3, 0) * mat(2, 1) * mat(0, 2);
coft(0, 2) = mat(0, 1) * mat(1, 2) * mat(3, 3) + mat(1, 1) * mat(3, 2) * mat(0, 3) +
mat(3, 1) * mat(0, 2) * mat(1, 3) - mat(0, 1) * mat(3, 2) * mat(1, 3) -
mat(1, 1) * mat(0, 2) * mat(3, 3) - mat(3, 1) * mat(1, 2) * mat(0, 3);
coft(1, 2) = -(mat(0, 0) * mat(1, 2) * mat(3, 3) + mat(1, 0) * mat(3, 2) * mat(0, 3) +
mat(3, 0) * mat(0, 2) * mat(1, 3) - mat(0, 0) * mat(3, 2) * mat(1, 3) -
mat(1, 0) * mat(0, 2) * mat(3, 3) - mat(3, 0) * mat(1, 2) * mat(0, 3));
coft(2, 2) = mat(0, 0) * mat(1, 1) * mat(3, 3) + mat(1, 0) * mat(3, 1) * mat(0, 3) +
mat(3, 0) * mat(0, 1) * mat(1, 3) - mat(0, 0) * mat(3, 1) * mat(1, 3) -
mat(1, 0) * mat(0, 1) * mat(3, 3) - mat(3, 0) * mat(1, 1) * mat(0, 3);
coft(3, 2) = -(mat(0, 0) * mat(1, 1) * mat(3, 2) + mat(1, 0) * mat(3, 1) * mat(0, 2) +
mat(3, 0) * mat(0, 1) * mat(1, 2) - mat(0, 0) * mat(3, 1) * mat(1, 2) -
mat(1, 0) * mat(0, 1) * mat(3, 2) - mat(3, 0) * mat(1, 1) * mat(0, 2));
coft(0, 3) = -(mat(0, 1) * mat(1, 2) * mat(2, 3) + mat(1, 1) * mat(2, 2) * mat(0, 3) +
mat(2, 1) * mat(0, 2) * mat(1, 3) - mat(0, 1) * mat(2, 2) * mat(1, 3) -
mat(1, 1) * mat(0, 2) * mat(2, 3) - mat(2, 1) * mat(1, 2) * mat(0, 3));
coft(1, 3) = mat(0, 0) * mat(1, 2) * mat(2, 3) + mat(1, 0) * mat(2, 2) * mat(0, 3) +
mat(2, 0) * mat(0, 2) * mat(1, 3) - mat(0, 0) * mat(2, 2) * mat(1, 3) -
mat(1, 0) * mat(0, 2) * mat(2, 3) - mat(2, 0) * mat(1, 2) * mat(0, 3);
coft(2, 3) = -(mat(0, 0) * mat(1, 1) * mat(2, 3) + mat(1, 0) * mat(2, 1) * mat(0, 3) +
mat(2, 0) * mat(0, 1) * mat(1, 3) - mat(0, 0) * mat(2, 1) * mat(1, 3) -
mat(1, 0) * mat(0, 1) * mat(2, 3) - mat(2, 0) * mat(1, 1) * mat(0, 3));
coft(3, 3) = mat(0, 0) * mat(1, 1) * mat(2, 2) + mat(1, 0) * mat(2, 1) * mat(0, 2) +
mat(2, 0) * mat(0, 1) * mat(1, 2) - mat(0, 0) * mat(2, 1) * mat(1, 2) -
mat(1, 0) * mat(0, 1) * mat(2, 2) - mat(2, 0) * mat(1, 1) * mat(0, 2);
}
} // namespace
namespace angle
{
template <typename T>
class Matrix
{
public:
Matrix(const std::vector<T> &elements, const unsigned int numRows, const unsigned int numCols)
: mElements(elements), mRows(numRows), mCols(numCols)
{
ASSERT(rows() >= 1 && rows() <= 4);
ASSERT(columns() >= 1 && columns() <= 4);
}
Matrix(const std::vector<T> &elements, const unsigned int size)
: mElements(elements), mRows(size), mCols(size)
{
ASSERT(rows() >= 1 && rows() <= 4);
ASSERT(columns() >= 1 && columns() <= 4);
}
Matrix(const T *elements, const unsigned int size) : mRows(size), mCols(size)
{
ASSERT(rows() >= 1 && rows() <= 4);
ASSERT(columns() >= 1 && columns() <= 4);
for (size_t i = 0; i < size * size; i++)
mElements.push_back(elements[i]);
}
const T &operator()(const unsigned int rowIndex, const unsigned int columnIndex) const
{
ASSERT(rowIndex < mRows);
ASSERT(columnIndex < mCols);
return mElements[rowIndex * columns() + columnIndex];
}
T &operator()(const unsigned int rowIndex, const unsigned int columnIndex)
{
ASSERT(rowIndex < mRows);
ASSERT(columnIndex < mCols);
return mElements[rowIndex * columns() + columnIndex];
}
const T &at(const unsigned int rowIndex, const unsigned int columnIndex) const
{
ASSERT(rowIndex < mRows);
ASSERT(columnIndex < mCols);
return operator()(rowIndex, columnIndex);
}
Matrix<T> operator*(const Matrix<T> &m)
{
ASSERT(columns() == m.rows());
unsigned int resultRows = rows();
unsigned int resultCols = m.columns();
Matrix<T> result(std::vector<T>(resultRows * resultCols), resultRows, resultCols);
for (unsigned int i = 0; i < resultRows; i++)
{
for (unsigned int j = 0; j < resultCols; j++)
{
T tmp = 0.0f;
for (unsigned int k = 0; k < columns(); k++)
tmp += at(i, k) * m(k, j);
result(i, j) = tmp;
}
}
return result;
}
void operator*=(const Matrix<T> &m)
{
ASSERT(columns() == m.rows());
Matrix<T> res = (*this) * m;
size_t numElts = res.elements().size();
mElements.resize(numElts);
memcpy(mElements.data(), res.data(), numElts * sizeof(float));
}
bool operator==(const Matrix<T> &m) const
{
ASSERT(columns() == m.columns());
ASSERT(rows() == m.rows());
return mElements == m.elements();
}
bool operator!=(const Matrix<T> &m) const { return !(mElements == m.elements()); }
bool nearlyEqual(T epsilon, const Matrix<T> &m) const
{
ASSERT(columns() == m.columns());
ASSERT(rows() == m.rows());
const auto &otherElts = m.elements();
for (size_t i = 0; i < otherElts.size(); i++)
{
if ((mElements[i] - otherElts[i] > epsilon) && (otherElts[i] - mElements[i] > epsilon))
return false;
}
return true;
}
unsigned int size() const
{
ASSERT(rows() == columns());
return rows();
}
unsigned int rows() const { return mRows; }
unsigned int columns() const { return mCols; }
std::vector<T> elements() const { return mElements; }
T *data() { return mElements.data(); }
const T *constData() const { return mElements.data(); }
Matrix<T> compMult(const Matrix<T> &mat1) const
{
Matrix result(std::vector<T>(mElements.size()), rows(), columns());
for (unsigned int i = 0; i < rows(); i++)
{
for (unsigned int j = 0; j < columns(); j++)
{
T lhs = at(i, j);
T rhs = mat1(i, j);
result(i, j) = rhs * lhs;
}
}
return result;
}
Matrix<T> outerProduct(const Matrix<T> &mat1) const
{
unsigned int cols = mat1.columns();
Matrix result(std::vector<T>(rows() * cols), rows(), cols);
for (unsigned int i = 0; i < rows(); i++)
for (unsigned int j = 0; j < cols; j++)
result(i, j) = at(i, 0) * mat1(0, j);
return result;
}
Matrix<T> transpose() const
{
Matrix result(std::vector<T>(mElements.size()), columns(), rows());
for (unsigned int i = 0; i < columns(); i++)
for (unsigned int j = 0; j < rows(); j++)
result(i, j) = at(j, i);
return result;
}
T determinant() const
{
ASSERT(rows() == columns());
switch (size())
{
case 2:
return at(0, 0) * at(1, 1) - at(0, 1) * at(1, 0);
case 3:
return at(0, 0) * at(1, 1) * at(2, 2) + at(0, 1) * at(1, 2) * at(2, 0) +
at(0, 2) * at(1, 0) * at(2, 1) - at(0, 2) * at(1, 1) * at(2, 0) -
at(0, 1) * at(1, 0) * at(2, 2) - at(0, 0) * at(1, 2) * at(2, 1);
case 4:
{
const float minorMatrices[4][3 * 3] = {{
at(1, 1),
at(2, 1),
at(3, 1),
at(1, 2),
at(2, 2),
at(3, 2),
at(1, 3),
at(2, 3),
at(3, 3),
},
{
at(1, 0),
at(2, 0),
at(3, 0),
at(1, 2),
at(2, 2),
at(3, 2),
at(1, 3),
at(2, 3),
at(3, 3),
},
{
at(1, 0),
at(2, 0),
at(3, 0),
at(1, 1),
at(2, 1),
at(3, 1),
at(1, 3),
at(2, 3),
at(3, 3),
},
{
at(1, 0),
at(2, 0),
at(3, 0),
at(1, 1),
at(2, 1),
at(3, 1),
at(1, 2),
at(2, 2),
at(3, 2),
}};
return at(0, 0) * Matrix<T>(minorMatrices[0], 3).determinant() -
at(0, 1) * Matrix<T>(minorMatrices[1], 3).determinant() +
at(0, 2) * Matrix<T>(minorMatrices[2], 3).determinant() -
at(0, 3) * Matrix<T>(minorMatrices[3], 3).determinant();
}
default:
UNREACHABLE();
break;
}
return T();
}
Matrix<T> inverse() const
{
ASSERT(rows() == columns());
Matrix<T> coft(std::vector<T>(mElements.size()), rows(), columns());
switch (size())
{
case 2:
coft(0, 0) = at(1, 1);
coft(1, 0) = -at(1, 0);
coft(0, 1) = -at(0, 1);
coft(1, 1) = at(0, 0);
break;
case 3:
coft(0, 0) = at(1, 1) * at(2, 2) - at(2, 1) * at(1, 2);
coft(1, 0) = -(at(1, 0) * at(2, 2) - at(2, 0) * at(1, 2));
coft(2, 0) = at(1, 0) * at(2, 1) - at(2, 0) * at(1, 1);
coft(0, 1) = -(at(0, 1) * at(2, 2) - at(2, 1) * at(0, 2));
coft(1, 1) = at(0, 0) * at(2, 2) - at(2, 0) * at(0, 2);
coft(2, 1) = -(at(0, 0) * at(2, 1) - at(2, 0) * at(0, 1));
coft(0, 2) = at(0, 1) * at(1, 2) - at(1, 1) * at(0, 2);
coft(1, 2) = -(at(0, 0) * at(1, 2) - at(1, 0) * at(0, 2));
coft(2, 2) = at(0, 0) * at(1, 1) - at(1, 0) * at(0, 1);
break;
case 4:
CofactorTransposed(*this, coft);
break;
default:
UNREACHABLE();
break;
}
// The inverse of A is the transpose of the cofactor matrix times the reciprocal of the
// determinant of A.
T det = determinant();
Matrix<T> result(std::vector<T>(mElements.size()), rows(), columns());
for (unsigned int i = 0; i < rows(); i++)
for (unsigned int j = 0; j < columns(); j++)
result(i, j) = (det != static_cast<T>(0)) ? coft(i, j) / det : T();
return result;
}
void setToIdentity()
{
ASSERT(rows() == columns());
const auto one = T(1);
const auto zero = T(0);
for (auto &e : mElements)
e = zero;
for (unsigned int i = 0; i < rows(); ++i)
{
const auto pos = i * columns() + (i % columns());
mElements[pos] = one;
}
}
template <unsigned int Size>
static void setToIdentity(T (&matrix)[Size])
{
static_assert(gl::iSquareRoot<Size>() != 0, "Matrix is not square.");
const auto cols = gl::iSquareRoot<Size>();
const auto one = T(1);
const auto zero = T(0);
for (auto &e : matrix)
e = zero;
for (unsigned int i = 0; i < cols; ++i)
{
const auto pos = i * cols + (i % cols);
matrix[pos] = one;
}
}
protected:
std::vector<T> mElements;
unsigned int mRows;
unsigned int mCols;
};
// Not derived from Matrix<float>: fixed-size std::array instead, to avoid malloc
class Mat4
{
public:
Mat4();
Mat4(const Matrix<float> generalMatrix);
Mat4(const std::vector<float> &elements);
Mat4(const float *elements);
Mat4(float m00,
float m01,
float m02,
float m03,
float m10,
float m11,
float m12,
float m13,
float m20,
float m21,
float m22,
float m23,
float m30,
float m31,
float m32,
float m33);
static Mat4 Rotate(float angle, const Vector3 &axis);
static Mat4 Translate(const Vector3 &t);
static Mat4 Scale(const Vector3 &s);
static Mat4 Frustum(float l, float r, float b, float t, float n, float f);
static Mat4 Perspective(float fov, float aspectRatio, float n, float f);
static Mat4 Ortho(float l, float r, float b, float t, float n, float f);
Mat4 product(const Mat4 &m);
Vector4 product(const Vector4 &b);
void dump();
float *data() { return mElements.data(); }
const float *constData() const { return mElements.data(); }
float operator()(const unsigned int rowIndex, const unsigned int columnIndex) const
{
ASSERT(rowIndex < 4);
ASSERT(columnIndex < 4);
return mElements[rowIndex * 4 + columnIndex];
}
float &operator()(const unsigned int rowIndex, const unsigned int columnIndex)
{
ASSERT(rowIndex < 4);
ASSERT(columnIndex < 4);
return mElements[rowIndex * 4 + columnIndex];
}
float at(const unsigned int rowIndex, const unsigned int columnIndex) const
{
ASSERT(rowIndex < 4);
ASSERT(columnIndex < 4);
return operator()(rowIndex, columnIndex);
}
bool operator==(const Mat4 &m) const { return mElements == m.elements(); }
bool nearlyEqual(float epsilon, const Mat4 &m) const
{
const auto &otherElts = m.elements();
for (size_t i = 0; i < otherElts.size(); i++)
{
if ((mElements[i] - otherElts[i] > epsilon) && (otherElts[i] - mElements[i] > epsilon))
return false;
}
return true;
}
const std::array<float, 4 * 4> &elements() const { return mElements; }
Mat4 transpose() const
{
Mat4 result;
for (unsigned int i = 0; i < 4; i++)
for (unsigned int j = 0; j < 4; j++)
result(i, j) = at(j, i);
return result;
}
Mat4 inverse() const
{
Mat4 coft;
CofactorTransposed(*this, coft);
float det = at(0, 0) * coft(0, 0) + at(0, 1) * coft(1, 0) + at(0, 2) * coft(2, 0) +
at(0, 3) * coft(3, 0);
Mat4 result = coft;
for (int i = 0; i < 16; i++)
{
result.data()[i] /= det;
}
return result;
}
private:
std::array<float, 4 * 4> mElements;
};
} // namespace angle
#endif // COMMON_MATRIX_UTILS_H_