Comments (9)
@rohitvarkey, is this 20x slowdown consistent with the C call overhead, or is it due to the fact that edgeweight looks at all the edges of a vertex to find the edge, while edgeparse already has the edge and is just extracting the weight?
from stingergraphs.jl.
I think the latter is probably the right explanation. The Julia C overhead is pretty small. But the ccall
to stinger_edgeweight
ends up traversing all the edges of a vertex to find the edge rather than just reading the value off an edge already in memory. With more edges, the overhead will be more evident as the C function has to traverse more edges in the stinger_edgeweight
function.
from stingergraphs.jl.
Thank you for the explanation. Given the source and destination vertices of an edge, does Stinger have a function to retrieve its weight without traversing through all the edges of a vertex? If so, making it available in the Julia-Stinger would be highly desirable!
from stingergraphs.jl.
This is unfortunately one area where STINGER performance is going to poor (at least on high-degree vertices). STINGER was designed with traversal in mind, so it's database-like query features are not great. Fixing this would require either a second index over the edges (prohibitively expensive) or a re-design of the linked list of blocks adjacency structure. We have had discussions about how we might approach this, but nothing has been prototyped yet.
from stingergraphs.jl.
Right, the design of stinger is one based on implementing high performance parallel algorithms, which means that any operation on one edge is not optimized.
What is the circumstance surrounding your need to get a single edge out of the stinger? Can we restructure the higher level algorithm to avoid this operation?
from stingergraphs.jl.
I am considering the cases for streaming updates. For example, if the edge weight represents the number of interactions between two specific vertices, one may want to increment that weight when new interactions are observed. That will likely involve access and modification of the weight of a specific edge.
In some cases though, the updates will involve all the edges to and from a certain vertex. Is there a fast way to retrieve the weights of all such edges? I am using the foralledges iterator to access each edge of a certain vertex now, but it's not clear how I can get their weights.
from stingergraphs.jl.
I am considering the cases for streaming updates. For example, if the edge weight represents the number of interactions between two specific vertices, one may want to increment that weight when new interactions are observed. That will likely involve access and modification of the weight of a specific edge.
I was looking through the stinger C source and it seems like there is another C function, called stinger_incr_edge
that increments the edge weight passed in rather than set it like stinger_insert_edge
(which is called fom Julia currently) does. I should be able to add an interface for you to use that function if you'd like. However, this C function also has to iterate through all the edges of the vertex before being able to update it.
In some cases though, the updates will involve all the edges to and from a certain vertex. Is there a fast way to retrieve the weights of all such edges? I am using the foralledges iterator to access each edge of a certain vertex now, but it's not clear how I can get their weights.
The following will work to load the edges and the edge weights into Julia. But you will not be able to update the weights in the C memory as it the edge has been loaded into Julia already.
julia> s = Stinger()
StingerGraphs.Stinger(Ptr{Void} @0x00000001e4e7b000)
julia> for i=1:5
insert_edge!(s, 0, 0, i, i, 0)
end
julia> foralledges(s, 0) do e, src, etype
@show e.weight
end
e.weight = 1
e.weight = 2
e.weight = 3
e.weight = 4
e.weight = 5
Another way to solve this for fast updation of all vertices would be write your own foralledgesupdate
function. I've written up a quick implementation in #40.
from stingergraphs.jl.
stinger_batch_incr_edges
is the way to go here. You provide a list of edges to update and it applies all of them in parallel, adding up the weights. It batches up the updates so that each neighbor list is only traversed once. I think we held off on providing a wrapper because this function is implemented using C++, which is harder to interface with Julia.
from stingergraphs.jl.
Yes, the e.weight allowed me to access the edge weights during a traversal, which is fast. I noticed the weights are reported in one direction but not the other and opened up a separate issue on this. I'll follow up on the batch update in #40
from stingergraphs.jl.
Related Issues (18)
- Distribute Stinger library along with the Package HOT 4
- insert remove optimization from ehein
- Kronecker Graph generator HOT 2
- Neighborhood iteration on julia side
- Type stability in threads loop HOT 1
- Change stinger allocation sizes HOT 2
- atomics HOT 1
- STINGER graph creation is slow HOT 8
- Transferring this repo to stingergraph organization HOT 1
- Streaming Graph Challenge HOT 2
- fast function for checking the existence of an edge? HOT 2
- edge weight inserted in one direction only HOT 3
- Info about upcoming removal of packages in the General registry
- Trying to remove a loop edge makes stinger go into an infinite loop HOT 1
- Parallel BFS
- BFS Serial HOT 3
- Custom Array Type for Vertices? HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from stingergraphs.jl.