Paul Menzel has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/31545 )
Change subject: acpi: Sort the reported APIC-IDs in the MADT table ......................................................................
Patch Set 5: Code-Review+1
Patch Set 4:
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.
Thank you for your responses, and sorry for being unclear. I just wanted to know, if it is noticeable in the output of `cbmem -t`.