related to
- #9

in order for the measurements not to influence the experiment, the seeds passed to the runs need to not include the _measurement schedule_ parameters!

EDIT: in the end, it's more than that, we want to only include things related to the environment in its hash, nothing related to the measurements, i.e. we want to either
- exclude `strategies`, `nb_scenarii`, `measurement_schedule`, `measurement_schedule_start`, `nb_measurements` and `max_t`
- include `nb_bytes`, `k`, `n` and `environment`

## output sample
let's say the current seed is `"b239e48345ac457b492cc164f58c010d07292c88e4791e607d91796baec7f334"` and the experiment has ID `fixed:0-single:3-5-50-10240`, and that we are watching both the creation of the first experiment and a few runs, e.g.
- `002d8de28913efbf7dbd111b817ae901fee2d47882ba7aa76d293c2d95d9652c`
- `015672b37c9cf1a6b475937987294f9a503a922ffbcfdfc5d18ef839fac91b8c`
- `080a51a17ac43fcbdf08f77f3bc993983fef589bd9672f04382af4b16dd09b13`

then the output would look like
```
b239e48  fixed:0-single:3-5-50-10240            at 2024-05-30 15:24:12
b239e48  fixed:0-single:3-5-50-10240  002d8de   at 2024-05-30 15:24:14
b239e48  fixed:0-single:3-5-50-10240  015672b   at 2024-05-30 15:24:16
b239e48  fixed:0-single:3-5-50-10240  080a51a   at 2024-05-30 15:24:18
```

we are switching
- _naive recoding_ to _$(k, 1)$-re-encoding_
- _true recoding_ to _$k$-recoding_

this is to have a complete identifier for each run, which does not depend at all on the time at which the experiment runs.

related to
- !122

## description
!122 introduced a `draw_unique_indices` function which uses a `HashSet` to accumulate unique indices in the range `0..<len`.
however, a `HashSet` does not preserve the order of insertion when iterating over the elements of the set... which results in apparent randomness, even though the RNG seed is the same 😮 

this MR switches back to using `shuffle` which used to work, even though a bit less performant 👌   
it's basically a revert of !122, while keeping the refactoring into `random.rs`.

## measuring the performance
i did run the same timing experiment from !122 but with `main` on `bb55005f` and the MR on `fix-shuffle`

| env     | main                   | mr                      | improvement         |
| ------- | ---------------------- | ----------------------- | ------------------- |
| fixed:0 | 6sec 244ms 238µs 45ns | 8sec 734ms 929µs 328ns | -39.88783363238997  |
| fixed:1 | 639ms 720µs 39ns      | 731ms 360µs 261ns      | -14.325051024390373 |

we loose a bit

- add optional `$.help` to argument `err` of `error throw`
- parse `prng_seed: [u8; 32]` in `rng` and `inbreeding`
- compute the "_local_" seed by hashing the "_global_" seed, the strategy and the iteration index
- pass `--prng-seed: string`, a 64-char long seed to `inbreeding run`

because the "_environment_" can contain an experiment separator, e.g. `random-fixed`, more powerful `parse` patterns needs to be used.

* 7b44a886 refactor constants from `inbreeding load`
* 64e446f7 move `remove-cache-prefix` to new `path.nu`
* 822b03fd add `inbreeding inspect`

in order to add more information in the experiment names, e.g. $k$, $n$ and $\#\text{bytes}$, this MR changes the cache files format from
```
{seed}/{timestamp}/{env}/{strategy}/...
```
to
```
{seed}/{timestamp}-{env}-{strategy}-{k}-{n}-{nb_bytes}/...
```

this MR turns `./.nushell/` into a directory module by
- adding `mod.nu`
- exporting all the modules

all uses of `.nushell/` have been fixed to not mention `.nu` internal modules anymore.

> 💡 **Note**  
> the `.nushell venv` module has been removed because, when the `$venv.VENV` activation script is not there, Nushell can't parse the whole `.nushell` module, which is very annoying to have to rely of the state of the external filesystem to be able to simply parse a module...

this also bumps Nushell to 0.93.0 to include the "extra" command `fmt`, see [Nushell 0.92.0](https://www.nushell.sh/blog/2024-04-02-nushell_0_92_0.html#incorporating-the-extra-feature-by-default-toc)

in `./bins/inbreeding/`, this MR does
- refactor the "list item drawing" from `environment.rs` and `strategy.rs` into the `draw_unique_elements` function of new `random.rs` module
- use a `HashSet` to draw unique indices in the slice of "things" to draw from and then extracts the items corresponding to these indices

## results
```bash
use ./bins/inbreeding
use std bench

const PRNG_SEED = 0
const OPTS = {
    nb_bytes: (10 * 1_024),
    k: 10,
    n: 20,
    nb_measurements: 100,
    nb_scenarii: 10,
    measurement_schedule: 1,
    measurement_schedule_start: 2_000,
    max_t: 2_000,
    strategies: [ "single:5" ],
    environment: null,
}

def run [rev: string] {
    git co $rev

    inbreeding build

    let a = bench --rounds 5 {
        inbreeding run --options ($OPTS | update environment "fixed:0") --prng-seed $PRNG_SEED
    }
    let b = bench --rounds 5 {
        inbreeding run --options ($OPTS | update environment "fixed:1") --prng-seed $PRNG_SEED
    }

    {
        0: $a,
        1: $b,
    }
}

let main = run a29b511d
let mr = run fix-shuffle
```
```bash
let table = [
    [env, main, mr, improvement];

    ["fixed:0", $main."0".mean, $mr."0".mean, (($main."0".mean - $mr."0".mean) / $main."0".mean * 100)],
    ["fixed:1", $main."1".mean, $mr."1".mean, (($main."1".mean - $mr."1".mean) / $main."1".mean * 100)],
]

$table | to md --pretty
```

| env     | main                    | mr                      | improvement        |
| ------- | ----------------------- | ----------------------- | ------------------ |
| fixed:0 | 8sec 504ms 794µs 784ns | 6sec 353ms 206µs 645ns | 25.298530930431912 |
| fixed:1 | 727ms 648µs 292ns      | 639ms 443µs 782ns      | 12.12186037811795  |

the improvement is quite nice, even though not huge, but the code is cleaner anyways 🙏

this adds `$.diversity.e` to the output of `inbreeding load` and input of `inbreeding plot` to show errors bars in the final plot.

these can be discarded by running something similar to
```bash
inbreeding load $experiment
    | reject diversity.e
    | inbreeding plot --options { k: $OPTS.k }
```

plotting "inbreeding" results is now done in two steps
- `load` the data from raw experiment files with `inbreeding load`
- `plot` the results by piping this data into `inbreeding plot`

## new structure for the repository
- benchmarks are in `./benchmarks/` and can be run with either `cargo run --package benchmarks --bin <bench>` or the commands in `./benchmarks/README.md`
```
├── Cargo.toml
├── README.md
└── src
    └── bin
        ├── commit.rs
        ├── fec.rs
        ├── linalg.rs
        ├── operations
        │   ├── curve_group.rs
        │   └── field.rs
        ├── recoding.rs
        ├── setup.rs
        └── setup_size.rs
```

- examples are now in `./bins/` as standalone binaries and can be run either with `cargo run --package <pkg>` or with the help of the `cargo bin` command from `.nushell/cargo.nu`
```
├── curves
│   ├── Cargo.toml
│   ├── README.md
│   └── src
│       └── main.rs
├── inbreeding
│   ├── build.nu
│   ├── Cargo.toml
│   ├── consts.nu
│   ├── mod.nu
│   ├── plot.nu
│   ├── README.md
│   ├── run.nu
│   └── src
│       ├── environment.rs
│       ├── main.rs
│       └── strategy.rs
├── rank
│   ├── Cargo.toml
│   └── src
│       └── main.rs
└── rng
    ├── Cargo.toml
    └── src
        └── main.rs
```

- Nushell modules are now located in `./.nushell/`

## changelog
apart from the changes to the general structure of the repo:
- `binary.nu` -> `.nushell/binary.nu`
- new `cargo bin` command from `.nushell/cargo.nu`
- `error throw` is now defined in `.nushell/error.nu`
- main TOML has been greatly simplified because the dependencies of "examples" have been moved to the associated crates
- the rest is basically the same but in the new structure

related to
- !113

this MR makes sure that the seeds given to each "strategy + scenario" loop are different by generating a bunch of unique seeds per strategy.

this will make `inbreeding run` dump all the data as-is to files on disk.
data will be arranged in the following way
- the `$CACHE` is `~/.cache/komodo/inbreeding/`
- each seed will have its own directory: `$CACHE/<seed>/`
- each strategy and environment will have their own directory: `$CACHE/<seed>/<date>/<env>/<strat>/`
- finally each recoding scenario will go to its own subdirectory: `$CACHE/<seed>/<date>/<env>/<strat>/<i>`

> ❗ **Important**  
> the plotting pipeline is broken for now but will be fixed in later MRs soon...

- add `--prng-seed: u8` to fix the random number generator seed

## example
by running the following snippet, we get
- `first.123.png` and `second.123.png` with `--prng-seed 123` which are the same
- `first.111.png` and `second.111.png` with `--prng-seed 111` which are the same
- `first.111.png` and `first.123.png` are different

```bash
use ./scripts/inbreeding

const OPTS = {
    nb_bytes: (10 * 1_024),
    k: 10,
    n: 20,
    nb_scenarii: 10,
    nb_measurements: 10,
    measurement_schedule: 1,
    measurement_schedule_start: 0,
    max_t: 50,
    strategies: [
        "single:1",
        "double:0.5:1:2",
        "single:2"
        "double:0.5:2:3",
        "single:3"
        "single:5"
        "single:10",
    ],
    environment: "random-fixed:0.5:1",
}

inbreeding build

inbreeding run --options $OPTS --prng-seed 123 --output /tmp/first.123.nuon
inbreeding plot /tmp/first.123.nuon --options { k: $OPTS.k } --save /tmp/first.123.png

inbreeding run --options $OPTS --prng-seed 123 --output /tmp/second.123.nuon
inbreeding plot /tmp/second.123.nuon --options { k: $OPTS.k } --save /tmp/second.123.png

inbreeding run --options $OPTS --prng-seed 111 --output /tmp/first.111.nuon
inbreeding plot /tmp/first.111.nuon --options { k: $OPTS.k } --save /tmp/first.111.png

inbreeding run --options $OPTS --prng-seed 111 --output /tmp/second.111.nuon
inbreeding plot /tmp/second.111.nuon --options { k: $OPTS.k } --save /tmp/second.111.png
```

| seed | first | second |
| ---- | ----- | ------ |
| 123  | ![first.123](/uploads/6b09bf94ca7019e200a47e1a53adc533/first.123.png) | ![second.123](/uploads/fa77c1be84d6279f71cbfe3064c83242/second.123.png) |
| 111  | ![first.111](/uploads/bd31a0832825ecbef48178b2e8689a6f/first.111.png) | ![second.111](/uploads/e1c00e0a6765e82388a3c7142847bbab/second.111.png) |

- define `scripts/color.nu` to manipulate RGB colors, especially mix two colors together
- compute the color of _hybrid recoding strategies_ as a weighted sum of the two _simple recoding strategies_ involved, e.g. if the strategy is "10% of the time recode 2 shards and 90% of the time recode 3", then the color of that curve will be 10% the color of the simple strategy recoding 2 shards and 90% the color of the other simple strategy recoding 3 shards
- make the _hybrid_ curves transparent and dashed

## example
![foo](/uploads/71afca07a87fc38e3fa005cebfab4e50/foo.png)

- add a timestamp to all the measurements of the _diversity_ from `inbreeding/mod.rs`
- allow to delay the measurement starts with `--measurement-schedule-start`, to help completing already existing measurements

> ❗ **Important**  
> existing measurement files will have to change shape from
> ```
> table<strategy: string, diversity: list<float>>
> ```
> to
> ```
> table<strategy: string, diversity: table<t: int, diversity: float>>
> ```

makes sure
- "inbreeding" experiment quits when there are less than $k$ shards
- `fec::decode` returns `KomodoError::TooFewShards` when no shards are provided

just a small QoL improvement

this MR is two-fold
- refactor `run.nu` and `plot.nu` from `scripts/inbreeding/` into Nushell modules with `--options` as argument instead of `options.nu` (a7cebb95, 6b72191f and 5f1c4963)
- introduce another level of depth to the measurements (a0e52e95)

> 💡 **Note**  
> in the table below
> - $s$ is the number of recoding scenarii averages together
> - $m$ is the number of measurements per point
> - two iterations of the same experiment are shown side by side for comparison

s   |    m | . | .
:--:|:----:|:-------------------------:|:-------------------------:
1   | 10   | ![inbreeding_1_10.1](/uploads/c593393edb3513c9d77b0fe134c27fd7/inbreeding_1_10.1.png) | ![inbreeding_1_10.2](/uploads/97c85b36833112de51a2b756ade53479/inbreeding_1_10.2.png)
1   | 100  | ![inbreeding_1_100.1](/uploads/af4da1d7cf76ef43fb39c2a3a529b7cd/inbreeding_1_100.1.png) | ![inbreeding_1_100.2](/uploads/e187298709d524437dea503be6ac555f/inbreeding_1_100.2.png)
1   | 1000 | ![inbreeding_1_1000.1](/uploads/394821777baeff9fec589440ba4c554c/inbreeding_1_1000.1.png) | ![inbreeding_1_1000.2](/uploads/1d592b791075f204f8a0ebdd739403dd/inbreeding_1_1000.2.png)
10  | 100  | ![inbreeding_10_100.1](/uploads/3c822e7669e9f0b4d97919e5a3bd4bca/inbreeding_10_100.1.png) | ![inbreeding_10_100.2](/uploads/aa6b54ec64f82ca386dae4e262dcd0b6/inbreeding_10_100.2.png)
100 | 10   | ![inbreeding_100_10.1](/uploads/7ef383143d981717b0ad01dee0359eb0/inbreeding_100_10.1.png) | ![inbreeding_100_10.2](/uploads/ce71a32a7f6e9ba3c4dae563aeefd856/inbreeding_100_10.2.png)
100 | 100  | ![inbreeding_100_100.1](/uploads/e2038273051f959d8be69fef9ba7a493/inbreeding_100_100.1.png) | ![inbreeding_100_100.2](/uploads/0ef30735597e1a6812484d1cac4d34ca/inbreeding_100_100.2.png)

we can see that
- the smaller the $s$, the more different the two figures are on each line -> this is likely due to the fact that, if only one recoding scenario is used, then repeating the same experiment will result in very different results and measurements. Running the same experiment $s$ times and averaging helps reducing the variance along this axis
- the smaller the $m$, the more noisy the measures of each points -> this is simply because, when $m$ is small, the variance of the empirical means measured for each point is higher

## final results
![inbreeding](/uploads/e561f4e4acad8eedbb3ccf1a4666c302/inbreeding.png)
![inbreeding_100_100_1](/uploads/37ab0eacb5159137595579dfbb20250c/inbreeding_100_100_1.png)

this will use PLNK version 0.7.0 with prettier progress bars.

check for empty inputs in the `run.nu` scripts

up until now, elliptic curves have been hardcoded in the benchmarks, forcing to run them on all supported curves...

this MR makes it possible to use only a subset of curves.

> 💡 **Note**  
> when running the same commands from !104, minus the "inbreeding" ones which are not affected by this MR, the time goes from 12min 33sec to 4min 28sec 🎉 


## TODO
- [x] setup
- [x] commit
- [x] recoding
- [x] fec
- [ ] linalg
- [ ] setup size
- [ ] field operations
- [ ] group operations

> 💡 **Note**  
> because all the unticked bullet points above are far from critical to the paper and do require to measure all curves, i won't change these for now

this MR moves run and plot commands from `examples/benches/README.md` to
- `scripts/setup/`: `run.nu` and `plot.nu`
- `scripts/commit/`: `run.nu` and `plot.nu`
- `scripts/recoding/`: `run.nu` and `plot.nu`
- `scripts/fec/`: `run.nu` and `plot.nu`
- `scripts/inbreeding/`: `build.nu`, `run.nu` and `plot.nu`

to generate all the figures at once
```bash
use scripts/setup/run.nu; seq 0 13 | each { 2 ** $in } | run --output data/setup.ndjson
use ./scripts/setup/plot.nu; plot data/setup.ndjson --save ~/setup.pdf

use scripts/commit/run.nu; seq 0 13 | each { 2 ** $in } | run --output data/commit.ndjson
use ./scripts/commit/plot.nu; plot data/commit.ndjson --save ~/commit.pdf

use scripts/recoding/run.nu; seq 0 18 | each { 512 * 2 ** $in } | run --ks [2, 4, 8, 16] --output data/recoding.ndjson
use ./scripts/recoding/plot.nu; plot data/recoding.ndjson --save ~/recoding.pdf

use scripts/fec/run.nu; seq 0 18 | each { 512 * 2 ** $in } | run --ks [2, 4, 8, 16] --output data/fec.ndjson
use ./scripts/fec/plot.nu; plot encoding data/fec.ndjson --save ~/encoding.pdf
use ./scripts/fec/plot.nu; plot decoding data/fec.ndjson --save ~/decoding.pdf
use ./scripts/fec/plot.nu; plot e2e data/fec.ndjson --save ~/e2e.pdf

use ./scripts/fec/plot.nu; plot combined data/fec.ndjson --recoding data/recoding.ndjson --save ~/comparison.pdf
use ./scripts/fec/plot.nu; plot ratio data/fec.ndjson --recoding data/recoding.ndjson --save ~/ratio.pdf

./scripts/inbreeding/build.nu
./scripts/inbreeding/run.nu --output data/inbreeding.nuon
./scripts/inbreeding/plot.nu data/inbreeding.nuon --save ~/inbreeding.pdf
```

> 💡 **Note**  
> this took around 27min 18sec in total on my machine with 14min 45sec for the inbreeding section only and 12min 33sec for the rest

this MR:
- refactors the "inbreeding" example into `examples/inbreeding/`
- adds `--strategy` and `--environment`
  - `Strategy::draw` will draw the number of shards to keep for recoding
  - `Environment::update` will update the pool of shards by losing some of them

- update `benches/README.md` to use `cargo run --release --example ...`
- add `build-examples` to `Makefile` to build all examples in release

### minor change
add two `eprintln!` in `inbreeding.rs` to show the experiment parameters

- new `scripts/plot.nu` with common tools and options
- better sets of parameters
- better commands in `benches/README.md`

* 240be2a6 add `--measurement-schedule` to inbreeding
* ace8b364 include max_t in the range
* a3345a88 shuffle the shards before recoding
* 6995c103 use `fec::recode_random`
* 2e729ab2 add second level of progress bar
* 84bef553 update the README
* 42ec5760 make Clippy happy

this MR makes the plot a bit nicer.

## new figures
![setup](/uploads/e6a7ac4e7460d8ff7015906216f9d30b/setup.png)
![commit](/uploads/a40700913594771cefeba45a44b2370b/commit.png)
![recoding](/uploads/1f3e86763c897dcf034e4b01ba858ada/recoding.png)
![decoding](/uploads/dd703ba4af59b4043ae5bb966f8b55ae/decoding.png)
![encoding](/uploads/6dbc077bbfe8086357074a0e18c8b530/encoding.png)
![e2e](/uploads/9eb92dbb8dc013ef803bde70f3e04f02/e2e.png)
![inbreeding](/uploads/9f7dac6a48c24e97448e92a69a506d2f/inbreeding.png)

this MR adds `examples/inbreeding.rs` which allows to do two things
- _naive recoding_: in order to generate a new random shard, we first $k$-decode the whole data and then $1$-encode a single shard
- _true recoding_: to achieve the same goal, we directly $k$-recode shards into a new one

## the scenario
regardless of the _recoding strategy_, the scenario is the same
1. data is split into $k$ shards and $n$ original shards are generated
2. for a given number of steps $s$, $k$ shards are drawn randomly with replacement and we count the number of successful decoding, given a measure of the _diversity_, $$\delta = \frac{\#success}{\#attempts}$$
3. create a new _recoded shard_ and add it to the $n$ previous ones, i.e. $n$ increases by one
4. repeat steps 2. and 3. as long as you want
 
## results
![inbreeding](/uploads/b81614abcae01b7c915435aa87ccaec0/inbreeding.png)

STEVAN Antoine authored 11 months ago and DETCHART Jonathan committed 11 months ago

we want to compare
- _naive recoding_: k-decoding followed by 1-encoding
- _komodo recoding_: k-recoding with $k = \#\text{shards}$

# results
> 💡 **Note**  
> we see that the _naive recoding_ is around 100 times slower compared to the _komodo recoding_ 🎉 

> 💡 **Note**  
> the format of the labels is always `{curve} / {k}`

![e2e](/uploads/9ffbae9188434f27f7018155de74982b/e2e.png)
![recoding](/uploads/17ddb76efe7719970849eeda655a68da/recoding.png)

i've moved the plotting scripts to [GPLT](https://gitlab.isae-supaero.fr/a.stevan/gplt) which allows to install a single command, called `gplt`, with two subcommands
- `gplt plot` which is the same as old `python scripts/plot/plot.py`
- `gplt multi_bar` which is the same as old `python scripts/plot/multi_bar.py`

otherwise, k doesn't play any role in the "recoding" benchmark

this MR adds
- `examples/benches/bench_fec.rs` to the list of example benches
- instructions on how to run the new benchmark and plot the results

## results
![encoding](/uploads/d474aa6f39ea20c6b346fb17d2e7ecdc/encoding.png)
![decoding](/uploads/061944e49f02541ea93ac0de9547ce37/decoding.png)
![e2e](/uploads/bb27f4bb6290c4697a65faa59a0ac4e0/e2e.png)