Patch Set 4: Code-Review+1
(1 comment)
Patch Set 3:
Patch Set 3:
(1 comment)
Does this have a time penalty?
I am pretty sure it is the one the sorting algorithm has, and it surely depends on the number of CPUs.
It's bound by CONFIG_MAX_CPUS which (AFAICS) is at most 48 in our tree, in serengeti_cheetah_fam10. That would mean ~2500 swaps at most in highly localized code and data.
I guess we can deal with that when it becomes an issue? I have the suspicion that using timsort (another stable sort) won't fare much better on our data set because of setup and copying costs (whereas bubble sort works in-place).
Yes, it highliy depends on CONFIG_MAX_CPUS. Even if we hit the worst case (O(n²)) this would mean 2304 swaps. I gues on modern CPUs this should not be an issue and we can deal with it once it will become an issue.
The benefit of having bubble sort is as you mentioned that it works in-place. No need to copy data while sorting. And with the added abort condition real-life runtime should't be that bad.
1 comment:
Patch Set #4, Line 162: apic_ids
add a bounds check for the array. It _should_ never happen, but...
There is a bounds check already in the MP-Init code (the one I have looked into) when the cpu entries are generated. But there might be cases where it is missing. I will add a check.
To view, visit change 31545. To unsubscribe, or for help writing mail filters, visit settings.