about summary refs log tree commit diff
path: root/third_party
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2023-03-10T11·17+0300
committertazjin <tazjin@tvl.su>2023-03-13T20·30+0000
commitd00229753d32de2a38b52a3ae5feddc6ee10cefd (patch)
tree767ef8b350b0b193b8a9ce2f5685112ade3f2619 /third_party
parent21782d24f5f16942cb67fee6c098aa15bdf88d0c (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 'third_party')
0 files changed, 0 insertions, 0 deletions