Now resolved in https://github.com/rakudo/rakudo/commit/f925c64826f78803969bb43398877309f6b4a1ac
Closing. On 2017-09-15 09:01:04, alex.jakime...@gmail.com wrote: > 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
