Memory Usage

[sebogh]

another stuff that over allocate memory (i'm run benchmark for 100000 count)

can we lower the memory usage?

ROUTINE ======================== github.com/heimdalr/dag.(*DAG).AddEdge in /home/vtolstov/.cache/go-path/pkg/mod/github.com/heimdalr/dag
@v0.9.11/dag.go
  252.53MB   596.07MB (flat, cum) 23.62% of Total
         .          .    179:   if d.isEdge(src, dst) {
         .          .    180:           return EdgeDuplicateError{src, dst}
         .          .    181:   }
         .          .    182:
         .          .    183:   // get descendents and ancestors as they are now
         .   149.02MB    184:   descendants, _ := d.GetDescendants(dst)
         .   194.52MB    185:   ancestors, _ := d.GetAncestors(src)
         .          .    186:
         .          .    187:   // check for circles, iff desired
         .          .    188:   if src == dst || descendants[src] {
         .          .    189:           return EdgeLoopError{src, dst}
         .          .    190:   }
         .          .    191:
         .          .    192:   d.muDAG.Lock()
         .          .    193:
         .          .    194:   // prepare d.outbound[src], iff needed
         .          .    195:   if _, exists := d.outboundEdge[src]; !exists {
   52.01MB    52.01MB    196:           d.outboundEdge[src] = make(map[Vertex]bool)
         .          .    197:   }
         .          .    198:
         .          .    199:   // dst is a child of src
   97.51MB    97.51MB    200:   d.outboundEdge[src][dst] = true
         .          .    201:
         .          .    202:   // prepare d.inboundEdge[dst], iff needed
         .          .    203:   if _, exists := d.inboundEdge[dst]; !exists {
   40.50MB    40.50MB    204:           d.inboundEdge[dst] = make(map[Vertex]bool)
         .          .    205:   }
         .          .    206:
         .          .    207:   // src is a parent of dst
   62.51MB    62.51MB    208:   d.inboundEdge[dst][src] = true
         .          .    209:
         .          .    210:   // for dst and all its descendants delete cached ancestors
         .          .    211:   for descendant := range descendants {
         .          .    212:           if _, exists := d.ancestorsCache[descendant]; exists {
         .          .    213:                   delete(d.ancestorsCache, descendant)

[sebogh]

Descendants and ancestors get cached which (depending on the graph) may eat up a lot of memory (in fact, if fully populated, it is the transitive closure). As caches are populated, querying is really fast - a property I need.

Currently I don't see a way to lower the memory footprint. But I'm happy to review Pull Requests. ;)

[sebogh]

Can you provide your test and how you executed it?

[vtolstov]

I'm use dag as service. So i have some service that receives payload and dag name. After that it loads dag from database and run execution.
I think that main drawback that for each requests i'm load dag. So maybe i need some lru caching and check for update from db.

[vtolstov]

after using caching, memory usage is small. so this is not the issue now

[vtolstov]

mostly memory usage can be lower without maps and use slices or some other optimized stuff.