Efficiently traverse binary tree represented as tuple of tuples

General Usage Performance
,
10

Interesting. I find results that are similar to Jutho’s. I have an implementation of Sedgwick’s left leaning red black trees (which is recursive). If I type the left and right node pointers I see a 4X slow down in creating a tree with 1M integer keys. The cost of querying all is about the same for the two versions. To be clear, the only change in the to versions is the type of the left and right fields of the node struct. I did not investigate further because the strategy of allocating each node separately is a loser.

# using untyped left, right

julia> ivec = rand(-30000000:30000000, 1000000);

julia> @benchmark make_tree($ivec)
BenchmarkTools.Trial: 
  memory estimate:  53.03 MiB
  allocs estimate:  991744
  --------------
  minimum time:     4.187 s (1.87% GC)
  median time:      4.333 s (2.89% GC)
  mean time:        4.333 s (2.89% GC)
  maximum time:     4.479 s (3.84% GC)
  --------------
  samples:          2
  evals/sample:     1

julia> tree = make_tree(ivec);


julia> @benchmark find_all_keys($tree, $ivec)
BenchmarkTools.Trial: 
  memory estimate:  1.26 GiB
  allocs estimate:  83484932
  --------------
  minimum time:     3.798 s (0.49% GC)
  median time:      3.804 s (0.50% GC)
  mean time:        3.804 s (0.50% GC)
  maximum time:     3.809 s (0.50% GC)
  --------------
  samples:          2
  evals/sample:     1



# using Union{LLRBTreeNode, Nothing} for the types of left, right

julia> @benchmark make_tree($ivec)
BenchmarkTools.Trial: 
  memory estimate:  330.67 MiB
  allocs estimate:  19187151
  --------------
  minimum time:     18.779 s (2.50% GC)
  median time:      18.779 s (2.50% GC)
  mean time:        18.779 s (2.50% GC)
  maximum time:     18.779 s (2.50% GC)
  --------------
  samples:          1
  evals/sample:     1

julia> tree = make_tree(ivec);

julia> @benchmark find_all_keys($tree, $ivec)
BenchmarkTools.Trial: 
  memory estimate:  1.28 GiB
  allocs estimate:  84970712
  --------------
  minimum time:     3.871 s (0.47% GC)
  median time:      3.884 s (0.46% GC)
  mean time:        3.884 s (0.46% GC)
  maximum time:     3.896 s (0.45% GC)
  --------------
  samples:          2
  evals/sample:     1