GiNaC-devel

Download

ginac-devel@ginac.de

April 2002

2 participants
2 discussions

Fibonacci Hashing revisted
by Richard B. Kreckel 02 May '02

02 May '02

Hi, As a sequel to that thread about Fateman's fast mult benchmark I have growing qualms about our hashcode generation. First, the observations made in basic::compare(const basic&): 1) Hardly ever a hash collision between different types occur while hash collissions between different types are very frequent. This suggests that something is better in one case than in the other. 2) Of course, there are unavoidable collisions when two equal objects are compared. These amount to about 2/3 of all cases. In other words: 1/3 of all collisions result in a call to compare_same_type() and a subsequent traversal. This seems way too much, given a hash-space of 31 bit. (More on that later.) 3) Applying a unary ~ on the hash-values of class numeric (i.e. inverting all bits) reduces the number of collisions by about 20% and results in a speedup of about 10%. As a crude estimate we could deduce a potential speedup factor two(!), given an ideal collision-free hashing. No, I don't expect this to happen, but maybe 50% should be doable. What's wrong with our hashing? I am still trying to find out. Right now, what I have is this: a) CLN's hashes are sub-optimal for our purposes. Basically, they seem to populate too few bits for the frequent small numbers. Maybe that can be improved. This results in some funny collisions due to some fundamental properties of the binary number system. That should be easy to improve even without changing anything in CLN. (I hesitate doing this in CLN since I have no idea what other people are using cln::equal_hashcode() for.) b) We rotate the bits in expairseq::calchash() before xoring with the next element. I doubt this makes sense. The rotation is done in order to have h(h(X),h(Y)) be different from h(h(Y),h(X)). This looks superfluous to me, since the elements of expairseq are canonicalized anyways when the hashing occurs so commutativity should be a non-issue. c) The split-up of our hash space into two halves, one for numeric hashes and one for non-numeric hashes effectively throws away one valuable bit. As far as I can recall, there were some historic reasons why this was done (initially, we didn't have hashes for numeric types). However, if one would like to try out the hashtab-based class expairseq again, then the implementation seems to demand that split-up. See expairseq::calc_hashindex(const ex&) for the only occurrence of the is_a_numeric_hash() macro. Hmm, I fail to see the theoretical reason why hashtabs need such a trick. Since I very much like to introduce one clean globalized hash space, I need to remove this code. Is it really needed? Why? Call for help: Does anyone know more about this stuff? (Alex, maybe you, since you wrote it long ago?!?) Regards -richy. -- Richard B. Kreckel <Richard.Kreckel(a)Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>

2 3

Re: Form is really slow and fast for me. What could this mean?
by FORM Administrator 17 Apr '02

17 Apr '02

In the single line example FORM will definitely not look for common subexpressions and try to evaluate them separately. That is completely against its philisophy. There you would have to help it a bit. Note that it will always be possible to invent benchmarks like this that give poor performance. Actual performance is what counts most. Cheers Jos Vermaseren

1 0