quil-rs icon indicating copy to clipboard operation
quil-rs copied to clipboard

Hashing Expressions should be fast

Open kalzoo opened this issue 1 year ago • 2 comments

This expression appears to take over 2 minutes to hash on a decent laptop using the default Rust SipHasher:

(6.283185307179586*(-((-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(-((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+(1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)+1830.4305845069357))+2997.220957806505) - ((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+3082.921997445349)+-((-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+(-((-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(-((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+(1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)+1830.4305845069357))+2997.220957806505) - ((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+3082.921997445349)+(1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+-((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527))+3552.7822825370968) - ((-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(-((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+(1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)+1830.4305845069357))+2997.220957806505) - ((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+3082.921997445349)+(((1827.142690137572+-(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702) - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - ((-3.141592653589793+gamma[0]*-1.3670709112264738)/6.283185307179586+1293.2884354900702)+1830.4305845069357))+(2404.366183299857+(-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+(1292.2571023206997 - (-3.141592653589793+(gamma[0]*-1.3670709112264738)/6.283185307179586)+1293.2884354900702)) - 2473.4667568746527)+3654.308518679512+(-3.141592653589793+gamma[0]*-1.4598346220303238)/6.283185307179586)))+0.4345210910722077)/6.283185307179586

While there is some complexity in hashing expressions in the current implementation, this should still not take that long. This suggests moving forward on past conversations about separating (normalizing) from (equality checking) so that the latter would be fast and cheap.

Additionally, quil-rs considers this expression to be maximally simplified, which is surprising and likely stands to be improved.

kalzoo avatar Jul 14 '23 22:07 kalzoo