Author: jbellis
Date: Fri Aug 13 20:33:49 2010
New Revision: 985349
URL: http://svn.apache.org/viewvc?rev=985349&view=rev
Log:
optimize [Time|Lexical]UUIDType comparison further. patch by Folke Behrens;
reviewed by jbellis for CASSANDRA-1368
Modified:
cassandra/trunk/CHANGES.txt
cassandra/trunk/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
Modified: cassandra/trunk/CHANGES.txt
URL:
http://svn.apache.org/viewvc/cassandra/trunk/CHANGES.txt?rev=985349&r1=985348&r2=985349&view=diff
==============================================================================
--- cassandra/trunk/CHANGES.txt (original)
+++ cassandra/trunk/CHANGES.txt Fri Aug 13 20:33:49 2010
@@ -6,6 +6,7 @@ dev
* restore use of mmap_index_only option (CASSANDRA-1241)
* dropping a keyspace with no column families generated an error
(CASSANDRA-1378)
+ * optimize [Time|Lexical]UUIDType comparison further (CASSANDRA-1368)
0.7-beta1
Modified:
cassandra/trunk/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
URL:
http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java?rev=985349&r1=985348&r2=985349&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
(original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
Fri Aug 13 20:33:49 2010
@@ -40,26 +40,29 @@ public class TimeUUIDType extends Abstra
{
return 1;
}
-
- long t1 = getTimestamp(o1);
- long t2 = getTimestamp(o2);
- return t1 < t2 ? -1 : (t1 > t2 ? 1 : FBUtilities.compareByteArrays(o1,
o2));
+ int res = compareTimestampBytes(o1, o2);
+ if (res != 0)
+ return res;
+ return FBUtilities.compareByteArrays(o1, o2);
}
- static long getTimestamp(byte[] bytes)
+ private static int compareTimestampBytes(byte[] o1, byte[] o2)
{
- long low = 0;
- int mid = 0;
- int hi = 0;
-
- for (int i = 0; i < 4; i++)
- low = (low << 8) | (bytes[i] & 0xff);
- for (int i = 4; i < 6; i++)
- mid = (mid << 8) | (bytes[i] & 0xff);
- for (int i = 6; i < 8; i++)
- hi = (hi << 8) | (bytes[i] & 0xff);
-
- return low + ((long)mid << 32) + ((long)(hi & 0x0FFF) << 48);
+ int d = (o1[6] & 0xF) - (o2[6] & 0xF);
+ if (d != 0) return d;
+ d = (o1[7] & 0xFF) - (o2[7] & 0xFF);
+ if (d != 0) return d;
+ d = (o1[4] & 0xFF) - (o2[4] & 0xFF);
+ if (d != 0) return d;
+ d = (o1[5] & 0xFF) - (o2[5] & 0xFF);
+ if (d != 0) return d;
+ d = (o1[0] & 0xFF) - (o2[0] & 0xFF);
+ if (d != 0) return d;
+ d = (o1[1] & 0xFF) - (o2[1] & 0xFF);
+ if (d != 0) return d;
+ d = (o1[2] & 0xFF) - (o2[2] & 0xFF);
+ if (d != 0) return d;
+ return (o1[3] & 0xFF) - (o2[3] & 0xFF);
}
public String getString(byte[] bytes)
Modified:
cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
URL:
http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java?rev=985349&r1=985348&r2=985349&view=diff
==============================================================================
---
cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
(original)
+++
cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
Fri Aug 13 20:33:49 2010
@@ -18,6 +18,9 @@
*/
package org.apache.cassandra.db.marshal;
+import java.util.Arrays;
+import java.util.Random;
+
import org.junit.Test;
import static org.junit.Assert.assertEquals;
@@ -27,7 +30,7 @@ import org.apache.cassandra.db.marshal.T
import org.safehaus.uuid.UUID;
import org.safehaus.uuid.UUIDGenerator;
-public class TimeUUIDTypeTest extends CleanupHelper
+public class TimeUUIDTypeTest
{
TimeUUIDType timeUUIDType = new TimeUUIDType();
UUIDGenerator generator = UUIDGenerator.getInstance();
@@ -48,9 +51,9 @@ public class TimeUUIDTypeTest extends Cl
UUID b = generator.generateTimeBasedUUID();
UUID c = generator.generateTimeBasedUUID();
- assertEquals(-1, timeUUIDType.compare(a.asByteArray(),
b.asByteArray()));
- assertEquals(-1, timeUUIDType.compare(b.asByteArray(),
c.asByteArray()));
- assertEquals(-1, timeUUIDType.compare(a.asByteArray(),
c.asByteArray()));
+ assert timeUUIDType.compare(a.asByteArray(), b.asByteArray()) < 0;
+ assert timeUUIDType.compare(b.asByteArray(), c.asByteArray()) < 0;
+ assert timeUUIDType.compare(a.asByteArray(), c.asByteArray()) < 0;
}
@Test
@@ -60,18 +63,30 @@ public class TimeUUIDTypeTest extends Cl
UUID b = generator.generateTimeBasedUUID();
UUID c = generator.generateTimeBasedUUID();
- assertEquals(1, timeUUIDType.compare(c.asByteArray(),
b.asByteArray()));
- assertEquals(1, timeUUIDType.compare(b.asByteArray(),
a.asByteArray()));
- assertEquals(1, timeUUIDType.compare(c.asByteArray(),
a.asByteArray()));
+ assert timeUUIDType.compare(c.asByteArray(), b.asByteArray()) > 0;
+ assert timeUUIDType.compare(b.asByteArray(), a.asByteArray()) > 0;
+ assert timeUUIDType.compare(c.asByteArray(), a.asByteArray()) > 0;
}
@Test
- public void testTimestamp()
+ public void testTimestampComparison()
{
- for (int i = 0; i < 100; i++)
+ Random rng = new Random();
+ byte[][] uuids = new byte[100][];
+ for (int i = 0; i < uuids.length; i++)
+ {
+ uuids[i] = new byte[16];
+ rng.nextBytes(uuids[i]);
+ // set version to 1
+ uuids[i][6] &= 0x0F;
+ uuids[i][6] |= 0x10;
+ }
+ Arrays.sort(uuids, timeUUIDType);
+ for (int i = 1; i < uuids.length; i++)
{
- UUID uuid = generator.generateTimeBasedUUID();
- assert TimeUUIDType.getTimestamp(uuid.asByteArray()) ==
LexicalUUIDType.getUUID(uuid.asByteArray()).timestamp();
+ long i0 = LexicalUUIDType.getUUID(uuids[i - 1]).timestamp();
+ long i1 = LexicalUUIDType.getUUID(uuids[i]).timestamp();
+ assert i0 <= i1;
}
}
}
