1

I thought up a simple and efficient way to combine states with events to make event handling more efficient. My idea of state checking involves State objects that hold reference to mutable variables in an object.

I figure that using a sort of hashCode() for an Object and checking between the two states would be more efficient than iterating over the contents of a State object and comparing to the target state.

Problem is, hashCode() isn't calculated on a per-state basis. Is there some method similar to hashCode() that I can use to compare two states without comparing their contents directly and is cheap on CPU usage?

Edit: I didn't realize hashCode() is on a per-state basis.

  • you can optimize the state check by first checking the the hashcode of each field before checking equality. – ratchet freak Jun 2 '15 at 15:56
  • @ratchetfreak I'm trying to avoid iteration, and that would require it. – AMDG Jun 2 '15 at 15:59
  • You may implement hashCode so it only depends of the state, it will be still a valid implementation. It might be undesirable to use in maps (apart from being mutable) because of a possible high number of collisions. Or maybe I am missing your point. – SJuan76 Jun 2 '15 at 18:33
  • @LinkTheProgrammer Lock post? Are you asking for your post to be put on hold? – candied_orange Jun 4 '15 at 1:34
  • @CandiedOrange I'm asking for the post to die and go to nirvana. – AMDG Jun 4 '15 at 3:22
3

You are looking for hashCode() plus a few of the optimizations and overhead associated with it found in other Java classes.

If the hash code is different, than the state is different. That is part of the contract of hashCode(). However, comparing two hash codes generated on the fly for two objects is just as expensive (and possibly more so because the complete state must be interrogated in order to create the hash code while .equals(T object) can bail out early).

Thus, you go to caching the hash code once you compute it so you only need to generate it once. However, that 'only generate it once' is 'only generate it once per state'. If the object is an immutable, then you can cache it as soon as it is asked for and return that cached value forever more. This can be seen in String.hashCode(). String will return the computed hash code if it has already been computed.

However, if the object is mutable, each time you mutate the object you will need to invalidate the hash code that has been generated previously. This is where the overhead comes in.

All that said, the simple and understandable thing to do that doesn't add complexity to your code is to use equals(T object). Test the most likely mutated fields first and let the JIT optimizer do its thing.

  • Oh, so hashCode() is on a per-state basis? Then how does a HashMap work if the objects change, and the hashCode() becomes different? – AMDG Jun 2 '15 at 16:03
  • 5
    @LinkTheProgrammer you enter the realm of "here be dragons" if you have a HashMap where the key is mutable and mutates. Don't do that. – user40980 Jun 2 '15 at 16:04
  • Then why does HashMap call hashCode() for objects it contains? – AMDG Jun 2 '15 at 16:06
  • 4
    @LinkTheProgrammer Simple answer: It doesn't. ;-) Using mutable Objects as keys in a HashMap (or elements of a HashSet) is erroneous. If the hashCode changes, the objects can't be equal anymore and therefore cannot be used in such a way. – Ray Jun 2 '15 at 16:07
  • 1
    @LinkTheProgrammer: I encourage you to read Eric Lippert's Guidelines and rules for GetHashCode. It was written from the perspective of C#, but the guidelines are basically the same. – Brian Jun 2 '15 at 16:08
1

It's not entirely clear what you're looking for. But if you want to detect state change events without laborious comparison it's a well proven pattern to use a version indicator. That can be as simple as a counter that is incremented each time any relevant data is modified.

Depending on the purpose you might encounter one of two classes of problems. First is the AA problem. The set method of property with the value A is called with the value A. A naive implementation records a change (by incrementing the version counter) but nothing actually changed. Second is the ABA or ABC problem. If a set method is called twice before a 'monitor mechanism' visits the object again it will miss state B and may (in the ABA case) entirely miss that a change 'really' occurred.

That might not matter. It might make the program slightly less efficient (causing say screen updates that in fact change nothing) or worse break logic.

  • This incrementing based on state change is a good idea for non-realtime programs I would suppose. I would prefer a way to do so on the fly. In my case, every nanosecond counts. And proven by all those problems which can be encountered due to race conditions, that's the last problem I need and overly complex. – AMDG Jun 2 '15 at 16:31
  • Unless you're going to emit a message (to a monitor) when state changes I would say for nanosecond counts of 'did something here just change' then a version counter is indicated (not contra-indicated). It's partly a matter of whether you need to respond to all changes or just know if there were changes since your last visit. – Persixty Jun 2 '15 at 16:37
  • Well, events are on a "last-visit" basis. – AMDG Jun 2 '15 at 16:38
  • 1
    @LinkTheProgrammer before you give up on avoiding iteration let me ask, do you know how the observer pattern works? – candied_orange Jun 3 '15 at 1:05
  • 1
    @LinkTheProgrammer how passive is passive? The observer pattern is flexible enough to let you dump a reference to every updated object in a queue that you can process (inspect state) whenever you like, as passively as you like. Thus avoiding iterating over things that haven't changed. When you process and when you clear the queue are completely decoupled from when state changes. If, rather than passive, you decide to be aggressive about clearing the queue, look into the producer consumer pattern. – candied_orange Jun 4 '15 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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