diff options
author | Vincent Ambo <mail@tazj.in> | 2023-03-10T11·17+0300 |
---|---|---|
committer | tazjin <tazjin@tvl.su> | 2023-03-13T20·30+0000 |
commit | d00229753d32de2a38b52a3ae5feddc6ee10cefd (patch) | |
tree | 767ef8b350b0b193b8a9ce2f5685112ade3f2619 /nix/yants | |
parent | 21782d24f5f16942cb67fee6c098aa15bdf88d0c (diff) |
feat(tvix/eval): implement asynchronous list sorting algorithm r/5961
In order to implement an asynchronous builtins.sort (required for moving builtins to generators), we need an `async` sorting algorithm as our comparators involve invoking a Nix function. This commit implements a fairly simple, optimised bubble sort as the sorting algorithm used in our `async fn sort_by`. There don't seem to be any crates providing async versions of things like this, and they might actually be pretty hard to implement generically due to some constraints about how `async` works. Note that this algorithm is less efficient than the hybrid "timsort/mergesort/insert sort" used in the Rust standard library. I tried to write a merge sort implementation, but ran into isuses with the sort becoming unstable because our comparators can not yield equality. This is the simplest implementation which I know to be correct. Note that as of this commit this is *not* covered by the Tvix test suite, but it will be as soon as the rest of the generator code lands. Change-Id: Ia9a604f7dd941d6acc9212c902e0e637ed75bebc Reviewed-on: https://cl.tvl.fyi/c/depot/+/8239 Reviewed-by: Adam Joseph <adam@westernsemico.com> Tested-by: BuildkiteCI
Diffstat (limited to 'nix/yants')
0 files changed, 0 insertions, 0 deletions