Patricia VS Quicktrie

test.go

package main

import (
	"crypto/rand"
	"log"
	"net/http"
	_ "net/http/pprof"

	"github.com/apokalyptik/quicktrie"
	"gopkg.in/tchap/go-patricia.v1/patricia"
)

func main() {
	go func() { log.Println(http.ListenAndServe("localhost:6060", nil)) }()
	pt := patricia.NewTrie()
	qkv := trie.NewKVTrie()
	qbw := trie.NewBWTrie()
	for i := 0; i < 1000000; i++ {
		b := make([]byte, 25)
		rand.Read(b)
		pt.Insert(b, struct{}{})
		qkv.Add(b, struct{}{})
		qbw.Add(b)
	}
	log.Printf("ready")
	var wait = make(chan struct{})
	<-wait
}

go tool pprof http://localhost:6060/debug/pprof/heap

Read http://localhost:6060/debug/pprof/symbol
Fetching /pprof/heap profile from localhost:6060 to
  /var/folders/wy/9vyw7q9j0fv1m14v3892qczm0000gn/T/kAZwxJ6duS
Wrote profile to /var/folders/wy/9vyw7q9j0fv1m14v3892qczm0000gn/T/kAZwxJ6duS
Adjusting heap profiles for 1-in-524288 sampling rate
Welcome to pprof!  For help, type 'help'.
(pprof) top25 --cum
Total: 623.5 MB
     0.0   0.0%   0.0%    623.5 100.0% runtime.gosched0
     0.0   0.0%   0.0%    623.5 100.0% runtime.main
    21.5   3.4%   3.4%    623.0  99.9% main.main
     0.0   0.0%   3.4%    457.0  73.3% gopkg.in/tchap/go-patricia.v1/patricia.(*Trie).Insert
     7.5   1.2%   4.7%    457.0  73.3% gopkg.in/tchap/go-patricia.v1/patricia.(*Trie).put
   339.0  54.4%  59.0%    339.0  54.4% gopkg.in/tchap/go-patricia.v1/patricia.NewTrie
     0.0   0.0%  59.0%    144.5  23.2% github.com/apokalyptik/quicktrie.(*Trie).Add
    79.5  12.8%  71.8%     79.5  12.8% github.com/apokalyptik/quicktrie.(*kvTrie).add
     0.0   0.0%  71.8%     66.0  10.6% gopkg.in/tchap/go-patricia.v1/patricia.(*sparseChildList).add
    66.0  10.6%  82.4%     66.0  10.6% gopkg.in/tchap/go-patricia.v1/patricia.newDenseChildList
    65.0  10.4%  92.8%     65.0  10.4% github.com/apokalyptik/quicktrie.(*bwTrie).add
    44.5   7.1%  99.9%     44.5   7.1% gopkg.in/tchap/go-patricia.v1/patricia.(*denseChildList).add
     0.0   0.0%  99.9%      0.5   0.1% newm
     0.5   0.1% 100.0%      0.5   0.1% runtime.allocm
(pprof)