builtin: List.concatUtf8 : List U8, Str -> Str

[shua]

The intent of this change is to implement a Str.concatUtf8 builtin which allows a string to be concatenated to a List U8 as utf-8 encoded bytes. The motivation for this change is #3251 .

[shua]

Just ran a benchmark, and it does seem to show an improvement (for a sufficiently high number of concats in the same running program)

add-benchmark.patch

``` From 2c9338beb4509ee6ea2524a73715280a67225bf4 Mon Sep 17 00:00:00 2001 From: shua Date: Sun, 9 Jun 2024 00:08:38 +0200 Subject: [PATCH] add benchmark for big enough 'n' it seems to help bench-group_wall-time/Benchmarking "listConcatUtf8" time: [8.1329 ms 8.1724 ms 8.2099 ms] change: [-59.891% -59.676% -59.444%] (p = 0.00 < 0.05) Performance has improved. Found 1 outliers among 200 measurements (0.50%) 1 (0.50%) high mild --- crates/cli/benches/time_bench.rs | 3 ++- .../cli/tests/benchmarks/listConcatUtf8.roc | 26 +++++++++++++++++++ crates/cli_utils/src/bench_utils.rs | 11 ++++++++ 3 files changed, 39 insertions(+), 1 deletion(-) create mode 100644 crates/cli/tests/benchmarks/listConcatUtf8.roc diff --git a/crates/cli/benches/time_bench.rs b/crates/cli/benches/time_bench.rs index 7f301634b..782631020 100644 --- a/crates/cli/benches/time_bench.rs +++ b/crates/cli/benches/time_bench.rs @@ -1,7 +1,7 @@ use std::time::Duration; use cli_utils::bench_utils::{ - bench_cfold, bench_deriv, bench_nqueens, bench_quicksort, bench_rbtree_ck, + bench_cfold, bench_concat_utf8, bench_deriv, bench_nqueens, bench_quicksort, bench_rbtree_ck, }; use criterion::{measurement::WallTime, BenchmarkGroup, Criterion, SamplingMode}; @@ -31,6 +31,7 @@ fn bench_group_wall_time(c: &mut Criterion) { bench_rbtree_ck, // ms = makeMap 5 80000 // bench_rbtree_delete, // m = makeMap 100000 bench_quicksort, // list size 10000 + bench_concat_utf8, ]; for bench_func in bench_funcs.iter() { diff --git a/crates/cli/tests/benchmarks/listConcatUtf8.roc b/crates/cli/tests/benchmarks/listConcatUtf8.roc new file mode 100644 index 000000000..7546eb761 --- /dev/null +++ b/crates/cli/tests/benchmarks/listConcatUtf8.roc @@ -0,0 +1,26 @@ +app "listConcatUtf8" + packages { pf: "platform/main.roc" } + imports [pf.Task] + provides [main] to pf + +concat = \n -> + nas = + List.repeat "na" n + |> List.walk [] List.concatUtf8 + # |> List.walk [] (\l, s -> List.concat l (Str.toUtf8 s)) + List.concatUtf8 nas " BATMAN" + +main : Task.Task {} [] +main = + input <- Task.attempt Task.getInt + + when input is + Ok n -> + m = Num.toU64 n + msg = concat m + if (List.len msg) != (2*m + (Str.countUtf8Bytes " BATMAN")) then + Task.putLine "fail" + else + Task.putLine "pass" + Err _ -> + Task.putLine "fail" diff --git a/crates/cli_utils/src/bench_utils.rs b/crates/cli_utils/src/bench_utils.rs index 253f67b92..52ff0fb04 100644 --- a/crates/cli_utils/src/bench_utils.rs +++ b/crates/cli_utils/src/bench_utils.rs @@ -156,6 +156,17 @@ pub fn bench_rbtree_delete(bench_group_opt: Option<&mut Benchmar ); } +pub fn bench_concat_utf8(bench_group_opt: Option<&mut BenchmarkGroup>) { + exec_bench_w_input( + &file_path_from_root("crates/cli/tests/benchmarks", "listConcatUtf8.roc"), + "1000000", + "listConcatUtf8", + // "[1, 2, 3, 4, 240, 159, 144, 166]\n", + "pass\n", + bench_group_opt, + ); +} + pub fn bench_quicksort(bench_group_opt: Option<&mut BenchmarkGroup>) { exec_bench_w_input( &file_path_from_root("crates/cli/tests/benchmarks", "quicksortApp.roc"), -- 2.44.0 ```

Run with a single call in the benchmark, there is no measurable improvement, but with 1,000,000 calls in a single benchmark, the results are

bench-group_wall-time/Benchmarking "listConcatUtf8"
                        time:   [8.1329 ms 8.1724 ms 8.2099 ms]
                        change: [-59.891% -59.676% -59.444%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 200 measurements (0.50%)
  1 (0.50%) high mild

[lukewilliamboswell]

This is looking good. Just need to resolve CI issues.

@Anton-4 any idea why xcrun might be missing?

= note: xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/CommandLineTools/usr/bin/xcrun

[Anton-4]

cargo test-gen-llvm-wasm --locked --release failed with:

test gen_list::list_concat_utf8 ... FAILED

 Call parameter type does not match function signature!
%str.RocStr %"#arg2"
 ptr  call void @roc_builtins.list.concat_utf8(ptr noalias nocapture nonnull sret(%list.RocList) %list_alloca, ptr nocapture nonnull readonly %list_alloca1, %str.RocStr nocapture nonnull readonly %"#arg2"), !dbg !993
define internal fastcc %list.RocList @List_concatUtf8_6b9d2d153924c8f8a993721e2b812757c4eec621dcc2108756cfa755bec(%list.RocList %"#arg1", %str.RocStr %"#arg2") !dbg !989 {
entry:
  %list_alloca1 = alloca %list.RocList, align 8
  %list_alloca = alloca %list.RocList, align 8
  store %list.RocList %"#arg1", ptr %list_alloca1, align 4, !dbg !993
  call void @roc_builtins.list.concat_utf8(ptr noalias nocapture nonnull sret(%list.RocList) %list_alloca, ptr nocapture nonnull readonly %list_alloca1, %str.RocStr nocapture nonnull readonly %"#arg2"), !dbg !993
  %load_list = load %list.RocList, ptr %list_alloca, align 4, !dbg !993
  ret %list.RocList %load_list, !dbg !993
}

[Anton-4]

There were some network issues with the CI machines, I restarted the failed jobs now.