Supporting mixed sequence of Ints and longs in Java/Android

[Nathan Tippy]

I want to read a Java array from beginning to the end to allow good pre-fetch behavior. 

But the list however is a mix of mostly int with periodic longs. Lets say 5 ints for every long on average.

For simplicity I know the index where the longs appear (eg a repeating pattern).  

NOTE: I also need Android compatibility so I think that would eliminate any Unsafe solutions (Please correct me if I am wrong).

Here are my design choices, which would be the most sympathetic?

A. Use int[] and when a long is encountered take something like  int[x]<<32 | int[x+1] to rebuild the long. 

    Is the overhead here of the << and | going to hurt too much?

B. Use long[] and downcast all the ints

    Is the extra width padding around the ints going to hurt too much?

C. Use two arrays int[] and long[] jumping between them as needed while keeping to position indexes.

    (existing code does this and I feel that it can be improved, this is why I am asking.)

D. any other ideas?

[Aleksey Shipilev]

E. Use DirectByteBuffer which already encapsulates the byte[] storage and full-width Unsafe operations, whether it's int or long.

-Aleksey.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter Lawrey]

You can use direct ByteBuffer to use Unsafe on the platforms which have it. Its not quite as efficient but the overhead is small compared with cache miss costs.

However you might find the int [] and long [] as fast or faster and simpler.
Prefetching works just fine from two arrays instead of one.

--

[Peter Lawrey]

Note: there is no byte [] for a direct ByteBuffer.

[Aleksey Shipilev]

Right. That was a typo. At least in OpenJDK, direct ByteBuffers operate on plain Unsafe-allocated memory.

-Aleksey.

[awei...@voltdb.com]

Hi,

long[] vs int[] probably won't make a difference prefetch wise. Doing the extra casts long to int is probably more work, but I don't know how casts are implemented and have never measured their cost. ByteBuffer is going to do more work than iterating an array of bytes since it does bounds checking and possibly a few more instructions once you have written a loop around it.

If the period is fixed you could unroll the loop, and have multiple copies if there are a few common periods. Also, do you need to downcast at all? I don't know what the difference in latency and throughput is between ints and longs.

If you want to know what works best you can write a benchmark with JMH and find out although what works best on Android will not necessarily match what is best for HotSpot. They are very different runtimes. Let's not forget the differences between presumably x86 and ARM as well.

Ariel

On Wednesday, March 19, 2014 2:04:26 PM UTC-4, Aleksey Shipilev wrote:

Right. That was a typo. At least in OpenJDK, direct ByteBuffers operate on plain Unsafe-allocated memory.

-Aleksey.

On Wed, Mar 19, 2014 at 10:03 PM, Peter Lawrey <peter....@gmail.com> wrote:

Note: there is no byte [] for a direct ByteBuffer.

On 19 Mar 2014 17:59, "Aleksey Shipilev" <aleksey....@gmail.com> wrote:

E. Use DirectByteBuffer which already encapsulates the byte[] storage and full-width Unsafe operations, whether it's int or long.

-Aleksey.

On Wed, Mar 19, 2014 at 9:46 PM, Nathan Tippy <natha...@gmail.com> wrote:

I want to read a Java array from beginning to the end to allow good pre-fetch behavior. 

But the list however is a mix of mostly int with periodic longs. Lets say 5 ints for every long on average.

For simplicity I know the index where the longs appear (eg a repeating pattern).  

NOTE: I also need Android compatibility so I think that would eliminate any Unsafe solutions (Please correct me if I am wrong).

Here are my design choices, which would be the most sympathetic?

A. Use int[] and when a long is encountered take something like  int[x]<<32 | int[x+1] to rebuild the long. 

    Is the overhead here of the << and | going to hurt too much?

B. Use long[] and downcast all the ints

    Is the extra width padding around the ints going to hurt too much?

C. Use two arrays int[] and long[] jumping between them as needed while keeping to position indexes.

    (existing code does this and I feel that it can be improved, this is why I am asking.)

D. any other ideas?

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

[tm jee]

 If performance aren't an obvious issue, I'd rather go for methods like 2 array or any method that is obvious to anyone who reads the code. I'm just guessing Bytebuffer or not wouldn't make much of a difference even with reasonable array size. Just my 2 cents. Btw is good performance wise is ByteBuffer in ARM arch, just curious.

[Peter Lawrey]

Afaik android doesn't have intrinsics for ByteBuffer / Unsafe. This should impact performance.

On 20 Mar 2014 23:27, "tm jee" <tmj...@gmail.com> wrote:

 If performance aren't an obvious issue, I'd rather go for methods like 2 array or any method that is obvious to anyone who reads the code. I'm just guessing Bytebuffer or not wouldn't make much of a difference even with reasonable array size. Just my 2 cents. Btw is good performance wise is ByteBuffer in ARM arch, just curious.

--