must be a faster way (in SPIN)

Bobb Fwed

I am generating a hash value to use as a table address. I want it to return an even number between (and including) 0 and less than the specified table size (which is a multiple of 32 or 64). For example, the table size can be 128, and I want the hash to give me an even value between 0 and 126 (inclusive).

In the past, I required the table size to be a value that was a exponential value of 2. This allowed me to just binary-AND it to the value range I need.

[hash is a generated value that can be any 32-bit value]

Previous code:

hash &= constant(table_size - 2) ' takes 1008 cycles

Now, with the new number requirement, this is the fastest/best I can think of in the half hour I've been pondering it as I program other things:

hash := (||hash // constant(table_size / 2)) << 1 ' takes 1760 cycles (175% of the original time)

This is way slower than before, and I was hoping someone on the forum here would know a faster way to get the same result. Even the smallest increase in speed would be helpful, as this method is called constantly throughout the object.

AndreL

The problem with spin is its not an optimizing compiler, so doing things that normally would seem to be faster are in fact slower. So, things to try are the order you do things and any kind of pre-computed lookups you can do for a partial calculation that can be used in the final calculation. Also, try making code LONGER can actually make it faster in some cases with spin.

Andre'

Mike Green

The main difference is that you're now using division rather than a logical-and operation. Division is probably the slowest operator in Spin. That's why hash tables tend to come in sizes of powers of 2, particularly when using microcontrollers without hardware divide instructions.

Phil Pilgrim (PhiPi)

What is your hash function? Maybe it can be modified, in consideration of the table size, to limit its range.

-Phil

potatohead

Just do "
"table_size >> 1", instead of "table_size / 2" That will be a nice speed boost to the expression you showed us right there.

Shift right = divide by two, shift left = multiply by two. Another speed boost would be to get rid of the modulo, using shifts and adds to get to the proper table size. A few of those is quicker than one modulo, so you might see another gain doing that.

Best speed is a table that is a power of two, as was noted above.

MagIO2

@Potatohead:
This will be a non-booster ;o) He put the division into a constant statement, so it won't be executed at runtime at all. Nevertheless the tip is valid for other code.
And Bobb came from a power to two table size.

@Bobb:
Don't have the time currently to think about the problem in detail but here are my intermediate thoughts:
Create a bitmask dereived from table_size by simply setting all the least significant bits to 1 except bit 0 which is always 0. For example
table_size = %1001_1101 would then give a mask %1111_1110

This you can do by defining it as constant or if the table_size can change during runtime you'd only do at the time the size changes.
Then you and the hash with this mask as you did it with power of two table sizes.
Then you only need an if statement which checks if the hash is bigger than table_size and if so subtract the table_size from the hash.

Maybe this is faster.

potatohead

Of course! I completely misread that.

max72

As an alternative have you considered spinLMM? If you are looking for a spin only solution to spare a COG it could be a good option.
Massimo

Bobb Fwed

Sorry, for the late reply. Thank you for all the information so far, I didn't have access to the program over the weekend, so here it the hash function.

Phil Pilgrim (PhiPi) wrote: »

What is your hash function? Maybe it can be modified, in consideration of the table size, to limit its range.

-Phil

PRI gethash (nameAddr) : hash | i, length 
' return a simple checksum within the confines of table_size                  

  length := strsize(nameAddr) - 1

  hash := $55555555                                                             ' alternating 1s and 0s
  REPEAT i FROM 0 TO length
    hash += byte[nameAddr + i] + hash << 5

  hash := (||hash // constant(table_size / 2)) << 1                             ' even numbers 0 through table_size

Dave Hein

You are subtracting 1 from the strsize, which means that the last character is not included in the hash code. I don't know if that intentional or not. I believe you can speed up the loop if you write it as follows:

  repeat length
    hash += byte[nameAddr++] + hash << 5

Beau Schwabe

Bobb Fwed,

Since your table_size is essentially a power of 2, you can use the bitwise AND operator rather than the Modulus operator. That shaves 512 cycles off of your 1760.

Phil Pilgrim (PhiPi)

Dave,

He's doing it right. The range 0 .. strsize - 1 covers all the bytes.

-Phil

Bobb Fwed

@Dave, the strsize -1 thing is to keep the correct number of loop executions, because the loop starts at 0, not 1, so the counting needs to be adjusted. It is done correctly.
Yes, the reworked loop speeds things up. I remember now wanting to do that at one point, but it affects the output, so I didn't. But now I am requiring the tables to be rewritten after this version, because there are too many changes, so it's all good.

@Beau, I am trying to remove the power of two requirement. Currently it is required, but I'm trying to make the program more flexible to allow more precise use of the EEPROM.

Bobb Fwed

And because the REPEAT value is only evaluated once, I was able to remove the length storage to the variable. Here is the new method (which is faster than the old method even with the slow modulus stuff):

PRI gethash (nameAddr) : hash 
' return a simple checksum within the confines of table_size                  

  hash := $55555555                                                             ' alternating 1s and 0s
  REPEAT strsize(nameAddr)
    hash += byte[nameAddr++] + hash << 5

  hash := (||hash // constant(table_size / 2)) << 1                             ' even numbers 0 through table_size

I assume the strsize -1 thing is to ignore the terminating byte

That's definitely not true in this version of the method, so the -1 has been removed.