Bug 186726

Summary:	SymbolTable wastes 3.5MB of HashTable capacity on cnn.com
Product:	WebKit	Reporter:	Simon Fraser (smfr) <simon.fraser>
Component:	JavaScriptCore	Assignee:	Nobody <webkit-unassigned>
Status:	NEW ---
Severity:	Normal	CC:	keith_miller, mark.lam, saam, simon.fraser, webkit-bug-importer, ysuzuki
Priority:	P2	Keywords:	InRadar
Version:	WebKit Nightly Build
Hardware:	Unspecified
OS:	Unspecified

Description Simon Fraser (smfr) 2018-06-16 12:19:41 PDT

Using tooling from bug 186698, loading can and running "notifyutil -p com.apple.WebKit.dumpHashTableCapacity" shows:

Wasted capacity: 1570032 bytes (used 640016 of 2210048 bytes, utilization: 28.96%) - 6908 allocations
1   0x116698ef5 WTF::HashTable<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, WTF::KeyValuePair<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry>, WTF::KeyValuePairKeyExtractor<WTF::KeyValuePair<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry> >, JSC::IdentifierRepHash, WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::KeyValuePairTraits, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > > >::HashTable()
2   0x116698ed5 WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::HashMap()
3   0x11668fc05 WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::HashMap()
4   0x11668fa6e JSC::SymbolTable::SymbolTable(JSC::VM&)
5   0x11668fc4d JSC::SymbolTable::SymbolTable(JSC::VM&)
6   0x11580d3a1 JSC::SymbolTable::create(JSC::VM&)
7   0x116690951 JSC::SymbolTable::cloneScopePart(JSC::VM&)
8   0x11575434c JSC::CodeBlock::setConstantRegisters(WTF::Vector<JSC::WriteBarrier<JSC::Unknown, WTF::DumbValueTraits<JSC::Unknown> >, 0ul, WTF::CrashOnOverflow, 16ul> const&, WTF::Vector<JSC::SourceCodeRepresentation, 0ul, WTF::CrashOnOverflow, 16ul> const&)

Comment 1 Radar WebKit Bug Importer 2018-06-16 12:20:04 PDT

<rdar://problem/41189082>

Comment 2 Simon Fraser (smfr) 2018-06-16 12:21:08 PDT

As well as this one:

Wasted capacity: 1291168 bytes (used 579168 of 1870336 bytes, utilization: 30.97%) - 5382 allocations
1   0x116698ef5 WTF::HashTable<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, WTF::KeyValuePair<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry>, WTF::KeyValuePairKeyExtractor<WTF::KeyValuePair<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry> >, JSC::IdentifierRepHash, WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::KeyValuePairTraits, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > > >::HashTable()
2   0x116698ed5 WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::HashMap()
3   0x11668fc05 WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::HashMap()
4   0x11668fa6e JSC::SymbolTable::SymbolTable(JSC::VM&)
5   0x11668fc4d JSC::SymbolTable::SymbolTable(JSC::VM&)
6   0x11580d3a1 JSC::SymbolTable::create(JSC::VM&)
7   0x11580a7da JSC::BytecodeGenerator::BytecodeGenerator(JSC::VM&, JSC::FunctionNode*, JSC::UnlinkedFunctionCodeBlock*, JSC::DebuggerMode, JSC::VariableEnvironment const*)
8   0x1158116fd JSC::BytecodeGenerator::BytecodeGenerator(JSC::VM&, JSC::FunctionNode*, JSC::UnlinkedFunctionCodeBlock*, JSC::DebuggerMode, JSC::VariableEnvironment const*)

and 

Wasted capacity: 713440 bytes (used 580896 of 1294336 bytes, utilization: 44.88%) - 147 allocations
1   0x116698ef5 WTF::HashTable<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, WTF::KeyValuePair<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry>, WTF::KeyValuePairKeyExtractor<WTF::KeyValuePair<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry> >, JSC::IdentifierRepHash, WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::KeyValuePairTraits, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > > >::HashTable()
2   0x116698ed5 WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::HashMap()
3   0x11668fc05 WTF::HashMap<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> >, JSC::SymbolTableEntry, JSC::IdentifierRepHash, WTF::HashTraits<WTF::RefPtr<WTF::UniquedStringImpl, WTF::DumbPtrTraits<WTF::UniquedStringImpl> > >, JSC::SymbolTableIndexHashTraits>::HashMap()
4   0x11668fa6e JSC::SymbolTable::SymbolTable(JSC::VM&)
5   0x11668fc4d JSC::SymbolTable::SymbolTable(JSC::VM&)
6   0x11580d3a1 JSC::SymbolTable::create(JSC::VM&)
7   0x11657c560 JSC::JSSegmentedVariableObject::finishCreation(JSC::VM&)
8   0x1165084f3 JSC::JSGlobalObject::finishCreation(JSC::VM&, JSC::JSObject*)

Comment 3 Saam Barati 2018-06-17 11:36:24 PDT

Maybe we should consider a sorted vector here.

I still think we should consider implementing Robin Hood hash tables