aiken-lang / stdlib

The Aiken Standard Library
https://aiken-lang.github.io/stdlib
Apache License 2.0
47 stars 26 forks source link

`list.count` should be using `foldr` #82

Closed KristianBalaj closed 4 months ago

KristianBalaj commented 8 months ago

foldr seems to be more performant in Aiken when doing aggregations and count is an aggregation.

Check out the following benchmark (countl is the one currently implemented in stdlib):

fn countl(self: List<a>, predicate: fn(a) -> Bool) -> Int {
  list.foldl(
    self,
    0,
    fn(item, total) {
      if predicate(item) {
        total + 1
      } else {
        total
      }
    },
  )
}

fn countr(self: List<a>, predicate: fn(a) -> Bool) -> Int {
  list.foldr(
    self,
    0,
    fn(item, total) {
      if predicate(item) {
        total + 1
      } else {
        total
      }
    },
  )
}

And the benchmark:

test countl_1() {
  countl([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], fn(a) { a >= 2 }) == 9
}
test countr_1() {
  countr([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], fn(a) { a >= 2 }) == 9
}

Resulting in the following:

    │ PASS [mem: 47251, cpu: 18667630] countl_1
    │ PASS [mem: 46951, cpu: 18598630] countr_1
rvcas commented 8 months ago

hm interesting observation. Thank you