On 05/09/2014 06:03 AM, Peter Zijlstra wrote:
On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:static inline unsigned long task_weight(struct task_struct *p, int nid) { - unsigned long total_faults; + unsigned long total_faults, score;if (!p->numa_faults_memory) return 0; @@ -940,15 +997,32 @@ static inline unsigned long task_weight(struct task_struct *p, int nid) if (!total_faults) return 0; - return 1000 * task_faults(p, nid) / total_faults; + score = 1000 * task_faults(p, nid); + score += nearby_nodes_score(p, nid, true); + + score /= total_faults; + + return score; }So you add an O(nr_nodes) loop to task_weight(), but that in itself is already called from O(nr_nodes) loops, yielding a total complexity of O(nr_nodes^2).
However, it only does actual calculations for nodes that are closer by than the furthest away nodes in the system. Hopefully on even the largest systems, that will mean an "island" of a handful of nodes, with everything else being at the same large distance.
This might be fine, but algorithmic complexity should very much be a part of the changelog I think.
Agreed, I do need to document this kind of thing better, if only because it gives people a chance to verify my assumptions. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
