Messages in this thread | | | Date | Fri, 09 May 2014 11:16:53 -0400 | From | Rik van Riel <> | Subject | Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies |
| |
On 05/09/2014 06:03 AM, Peter Zijlstra wrote: > On Thu, May 08, 2014 at 01:23:29PM -0400, riel@redhat.com 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.
| |