Incrementing large numbers

[mtbc]

At work I program in Java 7 mostly. I was asked to add some statistics-gathering to some code that gets called a lot so performance is key. After some initial test runs, back-of-the-envelope calculations about for how long our servers may run, etc., I did not feel safe in assuming that even a eight-byte long counter would never wrap around. In practice, I do not think a production server facing a continuously heavy workload during many years' uptime would come close to overflowing my long but I am used to having so much margin to work with that I do not even have to think about the issue.

A surprising discovery for me is that Java 7 does not offer efficient incrementing of arbitrarily large integers. Coming from a functional programming background I appreciate immutable values but I also appreciate compilers that can optimize much of the heap allocation out of the native code they generate. I have far less faith in what Java does, or indeed may do, with BigInteger, and people on the Internet already seem to have done some performance testing.

Fortunately, not all surprising discoveries are bad. It also turns out to be easy to increment an arbitrarily large integer with few heap allocations by storing it as a byte array, here named count:

for (int index = count.length; index > 0;)
  if (++count[--index] != 0)
    return;
count = new byte[count.length + 1];
count[0] = 1;

To log the statistic readably it suffices to return new BigInteger(1, count).

Comments

[goldibehr]

While it works fine, BigInteger seems like overkill. You could quickly make your own 128-bit "LongLong" class holding 2 long values. That object would far less expensive to increment than the code you show.

How many increments per second does the problem need?

[mtbc]

Fortunately I need the BigInteger bit rather rarely, just when I bother writing the current counts to logs (currently several times per minute). Given that I don't need the BigInteger to do the increment, I'm not sure why my increment code would be expensive: it'll typically return in the first loop iteration? The worst I can see is it does have to look at the array, which will be on the heap rather than passed on the stack, but I would guess that a LongLong's fields would be likewise. (I'm guessing that index just ends up as a register.)

It may not actually be much more than a few tens of thousands of increments per second which of course by modern standards is nothing, but I've not worked hard to be sure of an upper limit and we seem to increase the scale of data we want to push through the system faster than we can comfortably scale the system itself, so I'm worried that we may be up some orders of magnitude before anybody ever looks again at the code.

Update: Ah, I realize I was probably unclear: when I write of returning the BigInteger, I didn't mean from the increment method: I probably snipped too much context!

[goldibehr]

Yeah, I misunderstood. I thought you were creating a new BigInteger object every time you incremented.

[mtbc]

Thanks for speaking up! It was worth clarifying.