Reference or copy: segment of an array as function argument

General Usage Performance
1

Sometimes, a segment of an array needs to be used as an argument to a function; e.g., consider searching for x in a part of an (sorted) array A:

searchsortedfirst(A[5:end], x)

Does this way produce a new copy of the corresponding segment of the array; i.e., A[5:end]?
If so, is there a better way to preclude that copy?

2

Yes

@view A[5:end]

4 Likes
3

I have tried several ways according to your suggestion:

  1. searchsortedfirst( @view A[5:end] , x0)
    produces the following error:

ArgumentError: Invalid use of @view macro: argument must be a reference expression A[…].

  1. vA = @view A[5:end]; searchsortedfirst(vA, x0)
    works as expected.

  2. vA = view(A, 5:end)
    produces the following error

syntax: missing last argument in “5:” range expression

I do not see especially why case 3 does not work.
Could you please elaborate on that?

4

In (1), the problem is that the expression is parsed like searchsortedfirst(@view(A[5:end], x0)), i.e. the two arguments are taken together. Just add explicit parantheses to the first argument — searchsortedfirst(@view(A[5:end]), x0) instead.

For (3), the macro and function call versions need to differ since end is not valid in an arbitrary function call argument (i.e. it needs the context of the array indexing to be automatically lowered to valid code). The correct form would look something like vA = view(A, 5:endof(A)).

1 Like
5

clear explanation. thanks a lot.

6

Using a view has the problem that it allocates on julia 0.6. If you need to construct these views in an inner loop, then this will mean trouble. Luckily the thing you are asking for is already provided in sort.jl; use the following:

searchsortedfirst(A, x, 5, length(A), Base.Order.ForwardOrdering()) - 5 + 1

1 Like
7

could you please explain the expression you have provided?
Base.Order.ForwardOrdering() and - 5 + 1, in particular.

8

searchsortedfirst(A, x, lo, hi, order) searches only in the interval lo:hi. In order to get the same result as for the view, you need to shift the indices again, i.e. subtract (lo-1). You can also use this version to speed up the search, if you already know something about the position of your target.

For some unclear reason, this variant is not exported with all the fancy default argument bells-and-whistles. This means that you need to provide the order explicitly. This is done by Base.Order.ForwardOrdering(), which is the default used by searchsortedfirst(A, x). If you used keyword parameters (e.g. searchsortedfirst(A, x; by=fun)) then you would need to look into sort.jl in order to see how to provide these.

2 Likes
9

thanks for the elaboration.

10

And of course, benchmark if all these complications end up actually making a difference in performance.