hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From li...@apache.org
Subject svn commit: r1459470 - /hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
Date Thu, 21 Mar 2013 18:53:55 GMT
Author: liyin
Date: Thu Mar 21 18:53:54 2013
New Revision: 1459470

URL: http://svn.apache.org/r1459470
Log:
[Master]Optimize HRegionServer.updateOutboundMsgs and HRegionServer.addOutboundMsgs

Author: adela

Summary: Optimizing the two methods to execute in O(n).

Test Plan: will run unittests

Reviewers: aaiyer, liyintang, kannan

Reviewed By: aaiyer

CC: hbase-eng@

Differential Revision: https://phabricator.fb.com/D715356

Task ID: 2124466

Modified:
    hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java

Modified: hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
URL: http://svn.apache.org/viewvc/hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java?rev=1459470&r1=1459469&r2=1459470&view=diff
==============================================================================
--- hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
(original)
+++ hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
Thu Mar 21 18:53:54 2013
@@ -910,39 +910,37 @@ public class HRegionServer implements HR
     LOG.info(Thread.currentThread().getName() + " exiting");
   }
 
-  /*
+  /**
    * Add to the passed <code>msgs</code> messages to pass to the master.
+   *
    * @param msgs Current outboundMsgs array; we'll add messages to this List.
    */
-  // Amit: Warning n^2 loop. Can bring it down to O(n) using a hash map.
-  private void addOutboundMsgs(final List<HMsg> msgs) {
+  private void addOutboundMsgs(List<HMsg> msgs) {
     if (msgs.isEmpty()) {
       this.outboundMsgs.drainTo(msgs);
       return;
     }
-    OUTER: for (HMsg m: this.outboundMsgs) {
-      for (HMsg mm: msgs) {
-        // Be careful don't add duplicates.
-        if (mm.equals(m)) {
-          continue OUTER;
-        }
+    Set<HMsg> msgsSet = new HashSet<HMsg>(msgs);
+    for (HMsg m: this.outboundMsgs) {
+      if (!msgsSet.contains(m)) {
+        msgs.add(m);
+        msgsSet.add(m);
       }
-      msgs.add(m);
     }
   }
 
-  /*
+  /**
    * Remove from this.outboundMsgs those messsages we sent the master.
+   *
    * @param msgs Messages we sent the master.
    */
   private void updateOutboundMsgs(final List<HMsg> msgs) {
     if (msgs.isEmpty()) return;
-    for (HMsg m: this.outboundMsgs) {
-      for (HMsg mm: msgs) {
-        if (mm.equals(m)) {
-          this.outboundMsgs.remove(m);
-          break;
-        }
+    Set<HMsg> msgsSet = new HashSet<HMsg>(msgs);
+    for (Iterator<HMsg> iterator = this.outboundMsgs.iterator(); iterator.hasNext();)
{
+      HMsg m = (HMsg) iterator.next();
+      if (msgsSet.contains(m)){
+        iterator.remove();
       }
     }
   }



Mime
View raw message