821151 - Add splay tree utility class

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

Bug 814966 needs some sort of balanced search tree for quickly deciding whether a given interval can be allocated to a physical register without colliding with existing allocations.  Splay trees are nice for this because they are very simple and take amortized logarithmic time for all common operations.  Similar to bug 817769, it would be nice to make this a generic class.

Comment 1

[Luke Wagner [:luke]]

Comment on attachment 691660 [details] [diff] [review]
patch

Review of attachment 691660 [details] [diff] [review]:
-----------------------------------------------------------------

Nice

::: js/src/ds/SplayTree.h
@@ +14,5 @@
> +
> +/*
> + * Class which represents a splay tree with nodes allocated from a LifoAlloc.
> + * Splay trees are balanced binary search trees for which search, insert and
> + * remove are all amortized O(log n).

s/amortized/average/

@@ +17,5 @@
> + * Splay trees are balanced binary search trees for which search, insert and
> + * remove are all amortized O(log n).
> + *
> + * T indicates the type of tree elements, C must have a static
> + * compare(const T&, const T&) method ordering the elements.

This container doesn't call T's destructor so it should only be used for PODs.  Could you mention this in the comment and then static assert IsPodType<T> in the class.  Note: JS_STATIC_ASSERT doesn't work in template class bodies or assert at all in member functions, so you'll want to:
  typedef typename tl::StaticAssert<tl::IsPodType<T>::result>::result isPodAssert;
or something.

@@ +139,5 @@
> +
> +    Node *lookup(const T &v)
> +    {
> +        JS_ASSERT(root);
> +        Node *node = root, *last = root;

I think it'd be a bit more clear to rename 'last' to 'parent' and either leave it uninitialized (since it is immediately clobbered) or, if you'd like, assign it to NULL since the parent of the root is NULL.

@@ +173,5 @@
> +
> +    void splay(Node *node)
> +    {
> +        // Rotate the element until it is at the root of the tree. Performing
> +        // the rotations in this fashion preserves the amortized balancing of

s/amortized/average/ or "expected" or something probabilistic sounding.

@@ +205,5 @@
> +        Node *parent = node->parent;
> +        if (parent->left == node) {
> +            //     x          y
> +            //   y  c  ==>  a  x
> +            //  a b           b c

pretty

@@ +223,5 @@
> +        }
> +        node->parent = parent->parent;
> +        parent->parent = node;
> +        if (node->parent) {
> +            Node *grandparent = node->parent;

if (Node *grandparent = node->parent) {

Comment 2

[Luke Wagner [:luke]]

Oops, Bill pointed out that splay trees are indeed amortized O(log(n)).  While the height of the tree can be O(n), making a worst-case *particular* access O(n), a sequence of m operations is O(m * log(n)).  Splay trees are even cooler than I thought!

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 691660 [details] [diff] [review]
patch

Review of attachment 691660 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ds/SplayTree.h
@@ +17,5 @@
> + * Splay trees are balanced binary search trees for which search, insert and
> + * remove are all amortized O(log n).
> + *
> + * T indicates the type of tree elements, C must have a static
> + * compare(const T&, const T&) method ordering the elements.

You could use the normal static-assert macro inside a method if you make sure the method's called by something every SplayTree user will use.  Putting a call to staticAsserts(), say, in the constructor would do the trick just fine.

Comment 4

[Brian Hackett [Laid off!]]

I added destructor invokes when freeing nodes to avoid the IsPodType asserts.  Instantiating tl::IsPodType for the class being used in BacktrackingAllocator required hoisting it out of BacktrackingAllocator and making related code far uglier.

https://hg.mozilla.org/integration/mozilla-inbound/rev/e4da3fe4a9da

Comment 5

[Luke Wagner [:luke]]

It's still not safe for regular non-POD object usage, though, as the splay tree destructor would need to destroy whatever objects remained.

Comment 6

[Brian Hackett [Laid off!]]

Attachment: consistent destructor behavior

Fair enough, this patch gives consistent destructor behavior (i.e. it is not called) and adds a comment describing the situation at the top of the class.  This interface is the same as for lifoAlloc->new_<...> objects, which are not required to be POD types.  Until this class has more users I don't think it's worth overengineering.

Comment 7

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/aafa9e2de532

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/e4da3fe4a9da
https://hg.mozilla.org/mozilla-central/rev/aafa9e2de532