Implementation for AbstractVector with limited storage

I am solving a problem where for each set of parameters, I can have 1–4 outcomes. How many depends on the parameters.

Currently I am using something not unlike

solutions = Vector{T}() # T is calculated before, it is an immutable composite type
for schema in (schema1, schema2, schema3, schema4)
    sol = try_solution(schema, parameters)
    if sol !== nothing
       push!(solutions, sol)
    end
end
pick_best(solutions)

I benchmarked my code and the allocation is costly (I am doing this multiple times).

An obvious solution would be implementing a <:AbstractVector{T} with limited size, eg

mutable struct LimitedVector{N,T}
    count::Int
    contents::MVector{N,T}
    LimitedVector{N,T}() = new(0, MVector{N,T}())
end

with the obvious push!, size, getindex.

Two questions:

  1. is there a package which implements something like this already? then I would not make yet another package :wink:
  2. is there a better approach?

What about sizehint!ing the Vector? It’s already doing effectively what your LimitedVector does (albeit with the ability to surpass N). Or just allocating an undef array of length N and then empty!ing it.

There’d still be opportunities for more micro-optimizations, but that’d be a very simple 80% sort of solution.

2 Likes

A SmallVector from SmallCollections.jl :

solutions = SmallVector{4,T}() # T is calculated before, it is an immutable composite type
for schema in (schema1, schema2, schema3, schema4)
    sol = try_solution(schema, parameters)
    if sol !== nothing
       solutions = push(solutions, sol)
    end
end
pick_best(solutions)
3 Likes