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

dart2js: Integer division by two is extremely slow compared to shift. #14166

Closed
lrhn opened this issue Oct 17, 2013 · 2 comments
Closed

dart2js: Integer division by two is extremely slow compared to shift. #14166

lrhn opened this issue Oct 17, 2013 · 2 comments
Labels
closed-obsolete Closed as the reported issue is no longer relevant type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) web-dart2js

Comments

@lrhn
Copy link
Member

lrhn commented Oct 17, 2013

In Dart, integer division by 2 is the same as right-shift by 1.

It isn't so in dart2js because dart2js doesn't have integers, and only does 32-bit shift operations, but it should still be possible to do some integer
divisions faster.

If you implement two binary searches where the only difference is using a single division or shift to find the middle index, i.e., either:
  int mid = min + ((max - min) >> 1);
or
  int mid = min + ((max - min) ~/ 2);
then the performance of the former is 120% better than the latter.
That is, the single ~/2 takes more time (more than >>) than the entire rest of the algorithm.

I'd prefer to be able to use ~/2 instead of >>1 when conceptually I'm really halving a value, and not shifting bits, but the overhead is too significant to ignore.

@lrhn
Copy link
Member Author

lrhn commented Oct 17, 2013

Attached the binary search benchmark (kop/ms is thousands of search operations per millisecond).


Attachment:
bintime.dart (1021 Bytes)

@kevmoo kevmoo added type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) and removed priority-unassigned labels Feb 29, 2016
@lrhn
Copy link
Member Author

lrhn commented Sep 12, 2016

I see only a ~5% difference now, which is reasonable because ~/ 2 isn't equivalent to >>1 for negative numbers, and the compiler probably doesn't realize that only positive numbers can occur in the code.

@lrhn lrhn closed this as completed Sep 12, 2016
@lrhn lrhn added the closed-obsolete Closed as the reported issue is no longer relevant label Sep 12, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
closed-obsolete Closed as the reported issue is no longer relevant type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) web-dart2js
Projects
None yet
Development

No branches or pull requests

2 participants