7 ms·

Because bubble sort is often faster for small sorts and it’s easy to write. This is the kernel, there’s no libc you have to write the sort algo yourself.

by _3u10 3y ago

IshKebab 3y ago
It's really because C doesn't have a proper dependency management system like modern languages do. If it did there's no reason you couldn't import a third party sorting algorithm in the kernel. You can do that in Rust for example, although you would just use the built in sort in this case.
- throwawaylinux 3y ago
  It's not because of that. There exist countless BSD compatible code out there, and many are taken and used in projects like this. CRC codes being an obvious example. There is no reason sort code could not have been grabbed from somewhere, no "dependency management system" required. The FreeBSD kernel has its own existing sort libraries already in the code too -- https://cgit.freebsd.org/src/tree/sys/libkern/qsort.c?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d https://cgit.freebsd.org/src/tree/sys/libkern/qsort.c?id=9a7... The real reason is because this is an early boot environment with exact constraints that are unusual if not unique to FreeBSD where the facilities to support your general language / runtime environment is not up yet.
  - tialaramex 3y ago
    > the facilities to support your general language / runtime environment is not up yet. Rust's [T].sort_unstable() is part of core, that is, the code to sort a slice of arbitrary type T doesn't need the allocator, operating system etc. Only if you want a fast stable sort do you need to wait for such an environment because their fast stable sort needs an allocator, I doubt that FreeBSD needs a stable sort here.
    - throwawaylinux 3y ago
      I'm not sure what part of my post you are addressing. If you had a kernel written in Rust, you would have to bring up the rust runtime environment as part of the boot process. You don't just magically get it because that's the language you used, whether it is "core" or not. You can't even execute simple functions before you have set up stack, and in this case apparently there is a constraint on stack usage. And evidently they do need a stable sort. In any case my main point is that it's not anything to do with dependency management, not quibbling about whether or not some language could support this function at this exact point of the boot.
      - tialaramex 3y ago
        > you would have to bring up the rust runtime environment as part of the boot process Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk. > And evidently they do need a stable sort. How so? They appear to even have a deliberate tie-breaking mechanism in their data structure, which suggests if order actually matters you're expected to specify when creating the data, not rely on stability to do what you expected.
        throwawaylinux 3y ago
        > > you would have to bring up the rust runtime environment as part of the boot process > Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk. I don't know what you're trying to say. The code which is written here that we are discussing is in a constrained environment where the regular kernel runtime facilities are not all available. This was cited as one of the reasons cited for open coding a very simple algorithm. > > And evidently they do need a stable sort. > How so? From reading comments from patch author here.
    - 3y ago
  - IshKebab 3y ago
    > the facilities to support your general language / runtime environment is not up yet. What facilities does Rust's sort require? It probably just needs a bit of stack but that's it. That qsort implementation doesn't look like it needs anything either tbh, though I only skimmed it.
    - throwawaylinux 3y ago
      Not sure, the qsort is recursive and stack limitations were mentioned. But the point being that the reason they don't use their library functions because it's a constrained environment. Maybe they could permit some of their sort library functions to be used in such a constrained environment, sure. Don't need rust to do that, just need to be happy that the implementation is suitable for purpose. Which they would have to do regardless of what language and runtime they were using.

Because bubble sort is often faster for small sorts and it’s easy to write. This is the kernel, there’s no libc you have to write the sort algo yourself.

by _3u10 3y ago

Because bubble sort is often faster for small sorts and it’s easy to write. This is the kernel, there’s no libc you have to write the sort algo yourself.

IshKebab 3y ago

It's really because C doesn't have a proper dependency management system like modern languages do. If it did there's no reason you couldn't import a third party sorting algorithm in the kernel. You can do that in Rust for example, although you would just use the built in sort in this case.

throwawaylinux 3y ago
It's not because of that. There exist countless BSD compatible code out there, and many are taken and used in projects like this. CRC codes being an obvious example. There is no reason sort code could not have been grabbed from somewhere, no "dependency management system" required. The FreeBSD kernel has its own existing sort libraries already in the code too -- https://cgit.freebsd.org/src/tree/sys/libkern/qsort.c?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d https://cgit.freebsd.org/src/tree/sys/libkern/qsort.c?id=9a7... The real reason is because this is an early boot environment with exact constraints that are unusual if not unique to FreeBSD where the facilities to support your general language / runtime environment is not up yet.
- tialaramex 3y ago
  > the facilities to support your general language / runtime environment is not up yet. Rust's [T].sort_unstable() is part of core, that is, the code to sort a slice of arbitrary type T doesn't need the allocator, operating system etc. Only if you want a fast stable sort do you need to wait for such an environment because their fast stable sort needs an allocator, I doubt that FreeBSD needs a stable sort here.
  - throwawaylinux 3y ago
    I'm not sure what part of my post you are addressing. If you had a kernel written in Rust, you would have to bring up the rust runtime environment as part of the boot process. You don't just magically get it because that's the language you used, whether it is "core" or not. You can't even execute simple functions before you have set up stack, and in this case apparently there is a constraint on stack usage. And evidently they do need a stable sort. In any case my main point is that it's not anything to do with dependency management, not quibbling about whether or not some language could support this function at this exact point of the boot.
    - tialaramex 3y ago
      > you would have to bring up the rust runtime environment as part of the boot process Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk. > And evidently they do need a stable sort. How so? They appear to even have a deliberate tie-breaking mechanism in their data structure, which suggests if order actually matters you're expected to specify when creating the data, not rely on stability to do what you expected.
      - throwawaylinux 3y ago
        > > you would have to bring up the rust runtime environment as part of the boot process > Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk. I don't know what you're trying to say. The code which is written here that we are discussing is in a constrained environment where the regular kernel runtime facilities are not all available. This was cited as one of the reasons cited for open coding a very simple algorithm. > > And evidently they do need a stable sort. > How so? From reading comments from patch author here.
  - 3y ago
- IshKebab 3y ago
  > the facilities to support your general language / runtime environment is not up yet. What facilities does Rust's sort require? It probably just needs a bit of stack but that's it. That qsort implementation doesn't look like it needs anything either tbh, though I only skimmed it.
  - throwawaylinux 3y ago
    Not sure, the qsort is recursive and stack limitations were mentioned. But the point being that the reason they don't use their library functions because it's a constrained environment. Maybe they could permit some of their sort library functions to be used in such a constrained environment, sure. Don't need rust to do that, just need to be happy that the implementation is suitable for purpose. Which they would have to do regardless of what language and runtime they were using.