This is an automated email from the ASF dual-hosted git repository.
dschneider pushed a commit to branch develop
in repository https://gitbox.apache.org/repos/asf/geode.git
The following commit(s) were added to refs/heads/develop by this push:
new 1969f39 GEODE-9514: optimize how Coder reads and writes "int" and
"long" values (#6765)
1969f39 is described below
commit 1969f3965092756fe1e5ba0dab89790f498c3893
Author: Darrel Schneider <[email protected]>
AuthorDate: Thu Aug 19 22:22:12 2021 -0700
GEODE-9514: optimize how Coder reads and writes "int" and "long" values
(#6765)
* added appendAsciiDigitsToByteBuf to Coder so that ints and longs
can more efficiently by added to a ByteBuf. The goal was to reduce
the number of short lived object allocations.
* longToBytes and intToBytes now use the new conversion code
and for small numbers canonical arrays are used
* bytesToLong optimized to not convert the byte array to a String
* getBulkStringResponse now uses getIntegerResponse
This method no longer truncates a Long to an Integer
---
.../apache/geode/redis/internal/netty/Coder.java | 271 +++++++++++++++++++--
.../geode/redis/internal/netty/CoderTest.java | 69 ++++++
2 files changed, 325 insertions(+), 15 deletions(-)
diff --git
a/geode-apis-compatible-with-redis/src/main/java/org/apache/geode/redis/internal/netty/Coder.java
b/geode-apis-compatible-with-redis/src/main/java/org/apache/geode/redis/internal/netty/Coder.java
index bfb289d..0119147 100644
---
a/geode-apis-compatible-with-redis/src/main/java/org/apache/geode/redis/internal/netty/Coder.java
+++
b/geode-apis-compatible-with-redis/src/main/java/org/apache/geode/redis/internal/netty/Coder.java
@@ -35,6 +35,7 @@ import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bINF;
import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bINFINITY;
import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bLOWERCASE_A;
import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bLOWERCASE_Z;
+import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bMINUS;
import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bMOVED;
import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bNIL;
import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bN_INF;
@@ -43,6 +44,7 @@ import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bNaN;
import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bOK;
import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bOOM;
import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bPERIOD;
+import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bPLUS;
import static org.apache.geode.redis.internal.netty.StringBytesGlossary.bP_INF;
import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bP_INFINITY;
import static
org.apache.geode.redis.internal.netty.StringBytesGlossary.bWRONGTYPE;
@@ -57,6 +59,7 @@ import java.util.List;
import io.netty.buffer.ByteBuf;
+import org.apache.geode.annotations.Immutable;
import org.apache.geode.annotations.internal.MakeImmutable;
import org.apache.geode.redis.internal.data.RedisKey;
@@ -100,13 +103,9 @@ public class Coder {
toWrite = stringToBytes(value);
writeStringResponse(buffer, toWrite);
} else if (v instanceof Integer) {
- buffer.writeByte(INTEGER_ID);
- buffer.writeBytes(intToBytes((Integer) v));
- buffer.writeBytes(bCRLF);
+ getIntegerResponse(buffer, (int) v);
} else if (v instanceof Long) {
- buffer.writeByte(INTEGER_ID);
- buffer.writeBytes(intToBytes(((Long) v).intValue()));
- buffer.writeBytes(bCRLF);
+ getIntegerResponse(buffer, (long) v);
} else {
throw new CoderException();
}
@@ -116,7 +115,7 @@ public class Coder {
private static void writeStringResponse(ByteBuf buffer, byte[] toWrite) {
buffer.writeByte(BULK_STRING_ID);
- buffer.writeBytes(intToBytes(toWrite.length));
+ appendAsciiDigitsToByteBuf(toWrite.length, buffer);
buffer.writeBytes(bCRLF);
buffer.writeBytes(toWrite);
buffer.writeBytes(bCRLF);
@@ -134,7 +133,7 @@ public class Coder {
public static ByteBuf getArrayResponse(ByteBuf buffer, Collection<?> items)
throws CoderException {
buffer.writeByte(ARRAY_ID);
- buffer.writeBytes(intToBytes(items.size()));
+ appendAsciiDigitsToByteBuf(items.size(), buffer);
buffer.writeBytes(bCRLF);
for (Object next : items) {
writeCollectionOrString(buffer, next);
@@ -155,12 +154,12 @@ public class Coder {
public static ByteBuf getScanResponse(ByteBuf buffer, BigInteger cursor,
List<?> scanResult) {
buffer.writeByte(ARRAY_ID);
- buffer.writeBytes(intToBytes(2));
+ buffer.writeByte(digitToAscii(2));
buffer.writeBytes(bCRLF);
byte[] cursorBytes = stringToBytes(cursor.toString());
writeStringResponse(buffer, cursorBytes);
buffer.writeByte(ARRAY_ID);
- buffer.writeBytes(longToBytes(scanResult.size()));
+ appendAsciiDigitsToByteBuf(scanResult.size(), buffer);
buffer.writeBytes(bCRLF);
for (Object nextObject : scanResult) {
@@ -242,14 +241,14 @@ public class Coder {
public static ByteBuf getIntegerResponse(ByteBuf buffer, int integer) {
buffer.writeByte(INTEGER_ID);
- buffer.writeBytes(intToBytes(integer));
+ appendAsciiDigitsToByteBuf(integer, buffer);
buffer.writeBytes(bCRLF);
return buffer;
}
public static ByteBuf getIntegerResponse(ByteBuf buffer, long l) {
buffer.writeByte(INTEGER_ID);
- buffer.writeBytes(longToBytes(l));
+ appendAsciiDigitsToByteBuf(l, buffer);
buffer.writeBytes(bCRLF);
return buffer;
}
@@ -311,12 +310,20 @@ public class Coder {
* literal to byte
*/
+ /**
+ * NOTE: Canonical byte arrays may be returned so callers
+ * must never modify the returned array.
+ */
public static byte[] intToBytes(int i) {
- return stringToBytes(String.valueOf(i));
+ return longToBytes(i);
}
+ /**
+ * NOTE: Canonical byte arrays may be returned so callers
+ * must never modify the returned array.
+ */
public static byte[] longToBytes(long l) {
- return stringToBytes(String.valueOf(l));
+ return convertLongToAsciiDigits(l);
}
public static byte[] doubleToBytes(double d) {
@@ -332,10 +339,56 @@ public class Coder {
}
public static long bytesToLong(byte[] bytes) {
- return Long.parseLong(bytesToString(bytes));
+ return parseLong(bytes);
+ }
+
+ private static NumberFormatException createNumberFormatException(byte[]
bytes) {
+ return new NumberFormatException("For input string: \"" +
bytesToString(bytes) + "\"");
}
/**
+ * This method was derived from openjdk Long.java parseLong
+ */
+ public static long parseLong(byte[] bytes) throws NumberFormatException {
+ final int len = bytes.length;
+ if (len <= 0) {
+ throw createNumberFormatException(bytes);
+ }
+ int i = 0;
+ long limit = -Long.MAX_VALUE;
+ boolean negative = false;
+ byte firstByte = bytes[0];
+ if (firstByte < NUMBER_0_BYTE) { // Possible leading "+" or "-"
+ if (firstByte == bMINUS) {
+ negative = true;
+ limit = Long.MIN_VALUE;
+ } else if (firstByte != bPLUS) {
+ throw createNumberFormatException(bytes);
+ }
+ if (len == 1) { // Cannot have lone "+" or "-"
+ throw createNumberFormatException(bytes);
+ }
+ i++;
+ }
+ final long multmin = limit / 10;
+ long result = 0;
+ while (i < len) {
+ // Accumulating negatively avoids surprises near MAX_VALUE
+ int digit = asciiToDigit(bytes[i++]);
+ if (digit < 0 || result < multmin) {
+ throw createNumberFormatException(bytes);
+ }
+ result *= 10;
+ if (result < limit + digit) {
+ throw createNumberFormatException(bytes);
+ }
+ result -= digit;
+ }
+ return negative ? result : -result;
+ }
+
+
+ /**
* A conversion where the byte array actually represents a string, so it is
converted as a string
* not as a literal double
*
@@ -471,4 +524,192 @@ public class Coder {
}
return doubleBytes;
}
+
+ /**
+ * Takes the given "value" and computes the sequence of ASCII digits it
represents,
+ * appending them to the given "buf".
+ */
+ public static void appendAsciiDigitsToByteBuf(long value, ByteBuf buf) {
+ buf.writeBytes(convertLongToAsciiDigits(value));
+ }
+
+ /**
+ * Convert the given "value" to a sequence of ASCII digits and
+ * returns them in a byte array. The only byte in the array that
+ * may not be a digit is the first byte will be '-' for a negative value.
+ * NOTE: the returned array's contents must not be modified by the caller.
+ */
+ private static byte[] convertLongToAsciiDigits(long value) {
+ final boolean negative = value < 0;
+ if (!negative) {
+ value = -value;
+ }
+ // at this point value <= 0
+
+ if (value > -100) {
+ // it has at most two digits: [-99..0]
+ return convertSmallLongToAsciiDigits((int) value, negative);
+ } else {
+ return convertBigLongToAsciiDigits(value, negative);
+ }
+ }
+
+ /**
+ * value is in the range [-99..0].
+ * This could be done using computation but a simple
+ * table lookup allows no allocations to be done since
+ * a canonical instance is returned.
+ */
+ private static byte[] convertSmallLongToAsciiDigits(int value, boolean
negative) {
+ value = -value;
+ // value is now 0..99
+ if (negative) {
+ return NEGATIVE_TABLE[value];
+ } else {
+ return POSITIVE_TABLE[value];
+ }
+ }
+
+ private static final int TABLE_SIZE = 100;
+ @Immutable
+ private static final byte[][] NEGATIVE_TABLE = new byte[TABLE_SIZE][];
+ @Immutable
+ private static final byte[][] POSITIVE_TABLE = new byte[TABLE_SIZE][];
+ static {
+ for (int i = 0; i < TABLE_SIZE; i++) {
+ NEGATIVE_TABLE[i] = createTwoDigitArray(-i, true);
+ POSITIVE_TABLE[i] = createTwoDigitArray(-i, false);
+ }
+ }
+
+ private static byte[] createTwoDigitArray(int value, boolean negative) {
+ int quotient = value / 10;
+ int remainder = (quotient * 10) - value;
+ int resultSize = (quotient < 0) ? 2 : 1;
+ if (negative) {
+ resultSize++;
+ }
+ byte[] result = new byte[resultSize];
+ int resultIdx = 0;
+ if (negative) {
+ result[resultIdx++] = bMINUS;
+ }
+ if (quotient < 0) {
+ result[resultIdx++] = digitToAscii(-quotient);
+ }
+ result[resultIdx] = digitToAscii(remainder);
+ return result;
+ }
+
+ /**
+ * This code was adapted from the openjdk Long.java getChars methods.
+ */
+ private static byte[] convertBigLongToAsciiDigits(long value, boolean
negative) {
+ final byte[] bytes = new byte[asciiByteLength(value, negative)];
+ int bytePos = bytes.length;
+
+ long quotient;
+ int remainder;
+ // Get 2 digits/iteration using longs until quotient fits into an int
+ while (value <= Integer.MIN_VALUE) {
+ quotient = value / 100;
+ remainder = (int) ((quotient * 100) - value);
+ value = quotient;
+ bytes[--bytePos] = DIGIT_ONES[remainder];
+ bytes[--bytePos] = DIGIT_TENS[remainder];
+ }
+
+ // Get 2 digits/iteration using ints
+ int intQuotient;
+ int intValue = (int) value;
+ while (intValue <= -100) {
+ intQuotient = intValue / 100;
+ remainder = (intQuotient * 100) - intValue;
+ intValue = intQuotient;
+ bytes[--bytePos] = DIGIT_ONES[remainder];
+ bytes[--bytePos] = DIGIT_TENS[remainder];
+ }
+
+ // We know there are at most two digits left at this point.
+ intQuotient = intValue / 10;
+ remainder = (intQuotient * 10) - intValue;
+ bytes[--bytePos] = digitToAscii(remainder);
+
+ // Whatever left is the remaining digit.
+ if (intQuotient < 0) {
+ bytes[--bytePos] = digitToAscii(-intQuotient);
+ }
+ if (negative) {
+ bytes[--bytePos] = bMINUS;
+ }
+ return bytes;
+ }
+
+ /**
+ * This code was derived from openjdk Long.java stringSize
+ * Returns the number of bytes needed to represent "value" as ascii bytes
+ * Note that "value" has already been negated if it was positive
+ * and we are told if that happened with the "negative" parameter.
+ *
+ * @param value long value already normalized to be <= 0.
+ * @param negative true if the original "value" was < 0.
+ * @return number of bytes needed to represent "value" as ascii bytes
+ *
+ * @implNote There are other ways to compute this: e.g. binary search,
+ * but values are biased heavily towards zero, and therefore
linear search
+ * wins. The iteration results are also routinely inlined in the
generated
+ * code after loop unrolling.
+ */
+ private static int asciiByteLength(long value, boolean negative) {
+ final int nonDigitCount = negative ? 1 : 0;
+ // Note since this is only called if value >= -100
+ // (see the caller of convertSmallLongToAsciiDigits)
+ // we skip the first two loops by starting
+ // powerOf10 at -1000 (instead of -10)
+ // and digitCount at 3 (instead of 1).
+ long powerOf10 = -1000;
+ final int MAX_DIGITS = 19;
+ for (int digitCount = 3; digitCount < MAX_DIGITS; digitCount++) {
+ if (value > powerOf10) {
+ return digitCount + nonDigitCount;
+ }
+ powerOf10 *= 10;
+ }
+ return MAX_DIGITS + nonDigitCount;
+ }
+
+ /**
+ * Given a digit (a value in the range 0..9) return its corresponding ASCII
code.
+ * NOTE: the caller is responsible for ensuring that 'digit' is in the
correct range.
+ */
+ public static byte digitToAscii(int digit) {
+ return (byte) (NUMBER_0_BYTE + digit);
+ }
+
+ public static int asciiToDigit(byte ascii) {
+ if (ascii >= NUMBER_0_BYTE && ascii <= NUMBER_0_BYTE + 9) {
+ return ascii - NUMBER_0_BYTE;
+ }
+ return -1;
+ }
+
+ @Immutable
+ private static final byte[] DIGIT_TENS = new byte[10 * 10];
+ static {
+ for (byte i = 0; i < 10; i++) {
+ for (byte j = 0; j < 10; j++) {
+ DIGIT_TENS[(i * 10) + j] = digitToAscii(i);
+ }
+ }
+ }
+
+ @Immutable
+ private static final byte[] DIGIT_ONES = new byte[10 * 10];
+ static {
+ for (byte i = 0; i < 10; i++) {
+ for (byte j = 0; j < 10; j++) {
+ DIGIT_ONES[(i * 10) + j] = digitToAscii(j);
+ }
+ }
+ }
}
diff --git
a/geode-apis-compatible-with-redis/src/test/java/org/apache/geode/redis/internal/netty/CoderTest.java
b/geode-apis-compatible-with-redis/src/test/java/org/apache/geode/redis/internal/netty/CoderTest.java
index 4211727..9c42509 100644
---
a/geode-apis-compatible-with-redis/src/test/java/org/apache/geode/redis/internal/netty/CoderTest.java
+++
b/geode-apis-compatible-with-redis/src/test/java/org/apache/geode/redis/internal/netty/CoderTest.java
@@ -28,6 +28,10 @@ import static
org.apache.geode.redis.internal.netty.Coder.stripTrailingZeroFromD
import static org.apache.geode.redis.internal.netty.Coder.toUpperCaseBytes;
import static org.assertj.core.api.Assertions.assertThat;
+import java.nio.charset.StandardCharsets;
+
+import io.netty.buffer.ByteBuf;
+import io.netty.buffer.ByteBufAllocator;
import junitparams.JUnitParamsRunner;
import junitparams.Parameters;
import org.junit.Test;
@@ -176,4 +180,69 @@ public class CoderTest {
};
}
+ @Test
+ public void verify_appendAsciiDigitsToByteBuf() {
+ for (long i = Long.MAX_VALUE; i > Long.MAX_VALUE - 1000; i--) {
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ for (long i = Long.MIN_VALUE; i < Long.MIN_VALUE + 1000; i++) {
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ for (long i = Integer.MAX_VALUE + 1000; i > Integer.MAX_VALUE - 1000; i--)
{
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ for (long i = Integer.MIN_VALUE + 1000; i > Integer.MIN_VALUE - 1000; i--)
{
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ for (long i = Short.MAX_VALUE + 1000; i > Short.MAX_VALUE - 1000; i--) {
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ for (long i = Short.MIN_VALUE + 1000; i > Short.MIN_VALUE - 1000; i--) {
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ for (long i = Byte.MIN_VALUE; i <= Byte.MAX_VALUE; i++) {
+ verify_appendAsciiDigitsToByteBuf(i);
+ }
+ }
+
+ private void verify_appendAsciiDigitsToByteBuf(long value) {
+ String expected = Long.toString(value);
+ ByteBuf buf = ByteBufAllocator.DEFAULT.heapBuffer();
+
+ Coder.appendAsciiDigitsToByteBuf(value, buf);
+
+ assertThat(buf.toString(StandardCharsets.UTF_8)).isEqualTo(expected);
+ }
+
+ @Test
+ public void verify_longToBytes_bytesToLong_consistency() {
+ for (long i = Long.MAX_VALUE; i > Long.MAX_VALUE - 1000; i--) {
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ for (long i = Long.MIN_VALUE; i < Long.MIN_VALUE + 1000; i++) {
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ for (long i = Integer.MAX_VALUE + 1000; i > Integer.MAX_VALUE - 1000; i--)
{
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ for (long i = Integer.MIN_VALUE + 1000; i > Integer.MIN_VALUE - 1000; i--)
{
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ for (long i = Short.MAX_VALUE + 1000; i > Short.MAX_VALUE - 1000; i--) {
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ for (long i = Short.MIN_VALUE + 1000; i > Short.MIN_VALUE - 1000; i--) {
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ for (long i = Byte.MIN_VALUE; i <= Byte.MAX_VALUE; i++) {
+ verify_longToBytes_bytesToLong_consistency(i);
+ }
+ }
+
+ private void verify_longToBytes_bytesToLong_consistency(long l) {
+ byte[] lBytes = Coder.longToBytes(l);
+ long l2 = Coder.bytesToLong(lBytes);
+ assertThat(l2).isEqualTo(l);
+ }
+
}
