2

I'm writing an A.I. to solve a "Maze of Life" puzzle. Attempting to store states to a HashSet slows everything down. It's faster to run it without a set of explored states. I'm fairly confident my node (state storage) implements equals and hashCode well as tests show a HashSet doesn't add duplicate states. I may need to rework the hashCode function, but I believe what's slowing it down is the HashSet rehashing and resizing.

I've tried setting the initial capacity to a very large number, but it's still extremely slow:

 val initCapacity = java.lang.Math.pow(initialGrid.width*initialGrid.height,3).intValue()
 val frontier = new QuickQueue[Node](initCapacity)

Here is the quick queue code:

class QuickQueue[T](capacity: Int) {

val hashSet = new HashSet[T](capacity)
val queue = new Queue[T]
    //methods below

For more info, here is the hash function. I store the grid values in bytes in two arrays and access it using tuples:

override def hashCode(): Int = {
  var sum = Math.pow(grid.goalCoords._1, grid.goalCoords._2).toInt
  for (y <- 0 until grid.height) {
     for (x <- 0 until grid.width) {
        sum += Math.pow(grid((x, y)).doubleValue(), x.toDouble).toInt
     }
     sum += Math.pow(sum, y).toInt
  }
  return sum
}

Any suggestions on how to setup a HashSet that wont slow things down? Maybe another suggestion of how to remember explored states?

P.S. using java.util.HashSet, and even with initial capacity set, it takes 80 seconds vs < 7 seconds w/o the set

kiritsuku
  • 52,967
  • 18
  • 114
  • 136
Tombstone
  • 157
  • 1
  • 13
  • 4
    That's a lot of calls to `Math.pow` in `hashCode`! You might want to cache the hash values. – Randall Schulz Feb 05 '13 at 19:09
  • 1
    Your hashCode function seems waaaay too computationally intensive. Something fast, using just bit fiddling would seem much better. – hatchet - done with SOverflow Feb 05 '13 at 19:18
  • I would recommend using immutable class to represent state and use `val` to cashe hashCode. Also, if you store the bytes in standard library collections, you can also use the hash function they provide directly. – Kane Feb 05 '13 at 19:23

2 Answers2

6

Okay, for a start, please replace

override def hashCode(): Int =

with

override lazy val hashCode: Int =

so you don't calculate (grid.height*grid.width) floating point powers every time you need to access the hash code. That should speed things up by an enormous amount.

Then, unless you somehow rely upon close cells having close hash codes, don't re-invent the wheel. Use scala.util.hashing.MurmurHash3.seqHash or somesuch to calculate your hash. This should speed your hash up by another factor of 20 or so. (Still keep the lazy val.)

Then you only have overhead from the required set operations. Right now, unless you have a lot of 0x0 grids, you are using up the overwhelming majority of your time waiting for math.pow to give you a result (and risking everything becoming Double.PositiveInfinity or 0.0, depending on how big the values are, which will create hash collisions which will slow things down still further).

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • If you are confident that most/every object's `hashCode` gets called, then you can avoid the `lazy` overhead. – ziggystar Feb 05 '13 at 20:25
  • @ziggystar - This is true but mostly irrelevant. `lazy val` takes a negligible amount of time compared to the rest of the hash set operations. – Rex Kerr Feb 05 '13 at 20:50
2

Note that the following assumes all your objects are immutable. This is a sane assumption when using hashing.

Also you should profile your code before applying optimization (use e.g. the free jvisualvm, that comes with the JDK).

Memoization for fast hashCode

Computing the hash code is usually a bottleneck. By computing the hash code only once for each object and storing the result you can reduce the cost of hash code computation to a minimum (once at object creation) at the expense of increased space consumption (probably moderate). To achieve this turn the def hashCode into a lazy val or val.

Interning for fast equals

Once you have the cost of hashCode eliminated, computing equals becomes a problem. equals is particularly expensive for collection fields and deep structures in general.

You can minimize the cost of equals by interning. This means that you acquire new objects of the class through a factory method, which checks whether the requested new object already exists, and if so, returns a reference to the existing object. If you assert that every object of this type is constructed in this way you know that there is only one instance of each distinct object and equals becomes equivalent to object identity, which is a cheap reference comparison (eq in Scala).

Community
  • 1
  • 1
ziggystar
  • 28,410
  • 9
  • 72
  • 124
  • 2
    The challenge with interning is avoiding over-retention of interned values, especially when they occupy a lot of main store. – Randall Schulz Feb 06 '13 at 02:49