Change Details

While booting on an emulator with instruction tracing enabled, I noticed that a rather large amount of time was being spent inside mi_startup. It turns out this is due to sorting an array of ~1000 items using bubble sort (this has been used since at least 1995). Replacing the hand-written bubble sort with a call to qsort() noticeably speeds up this function by reducing the sorting cost from 5.5M instructions to 117K (on RISC-V 64): ``` Sorting 1125 sysinit items 117378 instructions with qsort() 5509157 instructions with bubble ```

While booting on an emulator with instruction tracing enabled, I noticed that a rather large amount of time was being spent inside mi_startup. It turns out this is due to sorting an array of ~1000 items using bubble sort (this has been used since at least 1995). Replacing the hand-written bubble sort with a call to qsort() noticeably speeds up this function by reducing the sorting cost from 5.5M instructions to 117K (on RISC-V 64): ``` Sorting 1125 sysinit items 117378 instructions with qsort() 5509157 instructions with bubble ``` For an x86 VM this also helps noticeably, cperciva@ reports that this reduces the time mi_startup spends sorting from 6094436 cycles (2.031 ms) to 585496 cycles (0.195 ms).

While booting on an emulator with instruction tracing enabled, I noticed that a rather large amount of time was being spent inside mi_startup. It turns out this is due to sorting an array of ~1000 items using bubble sort (this has been used since at least 1995). Replacing the hand-written bubble sort with a call to qsort() noticeably speeds up this function by reducing the sorting cost from 5.5M instructions to 117K (on RISC-V 64): ``` Sorting 1125 sysinit items 117378 instructions with qsort() 5509157 instructions with bubble ``` For an x86 VM this also helps noticeably, cperciva@ reports that this reduces the time mi_startup spends sorting from 6094436 cycles (2.031 ms) to 585496 cycles (0.195 ms).