Skip to content

Performance concern regarding NumericRange.contains #23285

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

Open
klaeufer opened this issue May 29, 2025 · 3 comments
Open

Performance concern regarding NumericRange.contains #23285

klaeufer opened this issue May 29, 2025 · 3 comments
Labels

Comments

@klaeufer
Copy link

klaeufer commented May 29, 2025

Compiler version

3.7.0 and probably all prior

Minimized example

val m = Integer.MAX_VALUE.toLong
val n = 1000000000
val i = 2L * m - 2L
val range = m until i + 1L

val t0 = System.currentTimeMillis ; (1 to n) foreach (_ => range.start <= i && i < range.end) ; System.currentTimeMillis - t0

val t1 = System.currentTimeMillis ; (1 to n) foreach (_ => range.contains(i)) ; System.currentTimeMillis - t1

Output

val i: Long = 4294967292
val m: Int = 2147483647
val n: Int = 1000000000
val range: scala.collection.immutable.NumericRange.Exclusive[Long] = NumericRange 2147483647 until 4294967293

val t0: Long = 1748538438604
val res1: Long = 5533

val t1: Long = 1748538462486
val res3: Long = 14021

Expectation

res3 should be similar to res1, not two to three times as much.

@klaeufer klaeufer added the stat:needs triage Every issue needs to have an "area" and "itype" label label May 29, 2025
@He-Pin
Copy link
Contributor

He-Pin commented May 29, 2025

refs: #18044

@sjrd
Copy link
Member

sjrd commented May 30, 2025

Range is an Int range. IMO there is no more reason to specialize its contains method for Longs than for Doubles or BigInts.

May I suggest to alter the call site instead?

(1 to n) foreach (_ => i.toInt == i && range.contains(i.toInt))

@klaeufer
Copy link
Author

klaeufer commented May 30, 2025

My bad for mentioning Range. That's not my use case, so I removed the link to Range.contains and updated the issue title.

val range: scala.collection.immutable.NumericRange.Exclusive[Long]

Here is the corresponding contains method:

https://github.com/scala/scala/blob/v2.13.16/src/library/scala/collection/immutable/NumericRange.scala#L290

Because of this inherent/essential additional cost, this might simply become an API documentation issue where we could recommend using an explicit comparison if performance is critical.

@klaeufer klaeufer changed the title Performance problem in Range.contains - missing specialization for Long arguments Performance concern regarding NumericRange.contains May 30, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

4 participants