#2264 - vertices iterator for AbstractHyperrectangle

[schillic]

See #2264.

I was surprised that the iterator is generally slower. It is faster if it is not exhausted, though. I checked everything and I would conclude that the additional allocations are due to the way iteration is implemented: creation of a new Tuple in each iteration.

Defining the generator implementation:

function vertices2(H::AbstractHyperrectangle)
    n = dim(H)
    c = center(H)
    r = radius_hyperrectangle(H)
    p = Iterators.product(fill([1, -1], n)...)
    return Base.Generator(x -> c .+ r .* x, p)
end

julia> H = rand(Hyperrectangle, dim=10);

julia> function f(H)
           for v in LazySets.vertices2(H)
           end
       end;

julia> function g(H)
           for v in vertices(H)
           end
       end;

julia> function h(H)
           for v in vertices_list(H)
           end
       end;

julia> function f2(H, k)
           for (i, v) in enumerate(LazySets.vertices2(H))
               if i == k
                   return
               end
           end
       end;

julia> function g2(H, k)
           for (i, v) in enumerate(vertices(H))
               if i == k
                   return
               end
           end
       end;

julia> function h2(H, k)
           for (i, v) in enumerate(vertices_list(H))
               if i == k
                   return
               end
           end
       end;

# generate all vertices
julia> @btime f($H)
  400.304 μs (6151 allocations: 816.67 KiB)

julia> @btime g($H)
  62.453 μs (2052 allocations: 192.31 KiB)

julia> @btime h($H)
  50.713 μs (1027 allocations: 168.38 KiB)

# generate only k vertices
julia> @btime f2($H, 2)
  1.055 μs (15 allocations: 1.78 KiB)

julia> @btime g2($H, 2)
  249.454 ns (9 allocations: 752 bytes)

julia> @btime h2($H, 2)  # h/h2 are equivalent independent of k
  50.362 μs (1027 allocations: 168.38 KiB)

julia> @btime g2($H, 3)
  323.396 ns (12 allocations: 992 bytes)

julia> @btime f2($H, 4)
  1.448 μs (23 allocations: 2.88 KiB)

julia> @btime g2($H, 4)
  395.905 ns (15 allocations: 1.20 KiB)

The last two runs show that Incrementing k leads to three new allocations of size 240 bytes. One of them is of course the additional vertex that is generated. The two other allocations are probably the Tuples; at least I do not see where else the code would allocate anything depending on k.

[mforets]

I was surprised that the iterator is generally slower

have you considered using a generator? in Julia v1.6 one can directly map iterators, such that the vertices iterator for hyperrectangles is simply:

julia> p = Iterators.product(fill([1, -1], 2)...)
Base.Iterators.ProductIterator{Tuple{Vector{Int64},Vector{Int64}}}(([1, -1], [1, -1]))

julia> Iterators.map(x -> rand(2) .* x .+ rand(2), p)
Base.Generator{Base.Iterators.ProductIterator{Tuple{Vector{Int64},Vector{Int64}}},var"#27#28"}(var"#27#28"(), Base.Iterators.ProductIterator{Tuple{Vector{Int64},Vector{Int64}}}(([1, -1], [1, -1])))

julia> first(ans)
2-element Vector{Float64}:
 1.0472048628849284
 1.9230998571087827

the idea is to use the former method, see here.

we could otherwise try with Base.Generator (or IterTools.jl) as suggested in this question

[mforets]

whatever method we choose we should be sure that the vector is not changed, eg if H has sarray center and radius, the vertices should also be sarrays.

[schillic]

I played around with your suggestion of a generator. I updated the results in the OP (f is the new implementation). The generator implementation is much worse. Maybe I misunderstood something there.