russell@unturf.com
d4ed2dff91
Hibernate (5 HIGH): addColumn/addReferencedColumn/addIndex ArrayList→LinkedHashSet (19x) FK second-pass LinkedHashSet, orderHierarchy LinkedHashSet MyBatis (1 MEDIUM): sortConstructorMappings indexOf→HashMap (12x) EF Core (2 HIGH + 1 MEDIUM): FindGenerationProperty HashSet (250x), AddPrincipals HashSet (250x), FK discovery HashSet (6x) Diesel (3 MEDIUM): SQLite/MySQL row position()→BTreeMap (51x) SQLAlchemy (2 HIGH): _values_bindparam Set (500x), evaluated_keys Set (500x) Peewee (1 MEDIUM): _SortedFieldList.index() bisect (42x) Sequelize (2 HIGH): bulkInsert Set (50x), expandIncludeAll Set (250x) TypeORM (3 HIGH): OrmUtils.uniq Map (500x), diffColumns Set (125x), updatedColumns Set (100x) Doctrine ORM (1 HIGH + 2 MEDIUM): hydrator discriminator (26x), addSubClass (250x), SqlWalker partial (130x) GORM (1 MEDIUM): sortCallbacks getRIndex→map (194x) SQLite: SqliteTest unit proof 4/4 PASS (101x) Unit tests: all PASS — Hibernate/MyBatis/EfCore/Diesel/SQLAlchemy/Peewee/ Sequelize/TypeORM/Doctrine/GORM Whitepaper: 157 sites, 62 ecosystems; PDF 752K
85 lines
2.8 KiB
Markdown
85 lines
2.8 KiB
Markdown
# doctrine-orm-0002 — ClassMetadata::addSubClass: O(n²) subclass dedup during metadata loading
|
||
|
||
**Status:** OPEN
|
||
**Severity:** MEDIUM
|
||
**Component:** `doctrine/orm` — `src/Doctrine/ORM/Mapping/ClassMetadata.php`
|
||
**Affects:** Application startup / metadata cache warming; entity class hierarchies with many subclasses
|
||
|
||
---
|
||
|
||
## Root Cause
|
||
|
||
`ClassMetadata.php:2313` — `addSubClass()`:
|
||
|
||
```php
|
||
// DEFECTIVE — O(subclasses) linear scan per addSubClass call
|
||
public function addSubClass(string $className): void
|
||
{
|
||
if (is_subclass_of($className, $this->name) && ! in_array($className, $this->subClasses, true)) {
|
||
$this->subClasses[] = $className;
|
||
}
|
||
}
|
||
```
|
||
|
||
`$this->subClasses` is a plain PHP array (`public array $subClasses = []`, line 314).
|
||
`in_array` scans the entire array for every call.
|
||
|
||
`addSubClass()` is called inside loops in `ClassMetadataFactory`:
|
||
|
||
- `ClassMetadataFactory.php:152`: `$class->addSubClasses($parent->subClasses)` — bulk add loop
|
||
- `ClassMetadataFactory.php:386`: inside `foreach ($parentClasses as $parentClass)` loop inside
|
||
`findAbstractEntityClassesNotListedInDiscriminatorMap()`
|
||
|
||
The second call site is the worst case: for each discriminator map entry, `getParentClasses()`
|
||
returns all ancestor classes, and `addSubClass` is called for each. With S subclasses and
|
||
D depth, total comparisons: O(S × D × S) = O(S²×D).
|
||
|
||
---
|
||
|
||
## Complexity Analysis
|
||
|
||
| Metric | Defective | Fixed |
|
||
|--------|-----------|-------|
|
||
| Single addSubClass | O(current subclass count) | O(1) |
|
||
| Full hierarchy load (S subclasses) | O(S²) | O(S) |
|
||
| Growth pattern | Quadratic | Linear |
|
||
|
||
---
|
||
|
||
## Fix
|
||
|
||
Replace `$this->subClasses` with a parallel indexed structure, or use a `Set`-equivalent
|
||
(array keyed by class name):
|
||
|
||
```php
|
||
// Keep public array $subClasses for backward compat, add private set for O(1) lookup
|
||
private array $subClassSet = [];
|
||
|
||
public function addSubClass(string $className): void
|
||
{
|
||
if (is_subclass_of($className, $this->name) && ! isset($this->subClassSet[$className])) {
|
||
$this->subClassSet[$className] = true;
|
||
$this->subClasses[] = $className;
|
||
}
|
||
}
|
||
```
|
||
|
||
Alternatively, key `$subClasses` by class name directly (breaking change to indexed access).
|
||
|
||
---
|
||
|
||
## Call Sites
|
||
|
||
| File | Line | Context |
|
||
|------|------|---------|
|
||
| `src/Mapping/ClassMetadata.php` | 2313 | `addSubClass()` |
|
||
| `src/Mapping/ClassMetadataFactory.php` | 152 | bulk inherit from parent |
|
||
| `src/Mapping/ClassMetadataFactory.php` | 386 | discriminator map abstract class discovery |
|
||
|
||
---
|
||
|
||
## Speedup Estimate
|
||
|
||
Metadata loading for a hierarchy with 50 subclasses: ~50× reduction in membership check work.
|
||
Impact is startup/warm-up only (metadata is cached after first load). Applications without
|
||
metadata caching (e.g., dev mode with `auto_generate_proxy_classes`) see this on every request.
|