Opened 7 years ago

Closed 7 years ago

#2811 closed enhancement (fixed)

Make some DomainTree code updates

Reported by: muks Owned by: muks
Priority: medium Milestone: Sprint-20130806
Component: data source Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket:
Estimated Difficulty: 3 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description (last modified by muks)

This is a ticket to track some DomainTree code updates that I've made in a private branch.

  • The rebalance-after-insert code is reorganized to make it more straightforward to understand, and it's better commented.
  • There are tests (with random and sorted data) that verify that the tree is balanced, and doesn't go over the red-black theoretical limit. It constructs a random large million+ name zone and checks that the distance from every node to its subtree root is within limit. This is a check that was not implemented and we should have this as performance correctness proof, as the DomainTree? is so central to our memory datasrc performance.
  • Don't rebalance subtree roots.

Though the deletion ticket #2750 is independent, the balance testcase will be useful for the deletion work.

Subtickets

Change History (19)

comment:1 Changed 7 years ago by muks

  • Description modified (diff)

comment:2 Changed 7 years ago by muks

  • Owner set to UnAssigned
  • Status changed from new to reviewing

This branch is now ready for review.

comment:3 Changed 7 years ago by muks

  • Description modified (diff)

comment:4 Changed 7 years ago by muks

  • Description modified (diff)

comment:5 Changed 7 years ago by muks

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:6 Changed 7 years ago by muks

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:7 Changed 7 years ago by muks

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:8 Changed 7 years ago by muks

  • Milestone set to Next-Sprint-Proposed

comment:9 Changed 7 years ago by muks

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:10 Changed 7 years ago by muks

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:11 Changed 7 years ago by muks

  • Milestone changed from Next-Sprint-Proposed to Sprint-20130806

Moving to current sprint as we are running out of tickets.

comment:12 Changed 7 years ago by vorner

  • Owner changed from UnAssigned to vorner

comment:13 follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

Just few questions. What is the motivation for this change?

     } else if (order < 0) {
         node->setSubTreeRoot(false);
         parent->left_ = node;
+        insertRebalance(current_root, node);
     } else {
         node->setSubTreeRoot(false);
         parent->right_ = node;
+        insertRebalance(current_root, node);
     }
-    insertRebalance(current_root, node);
+
     if (new_node != NULL) {

Looking at the loop, shouldn't we stop it after the first rotation?

In the sorted test, I think we need 7 digits, 6 is not enough.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi Michal

Replying to vorner:

Hello

Just few questions. What is the motivation for this change?

     } else if (order < 0) {
         node->setSubTreeRoot(false);
         parent->left_ = node;
+        insertRebalance(current_root, node);
     } else {
         node->setSubTreeRoot(false);
         parent->right_ = node;
+        insertRebalance(current_root, node);
     }
-    insertRebalance(current_root, node);
+
     if (new_node != NULL) {

This is a minor optimization. In the specific case that the new node is the new root of a sub-tree, calling insertRebalance() on it is redundant as its main loop will exit without running and it will recolor it to BLACK unnecessarily.

Looking at the loop, shouldn't we stop it after the first rotation?

Which loop are you referring to?

In the sorted test, I think we need 7 digits, 6 is not enough.

This was done.

I've also added a minor wrapper around the color testing code. It may be a bit too much, but the code is simpler to read and the compiler should inline anyway.

The new branch (based on current master) is trac2811_2. The commits on this branch are identical up to the last review.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Replying to muks:

This is a minor optimization. In the specific case that the new node is the new root of a sub-tree, calling insertRebalance() on it is redundant as its main loop will exit without running and it will recolor it to BLACK unnecessarily.

Ah, now I see. The first is else if, not only if. Then it makes sense.

Looking at the loop, shouldn't we stop it after the first rotation?

Which loop are you referring to?

The big loop in the insertRebalance, the one starting with:

    // The node enters this method colored RED. We assume in our
    // red-black implementation that NULL values in left and right
    // children are BLACK.
    //
    // Case 1. If node is at the subtree root, we don't need to change
    // its position in the tree. We re-color it BLACK further below
    // (right before we return).
    while (node != (*subtree_root).get()) {
        // Case 2. If the node is not subtree root, but its parent is
        // colored BLACK, then we're done. This is because the new node
        // introduces a RED node in the path through it (from its
        // subtree root to its children colored BLACK) but doesn't
        // change the red-black properties.

In the case 4, it rotates the tree. I had the impression that once we rotate, the whole update rebalancing ends.

comment:16 in reply to: ↑ 15 Changed 7 years ago by muks

  • Owner changed from muks to vorner

Replying to vorner:

The big loop in the insertRebalance, the one starting with:

    // The node enters this method colored RED. We assume in our
    // red-black implementation that NULL values in left and right
    // children are BLACK.
    //
    // Case 1. If node is at the subtree root, we don't need to change
    // its position in the tree. We re-color it BLACK further below
    // (right before we return).
    while (node != (*subtree_root).get()) {
        // Case 2. If the node is not subtree root, but its parent is
        // colored BLACK, then we're done. This is because the new node
        // introduces a RED node in the path through it (from its
        // subtree root to its children colored BLACK) but doesn't
        // change the red-black properties.

In the case 4, it rotates the tree. I had the impression that once we rotate, the whole update rebalancing ends.

Yes. In this case, we go back to the start of the loop, case 1 is true and then case 2 breaks out of the while loop.

comment:17 follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

I believe it would be more readable to explicitly break out of the loop there than rely on the side-effects and influencing the next iteration. Or at least putting the explanation into a comment there. But I'll leave it up to you.

I think it is ready for merge (with or without the change).

comment:18 in reply to: ↑ 17 Changed 7 years ago by muks

Replying to vorner:

I believe it would be more readable to explicitly break out of the loop there than rely on the side-effects and influencing the next iteration. Or at least putting the explanation into a comment there. But I'll leave it up to you.

I think it is ready for merge (with or without the change).

I've added an explicit break there along with a comment.

comment:19 Changed 7 years ago by muks

  • Resolution set to fixed
  • Status changed from reviewing to closed

Merged to master branch in commit 7c0bad1643af13dedf9356e9fb3a51264b7481de:

* 07f6240 [2811] Explicitly break out of loop after rebalancing tree
* ccdb49a [2811] Cleanup color testing code
* f36f677 [2811] Use 8 digits instead of 6 in names
* c386d06 [2811] Don't call rebalance for subtree roots
* 56f4144 [2811] Use ints for consistency
* f6fd9cc [2811] Move common code to a separate function
* e323b23 [2811] Add test with names inserted in sorted order
* 063f70a [2811] Update comment
* 363e37a [2811] Add a DomainTreeTest.checkDistance testcase
* ee0e068 [2811] Reorganize the DomainTree::insertRebalance() implementation

Resolving as fixed. Thank you for the reviews Michal.

A ChangeLog entry was also added, as it updates the code for the data structure of zone data and it's better users have a way to find this if there are any problems.

Note: See TracTickets for help on using tickets.