Memory allocated in vectorized operations

[GeorgeR227]

This is an extension of issue #121. While individual accesses and sets have been fixed, vectorized operations are still allocating significantly more than they should. Here's a MWE:

using ACSets

SchTest = BasicSchema([:V,:E], [(:v0,:E,:V)])

@acset_type Test(SchTest, index=[:v0])

s = Test()

N = 10
add_parts!(s, :V, N)
idx = add_parts!(s, :E, N)

entry = ones(Int64, N);

function add_vector(s, idx, entry)
  s[idx, :v0] = entry
end

function add_loop(s, idx, entry)
  for (i, id) in enumerate(idx)
    s[id, :v0] = entry[i]
  end
end

begin 
  add_vector(s, idx, entry)
  add_loop(s, idx, entry)
end

@info "Using add_vector"
@time add_vector(s, idx, entry)

@info "Using add_loop"
@time add_loop(s, idx, entry)

As well as the results:

[GeorgeR227]

When reverting to ACSets 0.2.17 I'm getting very similar results so this seems to have a separate cause from that in issue #121.

Results for ACSets 0.2.17:

[GeorgeR227]

I have a feeling that this is again due to problems in constant propagation, specifically in the function here:

ACSets.jl/src/ACSetInterface.jl

Lines 264 to 268 in d6e41b1

	@inline function set_subpart!(acs::ACSet , parts::Union{AbstractVector{Int}, AbstractSet{Int}}, name, vals)
	broadcast(parts, vals) do part, val
	set_subpart!(acs, part, name, val)
	end
	end

I think the issue here is the broadcast and I've written up a small script showcasing it.

using ACSets

SchTest = BasicSchema([:V,:E], [(:v0,:E,:V)])

@acset_type Test(SchTest, index=[:v0])

s = Test()

N = 100
add_parts!(s, :V, N)
idx = add_parts!(s, :E, N)

entry = ones(Int64, N);

function add_broadcast(s, idx, entry, symbol)
  broadcast(idx, entry) do i, id
    set_subpart!(s, i, symbol, id)
  end
end

function add_broadcast(s, idx, entry)
  broadcast(idx, entry) do i, id
    set_subpart!(s, i, :v0, id)
  end
end

begin
  add_broadcast(s, idx, entry);
  add_broadcast(s, idx, entry, :v0);
end;


@info "Using add_broadcast known symbol"
@time add_broadcast(s, idx, entry);

@info "Using add_broadcast passed symbol"
@time add_broadcast(s, idx, entry, :v0);

Here are results. Both seem to scale with the number of parts to be added but the broadcast with the known symbol performs much better.

[ Info: Using add_broadcast known symbol

  0.000010 seconds (1 allocation: 144 bytes)

[ Info: Using add_broadcast passed symbol

  0.000030 seconds (18 allocations: 1.188 KiB)

[GeorgeR227]

Adding onto my previous comment it seems turning the symbol pass into a Val{symbol} and using where seems to allow the constant to propagate. This also works with Type{Val{symbol}}.

function add_broadcast(s, idx, entry, ::Val{symbol}) where symbol
  broadcast(idx, entry) do i, id
    set_subpart!(s, i, symbol, id)
  end
end

begin
  add_broadcast(s, idx, entry, Val(:v0));
end;

@info "Using add_broadcast passed val(symbol)"
@time add_broadcast(s, idx, entry, Val(:v0));

Results:

[ Info: Using add_broadcast passed val(symbol)

  0.000008 seconds (1 allocation: 144 bytes)

[jpfairbanks]

I ran code warn type on this and the problem seems to be that the symbol is not getting constant propped and so the return type of set_parts can't be inferred. It would be great if there is another inlining based fix like for the single index case that was just fixed.

When you pass in Val{s} where s <:Symbol there are no warnings type problems. Maybe we should just switch to telling users to call their functions with Val(:f) instead of :f

[epatters]

I'm assuming this issue was adequately resolved by #136. Please reopen if not.

[GeorgeR227]

Re-opening since issue still exists.

[epatters]

To be clear, I assume that a fix means zero allocations.

[GeorgeR227]

Yeah that's right.