Possible size issue in test in numeric.cpp
Hi. We're using GiNaC inside our multibody analysis software MBDyn to perform automatic differentiation of constitutive laws for deofrmable elements. Right now its use is not very intensive, but we plan to extend it quite soon. I haven't built GiNaC for a while, and today, rebuilding a 1.3.4 rpm, I noticed a warning in numeric.cpp. First, a note on the system: it's an AMD Athlon 64, running CentOS 4.2, which means stock RedHat gcc/g++ 3.4.5. I haven't checked with gcc 4.X yet, but the issue seems to be clear enough. The warning is at line 95 of ginac/numeric.cpp and it didn't change from GiNaC 1.3.4 to today's CVS: [masarati@ando ginac]$ make numeric.o if g++ -DHAVE_CONFIG_H -I. -I. -I.. -g -O2 -MT numeric.o -MD -MP -MF ".deps/numeric.Tpo" -c -o numeric.o numeric.cpp; \ then mv -f ".deps/numeric.Tpo" ".deps/numeric.Po"; else rm -f ".deps/numeric.Tpo"; exit 1; fi numeric.cpp: In constructor `GiNaC::numeric::numeric(int)': numeric.cpp:95: warning: comparison is always true due to limited range of data type numeric.cpp:95: warning: comparison is always true due to limited range of data type The constructor of "numeric" that takes an "int" as its argument "i" performs the test i < (1L << (cl_value_len-1)) On my system, "cl_value_len" is 32; so, "1L << 31" is out of range for an "int". Then, the test i >= -(1L << (cl_value_len-1)) follows, which is again out of range for an int. It took a while to figure out what that code was intended for. It appears that cln uses few bits of an int, on 32 bit architectures, to store reserved metainformation; on the contrary, on architectures with 64 bit pointers, the whole int range is available. My guess is that the test is incorrect on those architectures, but I admit I haven't investigated enough. I've placed a patch at <http://mbdyn.aero.polimi.it/~masarati/Download/mbdyn/ginac-numeric.patch>, please review or feel free to fix as appropriate, in case I'm missing anything obvious. Sincerely, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
Dear Pierangelo, On Sun, 6 Aug 2006, Pierangelo Masarati wrote:
numeric.cpp:95: warning: comparison is always true due to limited range of data type numeric.cpp:95: warning: comparison is always true due to limited range of data type
The constructor of "numeric" that takes an "int" as its argument "i" performs the test
i < (1L << (cl_value_len-1))
My guess is that the test is incorrect on those architectures, but I admit I haven't investigated enough.
I'm not a CLN expert either, but to me it does not seem that the code is incorrect. On the AMD 64 platform it is apparently always okay to apply the constructor cl_I(int) no matter how large the integer argument is. If the compiler is smart enough, it will automatically do what your patch is doing (i.e., throw the if out of the code), so I fail to see benefits from your patch. Best wishes, Chris
Chris Dams writes:
My guess is that the test is incorrect on those architectures, but I admit I haven't investigated enough.
I'm not a CLN expert either, but to me it does not seem that the code is incorrect. On the AMD 64 platform it is apparently always okay to apply the constructor cl_I(int) no matter how large the integer argument is. If the compiler is smart enough, it will automatically do what your patch is doing (i.e., throw the if out of the code), so I fail to see benefits from your patch.
OK, my main concern was about removing a couple annoying warnings (BTW: congratulations: they were the only warnings in the whole package, which seems pretty unusual to me, and a good programming practice). However, as far as I understand, although the code being safe, a test and a cast will always occur even if it's never required. It's not a big deal, I concur, but it looks like a misuse of the CLN definitions. My 2c. Cheers, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
Dear Pierangelo, Pierangelo Masarati schrieb:
Chris Dams writes:
My guess is that the test is incorrect on those architectures, but I admit I haven't investigated enough.
I'm not a CLN expert either, but to me it does not seem that the code is incorrect. On the AMD 64 platform it is apparently always okay to apply the constructor cl_I(int) no matter how large the integer argument is. If the compiler is smart enough, it will automatically do what your patch is doing (i.e., throw the if out of the code), so I fail to see benefits from your patch.
OK, my main concern was about removing a couple annoying warnings (BTW: congratulations: they were the only warnings in the whole package, which seems pretty unusual to me, and a good programming practice). However, as far as I understand, although the code being safe, a test and a cast will always occur even if it's never required. It's not a big deal, I concur, but it looks like a misuse of the CLN definitions. My 2c.
thanks for your patch! We had a discussion about it on the other GiNaC mailing list (ginac-devel) and we are going to apply it. It will be part of the forthcoming 1.3.5 release then. @Richy: You wondered why the other ctor for unsigned int doesn't raise such a warning. After looking at the code I now wonder whether the code there is optimal. The argument is compared against 2^(cl_value_len-1) and not 2^(cl_value_len)-1 as one might expect. Maybe this should be changed? Could you comment on this soon, because I'd like to roll the release this evening? Regards, Jens
Jens Vollinga writes:
thanks for your patch! We had a discussion about it on the other GiNaC mailing list (ginac-devel) and we are going to apply it. It will be part of the forthcoming 1.3.5 release then.
@Richy: You wondered why the other ctor for unsigned int doesn't raise such a warning. After looking at the code I now wonder whether the code there is optimal. The argument is compared against 2^(cl_value_len-1) and not 2^(cl_value_len)-1 as one might expect. Maybe this should be changed? Could you comment on this soon, because I'd like to roll the release this evening?
I agree it should be i < ((1UL << cl_value_len)-1) In this case, a fix similar to the "int" case on 64 bit architectires would apply, since a "unsigned" will always be less than 2^32. A patch is available at <http://mbdyn.aero.polimi.it/~masarati/Download/mbdyn/ginac-numeric-uint.pat ch> Cheers, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
Dear Pierangelo, Pierangelo Masarati schrieb:
Jens Vollinga writes:
@Richy: You wondered why the other ctor for unsigned int doesn't raise such a warning. After looking at the code I now wonder whether the code there is optimal. The argument is compared against 2^(cl_value_len-1) and not 2^(cl_value_len)-1 as one might expect. Maybe this should be changed? Could you comment on this soon, because I'd like to roll the release this evening?
I agree it should be i < ((1UL << cl_value_len)-1)
well, I have to correct myself: it should be i < (1UL << cl_value_len) I guess.
In this case, a fix similar to the "int" case on 64 bit architectires would apply, since a "unsigned" will always be less than 2^32. A patch is available at <http://mbdyn.aero.polimi.it/~masarati/Download/mbdyn/ginac-numeric-uint.pat ch>
thanks, but I've already done that :-) But still I want to wait for Richy's response before I put it in CVS, because it could be that CLN uses a signed data representation for small integers internally (crazy idea, but conceivable ... ;-)) so that the original if clause might be correct. Regards, Jens
Jens Vollinga writes:
I agree it should be i < ((1UL << cl_value_len)-1)
well, I have to correct myself: it should be i < (1UL << cl_value_len) I guess.
Right, sorry. I obviously had <= in mind :)
But still I want to wait for Richy's response before I put it in CVS, because it could be that CLN uses a signed data representation for small integers internally (crazy idea, but conceivable ... ;-)) so that the original if clause might be correct.
Looking at recent CLN stuff, I see that the internal representation of any type of data is a word, which is basically a "cl_uint" (in cln/object.h: typedef uintP cl_uint; // This ought to be called `cl_word'. where typedef unsigned long uintP; :) It doesn't really care about signedness until the value is extracted and shifted back to its position. I haven't looked into CLN's CVS yet, though, but this looks like something that shouldn't change quite often. However, since applications using CLN shouldn't be aware of those details, I'm getting convinced that the optimization you're trying to obtain in numeric.cpp should actually be moved to CLN, in the sense that being CLN a likely candidate as a building block for higher-level numerical libraries (like GiNaC, for example), it should provide means for safe and efficient machine and OS independent conversion between its internal representation and built-in types. Details about how to implement it are beyond the scope of this message; it could be by providing standard limits for the builtin types (like INT_MAX, UNIT_MAX and so in limits.h) or a test (sort of SAFE_CAST_TO_INT(x), SAFE_CAST_TO_UINT(x) and similar) or so. Cheers, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
Hi! Pierangelo Masarati wrote:
Looking at recent CLN stuff, I see that the internal representation of any type of data is a word, which is basically a "cl_uint" (in cln/object.h: typedef uintP cl_uint; // This ought to be called `cl_word'. where typedef unsigned long uintP; :) It doesn't really care about signedness until the value is extracted and shifted back to its position.
Correct.
I haven't looked into CLN's CVS yet, though, but this looks like something that shouldn't change quite often.
Correct.
However, since applications using CLN shouldn't be aware of those details, I'm getting convinced that the optimization you're trying to obtain in numeric.cpp should actually be moved to CLN, in the sense that being CLN a likely candidate as a building block for higher-level numerical libraries (like GiNaC, for example), it should provide means for safe and efficient machine and OS independent conversion between its internal representation and built-in types. Details about how to implement it are beyond the scope of this message; it could be by providing standard limits for the builtin types (like INT_MAX, UNIT_MAX and so in limits.h) or a test (sort of SAFE_CAST_TO_INT(x), SAFE_CAST_TO_UINT(x) and similar) or so.
This is documented in chapter 3.4 "Conversions". Cheers -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Richard B. Kreckel writes:
This is documented in chapter 3.4 "Conversions".
Right, I stopped reading too early. Anyway, what would be needed by GiNaC in this case, as far as I can tell, is only the test portion, without conversion. For example, borrowing from CLN's notation: bool cl_int_needs_heap(const int x) bool cl_uint_needs_heap(const unsigned int x); which basically checks whether a C int or unsigned will be stored by CLN without heap allocation. This is based on the assumption that, at some point, the 2^29 limit may move to some other value (because you need more tags, for example). Yet another approach (possibly the safest) would be to remove the 2^29 limitation in the cl_I::cl_I(const int) constructor, and let the constructor test for the value of the int. I feel I'm really drifting off-topic here; this discussion should really move to cln-list (if interesting at all). Cheers, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
Richard B. Kreckel writes:
I haven't looked into CLN's CVS yet, though, but this looks like something that shouldn't change quite often.
Correct.
Actually, playing with CLN's CVS HEAD I found that cl_value_len is no longer limited to 32 bits; right now, on my machine, it results into 64 - 3 (the #if (cl_pointer_size == 64) #define cl_value_shift 32 #else #define cl_value_shift (cl_tag_len+cl_tag_shift) #endif that was present at least in CLN 1.1.11 has now been turned into #define cl_value_shift (cl_tag_len+cl_tag_shift) so #define cl_value_len (cl_pointer_size - cl_value_shift) now is 61 instead of 32). So I'm back to the above warning, i.e. that comparing (int(i) < (1UL << 61)) is always true and so forth. Cheers, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
Hi! Jens Vollinga wrote:
Pierangelo Masarati schrieb:
Jens Vollinga writes:
@Richy: You wondered why the other ctor for unsigned int doesn't raise such a warning. After looking at the code I now wonder whether the code there is optimal. The argument is compared against 2^(cl_value_len-1) and not 2^(cl_value_len)-1 as one might expect. Maybe this should be changed? Could you comment on this soon, because I'd like to roll the release this evening?
I agree it should be i < ((1UL << cl_value_len)-1)
well, I have to correct myself: it should be i < (1UL << cl_value_len) I guess.
In this case, a fix similar to the "int" case on 64 bit architectires would apply, since a "unsigned" will always be less than 2^32. A patch is available at <http://mbdyn.aero.polimi.it/~masarati/Download/mbdyn/ginac-numeric-uint.pat ch>
thanks, but I've already done that :-)
But still I want to wait for Richy's response before I put it in CVS, because it could be that CLN uses a signed data representation for small integers internally (crazy idea, but conceivable ... ;-)) so that the original if clause might be correct.
For small integers, CLN uses immediate types (no heap allocation). They occupy cl_value_len bits. (Not all bits inside a word can be used, because some bits must be reserved for tagging heap-allocated objects.) Now, these integers of cl_value_len bits are signed: 2^(cl_value_len-1)...2^(cl_value_len-1)-1. The GiNaC code we are discussing uses different ctors, one from int and one from unsigned int, which both result in the same immediate type. There is no unsigned immediate type! For large numbers it must use some ctor that is not prone to rollover errors. (For reasons of performance, such rollover errors were deemed acceptable in CLN for int types, since when coding with ints, one has to be aware of these rollover errors anyway. In GiNaC, I didn't want to incur such behavior. Hence, the if statement.) The current code is correct. In the ctor from int, we can test that the undesired rollover starts at (1L << (cl_value_len-1)) and below -(1L << (cl_value_len-1))). Actual numbers are from a 32-bit system where cl_value_len is 30. They might be different on other machines. int i; cl_I X; i = (1L << (cl_value_len-1)); X = i; cout << i << " and " << X << endl; // bad: 536870912 and -536870912 i = i - 1; X = i; cout << i << " and " << X << endl; // good: 536870911 and 536870911 i = -(1L << (cl_value_len-1)); X = i; cout << i << " and " << X << endl; // good: -536870912 and -536870912 i = i - 1; X = i; cout << i << " and " << X << endl; // bad: -536870913 and 536870911 In the ctor from unsigned, we can verify that the undesired rollover is at the same point: unsigned i; cl_I X; i = (1UL << (cl_value_len-1)); X = i; cout << i << " and " << X << endl; // bad: 536870912 and -536870912 i = i - 1; X = i; cout << i << " and " << X << endl; // good: 536870911 and 536870911 Now, you seem to be suggesting to test against twice that value, i < (1UL << cl_value_len). This is going to lead to undesired behavior: unsigned i; cl_I X; i = (1UL << cl_value_len) - 1; X = i; cout << i << " and " << X << endl; // bad: 1073741823 and -1 HTH -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Richard B. Kreckel writes: [snip] Also, CLN's documentation states that |i| < 2^29, which means that the test in GiNaC for integers could be broken as well, as it does i >= -(1L << (cl_value_len-1)) which allows |i| == 2^29 when i is -2^29 (assuming cl_value_len == 30). Cheers, p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
[cross-posting for clarification] Pierangelo Masarati writes:
Richard B. Kreckel writes:
[snip]
Also, CLN's documentation states that |i| < 2^29, which means that the test in GiNaC for integers could be broken as well, as it does
i >= -(1L << (cl_value_len-1))
which allows |i| == 2^29 when i is -2^29 (assuming cl_value_len == 30).
Actually, CLN documentation in Section 3.1 states that <snip> Small integers (typically in the range -2^29...2^29-1, </snip> while in Section 3.4 it states that <snip> The conversion from `int' works only if the argument is < 2^29 and > -2^29. </snip> This is not necessarily contradictory, but it sounds a bit odd. Why would -2^29 be legal if no conversion occurs for that value? I'll post this remark to the cln-list as well. p. Dr. Pierangelo Masarati | voice: +39 02 2399 8309 Dip. Ing. Aerospaziale | fax: +39 02 2399 8334 Politecnico di Milano | mailto:pierangelo.masarati@polimi.it via La Masa 34, 20156 Milano, Italy | http://www.aero.polimi.it/~masarati Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html
participants (4)
-
Chris Dams
-
Jens Vollinga
-
Pierangelo Masarati
-
Richard B. Kreckel