0

I have the following code, which uses tones of memory, which is way higher than expected.
I used to pprof tool and it shows that the function NewEdge is allocating more than 94% of all the memory allocated by the program.

My question is, what is wrong with this code, that is uses so much memory:

type Vertex struct {
    Id                        string              `json:"id"`         // must be unique
    Properties                map[string]string   `json:"properties"` // to be implemented soon
    verticesThisIsConnectedTo map[string][]string `json:"-"`          //id for the edges *Edge // keys are Vertex ids, each pair of vertices can be connected to each other with multiple edges
    verticesConnectedToThis   map[string][]string `json:"_"`          //id for the edges *Edge // keys are Vertex ids,
}
type Edge struct {
    id         string            `json:"-"` // for internal use, unique
    Label      string            `json:"label"`
    SourceId   string            `json:"source-id"`
    TargetId   string            `json:"terget-id"`
    Type       string            `json:"type"`
    Properties map[string]string `json:"properties"` // to be implemented soon
}
func (v *Vertex) isPartof(g *Graph) bool {
    _, b := g.Vertices[v.Id]
    return b
}
func (g *Graph) NewEdge(source, target *Vertex, label, edgeType string) (Edge, error) {
    if source.Id == target.Id {
        return Edge{}, ERROR_NO_EDGE_TO_SELF_ALLOWED
    }
    if !source.isPartof(g) || !target.isPartof(g) {
        return Edge{}, errors.New("InvalidEdge, source or target not in this graph")
    }

    e := Edge{id: <-nextId, Label: label, SourceId: source.Id, TargetId: target.Id, Type: edgeType}
    g.Edges[e.id] = &e

    source.verticesThisIsConnectedTo[target.Id] = append(source.verticesThisIsConnectedTo[target.Id], e.id)
    target.verticesConnectedToThis[source.Id] = append(target.verticesConnectedToThis[source.Id], e.id)
    return e, nil
}

The allocation happens by a call like this: fakeGraph(Aragog, 2000, 1) where :

func fakeGraph(g Graph, nodesCount, followratio int) error {
    var err error
    // create the vertices
    for i := 0; i < nodesCount; i++ {
            v := NewVertex("") //FH.RandStr(10))
            g.AddVertex(v)
    }
    // create some "follow edges"
    followcount := followratio * nodesCount / 100
    vkeys := []string{}
    for pk := range g.Vertices {
            vkeys = append(vkeys, pk)
    }
    for ki := range g.Vertices {
            pidx := rand.Perm(nodesCount)
            followcounter := followcount
            for j := 0; j < followcounter; j++ {
                    _, err := g.NewEdge(g.Vertices[ki], g.Vertices[vkeys[pidx[j]]], <-nextId, EDGE_TYPE_FOLLOW)
                    if err != nil {
                            followcounter++ // to compensate for references to self
                    }
            }
    }
    return err
    }

Question / mystery :

I can create thousands of Vertexs and the memory usage is very reasonable. But calls to NewEdge are very memory intensive. I first noticed that the code was using tones of memory. I ran pprof with -memprofile and then used go tool pprof and got this:

(pprof) top10
Total: 9.9 MB
     8.9  89.9%  89.9%      8.9  89.9% main.(*Graph).NewEdge
     0.5   5.0%  95.0%      0.5   5.0% allocg
     0.5   5.0% 100.0%      0.5   5.0% fmt.Sprintf
     0.0   0.0% 100.0%      0.5   5.0% _rt0_go
     0.0   0.0% 100.0%      8.9  89.9% main.fakeGraph
     0.0   0.0% 100.0%      0.5   5.0% main.func·003
     0.0   0.0% 100.0%      8.9  89.9% main.main
     0.0   0.0% 100.0%      0.5   5.0% mcommoninit
(pprof)

Any help is very much appreciated.

7
  • You didn't show how you are allocating vertices. Perhaps the overhead is actually the assignment of the edge id to the source and target id maps? how many objects are you creating for these 10MB to be allocated? Jun 20, 2014 at 10:25
  • @not_a_Golfer thanks, I edited the question, and now it includes how I create them.
    – Ali
    Jun 20, 2014 at 11:23
  • I don't particularly see a problem. It depends how many Edge's you are creating and how large the various Ids are.
    – mzimmerman
    Jun 20, 2014 at 11:40
  • Your slices in your Vertex edge maps can grow pretty quickly. You might want to check their capacities. If this is indeed the case, you could consider another allocation strategy other than the default append.
    – seong
    Jun 20, 2014 at 12:34
  • I don't suppose you've tried this under Go 1.3? The GC has been improved for values on the stack. I ask because your NewEdge does allocate.. then is discarded in the call. I have seen screenshots of memory usage being halved in 1.3 - so perhaps give it a go? Can't hurt? Jun 20, 2014 at 13:28

1 Answer 1

1

@ali I think there is no mystery in this memory profiling. First of all, If you check size of your structs you will see what Edge struct is 2 times bigger than Vertex struct. (you can check size of structs by unsafe.Sizeof()) So, if you will call fakeGraph(Aragog, 2000, 1) Go will allocate:

  • 2000 Vertex structs
  • at least 2000 * 20 = 40 000 Edge structs
    As you can see NewEdge() will allocate at least 40 times more memory then fakeGraph()

Also, every time you will try to create new edge, new Edge struct will allocated - even if NewEdge() return error.

Another factor is - you return struct itself, not pointer to struct. In Go struct is value types, so entire struct will be copied once you will return from NewEdge() and it also can cause new allocation. Yes, I see what you never use returned struct, but I'm not sure if Go compiler will check caller's context and skip Edge copying

1
  • Thanks @varyous I don't know if it explains all the problem but the fact that I ignored the basic math (the number of edges), was a the main reason I freaked out. I still need to dig a bit deeper, but that explains a lot of the problem, and for the record, I figured it out a few hours ago, when I tried to explain the problem to a friend, and started counting the objects. But still, thanks for taking the time and going through the code. I appreciate it.
    – Ali
    Jun 20, 2014 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.