effekt-lang / effekt-lang/effekt

Further optimising stream fusion

Open
#1,064 2 comments 0 reactions 0 assignees View on GitHub
optimizer-wishlist
Dominant language
Scala
Stars
469
Forks
41
Avg merge
1d 16h
Merged PRs (30d)
23

Description

I was trying out "stream fusion" (example from https://gitlab.haskell.org/ghc/ghc/-/wikis/sequent-core#cases-where-we-win), can we do better here somehow?
At the very least, I'd like this program to not be worse with a new optimiser, cc @dvdvgt.

[Playground link](https://effekt-lang.org/playground.html?playground=hZFfa4MwFMXf%2FRTnMYHQtd1%2FRze6vY697amUIRppmEYxcXOI331JjGlxhT0Uiveec373hOc5TzV4KfRuuydfSdHyGFsa410KHUUZz5GLQvPGjoWsWx3jVSi7TdHjk%2FP6yQiwecRzVRUYwhgb9BFgHZRueFKecRhjcDEBGI3bQJno9OD0QJoojjdREGpTCD1%2BfKmkIh1Dp9woq5wP6eiDjyRmYtaHyIO0MqAY%2BPF%2FbKUzjNMrXJxufoKAGPsRZ8C30Ieg6tEZL7ePwNZw1ZacEEpH8MCiQq9ne%2FyP709xgXOinMN5MNdch0Rm6BYud97dEflU8mHXZiN3zFSqfy5%2Fl28jZJiDvJvncw892difMbO9lImQ9qlRN0LqQpLdimHNcMlwxXDNcMNwy3DHcM%2BwWu4X87yyysjaGGywxEB%2FAQ%3D%3D&repl=bWFpbigp)

```scala
effect emit[A](value: A): Unit

def filter[A](input: List[A]) { keep?: A => Bool }: List[A] = {
def stream[A](input: List[A]): Unit / emit[A] = input match {
case Nil() => ()
case Cons(x, xs) => do emit(x); stream(xs)
}

def unstream[A] { stream: => Unit / emit[A] }: List[A] =
try { stream(); Nil() } with emit[A] { x =>
Cons(x, resume(()))
}

def sfilter[A] { keep?: A => Bool } { stream: => Unit / emit[A] }: Unit / emit[A] =
try stream() with emit[A] {
case x and x.keep? => do emit(x); resume(())
case _ => resume(())
}

unstream {
sfilter { x => x.keep? } {
stream(input)
}
}
}

def main() = println([1, 2, 3, 4, 5, 6, 7, 8, 9, 10].filter { x => x.mod(2) == 0 })
```

Core IR:

```scala
interface emit_3589[A_3588] {}

def main_3594() = {
val v_r_4078: List_928[Int_409] = reset { {p_5070} => // Is the `reset-shift` even needed here anymore?
def stream_worker_5105(input_5102: List_928[Int_409]) = input_5102 match {
case Nil_1165 { () =>
return ()
}
case Cons_1166 { (x_5101: Int_409, xs_5100: List_928[Int_409]) =>
if (infixEq_73(mod_109(x_5101, 2), 0)) {
val __5210: Unit_405 = shift(p_5070) { {k_5150} =>
val v_r_5152: List_928[Int_409] = resume(k_5150) {
return ()
};
return make List_928[Int_409] Cons_1166(x_5101, v_r_5152)
};
stream_worker_5105(xs_5100) // I think we could lift these tail calls out of the if
} else {
stream_worker_5105(xs_5100) // see ^
}
}
}
val __5212: Unit_405 = stream_worker_5105(make List_928[Int_409] Cons_1166(1, make List_928[Int_409] Cons_1166(2, make List_928[Int_409] Cons_1166(3, make List_928[Int_409] Cons_1166(4, make List_928[Int_409] Cons_1166(5, make List_928[Int_409] Cons_1166(6, make List_928[Int_409] Cons_1166(7, make List_928[Int_409] Cons_1166(8, make List_928[Int_409] Cons_1166(9, make List_928[Int_409] Cons_1166(10, make List_928[Int_409] Nil_1165())))))))))));
return make List_928[Int_409] Nil_1165()
};
def go_5244(l_5242: List_928[Int_409]) = l_5242 match {
case Nil_1165 { () =>
return "Nil()"
}
case Cons_1166 { (x_5251: Int_409, xs_5249: List_928[Int_409]) =>
val v_r_5259: String_404 = go_5244(xs_5249);
return infixConcat_36(infixConcat_36(infixConcat_36(infixConcat_36("Cons(", show_15(x_5251)), ", "), v_r_5259), ")")
}
}
val v_r_5253: String_404 = go_5244(v_r_4078);
let tmp_5308 = println_1(v_r_5253)
return tmp_5308
}
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Use the linked playground example and its generated Core IR as the baseline. Read the optimizer behavior around the shown reset-shift and duplicated tail calls, then verify whether the optimized program is no worse and whether the unnecessary structure can be removed without changing the result.

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
compilers, performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.