Skip to content
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

Closed
p6rt opened this issue Sep 15, 2017 · 11 comments
Closed

Enum.succ and Enum.pred are O(n) #6522

p6rt opened this issue Sep 15, 2017 · 11 comments

Comments

@p6rt
Copy link

p6rt commented Sep 15, 2017

Migrated from rt.perl.org#132093 (status was 'resolved')

Searchable as RT132093$

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @AlexDaniel

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​: rakudo/rakudo#1156 (comment)

I think this ticket is closable without tests once the change is implemented.

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @AlexDaniel

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.jakimenko@​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​:
rakudo/rakudo#1156 (comment)

I think this ticket is closable without tests once the change is
implemented.

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @zoffixznet

On Thu, 14 Sep 2017 17​:47​:59 -0700, alex.jakimenko@​gmail.com wrote​:

but I guess it is possible to store the index of the current enum value and simply increment/decrement it when needed.

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)

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @zoffixznet

On Thu, 14 Sep 2017 18​:03​:16 -0700, alex.jakimenko@​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.jakimenko@​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​:
rakudo/rakudo#1156 (comment)

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] rakudo/rakudo@69dae1f3be
[2] rakudo/rakudo@8d938461a9
[3] Raku/roast@dfbbd70d46
[4] rakudo/rakudo@55aa7f28d3

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

@zoffixznet - Status changed from 'open' to 'resolved'

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @AlexDaniel

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 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)​:
* 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, cpan@​zoffix.com wrote​:

On Thu, 14 Sep 2017 18​:03​:16 -0700, alex.jakimenko@​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.jakimenko@​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​:
rakudo/rakudo#1156 (comment)

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] rakudo/rakudo@69dae1f3be
[2] rakudo/rakudo@8d938461a9
[3] Raku/roast@dfbbd70d46
[4] rakudo/rakudo@55aa7f28d3

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

@AlexDaniel - Status changed from 'resolved' to 'open'

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @AlexDaniel

Now resolved in rakudo/rakudo@f925c64

Closing.

On 2017-09-15 09​:01​:04, alex.jakimenko@​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 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)​:
*
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, cpan@​zoffix.com wrote​:

On Thu, 14 Sep 2017 18​:03​:16 -0700, alex.jakimenko@​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.jakimenko@​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​:
rakudo/rakudo#1156 (comment)

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] rakudo/rakudo@69dae1f3be
[2] rakudo/rakudo@8d938461a9
[3] Raku/roast@dfbbd70d46
[4] rakudo/rakudo@55aa7f28d3

@p6rt p6rt closed this as completed Sep 15, 2017
@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

@AlexDaniel - Status changed from 'open' to 'resolved'

@p6rt
Copy link
Author

p6rt commented Sep 15, 2017

From @zoffixznet

Well, as long as it benefits the "very fucking close", amirite?

Take care of the conch.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant