May 2014 - GiNaC-list

Re: [GiNaC-list] [PATCH] add configure option to enable deterministic sorting
by Valery Yundin 29 May '14

29 May '14

Hi, On 29 May 2014 07:31, Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> wrote: > I'm terribly sorry, but everything which makes the hash function worse > (slower or produces more collisions) is not acceptable. If you insist on that regardless of how it affects overall performance, it is not a technical problem and cannot be fixed with a patch. In any case, if my previous patches are not acceptable for whatever reasons GiNaC developers might have, I suggest to close this discussion by adding a configure option. So users can decide for themselves if (non-)determinism is worth few per-cent speed difference. Below is the simplest patch one can imagine. By default it keeps things as they are now. If user specifies --enable-determinism then make_hash_seed simply returns 0. Objects with the same calchash() implementation *and* the same contents *but* different types will have a hash collision, which be resolved in base::compare by using typeid_1.before(typeid_2) (on Linux it is a simple strcmp). Since it happens quite rarely (depends on a particular code of course), it is better than always using crc32 as in windows version of your code. In fact it can sometimes be faster than current "fast" hash. Best, Valery

1 0

[PATCH] fix bug/feature causing non-deterministic output
by Valery Yundin 29 May '14

29 May '14

Hi, Please see attached patch which fixes rather peculiar "feature" of GiNaC - non-determinism. One can think of many arguments why non-determinism of CAS is a bad idea. Shortly speaking, it is simply unacceptable. Especially when there is no good reason for it (and I can hardly think of a good reason anyway). At the moment GiNaC relies on OS-assigned memory addresses of type-names to define its term-ordering, which results in different output from the same program. When this bug was brought up in the mailing list (several times) the developers called it a "design decision". Well, it is time to stop the insanity. The attached patch fixes the bug at zero cost to the performance. Here are the results of "/usr/bin/time make check" (second run with pre-warmed caches) unpatched non-deterministic: 132.57 s fixed deterministic: 132.62 s Keep in mind that it wouldn't make GiNaC canonical ordering entirely predictable, since it still depends on the order of symbol declaration and such (btw, fixing that wouldn't be too hard either). But at least for the same program and compiler the result must be identical. PS I added FNV1a hash, one could just keep using crc32 which is already there. It makes no difference since the hash function is now called only once for each type (before it was called for every object). PPS I'm attaching patches against master and release_1-6-2 since I hope that developers recognize it as a bug and update stable releases as well. With best regards, Valery Yundin.

3 5

Re: [GiNaC-list] [PATCH] fix bug/feature causing non-deterministic output
by Valery Yundin 25 May '14

25 May '14

Hi, Updated patch, rev 3. Overloaded gethashseed() in a few classes which I missed before. Also modified gethashseed() to use "fast" hash for derived classes which do not overload it and made it independent of mangling scheme for non-template classes. Removed some debugging output. IMO "fast" hash can be removed entirely and if classes do not overload gethashseed() it will be taken care of by typeid. But since it is relevant only for custom user-defined classes, I don't care much. I kept it because GiNaC developers seem to have sentimental attachment to it. Best, Valery PS patch chunks have only 1 context line, because this list has post limit of 40kB With best regards, Mr. Valery Yundin. On 25 May 2014 18:44, Valery Yundin <yuvalery(a)gmail.com> wrote: > Hi, > > Updated patch, rev 3. > Overloaded gethashseed() in a few classes which I missed before. Also > modified gethashseed() to use "fast" hash for derived classes which do > not overload it and made it independent of mangling scheme for > non-template classes. Removed some debugging output. > > IMO "fast" hash can be removed entirely and if classes do not overload > gethashseed() it will be taken care of by typeid. But since it is > relevant only for custom user-defined classes, I don't care much. I > kept it since GiNaC developers seem to have sentimental attachment to > it. > > Best, > Valery

1 0

Possible bug in factor()
by tluthe＠physik.uni-bielefeld.de 18 May '14

18 May '14

Hi, there appears to be a bug in the multivariate factor() routine. For some expressions it seems to get stuck in an infinite loop, without any result or error messages appearing. The simplest expression I could find to reproduce this behaviour consistently is the expanded form of (3*x+2*y)*(x+y+x*y). For some other expressions (e.g. (x+2*y)*(x+y+x*y)) the problem occurs randomly, but not all the time. I'm guessing this is due to the randomness of the internal ordering of symbols. A minimal example code exhibiting the problem is attached. I've reproduced this bevahiour on openSuse and Ubuntu machines using GiNaC 1.6.2 and CLN 1.3.2. Regards, Thomas

2 1