Well, 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 https://github.com/rakudo/rakudo/commit/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): * https://github.com/azawawi/perl6-net-curl/blob/6058c370112a2477b71608ee273231cde1d8f4ae/lib/Net/Curl/NativeCall.pm6#L250-L457 * https://github.com/perl6/DBIish/blob/2059b722fd2efea25513eb7250ddfe4d1b42ec41/lib/DBDish/Pg/Native.pm6#L152-L308 * https://github.com/andydude/p6-c-parser/blob/d1deface417808b66b6d57c04e35a801d537dbae/lib/C/AST/Ops.pm6#L4-L90 * https://github.com/CurtTilmes/perl6-libcurl/blob/95f975fd4ac69c4a561de86dd03e03958e9983c9/lib/LibCurl/EasyHandle.pm6#L98-L189 Sure, not in thousands, but very fucking close. On 2017-09-15 08:04:30, c...@zoffix.com wrote: > On Thu, 14 Sep 2017 18:03:16 -0700, alex.jakime...@gmail.com wrote: > > Actually, another direct implication of using .first is this: > > > > Code: > > enum Animal (Cat => 0, Dog => 0, Human => 42); > > say Dog.succ > > > > Result: > > Dog > > > > > > So it's not just the algorithmic complexity, and we need a test for > > that. > > > > On 2017-09-14 17:47:59, alex.jakime...@gmail.com wrote: > > > Source code: > > > https://github.com/rakudo/rakudo/blob/nom/src/core/Enumeration.pm#L36- > > > L45 > > > > > > The problem is with this line: > > > my $index = @values.first( self, :k ); > > > > > > 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: > > > https://github.com/rakudo/rakudo/pull/1156#issuecomment-329640201 > > > > > > I think this ticket is closable without tests once the change is > > > implemented. > > > 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] https://github.com/rakudo/rakudo/commit/69dae1f3be > [2] https://github.com/rakudo/rakudo/commit/8d938461a9 > [3] https://github.com/perl6/roast/commit/dfbbd70d46 > [4] https://github.com/rakudo/rakudo/commit/55aa7f28d3
