High RAM usage

[awnumar]

This package is pulled in as a dependency of one of my dependencies, and it's causing unusually high RAM usage. Related issue: https://github.com/prologic/bitcask/issues/67

This looks like a memory leak to me since it's unlikely the garbage collector ran in the short time my program was running, and during that time it managed to slurp up 13 GB of memory.

[jsign]

The Node struct isn't very lean, and considering multiple Node are created for a single .Add depending on the key length, this result may be reasonable.

type Node struct {
    val       rune
    path      string
    term      bool
    depth     int
    meta      interface{}
    mask      uint64
    parent    *Node
    children  map[rune]*Node
    termCount int
}

Doing a quick analysis in the NewChild method allocs (from a bench of Add):

  788.57MB   788.57MB (flat, cum) 97.83% of Total
         .          .    154:           path:     path,
         .          .    155:           mask:     bitmask,
         .          .    156:           term:     term,
         .          .    157:           meta:     meta,
         .          .    158:           parent:   parent,
  170.01MB   170.01MB    159:           children: make(map[rune]*Node),
  333.03MB   333.03MB    160:           depth:    parent.depth + 1,
         .          .    161:   }
  285.53MB   285.53MB    162:   parent.children[node.val] = node
         .          .    163:   parent.mask |= bitmask
         .          .    164:   return node
         .          .    165:}

(Raw numbers doesn't matter, but ratios)

Maybe modeling the children as a simple slice would be more memory efficient, even if getting elements to involve iterating (mem cache might even transform it into a faster solution).