Using a code generator for algorithms accessing char[] byte[] or CharBuffer and ByteBuffer....

[Kevin Burton]

From time to time I have to implement algorithms like Ahoo Corasick or Boyer-Moore or BMDiff, etc. that need to be performant...

And thanks to Java silliness most of these algorithms will work with char[] byte[] or CharBuffer and ByteBuffer ....

Now I *could* wrap them in CharBuffer or ByteBuffer but that seems wasteful.

I know ByteBuffer and CharBuffer implement intrinsics for these get() operations but I'm wondering if it would make sense to write a code generator that would generate code using the same algorithm only tailored for each data structure.

Either that or I'm overthinking this problem and the intrinsics are just fine.

But of course I still have to handle the case of CharBuffer *and* ByteBuffer even if intrinsics work.

[Vitaly Davidovich]

What intrinsics are you referring to? Only the direct buffers have intrinsics, the heap ones are straight java code.

Have you compared performance of hand tailored vs more generic version for one of these?

--
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.

[Kevin Burton]

I haven't compared them but I'm still stuck with the situation of having two different implementations for byte and char data.  

I wanted the ability to load a byte[] and search for text strings within it using boyer-more... this would work well for ASCII data without having to first convert it to a String or char[] 

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

[Gil Tene]

The unfortunate downside of buffer access (compared to array access) is that unlike array lengths, buffer limits are not final. This can force the buffer range check (against the limit) to remain in your loops, rather than get hoisted out of them as it would when iteration over an array... The JIT may sometimes be able avoid this by leveraging memory ordering rules, but any volatile access or non-inlined method call in your loop will pretty much force the range check to occur again...

A way around this, which applies to on-heap buffers, is to get the byte[] or char[] form the buffer (using array()), as well as the arrayOffset() and limit(), and then operate directly on the arrays. For off-heap buffers (direct, mapped, etc.) you won't be able to get the array, and would then be forced to operate using the buffer api (or resort to unsafe, which I am duty bound to avoid recommending).

Of course, this assumes that the extra range check costs actually happen, and actually make a material difference in your case. E.g. your code may be clean enough (no volatiles or non-inlined method calls) to eliminate the difference. Or maybe the range check hides well in the pipeline in your case, and costs close to nothing. So I'd check for a difference first: compare (with JMH) running you logic on an array with running the same logic on a buffer. And to avoid accidents, make sure the array being operated on is in a local variable (not a final field) when you do this measurement (see Nitsan's blog entry showing some surprising effects that can occur when mixing arrays in final fields with seemingly innocent volatile ops). 

[Martin Thompson]

If I need to work generically with ranges of bytes I typically fall back to using something like the UnsafeBuffer in Agrona.

https://github.com/real-logic/Agrona/blob/master/src/main/java/uk/co/real_logic/agrona/concurrent/UnsafeBuffer.java

[Vitaly Davidovich]

I'm looking forward to time when final fields are treated as constants, unlike the current sorry situation.  It's really sad that default behavior is to not trust final fields.

sent from my phone

--

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.

[Gil Tene]

We're working on it ;-)

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

[Vitaly Davidovich]

So I know Vladimir Ivanov (Oracle) is looking into this -- are you/Azul as well?

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.

--

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.

[Nitsan Wakart]

FWIW: a grep on vmSymbols.hpp shows there's a single relevant buffer related intrinsic:

   do_intrinsic(_checkIndex,               java_nio_Buffer,        checkIndex_name, int_int_signature,            F_R)

Here: http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/tip/src/share/vm/classfile/vmSymbols.hpp#l766

Direct buffers may use (if unaligned access is allowed on the platform) Unsafe for reading larger than byte chunks e.g.:

    private int getInt(long a) {

        if (unaligned) {

            int x = unsafe.getInt(a);

            return (nativeByteOrder ? x : Bits.swap(x));

        }

        return Bits.getInt(a, bigEndian);

    }

And unsafe.getInt is an intrinsic.

[Vitaly Davidovich]

I tend to look at library_call.cpp for intrinsics, which is what C2 uses.  It has this note for checkIndex:

 case vmIntrinsics::_checkIndex:
    // We do not intrinsify this.  The optimizer does fine with it.
    return NULL;

The above makes sense since there's nothing "special" about the checkIndex(int,int) method.  And yes, direct buffers "have intrinsics" in the sense that the underlying Unsafe accessors are intrinsified.

[Kevin Burton]

On Tuesday, December 1, 2015 at 10:13:50 PM UTC-8, Gil Tene wrote:

The unfortunate downside of buffer access (compared to array access) is that unlike array lengths, buffer limits are not final. This can force the buffer range check (against the limit) to remain in your loops, rather than get hoisted out of them as it would when iteration over an array... The JIT may sometimes be able avoid this by leveraging memory ordering rules, but any volatile access or non-inlined method call in your loop will pretty much force the range check to occur again...

Yup. This is one reason I was thinking that for all use cases a code generator could build optimal / clean code for each case and it would also be easy to read.