- C++ threshold for "stupid" sorting algorithms (O(n^2)) - 3 Updates
- Union type punning in C++ - 6 Updates
- Don't be fooled by cpp.sh - 5 Updates
| Soviet_Mario <SovietMario@CCCP.MIR>: Jan 02 07:46PM +0100 On 02/01/2020 11:28, Christian Gollwitzer wrote: > Do mergesort: it is inherently stable, rather simple and > scales well for large sorts, too. > Christian I'll look for it, tnx -- 1) Resistere, resistere, resistere. 2) Se tutti pagano le tasse, le tasse le pagano tutti Soviet_Mario - (aka Gatto_Vizzato) |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 02 08:00PM +0100 >> for large sorts, too. >> Christian > I'll look for it, tnx And there's std::stable_sort which is usually implemented with megesort. With parallel_policy or parallel_unsequenced_policy it even exploits all cores. |
| "Öö Tiib" <ootiib@hot.ee>: Jan 02 03:11PM -0800 On Wednesday, 1 January 2020 18:13:02 UTC+2, Soviet_Mario wrote: > "allocator" (and I don't know what to pass as argument, I'd > just prefer the general purpose allocator). Dunno why only > these new vectors are provided. Vector has been always such. On usual case (over 99% of code) we do not provide that second argument since it has default value that is very rarely worth to change. Allocators are complex topic so these can be learned later. That default value is std::allocator<T> on case of std::vector and std::pmr::polymorphic_allocator<T> on case of std::pmr::vector (that is in standard since C++17). It is odd when IDE somehow requires entry of allocator, maybe find out what you did in settings that caused it and try to turn the behavior off. |
| boltar@nowhere.org: Jan 02 05:22PM On Thu, 2 Jan 2020 04:52:42 -0800 (PST) >> https://en.cppreference.com/w/cpp/numeric/bit_cast >Thanks, I didn't somehow even notice that. So we can throw away >our own type punning wrappers around memcpy in C++20. You realise using a union (or a cast) in theory uses very few CPU cycles to do type punning, whereas memcpy has the overhead of a function call + loop. Its an extremely inefficient way to do it if you don't need the new type to be in a seperate variable. |
| "Öö Tiib" <ootiib@hot.ee>: Jan 02 10:26AM -0800 > type punning, whereas memcpy has the overhead of a function call + loop. Its > an extremely inefficient way to do it if you don't need the new type to be in > a seperate variable. That is the typical behavior of gibberish team. In one post it is "de facto" in other "in theory". I wrote: Experiments of mine and others have shown that usage of memcpy instead of other ways of type punning tends to generate better or same codes. It is hard to find examples where other methods are really beneficial. Can the "defacto" gang provide any? No? I thought so. So drop your rubbish and show assemblers of realistic usages on real compilers where your "theories" hold. |
| Bo Persson <bo@bo-persson.se>: Jan 02 09:12PM +0100 > type punning, whereas memcpy has the overhead of a function call + loop. Its > an extremely inefficient way to do it if you don't need the new type to be in > a seperate variable. Obviously the bit_cast function will be inlined, as will the __builtin_memcpy (or whatever it is called for a specific compiler). And sizeof(To) and sizeof(From) are compile time constants, so no loop needed to copy, for example, 4 or 8 bytes. Instead we can expect a single register mov. I have my favorite example from a std::string constructor using both strlen and memcpy to construct the string. And the compiler optimizes this to 1 and 2 mov-instructions, respectively: std::string whatever = "abcdefgh"; 000000013FCC30C3 mov rdx,qword ptr [string "abcdefgh"] 000000013FCC30CA mov qword ptr [whatever],rdx 000000013FCC30D2 mov byte ptr [rsp+347h],0 000000013FCC30DA mov qword ptr [rsp+348h],8 000000013FCC30E6 mov byte ptr [rsp+338h],0 "Here traits_type::copy contains a call to memcpy, which is optimized into a single register copy of the whole string (carefully selected to fit). The compiler also transforms a call to strlen into a compile time 8." https://stackoverflow.com/a/11639305 Note that this example is from 8 years ago. Compilers haven't exactly become less optimizing since then. Bo Persson |
| peter koch <peter.koch.larsen@gmail.com>: Jan 02 12:39PM -0800 onsdag den 1. januar 2020 kl. 20.24.19 UTC+1 skrev Mr Flibble: > If it works on all the compilers I care about does it really matter that it is *currently* classed as undefined behaviour? > I would say that everyone has "secretly" fucking done it some time or other so the C++ Standards Committee should get there act together and legalize it like it has been in C. > Can anyone provide a straight answer to this? It does not work with maximum optimization at least with gcc, and it has not done so for at least six years. I know from bitter personal experience (converting from IBM to IEEE floating point). Instead, just use std::bit_cast - implement it yourself, it is ten lines of code all included. If you compile with optimizations on, the resulting code has no overhead whatsoever. |
| Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jan 02 09:54PM On Thu, 2 Jan 2020 10:26:35 -0800 (PST) > so. > So drop your rubbish and show assemblers of realistic usages > on real compilers where your "theories" hold. More to the point, in gcc/clang memcpy is a built-in, and in VS an "intrinsic", and in most usages does not involve a function call at all (unless our poster does something like pass it as a function pointer), as your experiments show. In C++ it is the recommended alternative to punning with a union. However, I think you are wasting your time arguing with this guy: from his repetitive posts, he is either dim or a dick, possibly both. |
| David Brown <david.brown@hesbynett.no>: Jan 02 11:23PM +0100 > type punning, whereas memcpy has the overhead of a function call + loop. Its > an extremely inefficient way to do it if you don't need the new type to be in > a seperate variable. memcpy of a known small size will be handled inline by most decent compilers. Generally it does not lead to any memory accesses or code other than register movement. #include <string.h> float swapsign1(float x) { union { float f; unsigned int i; } u; u.f = x; u.i ^= 0x80000000; return u.f; } float swapsign2(float x) { unsigned int i; memcpy(&i, &x, sizeof(float)); i ^= 0x80000000; memcpy(&x, &i, sizeof(float)); return x; } These give identical code with gcc. Both versions are valid in C, but only swapsign2 is defined by the C++ standards (though gcc defines the behaviour as an extension). |
| boltar@nowhere.org: Jan 02 04:45PM On Thu, 02 Jan 2020 13:27:15 +0200 >>> standard feature. >> Where is it stated thats its illegal? >You see, I'm not against making the union type punning legal for POD So its not stated anywhere then. >types, for C compatibility, as proposed by Mr Flibble in another thread. >If and when this gets incorporated into the C++ standard, I will happily If its not in the standard but is it in C then it gets incorporated into C++ unless stated otherwise. >However, for now this is UB by the standard, and "illegal" is a >colloquial term often used for UB in technical standards. I used this >term because it seems you cannot really grasp what UB is. I have no idea what UB stands for nor do I care. |
| Melzzzzz <Melzzzzz@zzzzz.com>: Jan 02 04:55PM >>colloquial term often used for UB in technical standards. I used this >>term because it seems you cannot really grasp what UB is. > I have no idea what UB stands for nor do I care. UB is simply not guarranted to work as intended. -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| boltar@nowhere.org: Jan 02 05:24PM On Thu, 02 Jan 2020 16:55:44 GMT >>>term because it seems you cannot really grasp what UB is. >> I have no idea what UB stands for nor do I care. >UB is simply not guarranted to work as intended. Union behaviour is architecture specific anyway. You need to know what you're doing when you use them especially if writing cross platform code. |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 02 06:30PM +0100 >> UB is simply not guarranted to work as intended. > Union behaviour is architecture specific anyway. When you have your own variant through a union by selectively constructing and destructing one of the subobjects of a union, the behaviour isn't architecture-specific. |
| David Brown <david.brown@hesbynett.no>: Jan 02 10:58PM +0100 >>> Where is it stated thats its illegal? >> You see, I'm not against making the union type punning legal for POD > So its not stated anywhere then. The C++ standards are notoriously difficult to read on this particular point. C11 makes it clear that type-punning via unions is allowed - the C++ standards have no equivalent note. They do say, however, that at most one (non-static) data member can be "active" at a time. Based on the rules for lifetimes and active members of a union, writing to one member of the union and reading from a different member is undefined behaviour. Also note that the C and C++ standards consider anything that is not explicitly described behaviour, to be undefined behaviour. So since there isn't anything describing this usage in C++, the behaviour is undefined by default - it simply hasn't been given a definition. >> If and when this gets incorporated into the C++ standard, I will happily > If its not in the standard but is it in C then it gets incorporated into > C++ unless stated otherwise. Absolute nonsense. C++ is not a superset of C. You will get many subtle things wrong if you keep thinking this way. >> colloquial term often used for UB in technical standards. I used this >> term because it seems you cannot really grasp what UB is. > I have no idea what UB stands for nor do I care. It stands for "undefined behaviour" - something that does not have an effect or behaviour defined by the relevant standard. A particular compiler is always free to give a definition to the behaviour if it wants, but does not have to do so. Generally, you should avoid any kind of undefined behaviour in your code unless your compiler documents that it defines the particular point, and you are happy with code that is not portable. (There is nothing wrong with non-portable code, as long as you are aware of the issue.) |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment