Merge pull request #4936 from ethereum/binSelect

Binary search for dispatch.

3 files changed, 81 insertions, 6 deletions

diff --git a/libsolidity/codegen/Compiler.cpp b/libsolidity/codegen/Compiler.cpp
index 55f1d252..fe57cff6 100644
--- a/libsolidity/codegen/Compiler.cpp
+++ b/libsolidity/codegen/Compiler.cpp
@@ -34,13 +34,13 @@ void Compiler::compileContract(
 	bytes const& _metadata
 )
 {
-	ContractCompiler runtimeCompiler(nullptr, m_runtimeContext, m_optimize);
+	ContractCompiler runtimeCompiler(nullptr, m_runtimeContext, m_optimize, m_optimizeRuns);
 	runtimeCompiler.compileContract(_contract, _contracts);
 	m_runtimeContext.appendAuxiliaryData(_metadata);
 
 	// This might modify m_runtimeContext because it can access runtime functions at
 	// creation time.
-	ContractCompiler creationCompiler(&runtimeCompiler, m_context, m_optimize);
+	ContractCompiler creationCompiler(&runtimeCompiler, m_context, m_optimize, 1);
 	m_runtimeSub = creationCompiler.compileConstructor(_contract, _contracts);
 
 	m_context.optimise(m_optimize, m_optimizeRuns);
diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp
index ec55ae9b..79c53a1c 100644
--- a/libsolidity/codegen/ContractCompiler.cpp
+++ b/libsolidity/codegen/ContractCompiler.cpp
@@ -268,6 +268,70 @@ void ContractCompiler::appendDelegatecallCheck()
 	// "We have not been called via DELEGATECALL".
 }
 
+void ContractCompiler::appendInternalSelector(
+	map<FixedHash<4>, eth::AssemblyItem const> const& _entryPoints,
+	vector<FixedHash<4>> const& _ids,
+	eth::AssemblyItem const& _notFoundTag,
+	size_t _runs
+)
+{
+	// Code for selecting from n functions without split:
+	//   n times: dup1, push4 <id_i>, eq, push2/3 <tag_i>, jumpi
+	//   push2/3 <notfound> jump
+	// (called SELECT[n])
+	// Code for selecting from n functions with split:
+	//   dup1, push4 <pivot>, gt, push2/3<tag_less>, jumpi
+	//     SELECT[n/2]
+	//   tag_less:
+	//     SELECT[n/2]
+	//
+	// This means each split adds 16-18 bytes of additional code (note the additional jump out!)
+	// The average execution cost if we do not split at all are:
+	//   (3 + 3 + 3 + 3 + 10) * n/2 = 24 * n/2 = 12 * n
+	// If we split once:
+	//    (3 + 3 + 3 + 3 + 10) + 24 * n/4 = 24 * (n/4 + 1) = 6 * n + 24;
+	//
+	// We should split if
+	//     _runs * 12 * n > _runs * (6 * n + 24) + 17 * createDataGas
+	// <=> _runs * 6 * (n - 4) > 17 * createDataGas
+	//
+	// Which also means that the execution itself is not profitable
+	// unless we have at least 5 functions.
+
+	// Start with some comparisons to avoid overflow, then do the actual comparison.
+	bool split = false;
+	if (_ids.size() <= 4)
+		split = false;
+	else if (_runs > (17 * eth::GasCosts::createDataGas) / 6)
+		split = true;
+	else
+		split = (_runs * 6 * (_ids.size() - 4) > 17 * eth::GasCosts::createDataGas);
+
+	if (split)
+	{
+		size_t pivotIndex = _ids.size() / 2;
+		FixedHash<4> pivot{_ids.at(pivotIndex)};
+		m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(pivot)) << Instruction::GT;
+		eth::AssemblyItem lessTag{m_context.appendConditionalJump()};
+		// Here, we have funid >= pivot
+		vector<FixedHash<4>> larger{_ids.begin() + pivotIndex, _ids.end()};
+		appendInternalSelector(_entryPoints, larger, _notFoundTag, _runs);
+		m_context << lessTag;
+		// Here, we have funid < pivot
+		vector<FixedHash<4>> smaller{_ids.begin(), _ids.begin() + pivotIndex};
+		appendInternalSelector(_entryPoints, smaller, _notFoundTag, _runs);
+	}
+	else
+	{
+		for (auto const& id: _ids)
+		{
+			m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(id)) << Instruction::EQ;
+			m_context.appendConditionalJumpTo(_entryPoints.at(id));
+		}
+		m_context.appendJumpTo(_notFoundTag);
+	}
+}
+
 void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contract)
 {
 	map<FixedHash<4>, FunctionTypePointer> interfaceFunctions = _contract.interfaceFunctions();
@@ -290,13 +354,14 @@ void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contrac
 		CompilerUtils(m_context).loadFromMemory(0, IntegerType(CompilerUtils::dataStartOffset * 8), true);
 
 	// stack now is: <can-call-non-view-functions>? <funhash>
+	vector<FixedHash<4>> sortedIDs;
 	for (auto const& it: interfaceFunctions)
 	{
 		callDataUnpackerEntryPoints.insert(std::make_pair(it.first, m_context.newTag()));
-		m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(it.first)) << Instruction::EQ;
-		m_context.appendConditionalJumpTo(callDataUnpackerEntryPoints.at(it.first));
+		sortedIDs.emplace_back(it.first);
 	}
-	m_context.appendJumpTo(notFound);
+	std::sort(sortedIDs.begin(), sortedIDs.end());
+	appendInternalSelector(callDataUnpackerEntryPoints, sortedIDs, notFound, m_optimise_runs);
 
 	m_context << notFound;
 	if (fallback)
diff --git a/libsolidity/codegen/ContractCompiler.h b/libsolidity/codegen/ContractCompiler.h
index 001aec7c..266ace0b 100644
--- a/libsolidity/codegen/ContractCompiler.h
+++ b/libsolidity/codegen/ContractCompiler.h
@@ -38,8 +38,9 @@ namespace solidity {
 class ContractCompiler: private ASTConstVisitor
 {
 public:
-	explicit ContractCompiler(ContractCompiler* _runtimeCompiler, CompilerContext& _context, bool _optimise):
+	explicit ContractCompiler(ContractCompiler* _runtimeCompiler, CompilerContext& _context, bool _optimise, size_t _optimise_runs = 200):
 		m_optimise(_optimise),
+		m_optimise_runs(_optimise_runs),
 		m_runtimeCompiler(_runtimeCompiler),
 		m_context(_context)
 	{
@@ -81,6 +82,14 @@ private:
 	/// This is done by inserting a specific push constant as the first instruction
 	/// whose data will be modified in memory at deploy time.
 	void appendDelegatecallCheck();
+	/// Appends the function selector. Is called recursively to create a binary search tree.
+	/// @a _runs the number of intended executions of the contract to tune the split point.
+	void appendInternalSelector(
+		std::map<FixedHash<4>, eth::AssemblyItem const> const& _entryPoints,
+		std::vector<FixedHash<4>> const& _ids,
+		eth::AssemblyItem const& _notFoundTag,
+		size_t _runs
+	);
 	void appendFunctionSelector(ContractDefinition const& _contract);
 	void appendCallValueCheck();
 	void appendReturnValuePacker(TypePointers const& _typeParameters, bool _isLibrary);
@@ -122,6 +131,7 @@ private:
 	void storeStackHeight(ASTNode const* _node);
 
 	bool const m_optimise;
+	size_t const m_optimise_runs = 200;
 	/// Pointer to the runtime compiler in case this is a creation compiler.
 	ContractCompiler* m_runtimeCompiler = nullptr;
 	CompilerContext& m_context;