New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Enum.succ and Enum.pred are O(n) #6522
Comments
From @AlexDanielSource code: https://github.com/rakudo/rakudo/blob/nom/src/core/Enumeration.pm#L36-L45 The problem is with this line: Basically, .first will iterate through the elements, but I guess it is possible to store the index of the current enum value and simply increment/decrement it when needed. Some discussion here: rakudo/rakudo#1156 (comment) I think this ticket is closable without tests once the change is implemented. |
From @AlexDanielActually, another direct implication of using .first is this: Code: Result: So it's not just the algorithmic complexity, and we need a test for that. On 2017-09-14 17:47:59, alex.jakimenko@gmail.com wrote:
|
From @zoffixznetOn Thu, 14 Sep 2017 17:47:59 -0700, alex.jakimenko@gmail.com wrote:
That's trading more RAM for performance increase that's likely inconsequential in nearly all use cases. To hit any performance bottleneck you'd both have to be iterating over enums and have an Enumeration with a couple thousand values, but you'd be paying with extra memory in exactly all use cases. Premature optimization is the root of all evil. The bug mentioned later in the ticket is in Enumeration.WHICH that uses the value's + Enumeration's name, discarding the instance name. The nqp::eqaddr works as a workaround: rakudo/rakudo#1156 (comment) |
The RT System itself - Status changed from 'new' to 'open' |
From @zoffixznetOn Thu, 14 Sep 2017 18:03:16 -0700, alex.jakimenko@gmail.com wrote:
The wrong Enumeration:D being returned is now fixed[^1][^2] and tested[^3]. For the performance issue: I made[^4] .pred 8.4x faster and .succ 6x faster, while keeping the same O(). I hope that's sufficient compromise to close this ticket, given that the huge majority of Enumerations would have just a few elements, not thousands. [1] rakudo/rakudo@69dae1f3be |
@zoffixznet - Status changed from 'open' to 'resolved' |
From @AlexDanielWell, the title says “Enum.succ and Enum.pred are O(n)” and the issue is still there, so this ticket is definitely not resolved. If anything, it was rejected. However, the reasoning for keeping O(n) kinda contradicts itself. If we're trading RAM for performance, and the amount of elements in enums is small, it shouldn't really matter which way we go. However, as mentioned on the PR already, .succ-ing repeatedly gives us O(n²), and it's a good idea to avoid that. Looking at rakudo/rakudo@55aa7f28d3 , I'm kinda appreciating the point about premature optimization. However, 8.4x speedup does not resolve the issue with algorithmic complexity of O(n²) in user code. As for how huge an enum can be, here are some examples from the ecosystem (these are just the ones that jumped at me, there are probably more): Sure, not in thousands, but very fucking close. On 2017-09-15 08:04:30, cpan@zoffix.com wrote:
|
@AlexDaniel - Status changed from 'resolved' to 'open' |
From @AlexDanielNow resolved in rakudo/rakudo@f925c64 Closing. On 2017-09-15 09:01:04, alex.jakimenko@gmail.com wrote:
|
@AlexDaniel - Status changed from 'open' to 'resolved' |
From @zoffixznetWell, as long as it benefits the "very fucking close", amirite? Take care of the conch. |
Migrated from rt.perl.org#132093 (status was 'resolved')
Searchable as RT132093$
The text was updated successfully, but these errors were encountered: