search

monte-language / typhon

A virtual machine for Monte.
Other
67 stars 10 forks source link

optimize l.diverge(Int) and the like #202

Closed dckc closed 3 years ago

dckc commented 5 years ago

there is a massive speed boost waiting for us if we use collection strategies to speed up certain common situations like l.diverge(Int) by unboxing elements internally. This may require getting hands dirty with the JIT. -- @MostAwesomeDude Sep 2017 https://github.com/monte-language/typhon/issues/191#issue-255471872

...

FYI the change from .diverge() to .diverge(Int) in the montstone benchmark is worth a 4.8x slowdown. -- @MostAwesomeDude today

MostAwesomeDude commented 5 years ago

In a fat-pointer implementation, a generic optimization is available. Each fat pointer points to a script and a closure; instead of storing an array of fat pointers, a list could have a single script and an array of closures.

This can't possibly be outdone for anything where we'd need a full word per closure. For bytestrings and Unicode strings, we'll use packed formats already, so really the only wasteful case is List[Char].

MostAwesomeDude commented 3 years ago

I implemented this in e720df286d83b321fdb9f5b0755acdcfae431785 and made it usable in be868e4331bc053965724d45df5fdb3a6d893ad4.

MostAwesomeDude commented 3 years ago

I had to unwind a Hal-stack in order to benchmark this. The change from .diverge() to .diverge(Int) in the bench/montstone benchmark is currently about a 3.01x slowdown. I will accept that getting better here will basically require us to somehow totally internalize and erase the guard. However, I accomplished what I wanted to accomplish, and we got a non-trivial improvement.