You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tez.apache.org by go...@apache.org on 2014/08/29 20:26:52 UTC
git commit: TEZ-1488. Rename HashComparator to ProxyComparator and
implement in TezBytesComparator. (gopalv)
Repository: tez
Updated Branches:
refs/heads/master 2576bac55 -> bfba46724
TEZ-1488. Rename HashComparator to ProxyComparator and implement in TezBytesComparator. (gopalv)
Project: http://git-wip-us.apache.org/repos/asf/tez/repo
Commit: http://git-wip-us.apache.org/repos/asf/tez/commit/bfba4672
Tree: http://git-wip-us.apache.org/repos/asf/tez/tree/bfba4672
Diff: http://git-wip-us.apache.org/repos/asf/tez/diff/bfba4672
Branch: refs/heads/master
Commit: bfba46724d043dce22e0b313782b0c9e30bc2094
Parents: 2576bac
Author: Gopal V <go...@apache.org>
Authored: Fri Aug 29 11:26:36 2014 -0700
Committer: Gopal V <go...@apache.org>
Committed: Fri Aug 29 11:26:36 2014 -0700
----------------------------------------------------------------------
.../common/comparator/HashComparator.java | 29 -------
.../common/comparator/ProxyComparator.java | 46 +++++++++++
.../common/comparator/TezBytesComparator.java | 23 +++++-
.../common/sort/impl/PipelinedSorter.java | 10 +--
.../common/comparator/TestProxyComparator.java | 81 ++++++++++++++++++++
5 files changed, 154 insertions(+), 35 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tez/blob/bfba4672/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/HashComparator.java
----------------------------------------------------------------------
diff --git a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/HashComparator.java b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/HashComparator.java
deleted file mode 100644
index 56752f9..0000000
--- a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/HashComparator.java
+++ /dev/null
@@ -1,29 +0,0 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.tez.runtime.library.common.comparator;
-
-import org.apache.hadoop.classification.InterfaceAudience.Private;
-import org.apache.hadoop.classification.InterfaceStability.Unstable;
-
-@Unstable
-@Private
-public interface HashComparator<KEY> {
-
- int getHashCode(KEY key);
-
-}
http://git-wip-us.apache.org/repos/asf/tez/blob/bfba4672/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/ProxyComparator.java
----------------------------------------------------------------------
diff --git a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/ProxyComparator.java b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/ProxyComparator.java
new file mode 100644
index 0000000..5297f7c
--- /dev/null
+++ b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/ProxyComparator.java
@@ -0,0 +1,46 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.tez.runtime.library.common.comparator;
+
+import org.apache.hadoop.classification.InterfaceAudience.Private;
+import org.apache.hadoop.classification.InterfaceStability.Unstable;
+import org.apache.hadoop.io.RawComparator;
+
+@Unstable
+@Private
+public interface ProxyComparator<KEY> extends RawComparator {
+ /**
+ * This comparator interface provides a fast-path for comparisons between keys.
+ *
+ * The implicit assumption is that integer returned from this function serves
+ * as a transitive comparison proxy for the comparator that this implements.
+ *
+ * But this does not serve as a measure of equality.
+ *
+ * getProxy(k1) < getProxy(k2) implies k1 < k2 (transitive between different keys for sorting requirements)
+ *
+ * getProxy(k1) == getProxy(k2) does not imply ordering, but requires actual key comparisons.
+ *
+ * This serves as a way to short-circuit the RawComparator speeds.
+ *
+ * @param key
+ * @return proxy
+ */
+ int getProxy(KEY key);
+
+}
http://git-wip-us.apache.org/repos/asf/tez/blob/bfba4672/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/TezBytesComparator.java
----------------------------------------------------------------------
diff --git a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/TezBytesComparator.java b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/TezBytesComparator.java
index 7e921de..09b2b03 100644
--- a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/TezBytesComparator.java
+++ b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/comparator/TezBytesComparator.java
@@ -24,7 +24,8 @@ import org.apache.hadoop.io.WritableComparator;
@Public
@Unstable
-public class TezBytesComparator extends WritableComparator {
+public class TezBytesComparator extends WritableComparator implements
+ ProxyComparator<BytesWritable> {
public TezBytesComparator() {
super(BytesWritable.class);
@@ -39,4 +40,24 @@ public class TezBytesComparator extends WritableComparator {
return compareBytes(b1, s1, l1, b2, s2, l2);
}
+ @Override
+ public int getProxy(BytesWritable key) {
+ int prefix = 0;
+ final int len = key.getLength();
+ final byte[] content = key.getBytes();
+ int b1 = 0, b2 = 0, b3 = 0;
+ switch (len) {
+ default:
+ case 3:
+ b3 = content[2] & 0xff;
+ case 2:
+ b2 = content[1] & 0xff;
+ case 1:
+ b1 = content[0] & 0xff;
+ case 0:
+ }
+ prefix = (b1 << 16) | (b2 << 8) | (b3);
+ return prefix;
+ }
+
}
http://git-wip-us.apache.org/repos/asf/tez/blob/bfba4672/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/sort/impl/PipelinedSorter.java
----------------------------------------------------------------------
diff --git a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/sort/impl/PipelinedSorter.java b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/sort/impl/PipelinedSorter.java
index 8085f98..0a14946 100644
--- a/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/sort/impl/PipelinedSorter.java
+++ b/tez-runtime-library/src/main/java/org/apache/tez/runtime/library/common/sort/impl/PipelinedSorter.java
@@ -39,7 +39,7 @@ import org.apache.hadoop.fs.FSDataOutputStream;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.DataInputBuffer;
import org.apache.tez.common.TezUtilsInternal;
-import org.apache.tez.runtime.library.common.comparator.HashComparator;
+import org.apache.tez.runtime.library.common.comparator.ProxyComparator;
import org.apache.hadoop.io.RawComparator;
import org.apache.hadoop.util.IndexedSortable;
import org.apache.hadoop.util.IndexedSorter;
@@ -78,7 +78,7 @@ public class PipelinedSorter extends ExternalSorter {
int numSpills = 0;
private final int minSpillsForCombine;
- private final HashComparator hasher;
+ private final ProxyComparator hasher;
// SortSpans
private SortSpan span;
private ByteBuffer largeBuffer;
@@ -135,8 +135,8 @@ public class PipelinedSorter extends ExternalSorter {
.build());
// k/v serialization
- if(comparator instanceof HashComparator) {
- hasher = (HashComparator)comparator;
+ if(comparator instanceof ProxyComparator) {
+ hasher = (ProxyComparator)comparator;
LOG.info("Using the HashComparator");
} else {
hasher = null;
@@ -236,7 +236,7 @@ public class PipelinedSorter extends ExternalSorter {
int prefix = 0;
if(hasher != null) {
- prefix = hasher.getHashCode(key);
+ prefix = hasher.getProxy(key);
}
prefix = (partition << (32 - partitionBits)) | (prefix >>> partitionBits);
http://git-wip-us.apache.org/repos/asf/tez/blob/bfba4672/tez-runtime-library/src/test/java/org/apache/tez/runtime/library/common/comparator/TestProxyComparator.java
----------------------------------------------------------------------
diff --git a/tez-runtime-library/src/test/java/org/apache/tez/runtime/library/common/comparator/TestProxyComparator.java b/tez-runtime-library/src/test/java/org/apache/tez/runtime/library/common/comparator/TestProxyComparator.java
new file mode 100644
index 0000000..441feff
--- /dev/null
+++ b/tez-runtime-library/src/test/java/org/apache/tez/runtime/library/common/comparator/TestProxyComparator.java
@@ -0,0 +1,81 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.tez.runtime.library.common.comparator;
+
+import static org.junit.Assert.assertTrue;
+
+import java.nio.charset.Charset;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.io.BytesWritable;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+public class TestProxyComparator {
+ private static final Log LOG = LogFactory.getLog(TestProxyComparator.class);
+
+ final static String[] keys = {
+ "",
+ "A", "B",
+ "AA", "BB", "BA", "CB",
+ "AAA", "BBBB", "CCCCC",
+ /* utf-8 comparisons */
+ "\u00E6AAAA", "\u00F7", "A\u00F7", "\u00F7AAAAAAAAA",
+ "\u00F7\u00F7", "\u00F7\u00F7\u00E6\u00E6A",
+ "\u00F7\u00F7\u00E6\u00E6A"
+ };
+
+ private static final void set(BytesWritable bw, String s) {
+ byte[] b = s.getBytes(Charset.forName("utf-8"));
+ bw.set(b, 0, b.length);
+ }
+
+ @Before
+ public void setUp() throws Exception {
+ }
+
+ @After
+ public void cleanup() throws Exception {
+ }
+
+ @Test
+ public void testProxyComparator() {
+ final ProxyComparator<BytesWritable> comparator = new TezBytesComparator();
+ BytesWritable lhs = new BytesWritable();
+ BytesWritable rhs = new BytesWritable();
+ for (String l : keys) {
+ for (String r : keys) {
+ set(lhs, l);
+ set(rhs, r);
+ final int lproxy = comparator.getProxy(lhs);
+ final int rproxy = comparator.getProxy(rhs);
+ if (lproxy < rproxy) {
+ assertTrue(String.format("(%s) %d < (%s) %d", l, lproxy, r, rproxy),
+ comparator.compare(lhs, rhs) < 0);
+ }
+ if (lproxy > rproxy) {
+ assertTrue(String.format("(%s) %d > (%s) %d", l, lproxy, r, rproxy),
+ comparator.compare(lhs, rhs) > 0);
+ }
+ }
+ }
+ }
+}