HomePhorge

(#9671) Stop tracking size and height of nodes in RbTreeMap
1dc9c72bf739Unpublished

Unpublished Commit ยท Learn More

Repository Importing: This repository is still importing.

Description

(#9671) Stop tracking size and height of nodes in RbTreeMap

Profiling revealed RbTreeMap#update_size to be one of the most expensive methods
in a Puppet run. The only function of this method is to track the size
and height of every node, which in turn is used to provide the size and
height of the tree.

Individual nodes aren't accessible, so there is no need to keep track of
their size and height. While height of the tree is theoretically
interesting, we currently don't use it anywhere, and are unlikely to in
the future.

So we simplified the size tracking to simply update the size of the tree
on insertion and deletion.

Paired-With: Josh Cooper <josh@puppetlabs.com>

Details

Provenance
Nick Lewis <nick@puppetlabs.com>Authored on
vanmeeuwenPushed on Jun 2 2015, 2:22 PM
Parents
rPUf180f9be105a: (#9617) Add a red-black tree map
Branches
Unknown
Tags
Unknown

Event Timeline

Nick Lewis <nick@puppetlabs.com> committed rPU1dc9c72bf739: (#9671) Stop tracking size and height of nodes in RbTreeMap (authored by Nick Lewis <nick@puppetlabs.com>).Nov 11 2011, 11:26 PM