Hashing Performance in SimpleHashableState

[addy90]

While doing performance profiles, I noticed that in the IISimpleHashableState-Class in the valuesEqual()-Method the isArray()-Call is used. That call has a quite bad performance and perhaps it can be replaced by something more efficient... like you can see here: http://stackoverflow.com/questions/16170548/object-isarray-is-slow-is-there-a-fast-way-to-do-that

Perhaps by replacing with instanceof Object[] like supposed on stackoverflow we get a significant performance gain in the HashableState Comparison as the isArray()-Methods are called for every variable compared... Just a suggestion! Maybe there are more places like this in the code, you should do a search for "isArray" maybe...

[jmacglashan]

An interesting thought. I'll have to look into it and see if it improves things (or if you can run some tests to check, that would be helpful). I think the Apache HashCodeBuilder it uses unfortunately does isArray checks too.

FWIW though, HashableStateFactory objects are designed to be interchangeable. SimpleHashableStateFactory is just the most simple (heh) and safe catchall approach (and from which the standard abstraction methods provided derive)

However, if performance is an issue, it is wholly encouraged to write your own state-specific HashableStateFactory that is as fast as possible.

Alternatively, if it's your own domain and you'll only need to do one kind of equality for it, you can implement hashcode and equals in the State definition in the most efficient way you can and have the State implement HashableState (with the s() method turning itself), and then use a ReflectiveHashableStateFactory, which will just use the standard implemented methods on the state.

[addy90]

I made various tests with replacing isArray but finally tried out the benchmark I linked to on stackoverflow. Well the result is kind of annoying... it looks like the Java VM already optimized this case.

These are my results of the same benchmark that was linked on stackoverflow:
{s instanceof Object[]} spends 14ms
{s.getClass().isArray()} spends 14ms
{s.getClass().getName().charAt(0) == '['} spends 16ms

That was the same in my tests I did this afternoon. Though in the Profiler, one can see that the isArray() Method uses a lot of time, when I replace it with instanceof Object[](so that the software works as before), the time it needs stays the same, it just is not used within isArray() anymore.

So after all this never was an issue, it just looked like one that fooled both of us - I am sorry for that.
The reason I was digging this deep around is that I am writing several Reflection-Classes for building domains via Annotations so that ObjectInstances, PropositionalMethods, RewardMethods, SampleStates, OOStates and all of that are generated by the Reflection-Classes.

Of course this approach leads to two problems: Performance and what happens if you have special problems that the reflection classes do not cover. Well in the latter one you need to write your own code again or expand the reflection classes until they cover all possibilities. For my special problem I do the latter as it keeps the composition of the classes away so that I can focus on the domain variables, actions and method implementations with having dependency injection that calls my methods with the right objects already casted (and no String[] params variables). It's some kind of simplification.

What I want is that this approach is not much slower than the normal way from the tutorials. And it indeed is possible to be nearly as fast with two ideas: Caching and MethodHandles. So while building the domain via reflecting the classes, I generate MethodHandles that I later can call nearly as fast as native calls. And I cache all that so when the planning runs it uses the already created MethodHandles. Well and while digging with the StateHashing (like I can annotate a field wether it is relevant for the state hash or not, what is the reason why I use the MaskedHashableState) I found that "issue".

So at the moment, I am depending heavily on your provided HashableStateFactories as I am mostly optimizing for usability though still thinking of the performance so that it does not become too slow, which works quite good for now... but it is not finished, just something I am trying for being able to work faster with BURLAP.

[brawner]

I'm not sure if this functionality exists in burlap 3, but I had fairly
good results by using immutable states (copy on write) that also used
immutable objects and attributes. When new states were created by taking
actions, they just modified the attributes and objects that were necessary,
and kept references to everything else. I believe this has been carried
forward into burlap 3.

The advantage of this with regard to hashing, is that you can write a
HashFactory, and associated HashedState that cache the hash values. Then,
only the modified objects and values need to be rehashed. It can
significantly reduce cache times, which has large advantages in state
exploration.

James, does this functionality exist in burlap 3 at the moment?

On Tue, Aug 9, 2016 at 12:20 PM, Adrian [email protected] wrote:

I made various tests with replacing isArray but finally tried out the
benchmark I linked to on stackoverflow. Well the result is kind of
annoying... it looks like the Java VM already optimized this case.

These are my results of the same benchmark that was linked on
stackoverflow:
{s instanceof Object[]} spends 14ms
{s.getClass().isArray()} spends 14ms
{s.getClass().getName().charAt(0) == '['} spends 16ms

That was the same in my tests I did this afternoon. Though in the
Profiler, one can see that the isArray() Method uses a lot of time, when I
replace it with instanceof Object
http://so%20that%20the%20software%20works%20as%20before, the time it
needs stays the same, it just is not used within isArray() anymore.

So after all this never was an issue, it just looked like one that fooled
both of us - I am sorry for that.
The reason I was digging this deep around is that I am writing several
Reflection-Classes for building domains via Annotations so that
ObjectInstances, PropositionalMethods, RewardMethods, SampleStates,
OOStates and all of that are generated by the Reflection-Classes.

Of course this approach leads to two problems: Performance and what
happens if you have special problems that the reflection classes do not
cover. Well in the latter one you need to write your own code again or
expand the reflection classes until they cover all possibilities. For my
special problem I do the latter as it keeps the composition of the classes
away so that I can focus on the domain variables, actions and method
implementations with having dependency injection that calls my methods with
the right objects already casted (and no String[] params variables). It's
some kind of simplification.

What I want is that this approach is not much slower than the normal way
from the tutorials. And it indeed is possible to be nearly as fast with two
ideas: Caching and MethodHandles
https://docs.oracle.com/javase/8/docs/api/java/lang/invoke/MethodHandles.html.
So while building the domain via reflecting the classes, I generate
MethodHandles that I later can call nearly as fast as native calls. And I
cache all that so when the planning runs it uses the already created
MethodHandles. Well and while digging with the StateHashing (like I can
annotate a field wether it is relevant for the state hash or not, what is
the reason why I use the MaskedHashableState) I found that "issue".

So at the moment, I am depending heavily on your provided
HashableStateFactories as I am mostly optimizing for usability though still
thinking of the performance so that it does not become too slow, which
works quite good for now... but it is not finished, just something I am
trying for being able to work faster with BURLAP.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#132 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AA_x-jDa9ZnMBV3opeGj4r-oC1K-RR6Qks5qeKi5gaJpZM4Jf_6t
.

[jmacglashan]

Yes, the immutable paradigm more or less does exist in BURLAP 3 because domains now always implement their own State objects and State "copying" can be done shallow or deep. (Also, a lot of the existing domains do use shallow copying).

Given that, it is also absolutely possible to design the state to cache the hash codes so they don't get recomputed and curry them forward with any state "copying."

So yes, for optimizing a domain, that is definitely a viable path.