`contains?`/`in?` perform much slower for range checking than a simple `and?`

[drkameleon]

Describe the bug

Example (inspired by: https://adventofcode.com/2023/day/5)

if contains? a..b x [...]

vs

if and? [x >= a][x =< b] [...]

Expected behavior

Given how our ranges are defined, the two should have a very similar performance. But in fact, the former takes ages... :S

[RickBarretto]

For me, it's as expected.

$> arr: [1 2 3 4]

$> rng: 1..4

$> benchmark -> contains? arr 3
[benchmark] time: 1.898ms

$> benchmark -> contains? rng 3
[benchmark] time: 0.003ms

$> benchmark -> and? [3 >= 1] [3 =< 4]
[benchmark] time: 2.384ms

Version:

# version : v/0.9.83 b/1297 @ 2023-12-04T22:46:34-03:00
# arch    : amd64/windows

[drkameleon]

For me, it's as expected.

$> arr: [1 2 3 4]

$> rng: 1..4

$> benchmark -> contains? arr 3
[benchmark] time: 1.898ms

$> benchmark -> contains? rng 3
[benchmark] time: 0.003ms

$> benchmark -> and? [3 >= 1] [3 =< 4]
[benchmark] time: 2.384ms

Version:

# version : v/0.9.83 b/1297 @ 2023-12-04T22:46:34-03:00
# arch    : amd64/windows

Perhaps, it has to do with bigger numbers a range limits? Not so sure; will have to look into it... 🤔

Also, just an idea: running the above some hundreds-of-thousands (or more) times would perhaps helps to eliminate any "artifacts" in the measurements. 😉

[RickBarretto]

Actually, when running larger groups, it's slower...

$> arr: @0..10000

$> rng: 0..10000

$> benchmark -> contains? rng 7500
[benchmark] time: 0.289ms

$> benchmark -> contains? arr 7500
[benchmark] time: 0.072ms

$> benchmark -> contains? arr 250
[benchmark] time: 0.009ms

$> benchmark -> contains? rng 250
[benchmark] time: 0.022ms

I'll have a look of how we're handling Ranges right now.

[RickBarretto]

Well...

What I discovered:

helpers/ranges.nim:

proc contains*(rng: VRange, v: Value): bool {.inline,enforceNoRaises.} =
    rng.find(v) >= 0

vm/values/comparison.nim:

proc find*(a: openArray[Value], item: Value): int {.inline.}=
    result = 0
    for i in items(a):
        if i == item: return
        inc(result)
    result = -1  

[drkameleon]

Well...

What I discovered:

helpers/ranges.nim:

proc contains*(rng: VRange, v: Value): bool {.inline,enforceNoRaises.} =
    rng.find(v) >= 0

vm/values/comparison.nim:

proc find*(a: openArray[Value], item: Value): int {.inline.}=
    result = 0
    for i in items(a):
        if i == item: return
        inc(result)
    result = -1  

Jesus! Why did I implement it like this?!!!! Super weird...

That's an awesome catch! 😉

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.