I believe there is a way to get rid of explicit leaves without loosing the simplicity of the balancing operations. #104
Comments
|
This would save a lot of space since a tree with |
make-github-pseudonymous-again
added a commit
that referenced
this issue
Mar 31, 2021
Everything went as planned except that we needed to mock the child of
the deleted node when it is an implicit leaf.
The losses:
This change puts additional load on:
- delete_case{3,4,5},
- insert_case3, and
- rotate_{left,right}
This load comes from nullchecks before color checks and parent
assignments.
These checks should only be needed at the lowest levels of the fixed
path because of the red-black tree properties.
They could perhaps be circumvented entirely by adding additional mocked
leaves to the sibling of the child of the deleted node. This should
somehow be amortized by the facts that there is at most one deletion per
node created and that each node now costs less to create (because of the
allowed null pointers, see gains).
If property access is always preceded by a nullcheck and if an explicit
preceding nullcheck is somehow optimized away by the compiler, then perhaps
nothing needs to be done. We have to profile this.
The gains:
- all Leaf children are replaced by null (>1/6 space save)
- all isLeaf() calls are replaced by nullchecks: really faster? Should
be since I assume each method call must be preceded by a null check
internally?
Also we should rewrite delete_one_child to completely avoid this mocking
in case the deleted node is red. I left a TODO note about this.
This is progress on #104.
make-github-pseudonymous-again
added a commit
that referenced
this issue
Mar 31, 2021
Everything went as planned except that we needed to mock the child of
the deleted node when it is an implicit leaf.
The losses:
This change puts additional load on:
- delete_case{3,4,5},
- insert_case3, and
- rotate_{left,right}
This load comes from nullchecks before color checks and parent
assignments.
These checks should only be needed at the lowest levels of the fixed
path because of the red-black tree properties.
They could perhaps be circumvented entirely by adding additional mocked
leaves to the sibling of the child of the deleted node. This should
somehow be amortized by the facts that there is at most one deletion per
node created and that each node now costs less to create (because of the
allowed null pointers, see gains).
If property access is always preceded by a nullcheck and if an explicit
preceding nullcheck is somehow optimized away by the compiler, then perhaps
nothing needs to be done. We have to profile this.
The gains:
- all Leaf children are replaced by null (>1/6 space save)
- all isLeaf() calls are replaced by nullchecks: really faster? Should
be since I assume each method call must be preceded by a null check
internally?
Also we should rewrite delete_one_child to completely avoid this mocking
in case the deleted node is red. I left a TODO note about this.
This is progress on #104.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This involves only creating the leaves whose parent pointer is accessed and hard-coding the black color of implicit
nullleaves in the code somehow. This should be possible because the former is only required at the beginning of a deletion balancing operation, and the latter can be done by breaking symmetry, which is already done to some extent.The text was updated successfully, but these errors were encountered: