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 highly depends on CONFIG_MAX_CPUS. Even if we hit the worst case (O(n²)) this would mean 2304 swaps. I guess 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 shouldn't be that bad.

View Change

To view, visit change 31544. To unsubscribe, or for help writing mail filters, visit settings.