potential to speed up arrays

[shriram]

Looking up an array's length takes a fair bit of time, even if it's constant.

a1 = array-of(nothing, 100)

range(0, 1000000).foldl(
  lam(a,b):
    t1 = time-now()
    _ = array-length(a1)
    b + (time-now() - t1)
  end, 0)

# -> 2045 ms

l = array-length(a1)

range(0, 1000000).foldl(
  lam(a,b):
    t1 = time-now()
    _ = l
    b + (time-now() - t1)
  end, 0)

# -> 254 ms

(On my ~5yo laptop the times are roughly 2x these, but in roughly the same proportion.)

Credit to finding this to Louis Kilfoyle.

[sorawee]

To be fair:

a1 = array-of(nothing, 100)

range(0, 1000000).foldl(
  lam(a,b):
    t1 = time-now()
    _ = array-length(a1)
    b + (time-now() - t1)
  end, 0)

takes 2680ms in my laptop

a1 = array-of(nothing, 100)

fun f(x :: Number) -> Number:
  x
end

range(0, 1000000).foldl(
  lam(a,b):
    t1 = time-now()
    _ = f(1)
    b + (time-now() - t1)
  end, 0)

takes 2661ms in my laptop.

From these, I think it's about Pyret function call rather than array.

[shriram]

Good catch, thanks!

[shriram]

But the array's length does not have to be a call at all. It can be just a field lookup. Indeed, making it a field would make clearer that it's constant time and not potentially linear.

[blerner]

I think that's technically true. I think we went with a method to ensure that its interface was similar to lists as we could make it, though.

Making it a field rather than a method would have efficiency gains, and would preclude allowing arrays to grow dynamically. (They currently are fixed length, so this would not break any existing programs, but it would limit us in the future.)

[schanzer]

@blerner I'm assuming we never implemented this. Are there still plans to do so someday?

[blerner42]

I think it's part of a bigger reconsideration of how arrays work in Pyret; Array and RawArray are needlessly different, given how people are using them. This specific issue hasn't been implemented, but we'll think about it some more...