* tr1::unordered_set<double> bizarre rounding behavior (x86) @ 2005-07-05 13:05 Michael Veksler 2005-07-05 13:32 ` Paolo Carlini ` (2 more replies) 0 siblings, 3 replies; 32+ messages in thread From: Michael Veksler @ 2005-07-05 13:05 UTC (permalink / raw) To: gcc Hello, In previous discussions on rounding of double on x86 I wanted to find an example that points to the absurdity of current gcc behavior. At last I found such an example: ---- t.cpp start --- #include <tr1/unordered_set> #include <iostream> double x=3.0; int main() { std::tr1::unordered_set<double> myset; myset.insert(2/x); myset.insert(2/x); std::cout << myset.size() << " elements\n"; if (myset.size() > 1) std::cout << "Are last and first equal? " << std::boolalpha << ( *myset.begin() == *++myset.begin()) << "\n"; return 0; } --- t.cpp end --- Here is what I get (Pentium 4): --- trace begin --- test$ /opt/gcc-4.0-20050602/bin/g++ t.cpp test$ ./a.out 1 elements test$ /opt/gcc-4.0-20050602/bin/g++ -O3 -finline-limit=1000000 t.cpp test$ ./a.out 2 elements Are last and first equal? true --- trace end --- The behavior of the second run does not look right. What does it mean? 1. Is it forbidden by tr1 to define unordered_set<double> ? 2. Is it a bug in the tr1 document (which should have forbidden this). 3. Is it OK to have repetitions in unordered_set? 4. Is it a bug in gcc, for handling double the way it does? 5. Is it a bug in the implementation of tr1 in libstdc++ ? Maybe handling of double should move to a different translation unit, to avoid aggressive inlining. Or maybe there should be a specialization for equal_to<double>, where error bands will be used. Using error bands will work fine for unordered_set<doble> insertion. It may lead to the "loss" of close entries, but in case of double it sounds reasonable. P.S. std::tr1::hash<dobule> is implemented in a very bad way. it casts double to size_t, which of course does a very poor job on big values (is the result of 1.0e100 cast to size_t defined ?). Michael ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 13:05 tr1::unordered_set<double> bizarre rounding behavior (x86) Michael Veksler @ 2005-07-05 13:32 ` Paolo Carlini 2005-07-05 15:43 ` Michael Veksler 2005-07-05 14:28 ` Gabriel Dos Reis 2005-07-05 17:04 ` Paolo Carlini 2 siblings, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 13:32 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc Michael Veksler wrote: >The behavior of the second run does not look right. What does it mean? >1. Is it forbidden by tr1 to define unordered_set<double> ? >2. Is it a bug in the tr1 document (which should have forbidden this). >3. Is it OK to have repetitions in unordered_set? >4. Is it a bug in gcc, for handling double the way it does? >5. Is it a bug in the implementation of tr1 in libstdc++ ? > Maybe handling of double should move to a different > translation unit, to avoid aggressive inlining. Or maybe > there should be a specialization for equal_to<double>, > where error bands will be used. > > I can see two possibilites here. Either: 1. You know the answer. Then you should probably discuss it, preferably comparing gcc to other compilers and mentioning specific sections of the Standard, TR1, LIA*, and so on. 2. You don't know the answer. In that case you are supposed to file a PR and trust bug-masters and maintainers about the issue. > std::tr1::hash<dobule> is implemented in a very bad way. > it casts double to size_t, which of course does a very poor job on big > values (is the result of 1.0e100 cast to size_t defined ?). > > Thanks. Patches welcome, as usual: contributions are certainly encouraged, especially so from IBM - I would say - generally committed to the project in a constructive, high quality, and friendly way. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 13:32 ` Paolo Carlini @ 2005-07-05 15:43 ` Michael Veksler 2005-07-05 15:57 ` Gabriel Dos Reis 2005-07-05 20:36 ` Michael Veksler 0 siblings, 2 replies; 32+ messages in thread From: Michael Veksler @ 2005-07-05 15:43 UTC (permalink / raw) To: Paolo Carlini; +Cc: gcc Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 16:33:12: > Michael Veksler wrote: > > >The behavior of the second run does not look right. What does it mean? > >1. Is it forbidden by tr1 to define unordered_set<double> ? > >2. Is it a bug in the tr1 document (which should have forbidden this). > >3. Is it OK to have repetitions in unordered_set? > >4. Is it a bug in gcc, for handling double the way it does? > >5. Is it a bug in the implementation of tr1 in libstdc++ ? > > Maybe handling of double should move to a different > > translation unit, to avoid aggressive inlining. Or maybe > > there should be a specialization for equal_to<double>, > > where error bands will be used. > > > > > I can see two possibilites here. Either: > 1. You know the answer. Then you should probably discuss it, > preferably comparing gcc to other compilers and mentioning specific > sections of the Standard, TR1, LIA*, and so on. The only tr1 compilers I have access only to are xlC7 and gcc-4.0. Unfortunately, xlC7 works on PPC an architecture for which gcc's double should work just fine (as expected, always insert one element). As for TR1, 6.3.4.3 describes unordered_set and gives no restriction on type, and says "... container that supports unique keys...". Obviously, gcc-4.0 does not meet this criteria. Looking at 6.3.3, you can see the description of class template hash: "This class template is only required to be instantiable for integer types (3.9.1), floating point types (3.9.1.), ......" This indicates that unordered_set<double> should work fine, and contain no duplicates. Looking at 6.3.1 "Unordered associative container requirements" does not give any indication for illegality of unordered_set<double>. Yet, there is some text that makes it problematic for double. "Each unordered associative container is parameterized by Key, ...., and on a binary predicate Pred that induces an equivalence relation on values of type Key". "Two values k1 and k2 of type Key are considered equal if the container's equality function object returns true when passed those values. If k1 and k2 are equal, the hash function shall return the same value for both." Please note that it requires an "equivalence relation". It is impossible with gcc on x86, with or without error bounds to meet this criterion for double. Also, the requirement to return the same hash value for k1 and k2 (if Pred()(k1,k2)), is very problematic due to the way gcc handles double. Nothing in TR1 seems to indicate that unordered_XXX<double> is undefined or otherwise to be avoided. > 2. You don't know the answer. In that case you are supposed to file > a PR and trust bug-masters and maintainers about the issue. > > > std::tr1::hash<dobule> is implemented in a very bad way. > > it casts double to size_t, which of course does a very poor job on big > > values (is the result of 1.0e100 cast to size_t defined ?). > > > > > Thanks. Patches welcome, as usual: contributions are certainly > encouraged, especially so from IBM - I would say - generally committed > to the project in a constructive, high quality, and friendly way. Sorry, I am not on the gcc team (I am working on constraint solvers rather than compilers). I performed this review purely voluntarily. Besides, I don't have clearance to contribute GPL code (too much paperwork). Michael ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 15:43 ` Michael Veksler @ 2005-07-05 15:57 ` Gabriel Dos Reis 2005-07-05 16:04 ` Paolo Carlini 2005-07-05 20:36 ` Michael Veksler 1 sibling, 1 reply; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 15:57 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc Michael Veksler <VEKSLER@il.ibm.com> writes: [...] | > 2. You don't know the answer. In that case you are supposed to file | > a PR and trust bug-masters and maintainers about the issue. | > | > > std::tr1::hash<dobule> is implemented in a very bad way. | > > it casts double to size_t, which of course does a very poor job on | big | > > values (is the result of 1.0e100 cast to size_t defined ?). | > > | > > | > Thanks. Patches welcome, as usual: contributions are certainly | > encouraged, especially so from IBM - I would say - generally committed | > to the project in a constructive, high quality, and friendly way. | | Sorry, I am not on the gcc team (I am working on constraint solvers rather | than compilers). I performed this review purely voluntarily. And it is clearly welcome! I hope more will follow :-) -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 15:57 ` Gabriel Dos Reis @ 2005-07-05 16:04 ` Paolo Carlini 2005-07-05 20:18 ` Michael Veksler 0 siblings, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 16:04 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Michael Veksler, gcc Gabriel Dos Reis wrote: >| Sorry, I am not on the gcc team (I am working on constraint solvers rather >| than compilers). I performed this review purely voluntarily. > >And it is clearly welcome! I hope more will follow :-) > > Indeed. However, sorry, as a matter of politeness, in my opinion expressions like "absurdity" or "very bad way" are much better accepted if accompanied by corresponding constructive contributions. Or, alternately, just avoid such extreme statements and offer analyses preferring technical terms and citations, as you basically just did, thanks about that. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 16:04 ` Paolo Carlini @ 2005-07-05 20:18 ` Michael Veksler 2005-07-05 20:22 ` Paolo Carlini 0 siblings, 1 reply; 32+ messages in thread From: Michael Veksler @ 2005-07-05 20:18 UTC (permalink / raw) To: Paolo Carlini; +Cc: gcc, Gabriel Dos Reis Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 19:05:40: > > However, sorry, as a matter of politeness, in my opinion expressions > like "absurdity" or "very bad way" are much better accepted if > accompanied by corresponding constructive contributions. Or, > alternately, just avoid such extreme statements and offer analyses > preferring technical terms and citations, as you basically just did, > thanks about that. No offense meant, it's only due to cultural differences... I'll keep in mind to avoid such words, so that nobody is offended. Unfortunately, the text is much more dry and boring that way. Michael ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 20:18 ` Michael Veksler @ 2005-07-05 20:22 ` Paolo Carlini 0 siblings, 0 replies; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 20:22 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc, Gabriel Dos Reis Michael Veksler wrote: >Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 19:05:40: > > >>However, sorry, as a matter of politeness, in my opinion expressions >>like "absurdity" or "very bad way" are much better accepted if >>accompanied by corresponding constructive contributions. Or, >>alternately, just avoid such extreme statements and offer analyses >>preferring technical terms and citations, as you basically just did, >>thanks about that. >> >> >No offense meant, it's only due to cultural differences... >I'll keep in mind to avoid such words, so that nobody is offended. > > No problem ;) >Unfortunately, the text is much more dry and boring that way. > > Not necessarily: there are many different ways to deal with that "serious" ;) problem: for instance you can make a funny link to a movie, music you like, no? ;) Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 15:43 ` Michael Veksler 2005-07-05 15:57 ` Gabriel Dos Reis @ 2005-07-05 20:36 ` Michael Veksler 2005-07-05 20:41 ` Paolo Carlini 2005-07-05 21:21 ` Gabriel Dos Reis 1 sibling, 2 replies; 32+ messages in thread From: Michael Veksler @ 2005-07-05 20:36 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc, Paolo Carlini, Gabriel Dos Reis There is one more thing to consider: the ABI. By changing the code in the header file will break the ABI of tr1::unordered_set. Code compiled with older gcc and newer and fixed-gcc will not interoperate. I don't see an easy path to avoid ABI breakage this time, however how about preparing for future breakage when std::tr1::hash<T> changes again? Maybe move all the specialized hash<T> code from tr/functional into libstdc++.so? Maybe move specialized hashtable<double>, unordered_XXX<float> and friends into libstdc++.so? This way, when hash<T> and std::equal_to<double> change again, the ABI will be not as affected. Michael. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 20:36 ` Michael Veksler @ 2005-07-05 20:41 ` Paolo Carlini 2005-07-05 20:47 ` Paolo Carlini 2005-07-05 21:21 ` Gabriel Dos Reis 1 sibling, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 20:41 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc Michael Veksler wrote: >There is one more thing to consider: the ABI. >By changing the code in the header file will break the ABI >of tr1::unordered_set. Code compiled with older gcc and >newer and fixed-gcc will not interoperate. > > No, no, there are no problems. First, I don't see how changing the internals of a function like an hashing function would change the Binary Interface. Second, in general, we make no guarantees as far as the tr1 bits are concerned, this is also *explicitely* stated in the release notes. Really, please reconsider the issue, there are no problems. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 20:41 ` Paolo Carlini @ 2005-07-05 20:47 ` Paolo Carlini 2005-07-05 21:12 ` Michael Veksler 0 siblings, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 20:47 UTC (permalink / raw) To: Paolo Carlini; +Cc: Michael Veksler, gcc Paolo Carlini wrote: >Michael Veksler wrote: > >>There is one more thing to consider: the ABI. >>By changing the code in the header file will break the ABI >>of tr1::unordered_set. Code compiled with older gcc and >>newer and fixed-gcc will not interoperate. >> It occurs to me that by "ABI" you mean interoperability between different object modules, what I call sometimes "ABI" in the wide sense. Something much more difficult to obtain, which is not related to the linked *.so. Anyway, we don't guarantee anything for tr1, as per the release notes. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 20:47 ` Paolo Carlini @ 2005-07-05 21:12 ` Michael Veksler 0 siblings, 0 replies; 32+ messages in thread From: Michael Veksler @ 2005-07-05 21:12 UTC (permalink / raw) To: Paolo Carlini; +Cc: gcc, Paolo Carlini Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 23:48:03: > Paolo Carlini wrote: > > >Michael Veksler wrote: > > > >>There is one more thing to consider: the ABI. > >>By changing the code in the header file will break the ABI > >>of tr1::unordered_set. Code compiled with older gcc and > >>newer and fixed-gcc will not interoperate. > >> > It occurs to me that by "ABI" you mean interoperability between > different object modules, what I call sometimes "ABI" in the wide sense. Exactly, yes this is what I meant. > Something much more difficult to obtain, which is not related to the > linked *.so. Anyway, we don't guarantee anything for tr1, as per the > release notes. You are right. Too bad, but very much understandable for a TR. I hope that it will be stabilized in time for c++-0x. Michael ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 20:36 ` Michael Veksler 2005-07-05 20:41 ` Paolo Carlini @ 2005-07-05 21:21 ` Gabriel Dos Reis 1 sibling, 0 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 21:21 UTC (permalink / raw) To: gcc Michael Veksler <VEKSLER@il.ibm.com> writes: | There is one more thing to consider: the ABI. | By changing the code in the header file will break the ABI | of tr1::unordered_set. Code compiled with older gcc and | newer and fixed-gcc will not interoperate. tr1 is very experimental and we don't guarantee anything. -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 13:05 tr1::unordered_set<double> bizarre rounding behavior (x86) Michael Veksler 2005-07-05 13:32 ` Paolo Carlini @ 2005-07-05 14:28 ` Gabriel Dos Reis 2005-07-05 17:04 ` Paolo Carlini 2 siblings, 0 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 14:28 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc Michael Veksler <VEKSLER@il.ibm.com> writes: | Hello, | | In previous discussions on rounding of double on x86 I wanted | to find an example that points to the absurdity of current | gcc behavior. | At last I found such an example: Thanks for investing time in this and reporting. | ---- t.cpp start --- | #include <tr1/unordered_set> | #include <iostream> | | double x=3.0; | | int main() | { | std::tr1::unordered_set<double> myset; | myset.insert(2/x); | myset.insert(2/x); | std::cout << myset.size() << " elements\n"; | if (myset.size() > 1) | std::cout << "Are last and first equal? " | << std::boolalpha | << ( *myset.begin() == *++myset.begin()) | << "\n"; | return 0; | } | --- t.cpp end --- | | Here is what I get (Pentium 4): | | --- trace begin --- | test$ /opt/gcc-4.0-20050602/bin/g++ t.cpp | test$ ./a.out | 1 elements | test$ /opt/gcc-4.0-20050602/bin/g++ -O3 -finline-limit=1000000 t.cpp | test$ ./a.out | 2 elements | Are last and first equal? true | --- trace end --- | | The behavior of the second run does not look right. What does it mean? | 1. Is it forbidden by tr1 to define unordered_set<double> ? | 2. Is it a bug in the tr1 document (which should have forbidden this). | 3. Is it OK to have repetitions in unordered_set? | 4. Is it a bug in gcc, for handling double the way it does? | 5. Is it a bug in the implementation of tr1 in libstdc++ ? | Maybe handling of double should move to a different | translation unit, to avoid aggressive inlining. Or maybe | there should be a specialization for equal_to<double>, | where error bands will be used. The different behaviour do not look right to me, no matter how IBM is committed to GCC :-) At the very least, there is a problem with GCC -- please, in case anybody feels the need to read the standard to me; pause a minute :-) I don't believe it is OK to have repetition in an unordered set. However, there seems to be a need to clarifications. In particular, how an implementation is supposed to behave if it supported NaNs and other curiosity. I'll forward this to the LWG. | | | Using error bands will work fine for unordered_set<doble> insertion. | It may lead to the "loss" of close entries, but in case of double it sounds | reasonable. | | | P.S. | std::tr1::hash<dobule> is implemented in a very bad way. | it casts double to size_t, which of course does a very poor job on big | values (is the result of 1.0e100 cast to size_t defined ?). | | Michael -- Gabriel Dos Reis gdr@integrable-solutions.net ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 13:05 tr1::unordered_set<double> bizarre rounding behavior (x86) Michael Veksler 2005-07-05 13:32 ` Paolo Carlini 2005-07-05 14:28 ` Gabriel Dos Reis @ 2005-07-05 17:04 ` Paolo Carlini 2005-07-05 18:06 ` Gabriel Dos Reis 2005-07-05 18:08 ` Joe Buck 2 siblings, 2 replies; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 17:04 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc Michael Veksler wrote: > std::tr1::hash<dobule> is implemented in a very bad way. > it casts double to size_t, which of course does a very poor job on big > values (is the result of 1.0e100 cast to size_t defined ?). > > A possible solution would be using frexp & co to extract the mantissa and then work on it, one way or the other. You can find it proposed around. Then, often the exponent is simply discarded. What do you think? In case, please add your comments to the audit trail of 21193. I mean to work pretty soon on improving those hash functions. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 17:04 ` Paolo Carlini @ 2005-07-05 18:06 ` Gabriel Dos Reis 2005-07-05 18:10 ` Joe Buck 2005-07-06 12:38 ` Avi Kivity 2005-07-05 18:08 ` Joe Buck 1 sibling, 2 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 18:06 UTC (permalink / raw) To: gcc Paolo Carlini <pcarlini@suse.de> writes: | Michael Veksler wrote: | | > std::tr1::hash<dobule> is implemented in a very bad way. | > it casts double to size_t, which of course does a very poor job on big | > values (is the result of 1.0e100 cast to size_t defined ?). | > | > | A possible solution would be using frexp & co to extract the mantissa | and then work on it, one way or the other. You can find it proposed | around. Then, often the exponent is simply discarded. | | What do you think? It is definitely a good thing to use the full bits of value representation if we ever want to make all "interesting" bits part of the hash value. For reasonable or sane representations it suffices to get your hand on the object representation, e.g.: const int objsize = sizeof (double); typedef unsigned char objrep_t[objsize]; double x = ....; objrep_t& p = reintepret_cast<objrep_t&>(x); // ... and let frexp and friends only for less obvious value representation. -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:06 ` Gabriel Dos Reis @ 2005-07-05 18:10 ` Joe Buck 2005-07-05 18:32 ` Gabriel Dos Reis 2005-07-05 19:01 ` Michael Veksler 2005-07-06 12:38 ` Avi Kivity 1 sibling, 2 replies; 32+ messages in thread From: Joe Buck @ 2005-07-05 18:10 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: gcc On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote: > It is definitely a good thing to use the full bits of value > representation if we ever want to make all "interesting" bits part of > the hash value. For reasonable or sane representations it suffices to > get your hand on the object representation, e.g.: > > const int objsize = sizeof (double); > typedef unsigned char objrep_t[objsize]; > double x = ....; > objrep_t& p = reintepret_cast<objrep_t&>(x); > // ... > > and let frexp and friends only for less obvious value representation. I disagree; on an ILP32 machine, we pull out only 32 bits for the hash value, and if you aren't careful, your approach will wind up using the least significant bits of the mantissa. This will cause all values that are exactly representable as floats to collide. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:10 ` Joe Buck @ 2005-07-05 18:32 ` Gabriel Dos Reis 2005-07-05 18:42 ` Paolo Carlini 2005-07-05 19:01 ` Michael Veksler 1 sibling, 1 reply; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 18:32 UTC (permalink / raw) To: Joe Buck; +Cc: gcc Joe Buck <Joe.Buck@synopsys.COM> writes: | On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote: | > It is definitely a good thing to use the full bits of value | > representation if we ever want to make all "interesting" bits part of | > the hash value. For reasonable or sane representations it suffices to | > get your hand on the object representation, e.g.: | > | > const int objsize = sizeof (double); | > typedef unsigned char objrep_t[objsize]; | > double x = ....; | > objrep_t& p = reintepret_cast<objrep_t&>(x); | > // ... | > | > and let frexp and friends only for less obvious value representation. | | I disagree; on an ILP32 machine, we pull out only 32 bits for the hash | value, and if you aren't careful, your approach will wind up using the | least significant bits of the mantissa. This will cause all values that | are exactly representable as floats to collide. I'm not sure we're talking about the same thing. With the representations I'm talking about, value repsentation == object representation. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:32 ` Gabriel Dos Reis @ 2005-07-05 18:42 ` Paolo Carlini 2005-07-05 19:18 ` Gabriel Dos Reis 0 siblings, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 18:42 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Joe Buck, gcc Gabriel Dos Reis wrote: >Joe Buck <Joe.Buck@synopsys.COM> writes: > >| On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote: >| > It is definitely a good thing to use the full bits of value >| > representation if we ever want to make all "interesting" bits part of >| > the hash value. For reasonable or sane representations it suffices to >| > get your hand on the object representation, e.g.: >| > >| > const int objsize = sizeof (double); >| > typedef unsigned char objrep_t[objsize]; >| > double x = ....; >| > objrep_t& p = reintepret_cast<objrep_t&>(x); >| > // ... >| > >| > and let frexp and friends only for less obvious value representation. >| >| I disagree; on an ILP32 machine, we pull out only 32 bits for the hash >| value, and if you aren't careful, your approach will wind up using the >| least significant bits of the mantissa. This will cause all values that >| are exactly representable as floats to collide. > >I'm not sure we're talking about the same thing. With the >representations I'm talking about, value repsentation == object representation. > ... still, the hash functions for float, double and long double that we need for TR1 must return a size_t (6.3.3). How do you get a size_t from an objrep_t? (fulfilling the various requirements briefly reminded by Joe in his first message) Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:42 ` Paolo Carlini @ 2005-07-05 19:18 ` Gabriel Dos Reis 2005-07-05 19:52 ` Paolo Carlini 0 siblings, 1 reply; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 19:18 UTC (permalink / raw) To: Paolo Carlini; +Cc: Joe Buck, gcc Paolo Carlini <pcarlini@suse.de> writes: | Gabriel Dos Reis wrote: | | >Joe Buck <Joe.Buck@synopsys.COM> writes: | > | >| On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote: | >| > It is definitely a good thing to use the full bits of value | >| > representation if we ever want to make all "interesting" bits part of | >| > the hash value. For reasonable or sane representations it suffices to | >| > get your hand on the object representation, e.g.: | >| > | >| > const int objsize = sizeof (double); | >| > typedef unsigned char objrep_t[objsize]; | >| > double x = ....; | >| > objrep_t& p = reintepret_cast<objrep_t&>(x); | >| > // ... | >| > | >| > and let frexp and friends only for less obvious value representation. | >| | >| I disagree; on an ILP32 machine, we pull out only 32 bits for the hash | >| value, and if you aren't careful, your approach will wind up using the | >| least significant bits of the mantissa. This will cause all values that | >| are exactly representable as floats to collide. | > | >I'm not sure we're talking about the same thing. With the | >representations I'm talking about, value repsentation == object representation. | > | ... still, the hash functions for float, double and long double that we | need for TR1 must return a size_t (6.3.3). How do you get a size_t from | an objrep_t? The same way you would get a hash value out of unsigned char [N * sizeof(size_t)] ? | (fulfilling the various requirements briefly reminded by | Joe in his first message) I don't think Joe understood I was talking about hashing the value representation of the floating point object. If you regard the object representation as an array of bytes, does it take long realize it is not much different from hashing a character string? -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 19:18 ` Gabriel Dos Reis @ 2005-07-05 19:52 ` Paolo Carlini 2005-07-05 20:24 ` Gabriel Dos Reis 0 siblings, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 19:52 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Joe Buck, gcc Gabriel Dos Reis wrote: >If you regard the object representation as an array of bytes, does it >take long realize it is not much different from hashing a character >string? > It takes less if your proposal comes together with a specific one for character string hashing: not, trivially, because in this way the problem would be solved completely ;) but because, given the plethora of different ways you can hash character strings, I'm not sure one considered "good" for real text would be also good for strings-from-floats, there are *lots* of subtle statistical issues involved. For example, I'm not at all sure that the hash function suggested by submitter of 21193 would also work statistically well for floats (note that most of the real world succesful applications mentioned in the linked web page are about *real* text). I don't think laws like the famous ETAOINSHRDLU distribution of the english letters apply also to the bytes of floats, do you? ;) That said, I agree that reusing what we are going to have for strings also for floats is in any case better than the present placeholder, at the time certainly not considered by Matt the final production solution. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 19:52 ` Paolo Carlini @ 2005-07-05 20:24 ` Gabriel Dos Reis 0 siblings, 0 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 20:24 UTC (permalink / raw) To: gcc Paolo Carlini <pcarlini@suse.de> writes: | Gabriel Dos Reis wrote: | | >If you regard the object representation as an array of bytes, does it | >take long realize it is not much different from hashing a character | >string? | > | It takes less if your proposal comes together with a specific one for | character string hashing: You do have one already. Start from there. Measure, then we can argue later. Now that you realize it is same issue, we've made significant progress. [...] | involved. For example, I'm not at all sure that the hash function | suggested by submitter of 21193 would also work statistically well for | floats (note that most of the real world succesful applications | mentioned in the linked web page are about *real* text). I don't think Yes, but note also that those depend on some assumptions about the distribution of some words. Not every specific context would equally benefit from that. The point being that once you have reduced the problem to one previously known solved problem, it is only a matter of arguing about little details. I think that is far better than current situation. -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:10 ` Joe Buck 2005-07-05 18:32 ` Gabriel Dos Reis @ 2005-07-05 19:01 ` Michael Veksler 2005-07-05 19:24 ` Gabriel Dos Reis 1 sibling, 1 reply; 32+ messages in thread From: Michael Veksler @ 2005-07-05 19:01 UTC (permalink / raw) To: Joe Buck; +Cc: gcc, Gabriel Dos Reis Joe Buck <Joe.Buck@synopsys.COM> wrote on 05/07/2005 21:10:25: > On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote: > > It is definitely a good thing to use the full bits of value > > representation if we ever want to make all "interesting" bits part of > > the hash value. For reasonable or sane representations it suffices to > > get your hand on the object representation, e.g.: > > > > const int objsize = sizeof (double); > > typedef unsigned char objrep_t[objsize]; > > double x = ....; > > objrep_t& p = reintepret_cast<objrep_t&>(x); > > // ... > > > > and let frexp and friends only for less obvious value representation. > > I disagree; on an ILP32 machine, we pull out only 32 bits for the hash > value, and if you aren't careful, your approach will wind up using the > least significant bits of the mantissa. This will cause all values that > are exactly representable as floats to collide. For that you can do something like (or templated equivalent): namespace Impl { template <class T> size_t floating_point_hash(T in) { if (sizeof(in) <= sizeof(size_t)) Use Gaby's solution, with zero padding; else frexp and friends using Joe Buck's ideas; } } Gaby's solution should be done with care - to avoid any aliasing issues (never go directly from double& to size_t&). Both Gaby's and Joe Buck's solutions do not take the strangeness of IEEE (NNN?) into account. As I remember it (I don't have the reference at home), IEEE FP has many bit-representations for NaN, each containing some bit-encoding of errors. It has been years since I last saw the standard of IEEE FP, so I may give wrong details, but the main idea should be correct. "There *should* be a specialization for equal_to<double> that provides a strict weak ordering for NaNs as well as other values." [quoted forwarded mail from P.J. Plauger] Doing bit-wise conversions will not address this requirement. Michael ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 19:01 ` Michael Veksler @ 2005-07-05 19:24 ` Gabriel Dos Reis 0 siblings, 0 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-05 19:24 UTC (permalink / raw) To: Michael Veksler; +Cc: Joe Buck, gcc Michael Veksler <VEKSLER@il.ibm.com> writes: | Joe Buck <Joe.Buck@synopsys.COM> wrote on 05/07/2005 21:10:25: | | > On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote: | > > It is definitely a good thing to use the full bits of value | > > representation if we ever want to make all "interesting" bits part of | > > the hash value. For reasonable or sane representations it suffices to | > > get your hand on the object representation, e.g.: | > > | > > const int objsize = sizeof (double); | > > typedef unsigned char objrep_t[objsize]; | > > double x = ....; | > > objrep_t& p = reintepret_cast<objrep_t&>(x); | > > // ... | > > | > > and let frexp and friends only for less obvious value representation. | > | > I disagree; on an ILP32 machine, we pull out only 32 bits for the hash | > value, and if you aren't careful, your approach will wind up using the | > least significant bits of the mantissa. This will cause all values that | > are exactly representable as floats to collide. | | For that you can do something like (or templated equivalent): | namespace Impl | { | template <class T> | size_t floating_point_hash(T in) | { | if (sizeof(in) <= sizeof(size_t)) | Use Gaby's solution, with zero padding; | else | frexp and friends using Joe Buck's ideas; | } | } | | Gaby's solution should be done with care - to avoid any | aliasing issues (never go directly from double& to size_t&). The standard explicilty permit that you can regard any object as an array of unsigned char. Given that, and given no padding bits (e.g. the "sane" representation assumption), hashing any object larger than a size_t is no different from hashing a character string. Now, the question is how to make sure we do not have padding bits. For most targets, that assumption is OK; only the one subject of this discussion seems to pose problems ;-) | Both Gaby's and Joe Buck's solutions do not take | the strangeness of IEEE (NNN?) into account. | As I remember it (I don't have the reference at home), | IEEE FP has many bit-representations for NaN, each | containing some bit-encoding of errors. My proposal explicilty takes that into account in the sense that it looks at all bits of the value representation, therefore the encoding bits of the NaNs too. | "There *should* be a specialization for equal_to<double> that | provides a strict weak ordering for NaNs as well as other | values." [quoted forwarded mail from P.J. Plauger] | Doing bit-wise conversions will not address this requirement. I do not understand what you mean by that. -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:06 ` Gabriel Dos Reis 2005-07-05 18:10 ` Joe Buck @ 2005-07-06 12:38 ` Avi Kivity 2005-07-06 12:54 ` Gabriel Dos Reis 2005-07-06 12:54 ` Michael Veksler 1 sibling, 2 replies; 32+ messages in thread From: Avi Kivity @ 2005-07-06 12:38 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: gcc On Tue, 2005-07-05 at 20:05 +0200, Gabriel Dos Reis wrote: > Paolo Carlin > It is definitely a good thing to use the full bits of value > representation if we ever want to make all "interesting" bits part of > the hash value. For reasonable or sane representations it suffices to > get your hand on the object representation, e.g.: > > const int objsize = sizeof (double); > typedef unsigned char objrep_t[objsize]; > double x = ....; > objrep_t& p = reintepret_cast<objrep_t&>(x); > // ... > > and let frexp and friends only for less obvious value representation. most architectures have different bit representations for +0.0 and -0.0, yet the two values compare equal. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-06 12:38 ` Avi Kivity @ 2005-07-06 12:54 ` Gabriel Dos Reis 2005-07-06 12:54 ` Michael Veksler 1 sibling, 0 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-06 12:54 UTC (permalink / raw) To: Avi Kivity; +Cc: gcc Avi Kivity <avi@argo.co.il> writes: | On Tue, 2005-07-05 at 20:05 +0200, Gabriel Dos Reis wrote: | > Paolo Carlin | > It is definitely a good thing to use the full bits of value | > representation if we ever want to make all "interesting" bits part of | > the hash value. For reasonable or sane representations it suffices to | > get your hand on the object representation, e.g.: | > | > const int objsize = sizeof (double); | > typedef unsigned char objrep_t[objsize]; | > double x = ....; | > objrep_t& p = reintepret_cast<objrep_t&>(x); | > // ... | > | > and let frexp and friends only for less obvious value representation. | | most architectures have different bit representations for +0.0 and -0.0, | yet the two values compare equal. Indeed. Paolo, Michael and I have been discussing that offline. the signed zero representation is not the a serious one (say compare to having padding bits or how to handle NaNs properly) -- just compare to 0.0 and return hash value 0 before going mocking around with bytes. -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-06 12:38 ` Avi Kivity 2005-07-06 12:54 ` Gabriel Dos Reis @ 2005-07-06 12:54 ` Michael Veksler 2005-07-06 13:01 ` Avi Kivity 1 sibling, 1 reply; 32+ messages in thread From: Michael Veksler @ 2005-07-06 12:54 UTC (permalink / raw) To: Avi Kivity; +Cc: gcc, Gabriel Dos Reis Avi Kivity wrote on 06/07/2005 15:38:38: > On Tue, 2005-07-05 at 20:05 +0200, Gabriel Dos Reis wrote: > > Paolo Carlin > > It is definitely a good thing to use the full bits of value > > representation if we ever want to make all "interesting" bits part of > > the hash value. For reasonable or sane representations it suffices to > > get your hand on the object representation, e.g.: > > > > const int objsize = sizeof (double); > > typedef unsigned char objrep_t[objsize]; > > double x = ....; > > objrep_t& p = reintepret_cast<objrep_t&>(x); > > // ... > > > > and let frexp and friends only for less obvious value representation. > > most architectures have different bit representations for +0.0 and -0.0, > yet the two values compare equal. > Yet, their sign bit is observable through things like assert(a == 0.0); assert(b == 0.0); 1/(1/a+ 1/b) which would give either NaN or 0 depending on the sign of a and b. So do you want one or two copies in the set? ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-06 12:54 ` Michael Veksler @ 2005-07-06 13:01 ` Avi Kivity 2005-07-06 13:50 ` Gabriel Dos Reis 0 siblings, 1 reply; 32+ messages in thread From: Avi Kivity @ 2005-07-06 13:01 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc, Gabriel Dos Reis On Wed, 2005-07-06 at 15:54 +0300, Michael Veksler wrote: > > most architectures have different bit representations for +0.0 and -0.0, > > yet the two values compare equal. > > > > Yet, their sign bit is observable through things like > assert(a == 0.0); > assert(b == 0.0); > 1/(1/a+ 1/b) > which would give either NaN or 0 depending on the sign > of a and b. > > So do you want one or two copies in the set? > what matters is whether the sign bit is observable through the equality predicate. in the case of the operator==(double, double), it is not observable, so there should be only one copy in a set. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-06 13:01 ` Avi Kivity @ 2005-07-06 13:50 ` Gabriel Dos Reis 0 siblings, 0 replies; 32+ messages in thread From: Gabriel Dos Reis @ 2005-07-06 13:50 UTC (permalink / raw) To: Avi Kivity; +Cc: Michael Veksler, gcc Avi Kivity <avi@argo.co.il> writes: | On Wed, 2005-07-06 at 15:54 +0300, Michael Veksler wrote: | | > > most architectures have different bit representations for +0.0 and -0.0, | > > yet the two values compare equal. | > > | > | > Yet, their sign bit is observable through things like | > assert(a == 0.0); | > assert(b == 0.0); | > 1/(1/a+ 1/b) | > which would give either NaN or 0 depending on the sign | > of a and b. | > | > So do you want one or two copies in the set? | > | what matters is whether the sign bit is observable through the equality | predicate. in the case of the operator==(double, double), it is not | observable, so there should be only one copy in a set. Yes. That logical framework has some "problems" though. Assume x is NaN, then you would end up with as many xs as you insert in the set. -- Gaby ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 17:04 ` Paolo Carlini 2005-07-05 18:06 ` Gabriel Dos Reis @ 2005-07-05 18:08 ` Joe Buck 2005-07-05 18:12 ` Paolo Carlini 1 sibling, 1 reply; 32+ messages in thread From: Joe Buck @ 2005-07-05 18:08 UTC (permalink / raw) To: Paolo Carlini; +Cc: Michael Veksler, gcc On Tue, Jul 05, 2005 at 07:05:16PM +0200, Paolo Carlini wrote: > Michael Veksler wrote: > > > std::tr1::hash<dobule> is implemented in a very bad way. > > it casts double to size_t, which of course does a very poor job on big > > values (is the result of 1.0e100 cast to size_t defined ?). > > > > > A possible solution would be using frexp & co to extract the mantissa > and then work on it, one way or the other. You can find it proposed > around. Then, often the exponent is simply discarded. > > What do you think? Close, but not quite. Hash functions are, by nature, many-to-one. A good hash function has few collisions for values that frequently appear; the program will preform very poorly if many inputs hash to the same value. The existing function will make all values over max(size_t) collide (assuming the cast clips). Using only the mantissa is better, but if doubles are used to represent fixed-point, then common values like 0.25, 0.5, 1, 2, 4 might all be in the hash table, and they will collide. You could do frexp, scale the mantissa to form an integer (e.g. multiply by a large integer), then add it (modulo 2**n) to some prime number multiplied by the exponent. This should give good spreading for both large values and exactly representable values. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:08 ` Joe Buck @ 2005-07-05 18:12 ` Paolo Carlini 2005-07-05 19:58 ` Joe Buck 0 siblings, 1 reply; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 18:12 UTC (permalink / raw) To: Joe Buck; +Cc: Michael Veksler, gcc Hi Joe and Gaby and thanks for your messages, >Close, but not quite. > >Hash functions are, by nature, many-to-one. A good hash function has >few collisions for values that frequently appear; the program will preform >very poorly if many inputs hash to the same value. The existing function >will make all values over max(size_t) collide (assuming the cast clips). >Using only the mantissa is better, but if doubles are used to >represent fixed-point, then common values like 0.25, 0.5, 1, 2, 4 might >all be in the hash table, and they will collide. > >You could do frexp, scale the mantissa to form an integer (e.g. multiply >by a large integer), then add it (modulo 2**n) to some prime number >multiplied by the exponent. This should give good spreading for both >large values and exactly representable values. > Indeed, I can find around also more sophisticated solutions similar to your proposal, perhaps in the python library?!? I'm tempted to go along this way, but Gaby's idea also seems nice, opinions about it? We have to make a choice... or we can provide both and the user chooses... still we have to select a default ;) Thanks ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 18:12 ` Paolo Carlini @ 2005-07-05 19:58 ` Joe Buck 2005-07-05 19:59 ` Paolo Carlini 0 siblings, 1 reply; 32+ messages in thread From: Joe Buck @ 2005-07-05 19:58 UTC (permalink / raw) To: Paolo Carlini; +Cc: Michael Veksler, gcc On Tue, Jul 05, 2005 at 08:13:41PM +0200, Paolo Carlini wrote: > Hi Joe and Gaby and thanks for your messages, > > >Close, but not quite. > > > >Hash functions are, by nature, many-to-one. A good hash function has > >few collisions for values that frequently appear; the program will preform > >very poorly if many inputs hash to the same value. The existing function > >will make all values over max(size_t) collide (assuming the cast clips). > >Using only the mantissa is better, but if doubles are used to > >represent fixed-point, then common values like 0.25, 0.5, 1, 2, 4 might > >all be in the hash table, and they will collide. > > > >You could do frexp, scale the mantissa to form an integer (e.g. multiply > >by a large integer), then add it (modulo 2**n) to some prime number > >multiplied by the exponent. This should give good spreading for both > >large values and exactly representable values. > > > Indeed, I can find around also more sophisticated solutions similar to > your proposal, perhaps in the python library?!? I'm tempted to go along > this way, but Gaby's idea also seems nice, opinions about it? We have to > make a choice... or we can provide both and the user chooses... still we > have to select a default ;) If I were you I'd be tempted to crib from Python. Because of the centrality of good hashing for Python performance, I'm sure that they've done a good job. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: tr1::unordered_set<double> bizarre rounding behavior (x86) 2005-07-05 19:58 ` Joe Buck @ 2005-07-05 19:59 ` Paolo Carlini 0 siblings, 0 replies; 32+ messages in thread From: Paolo Carlini @ 2005-07-05 19:59 UTC (permalink / raw) To: Joe Buck; +Cc: Michael Veksler, gcc Joe Buck wrote: >If I were you I'd be tempted to crib from Python. Because of the >centrality of good hashing for Python performance, I'm sure that they've >done a good job. > I agree Joe, probably that's a good empirically tested solution. Paolo. ^ permalink raw reply [flat|nested] 32+ messages in thread
end of thread, other threads:[~2005-07-06 13:50 UTC | newest] Thread overview: 32+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2005-07-05 13:05 tr1::unordered_set<double> bizarre rounding behavior (x86) Michael Veksler 2005-07-05 13:32 ` Paolo Carlini 2005-07-05 15:43 ` Michael Veksler 2005-07-05 15:57 ` Gabriel Dos Reis 2005-07-05 16:04 ` Paolo Carlini 2005-07-05 20:18 ` Michael Veksler 2005-07-05 20:22 ` Paolo Carlini 2005-07-05 20:36 ` Michael Veksler 2005-07-05 20:41 ` Paolo Carlini 2005-07-05 20:47 ` Paolo Carlini 2005-07-05 21:12 ` Michael Veksler 2005-07-05 21:21 ` Gabriel Dos Reis 2005-07-05 14:28 ` Gabriel Dos Reis 2005-07-05 17:04 ` Paolo Carlini 2005-07-05 18:06 ` Gabriel Dos Reis 2005-07-05 18:10 ` Joe Buck 2005-07-05 18:32 ` Gabriel Dos Reis 2005-07-05 18:42 ` Paolo Carlini 2005-07-05 19:18 ` Gabriel Dos Reis 2005-07-05 19:52 ` Paolo Carlini 2005-07-05 20:24 ` Gabriel Dos Reis 2005-07-05 19:01 ` Michael Veksler 2005-07-05 19:24 ` Gabriel Dos Reis 2005-07-06 12:38 ` Avi Kivity 2005-07-06 12:54 ` Gabriel Dos Reis 2005-07-06 12:54 ` Michael Veksler 2005-07-06 13:01 ` Avi Kivity 2005-07-06 13:50 ` Gabriel Dos Reis 2005-07-05 18:08 ` Joe Buck 2005-07-05 18:12 ` Paolo Carlini 2005-07-05 19:58 ` Joe Buck 2005-07-05 19:59 ` Paolo Carlini
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).