stingergraph / stingergraphs.jl Goto Github PK

Distribute a version of the shared library with the library. Or set it up using BinDeps.

There is a python jupyter notebook for solving the DARPA streaming graph challenge that could use the stingergraphs.jl treatment.
https://github.com/graphchallenge/GraphChallenge/tree/master/StochasticBlockPartition/code/python.

What do you think about it @rohitvarkey?

• Bench
• Tests

See - #4

using StingerWrapper
s = Stinger()
insert_edge!(s, 0, 1, 1, 0, 0)
remove_edge!(s, 0, 1, 1) #Goes into infinite loop

The C definition of remove_edge! does have a note specifying how this function should not be called concurrently with the same source.

@jpfairbanks Does this case come under that condition? I guess we should add a check for this at the wrapper side (in remove_edge) in any case.

If we are not able to allow for deletion of loop edges, should we allow such an edge to be inserted in insert_edge! in the first place?

I noticed that when an edge is inserted, somehow the edge weight is only returned in one direction but not the other. For example:

g1 = Stinger(StingerGraphs.StingerConfig(100, 1004, 1, 1, 110^6, 0, 0, 0))
insert_edge!(g1, 0, 1, 2, 3, 0)

foralledges(g1, 1) do edge, src, etype
direction, neighbor = edgeparse(edge)
println(direction, " ", neighbor," ", edge.weight)
end

produces "2 2 3" as expected, but

foralledges(g1, 2) do edge, src, etype
direction, neighbor = edgeparse(edge)
println(direction, " ", neighbor," ", edge.weight)
end

produces "1 1 0", with weight being 0.

@ehein added this feature branch
https://github.com/ehein6/stinger/tree/optimize-batch-insert

Not sure this is an issue, but I noticed that retrieving edges weights using the edgeweight(g, src, dest, etype) function is significantly slower (~20 times) than just parsing the edge (i.e. edgeparse(edge)). Perhaps I am not retrieving the edge weight the right way? I am doing this on directed and weighted graphs with 1-10M edges. Thank you!

I think the

function atomic_cas!(x::Array{T}, i::Int, cmp::T, new::T)
    ptr = pointer(x) + i*sizof(T)
    llvmcall($"""
                         %rs = cmpxchg $lt* %0, $lt %1, $lt %2 acq_rel acquire
                         %rv = extractvalue { $lt, i1 } %rs, 0
                         ret $lt %rv
                         """, $typ, Tuple{Ptr{$typ},$typ,$typ},
                         ptr, cmp, new)
end

stuff would be a really great contribution to base julia.

While working on #4, I found that returning an Array{Int64} which is indexed by 1 might confuse users used to the zero based indexing in Stinger.

Maybe we can wrap these returned arrays using the shiny new custom abstract array types with non-1 indexing feature in 0.5. This will let users use zero based indexing on these arrays too!

Here is an octave implementation that should be easy to port.
https://gitorious.org/graph500/graph500?p=graph500:graph500.git;a=blob;f=octave/kronecker_generator.m;h=064b6d4f42194cc95ec4ab375dcbee7c3243b233;hb=01a32a9c16994c3cf30bbf4caabf9be128379416

When StingerWrapper loads a STINGER graph, it calls insert_edge! in a loop. This can be very slow, especially for high-degree vertices. Constructing the graph all at once can be done more quickly using stinger_set_initial_edges(). An example implementation of generating the array parameters for this function from an edge list is here: https://github.com/DynoGraph/stinger-dynograph/blob/1c7f8295d4b7d514a4074f0fe7c3d177421099bf/stinger_graph.cpp#L142

Add type annotations to the loops to help with stability and run with ppn:8 on pace.

It appears that the biggest performance hit we take in julia is using the gather_successors functiohn https://github.com/stingergraph/stinger/blob/dev/lib/stinger_core/src/stinger.c#L1832

If we could do the iteration over the edge blocks on the julia side, we could avoid a huge overhead.
This is the key C macro that this code uses: https://github.com/stingergraph/stinger/blob/dev/lib/stinger_core/inc/stinger_traversal.h#L123.

If the STINGER_FORALL_EDGES_OF_VTX macros were made into julia iterators, we could avoid a lot of overhead. The most direct port is a julia macro with the following usage

@forall_edges_of_vtx begin
    n = STINGER_EDGE_DEST
    w = STINGER_EDGE_WEIGHT
    tf = STINGER_EDGE_TIME_FIRST
    tr = STINGER_EDGE_TIME_RECENT
    t = STINGER_EDGE_TYPE
    if n >= 0 
      size_t where = stinger_size_fetch_add (&kout, 1)
      if where < max_outlen
        out[where] = n
        if(weight) weight[where] = w
        if(timefirst) timefirst[where] = tf
        if(timerecent) timerecent[where] = tr
        if(type) type[where] = t
      end
    end
end

Where the variables are defined in the macro like

/* Use these to access the current edge inside the above macros */
#define STINGER_EDGE_SOURCE source__
#define STINGER_EDGE_TYPE type__
#define STINGER_EDGE_DEST ((current_edge__->neighbor)&(~STINGER_EDGE_DIRECTION_MASK))
#define STINGER_EDGE_DIRECTION ((current_edge__->neighbor)&(STINGER_EDGE_DIRECTION_MASK))
#define STINGER_EDGE_WEIGHT current_edge__->weight
#define STINGER_EDGE_TIME_FIRST current_edge__->timeFirst
#define STINGER_EDGE_TIME_RECENT current_edge__->timeRecent
#define STINGER_IS_OUT_EDGE ((current_edge__->neighbor)&(STINGER_EDGE_DIRECTION_OUT))
#define STINGER_IS_IN_EDGE ((current_edge__->neighbor)&(STINGER_EDGE_DIRECTION_IN))

#define STINGER_GENERIC_FORALL_EDGES_OF_VTX_BEGIN(STINGER_,VTX_,EDGE_FILTER_,EB_FILTER_,PARALLEL_)\
  do {                                                                                                    \
    MAP_STING(STINGER_);                                                                                  \
    struct stinger_eb * ebpool_priv = ebpool->ebpool;                                                     \
    struct stinger_eb *  current_eb__ = ebpool_priv + stinger_vertex_edges_get(vertices, VTX_);           \
    while(current_eb__ != ebpool_priv) {                                                                  \
      int64_t source__ = current_eb__->vertexID;                                                          \
      int64_t type__ = current_eb__->etype;                                                               \
      EB_FILTER_ {                                                                                        \
        PARALLEL_                                                                                         \
        for(uint64_t i__ = 0; i__ < stinger_eb_high(current_eb__); i__++) {                               \
          if(!stinger_eb_is_blank(current_eb__, i__)) {                                                   \
            struct stinger_edge * current_edge__ = current_eb__->edges + i__;                             \
            EDGE_FILTER_ {

#define STINGER_GENERIC_FORALL_EDGES_OF_VTX_END()         \
            } /* end EDGE_FILTER_ */                      \
          } /* end if eb blank */                         \
        } /* end for edges in eb */                       \
      } /* end EB_FILTER_ */                              \
      current_eb__ = ebpool_priv + (current_eb__->next);  \
    } /* end while not last edge */                       \
  } while (0)

This could also get turned into a function that satisfied the do notation interface.

function forall_neighbors(func::Function, s::Stinger, v::Int)
   for u in edgeblocks(s, v)
       f(s, v, u)
   end
end

so that you would use it like

   forall_neighbors(s, v) do s, v, u
       #function body
   end

I guess this requires edgeblocks as an iterator http://docs.julialang.org/en/release-0.5/manual/interfaces/.

I think either way will reduce the overhead and get nearly equal performance.

Is there a fast function for checking if an edge exist, given the src and dest? I suppose I can just use edgeweight to see if it returns 0, but perhaps there is a faster way? Thank you!

Using stinger_new_full to optimize memory of stinger.

Can you transfer this to StingerGraph organization? David Ediger can grant any access you need.

• Bench
• Tests

As described in https://discourse.julialang.org/t/ann-plans-for-removing-packages-that-do-not-yet-support-1-0-from-the-general-registry/ we are planning on removing packages that do not support 1.0 from the General registry. This package has been detected to not support 1.0 and is thus slated to be removed. The removal of packages from the registry will happen approximately a month after this issue is open.

To transition to the new Pkg system using Project.toml, see https://github.com/JuliaRegistries/Registrator.jl#transitioning-from-require-to-projecttoml.
To then tag a new version of the package, see https://github.com/JuliaRegistries/Registrator.jl#via-the-github-app.

If you believe this package has erroneously been detected as not supporting 1.0 or have any other questions, don't hesitate to discuss it here or in the thread linked at the top of this post.