V_VALS_C and E_VALS_C

[gdalle]

Hi there,

Following up on our discussion in Slack :) First of all, thanks for your work on this library!

I understand the purpose of these two types is to describe the storage of vertex and edge values. However, since the related fields are constructed using typeof(...), I'm not sure the compiler is able to infer the types correctly. Here is an example supporting my hunch:

julia> using SimpleValueGraphs

julia> using Test

julia> @inferred ValGraph(0)
ERROR: return type ValGraph{Int32,Tuple{},Tuple{},Tuple{},Tuple{},Tuple{}} does not match inferred return type ValGraph{Int32,Tuple{},Tuple{},Tuple{},Tuple{},_A} where _A
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] top-level scope at none:1

What do you think? Could we make this better somehow?

[simonschoelly]

So it is indeed true that the compiler can't infer the type statically. In this case, this can certainly be fixed, maybe with usage of the@generated macro. What might probably be a bit more difficult are constructors of the form

ValGraph(0, edgeval_types=..., vertexval_types)

as it it is not always clear when keyword arguments are resolved at at runtime. I think this relies also a bit on const propagation, where there are no clear rules when that optimization is used. If it turns out that it is not possible to make the compiler infer the type statistically, there can always be the alternative constructor of the form

ValGraph{V, V_VALS, E_VALS, G_VALS}

This notation might just be a bit awkward to write.

In any case, I don't think it is a big issue here, as when you call some function with your graph, i.e. f(g, ...), the type of the graph is fully determined inside this function.

There is another issue with type instability, and that is when you have a graph with multiple vertex values (or edge, graph values) of different types, then get_vertexval(g, v, 1) is not typestable anymore. This can maybe be resolved in the future by inlining functions, in the hope that const propagation is triggered.

[gdalle]

OK, I think I understand now why my initial "problem" doesn't really matter :) thanks for your detailed explanations!

[gdalle]

I didn't know about inlining but I looked it up, and it seems like a nice solution to the get_value type instability. What is stopping you from implementing it? A lack of benchmarks?

[simonschoelly]

Just some lack of time - I only found really time in the last few months to get this package into the shape it is now. Actually I also now merged some patch that will help with type instability there.

[gdalle]

Hey! I'm getting back into graph structures, and I was wondering if you had made some progress towards solving type instability within get_vertexval(g, v, 1)? If not, can we guess how much it affects performance?

[simonschoelly]

I have not really had time to work on this yet, I probably would also have to check if constant propagation works not better on Julia v1.7.0.

It is rather heard to say how much performance is impacted, it might depend on how many different types are used for V_VALS and the code surrounding that statement.

[simonschoelly]

Btw. I now fixed some of the constructor instability but its only on the master branch.