graph.393b7a7.226-347.cpp

void phase::assign_memory(memory_size_type m) const {
	{
		dfs_traversal<phase::node_graph> dfs(*itemFlowGraph);
		dfs.dfs();
		std::vector<node *> order = dfs.toposort();
		for (size_t i = 0; i < order.size(); ++i) {
			if (order[i]->get_state() != node::STATE_FRESH) {
				throw call_order_exception(
					"Tried to call prepare on an none fresh node");
			}
			order[i]->set_state(node::STATE_IN_PREPARE);
			order[i]->prepare();
			if (order[i]->get_memory_fraction() == 0.0)
				order[i]->set_maximum_memory(order[i]->get_minimum_memory());
			order[i]->set_state(node::STATE_AFTER_PREPARE);
		}
	}

	bool unlimitedMaximumMemory = false;
	double fraction = 0.0;
	memory_size_type minimumMemory = 0;
	memory_size_type maximumMemory = 0;
	for (size_t i = 0; i < m_nodes.size(); ++i) {
		fraction += m_nodes[i]->get_memory_fraction();
		minimumMemory += m_nodes[i]->get_minimum_memory();
		maximumMemory += m_nodes[i]->get_maximum_memory();
		if (maximumMemory < m_nodes[i]->get_maximum_memory()) {
			// overflow
			unlimitedMaximumMemory = true;
		}
	}

	if (m < minimumMemory) {
		TP_LOG_WARNING_ID("Not enough memory for this phase. We have " << m << " but we require " << minimumMemory << '.');
		assign_minimum_memory();
		return;
	}

	if (!unlimitedMaximumMemory && m >= maximumMemory) {
		assign_maximum_memory();
		return;
	}

	if (fraction < 1e-9) {
		assign_minimum_memory();
		return;
	}

	std::vector<double> loMem(m_nodes.size());
	std::vector<double> hiMem(m_nodes.size());
	std::vector<double> prio(m_nodes.size());
	for (size_t i = 0; i < m_nodes.size(); ++i) {
		loMem[i] = static_cast<double>(m_nodes[i]->get_minimum_memory()) / m;
		prio[i] = m_nodes[i]->get_memory_fraction() / fraction;

		memory_size_type hi = m_nodes[i]->get_maximum_memory();
		if (hi == 0)
			hiMem[i] = 1.0;
		else
			hiMem[i] = static_cast<double>(hi) / m;
	}

	double c_lo = 0.0;
	double c_hi = 1.0;
	// Exponential search
	while (true) {
		double memoryAssigned = 0.0;
		for (size_t i = 0; i < m_nodes.size(); ++i) {
			memoryAssigned +=
				std::max(loMem[i], std::min(hiMem[i],
											c_hi * prio[i]));
		}
		if (memoryAssigned < 1.0)
			c_hi *= 2;
		else
			break;
	}

	if (c_hi == std::numeric_limits<double>::infinity()) {
		this->print_memory(log_debug());
		throw tpie::exception("Exponential search unbounded in assign_memory");
	}

	// Binary search
	while (true) {
		double memoryAssigned = 0.0;
		double c = c_lo + (c_hi-c_lo)/2;

		for (size_t i = 0; i < m_nodes.size(); ++i) {
			memoryAssigned +=
				std::max(loMem[i], std::min(hiMem[i],
											c * prio[i]));
		}

		memory_size_type memory = static_cast<memory_size_type>(memoryAssigned * m);
		if (memory > m) {
			c_hi = c;
		} else {
			c_lo = c;

			memory_size_type spill = m - memory;
			if (spill == 0) break;
		}
	}

	memory_size_type memoryAssigned = 0;

	for (size_t i = 0; i < m_nodes.size(); ++i) {
		memory_size_type lo = m_nodes[i]->get_minimum_memory();
		memory_size_type hi = m_nodes[i]->get_maximum_memory();
		memory_size_type assign =
			std::max(lo, std::min(hi, static_cast<memory_size_type>(m * c_lo * prio[i])));
		memoryAssigned += assign;
		m_nodes[i]->set_available_memory(assign);
	}

	if (memoryAssigned > m) {
		log_warning() << "Too much memory assigned in graph.cpp: Got " << m
			<< ", but assigned " << memoryAssigned
			<< " (" << (memoryAssigned-m) << " b too much)" << std::endl;
	}
}