Encoding and decoding an array of digits

Question

I have two simple functions where performance is critical, one for encoding an array of ints to a long, another for doing the opposite (decoding the long back to an array of ints).

The solutions I have come up with below are fairly fast. Can these be made even faster?

Please note: I am constrained by using the same function signatures.

    public static final long encode(int[] digits) {
        return 
          1000000000000000000L * digits[0]
        + 100000000000000000L * digits[1]
        + 10000000000000000L * digits[2]
        + 1000000000000000L * digits[3]
        + 100000000000000L * digits[4]
        + 10000000000000L * digits[5]
        + 1000000000000L * digits[6]
        + 100000000000L * digits[7]
        + 10000000000L * digits[8]
        + 1000000000L * digits[9]
        + 100000000L * digits[10]
        + 10000000L * digits[11]
        + 1000000L * digits[12]
        + 100000L * digits[13]
        + 10000L * digits[14]
        + 1000L * digits[15]
        + 100L * digits[16]
        + 10L * digits[17]
        + 1L * digits[18];
    }

    public static final int[] decode(long move) {
        int[] digits = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        int index = digits.length - 1;
        while(move > 0) {
            digits[index--] = (int)(move % 10);
            move = move / 10;
        }
        return digits;
    }

These are used for persisting a Chess move in a simple engine, for example:

//=========================================================================                                     
// MOVE INFO                                                                                                    
//=========================================================================                                     
public static final int MOVE_INFO_COUNT = 19;                                                                   
public static final int MOVE_INFO_EXTRA_1 = 0;                          // -> ACTIVE DIGIT IS ALWAYS 1          
public static final int MOVE_INFO_EXTRA_2 = 1;                          // -> UNUSED (0)                        
public static final int MOVE_INFO_EXTRA_3 = 2;                          // -> UNUSED (0)                        
public static final int MOVE_INFO_PLAYER = 3;                           // -> PLAYER CONSTANTS (0 - 1)          
public static final int MOVE_INFO_MOVE_TYPE = 4;                        // -> MOVE-TYPE CONSTANTS (0 - 8)       
public static final int MOVE_INFO_MOVED_PIECE = 5;                      // -> PIECE CONSTANTS (0 - 6)           
public static final int MOVE_INFO_SOURCE_ROW = 6;                       // -> RANK (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_SOURCE_COL = 7;                       // -> FILE (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_TARGET_ROW = 8;                       // -> RANK (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_TARGET_COL = 9;                       // -> FILE (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_CAPTURED_PIECE = 10;                  // -> PIECE CONSTANTS (0 - 6)           
public static final int MOVE_INFO_EN_PASSANT_ROW = 11;                  // -> RANK (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_EN_PASSANT_COL = 12;                  // -> FILE (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_PREVIOUS_EN_PASSANT_ROW = 13;         // -> RANK (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_PREVIOUS_EN_PASSANT_COL = 14;         // -> FILE (0 - 7) OR 9 = NOT APPLICABLE
public static final int MOVE_INFO_WHITE_CASTLING_RIGHTS = 15;           // -> CASTLING-RIGHTS CONSTANTS (0 - 3) 
public static final int MOVE_INFO_BLACK_CASTLING_RIGHTS = 16;           // -> CASTLING-RIGHTS CONSTANTS (0 - 3) 
public static final int MOVE_INFO_PREVIOUS_WHITE_CASTLING_RIGHTS = 17;  // -> CASTLING-RIGHTS CONSTANTS (0 - 3) 
public static final int MOVE_INFO_PREVIOUS_BLACK_CASTLING_RIGHTS = 18;  // -> CASTLING-RIGHTS CONSTANTS (0 - 3) 


import com.chess.engine.Move;
public class DEBUG_ENCODE_DECODE {

    private static final void benchmark(long iterations) {
        long start = System.currentTimeMillis();
        long counter = 0;
        for(long i = 0L; i < iterations; i++) {
            work();
            counter++;
        }
        long end = System.currentTimeMillis();
        System.out.println(counter +" ITERATIONS IN MILLISECONDS: " + (end - start));
    }

    private static final void work() {
        long move = 1000432101234567890L;

        if(Move.encodeMove(Move.decodeMove(move)) != move) {
            throw new RuntimeException("ENCODE DECODE FAILED");
        }
    }

    public static void main(String[] args) {
        benchmark(100000000);
    }
}

I agree with @cyrbil however I want to mention this post (stackoverflow.com/questions/17834190/…) as a quick reference. May need to test an implementation before you make a decision. — Sh4d0wsPlyr, Jul 10 '15 at 14:15
If you want optimized solution, look what the JDK does to parse an int. You're doing the same thing, just without the offset of the 0 char. — Marko Topolnik, Jul 10 '15 at 14:16
In your decode method, the MOD and DIV instructions are most probably the bottleneck. — Marko Topolnik, Jul 10 '15 at 14:17
To me this looks like a much better target for bitwise mapping. You have many params in the perfect ranges of 0-7 (3 bits fully utilized), 0-3 (2 bits fully utilized), and 0-1 (1 bit). — Marko Topolnik, Jul 10 '15 at 14:48

Marko Topolnik · Accepted Answer · 2015-07-11 17:31:09Z

By measuring with JMH I found your decoder being much slower than the encoder. Contrary to your conclusion that the bottleneck is array allocation, I find that the difference between one static array and a new array each time has secondary effect. Compare these results (single static array):

MeasureEncoding.decodeBitfield    avgt    5   5.896 ± 0.091  ns/op
MeasureEncoding.decodeConstantin  avgt    5  44.287 ± 1.217  ns/op
MeasureEncoding.decodeMarco13     avgt    5   7.256 ± 0.240  ns/op
MeasureEncoding.encodeBitfield    avgt    5   8.637 ± 0.279  ns/op
MeasureEncoding.encodeConstantin  avgt    5   8.942 ± 0.207  ns/op

with these (new array each time):

Benchmark                         Mode  Cnt   Score   Error  Units
MeasureEncoding.decodeBitfield    avgt    5  11.299 ± 0.360  ns/op
MeasureEncoding.decodeConstantin  avgt    5  50.503 ± 2.331  ns/op
MeasureEncoding.decodeMarco13     avgt    5  17.295 ± 0.120  ns/op
MeasureEncoding.encodeBitfield    avgt    5   8.560 ± 0.130  ns/op
MeasureEncoding.encodeConstantin  avgt    5   8.966 ± 0.161  ns/op

Your method comes out behind by a significant factor in both cases.

I conjecture that this is due to the involvement of the slow divison operators (/ and %). The surprising finding is that just unrolling your decoding loop (as in Marco13's proposal) makes a huge difference. It must be triggering some optimization of the division in the JIT compiler.

If you used bitfield-based encoding, performance would be better and more robust (not sensitive to special-cased JIT optimizations). Here is how it would look, not much different than your code:

public static long encodeBitfield(int[] move) {
  if (move.length != ARRAY_SIZE) {
    throw new IllegalArgumentException("move must have 19 elements");
  }
  long enc = 0;
  int bitsUsed = 0;
  enc |= move[3];
  enc |= (long) move[4] << (bitsUsed += 1);
  enc |= (long) move[5] << (bitsUsed += 4);
  enc |= (long) move[6] << (bitsUsed += 4);
  enc |= (long) move[7] << (bitsUsed += 4);
  enc |= (long) move[8] << (bitsUsed += 4);
  enc |= (long) move[9] << (bitsUsed += 4);
  enc |= (long) move[10] << (bitsUsed += 4);
  enc |= (long) move[11] << (bitsUsed += 4);
  enc |= (long) move[12] << (bitsUsed += 4);
  enc |= (long) move[13] << (bitsUsed += 4);
  enc |= (long) move[14] << (bitsUsed += 4);
  enc |= (long) move[15] << (bitsUsed += 4);
  enc |= (long) move[16] << (bitsUsed += 2);
  enc |= (long) move[17] << (bitsUsed += 2);
  enc |= (long) move[18] << (bitsUsed + 2);
  return enc;
}

public static int[] decodeBitfield(long move) {
  final int[] dec = new int[ARRAY_SIZE];
  dec[0] = 1;
  int ind = 3;
  dec[ind++] = (int) move & 1;
  move >>= 1;
  for (; ind < 15; ind++, move >>= 4) {
    dec[ind] = (int) move & 15;
  }
  for (; ind < ARRAY_SIZE; ind++, move >>= 2) {
    dec[ind] = (int) move & 3;
  }
  return dec;
}

For those interested, this is the full JMH code.

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@OperationsPerInvocation(1)
@Warmup(iterations = 8, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
@Fork(1)
public class MeasureEncoding
{
  public static final int ARRAY_SIZE = 19;
  final int[] digits = new int[ARRAY_SIZE];

  @Setup(Level.Iteration) public void setup() {
    for (int i = 0; i < digits.length; i++) {
      digits[i] = i % 10;
    }
  }

  @Benchmark public long encodeConstantin() {
    return encode(digits);
  }

  @Benchmark public long encodeBitfield() {
    return encodeBitfield(digits);
  }

  @Benchmark public int[] decodeConstantin() {
    return decode(1234567890123456789L);
  }

  @Benchmark public int[] decodeBitfield() {
    return decodeBitfield(0b11111111100110011001100101101001100110011001011010001L);
  }

  @Benchmark public int[] decodeMarco13() {
    return decodeMarco13(1234567890123456789L);
  }

  static long encode(int[] digits) {
    return
        1000000000000000000L * digits[0]
            + 100000000000000000L * digits[1]
            + 10000000000000000L * digits[2]
            + 1000000000000000L * digits[3]
            + 100000000000000L * digits[4]
            + 10000000000000L * digits[5]
            + 1000000000000L * digits[6]
            + 100000000000L * digits[7]
            + 10000000000L * digits[8]
            + 1000000000L * digits[9]
            + 100000000L * digits[10]
            + 10000000L * digits[11]
            + 1000000L * digits[12]
            + 100000L * digits[13]
            + 10000L * digits[14]
            + 1000L * digits[15]
            + 100L * digits[16]
            + 10L * digits[17]
            + 1L * digits[18];
  }

  static int[] decode(long move) {
    int[] digits = new int[19];
    int index = digits.length - 1;
    while(move > 0) {
      digits[index--] = (int)(move % 10);
      move = move / 10;
    }
    return digits;
  }

  static long encodeBitfield(int[] move) {
    if (move.length != ARRAY_SIZE) {
      throw new IllegalArgumentException("move must have 19 elements");
    }
    long enc = 0;
    int bitsUsed = 0;
    enc |= move[3];
    enc |= (long) move[4] << (bitsUsed += 1);
    enc |= (long) move[5] << (bitsUsed += 4);
    enc |= (long) move[6] << (bitsUsed += 4);
    enc |= (long) move[7] << (bitsUsed += 4);
    enc |= (long) move[8] << (bitsUsed += 4);
    enc |= (long) move[9] << (bitsUsed += 4);
    enc |= (long) move[10] << (bitsUsed += 4);
    enc |= (long) move[11] << (bitsUsed += 4);
    enc |= (long) move[12] << (bitsUsed += 4);
    enc |= (long) move[13] << (bitsUsed += 4);
    enc |= (long) move[14] << (bitsUsed += 4);
    enc |= (long) move[15] << (bitsUsed += 4);
    enc |= (long) move[16] << (bitsUsed += 2);
    enc |= (long) move[17] << (bitsUsed += 2);
    enc |= (long) move[18] << (bitsUsed + 2);
    return enc;
  }

  static int[] decodeBitfield(long move) {
    final int[] dec = new int[ARRAY_SIZE];
    dec[0] = 1;
    int ind = 3;
    dec[ind++] = (int) move & 1;
    move >>= 1;
    for (; ind < 15; ind++, move >>= 4) {
      dec[ind] = (int) move & 15;
    }
    for (; ind < ARRAY_SIZE; ind++, move >>= 2) {
      dec[ind] = (int) move & 3;
    }
    return dec;
  }

  static int[] decodeMarco13(long move)
  {
    int[] digits = new int[19];
    digits[18] = (int)(move % 10); move /= 10;
    digits[17] = (int)(move % 10); move /= 10;
    digits[16] = (int)(move % 10); move /= 10;
    digits[15] = (int)(move % 10); move /= 10;
    digits[14] = (int)(move % 10); move /= 10;
    digits[13] = (int)(move % 10); move /= 10;
    digits[12] = (int)(move % 10); move /= 10;
    digits[11] = (int)(move % 10); move /= 10;
    digits[10] = (int)(move % 10); move /= 10;
    digits[ 9] = (int)(move % 10); move /= 10;
    digits[ 8] = (int)(move % 10); move /= 10;
    digits[ 7] = (int)(move % 10); move /= 10;
    digits[ 6] = (int)(move % 10); move /= 10;
    digits[ 5] = (int)(move % 10); move /= 10;
    digits[ 4] = (int)(move % 10); move /= 10;
    digits[ 3] = (int)(move % 10); move /= 10;
    digits[ 2] = (int)(move % 10); move /= 10;
    digits[ 1] = (int)(move % 10); move /= 10;
    digits[ 0] = (int)(move % 10); move /= 10;
    return digits;
  }

  public static void main(String[] args) {
    final int[] move = {1, 0, 0, 1, 8, 6, 9, 9, 9, 9, 6, 9, 9, 9, 9, 3, 3, 3, 3};
    System.out.println(move.length);
    long encoded = encodeBitfield(move);
    System.out.println(Long.toString(encoded, 2));
    System.out.println(Arrays.toString(move));
    System.out.println(Arrays.toString(decodeBitfield(encoded)));
  }
}

Comments are not for extended discussion; this conversation has been moved to chat. — 200_success♦, Jul 12 '15 at 7:58

Marco13 · Answer 2 · 2015-07-12 11:30:54Z

There obviously are some constraints for modelling and representing this data. And from what I see in the question, it it not about whether there are solutions that achieve a higher performance, but how the given solution can be made faster, retaining the given signatures and constants.

In this regard:

Micro-optimizations with minor reorderings or attempts to avoid a few instructions most likely won't pay out: As confirmed by a run in a Hotspot-Disassembler VM, the modulo- and division operations will be optimized away by the JIT - at least, on 64bit platforms, where they will boil down to some sar and shl instructions, and the resulting code will no longer contain any div instructions at all.
Caching the values for a lookup does not seem feasible due to the range of the possible values, and because CPUs are darn fast, whereas memory is slow. Contrariwise, caching will likely slow things down due to ... caching (referring to the required hardware caching here).

So in the end, there is not much room for improvements. One might consider unrolling the loop in decode as well, with something like

public static final int[] decode(long move) 
{
    int[] digits = new int[19];
    digits[18] = (int)(move % 10); move /= 10;
    digits[17] = (int)(move % 10); move /= 10;
    digits[16] = (int)(move % 10); move /= 10;
    digits[15] = (int)(move % 10); move /= 10;
    digits[14] = (int)(move % 10); move /= 10;
    digits[13] = (int)(move % 10); move /= 10;
    digits[12] = (int)(move % 10); move /= 10;
    digits[11] = (int)(move % 10); move /= 10;
    digits[10] = (int)(move % 10); move /= 10;
    digits[ 9] = (int)(move % 10); move /= 10;
    digits[ 8] = (int)(move % 10); move /= 10;
    digits[ 7] = (int)(move % 10); move /= 10;
    digits[ 6] = (int)(move % 10); move /= 10;
    digits[ 5] = (int)(move % 10); move /= 10;
    digits[ 4] = (int)(move % 10); move /= 10;
    digits[ 3] = (int)(move % 10); move /= 10;
    digits[ 2] = (int)(move % 10); move /= 10;
    digits[ 1] = (int)(move % 10); move /= 10;
    digits[ 0] = (int)(move % 10); move /= 10;
    return digits;
}

Originally, I thought that this would most likely NOT bring any benefit:

If it was beneficial, the JIT would do it
If it is not beneficial, the JIT might be disturbed by the larger bytecode size (regarding method inlining limits)

But according to the answer by Marko Topolnik, it might in fact bring a speedup (although for a profound explanation, one would have to analyze the JIT output in more detail).

However, a side note: It is something that is hard to measure (even with tools like JMH or so). But it might be that the real bottleneck here is the allocation of the new array in the decode method (and the garbage that is caused there and has to be collected). You might try to avoid this allocation. You said that you can't change the signature to

public static final void decode(long move, int digits[])

so you don't have many options here either.

The only option is...

an option that dramatically changes how this method may be used. The returned array may NOT be stored in any way. The method will no longer be thread-safe. You should NOT blindly do this without being aware of the consequences.

But depending on how the array is actually used, you might consider writing the method as

private static final int digits[] = new int[19];
public static final int[] decode(long move) {
    ...
    return digits;
}

That is, return always the same, static instance of the array. If the returned array is only read once and processed (but not stored), this might be fine, and actually bring a speedup, in contrast to fiddling around, trying to avoid one or another iinc here and there...

Again, Marko Topolnik has included measurements for this in his answer, but I still think that whether or not this actually brings a speedup heavily depends on the application case - namely, on how the returned array is used: I think that here, Escape Analysis might come into play as well.

So I'd definitely recommend to consider the options and possibilities that have been mentioned so far, but still measure their effects in your actual program and base the final decisions on an actual Profiler run.

I have confirmed that the bottleneck was indeed the allocation and garbage collection of the int array. The answers and comments of all who have contributed have made me reconsider (yet again) the design of how to better represent a move. I really like how Marco13 presented his answer so will award him the answer but all contributions were extremely helpful. Thank you — Constantin, Jul 11 '15 at 6:41
Please continue this discussion in chat instead of this lengthy comment thread. — 200_success♦, Jul 12 '15 at 8:06

meriton · Answer 3 · 2015-07-10 15:52:11Z

Representing a move as an int[] rather than in instance of a dedicated class is a bad idea, as array accesses are bounds checked, and you lose the ability to use suitable types for the individual fields. (As your comment reveals that you have previously used another representation, I hope you can change reprentation again, even though your question seems indicate otherwise.)

class Move {
    boolean playerIsWhite;
    int type; // might want to use an enum instead
    int movingPiece; // likewise
    int sourceRow, sourceCol;
    int targetRow, targetCol;
    PieceType capturedPiece;
    int enPassantRow, enPassantCol; // seems redundant?
    int previousEnPassantRow, previousEnPassantCol; // likewise
    int castlingRightsBlack, castlingRightsWhite, previousCastlingRightsBlack, previousCastlingRightsWhite;

    long encode() {
        return (playerIsWhite ? 1 : 0)
             | (type << 1)
             | (movingPiece << 5)
             | (sourceRow << 8)
             | (sourceCol << 12)
             | (targetRow << 16)
             | (targetCol << 20)
             | (capturedPiece << 24)
             | (enPassantRow << 27)
             | (enPassantCol << 31)
             | (previousEnPassantRow << 35)
             | (previousEnPassantCol << 39)
             | (castlingRightsWhite << 43)
             | (castlingRightsBlack << 45)
             | (previousCastlingRightsWhite << 47)
             | (previousCastlingRightsBlack << 49);
    }

    static Move decode(long d) {
        Move m = new Move();
        m.playerIsWhite = (d & 1) != 0;
        m.type = (d >> 1) & 0b1111;
        m.movingPiece = (d >> 5) & 0b111;
        m.sourceRow = (d >> 12) & 0b1111;
        // and so on
        return m;
    }
}

Advantages over your approach:

no bounds checking, because we don't use an array (this also speeds up any other code working with Move objects)
no multiplications or divisions (adding, shifting and logical operations are cheaper)
fewer data dependencies, enabling better use of Instruction Level Parallelism.

Performance might be further improved by eliminating redundant fields in the Move object (how is enPassantRow different from targetRow, and previousEnPassantRow different from sourceRow? If it's just to recond that it was en passant move, why not add this as a new movetype?).

Bounds checking shouldn't be a major problem, there are surely ways to tell the JIT compiler it can eliminate most of them. Also, using all those direct constants for shifting is probably not helping. It may be imagined that they reduce dependencies, but the cost of loading them would mask any benefit. There's a good chance HotSpot actually compiles this into a register-maintained variable which is update as needed. — Marko Topolnik, Jul 10 '15 at 16:56
About using a custom class, OP was quite clear: I AM CONSTRAINED BY USING THE SAME FUNCTION SIGNATURES. — Marko Topolnik, Jul 10 '15 at 16:57
Ahem, I keep forgetting that there is actually a form of SHR which takes an inline shift distance. That annulls my argument about loading the constants. — Marko Topolnik, Jul 10 '15 at 17:47
@Marko: Citation needed about bounds checking. I am aware that the JIT will eliminate bounds checking in loops (if the array index is the loop index, and changes with a constant step size), but such is not the case in OP's encode method. As for not using an int[], OP's comments indicate he used to use a String before switching to int[], so why not a dedicated class? — meriton, Jul 10 '15 at 17:53
He used a String before switching to long as the encoded form, that's his design freedom. I guess he is plugging into some existing chess playing library. About bounds checking, if you start your method with if (move.lengh != 19) throw new IllegalArgumentException(); then the JIT can eliminate bounds checking on any constant-indexed array access---which is easily achievable here. Also it can eliminate checking in a loop which has a constant bound less than or equal to the checked length. — Marko Topolnik, Jul 10 '15 at 17:56

Carlos Bribiescas · Answer 4 · 2015-07-10 14:53:43Z

up vote 0 down vote

Since, as you said, your inputs are constrained. You may consider memoizing the function, so that you don't have to recalculate the output for the same input.

If it's too memory intensive, you can use a caching library that will auto cache the most used elements. (Although if the shown inputs are all the inputs then you should be good to keep them all in memory)

answered Jul 10 '15 at 14:53

Carlos Bribiescas

are you sure that the cache lookup will be cheaper than encoding from scratch? For instance, if the cache is a HashMap, a lookup requires computing a hashCode, which seems very similar to encoding the value into a long. – meriton Jul 10 '15 at 16:02

Thats a good question. You could certainly create a hash that would be faster. Instead of using a HashMap, you could cache it with a simple array and use something like this stackoverflow.com/questions/7996335/how-to-match-int-to-enum‌/… to convert the enums to an int. Then you're just going to an array for the answer. To your point, I don't know if his solution is faster than HashMap. – Carlos Bribiescas Jul 10 '15 at 16:20

add a comment |

asked	1 year ago
viewed	365 times
active	1 year ago

current community

your communities

more stack exchange communities

Encoding and decoding an array of digits

migrated from stackoverflow.com Jul 10 '15 at 18:27

4 Answers 4

Your Answer

Not the answer you're looking for? Browse other questions tagged java performance chess or ask your own question.

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Encoding and decoding an array of digits

migrated from stackoverflow.com Jul 10 '15 at 18:27

4 Answers 4

Did you find this question interesting? Try our newsletter

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java performance chess or ask your own question.

Visit Chat

Related

Hot Network Questions