search

monome / norns

norns is many sound instruments.
http://monome.org
GNU General Public License v3.0
633 stars 147 forks source link

Notate that wrap accepts integers; reimplement to be constant-time #1577

Closed sixolet closed 1 year ago

sixolet commented 2 years ago

fixes https://github.com/monome/norns/issues/1576

tyleretters commented 2 years ago

@sixolet initial review looks great! i can test in the next 24 hours or so.

are the crow commits supposed to be part of a separate PR?

sixolet commented 2 years ago

Okay, I did a little bit of git surgery to remove the weird merge commits or the commits that I already PRed or whatever happened there.

ngwese commented 2 years ago

For what it is worth the current implementation came as part this discussion https://github.com/monome/norns/pull/1277 - if performance is a concern it would be worth a little benchmark to confirm this is faster.

tyleretters commented 2 years ago

my test results look good! the behavior is 1:1. i approve the merge. (i don't have the permissions actually approve it on github.)

@ngwese there are two concerns - one is clarifying is for integers. i will let @sixolet speak to the constant-time / performance.

catfact commented 2 years ago

i provided the while in demonstration code as an alternative to a recursive version of the same thing - which had the same drawback, plus consuming unbounded stack space. i don't claim its optimal and it is indeed only for integers (thank you.)

regarding performance i'll note that the looped wrap is faster when it only needs to wrap once or twice, which is most of the time. (*) lua's modulo operator has several hidden costs: more metamethod lookups, two branches, and internal operation on doubles. (maybe this is improved in 5.3)

IOW: measure before optimizing, of course

(but overall i agree, constant time is better)

(*) such considerations might lead to wanting operations like increment_and_wrap for optimal performance.

sixolet commented 2 years ago

I think they were merged already. I can do some git surgery to extract them. I just switched to ff-only, I think the problem was I was merging from upstream.

On Sun, Jun 19, 2022 at 12:46 PM Tyler Etters @.***> wrote:

@sixolet https://github.com/sixolet initial review looks great! i can test in the next 24 hours or so.

are the crow commits supposed to be part of a separate PR?

— Reply to this email directly, view it on GitHub https://github.com/monome/norns/pull/1577#issuecomment-1159799481, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOZYKUHN6UVWNPVZ2HRS3VP52JJANCNFSM5ZFZ73SA . You are receiving this because you were mentioned.Message ID: @.***>