- Making std::list::size() O(1) is a mistake - 14 Updates
- Upcoming presentations on asynchronous network programming - 9 Updates
- timed_mutex -- but it acquires the lock - 1 Update
- Copy constructor with non-const argument - 1 Update
| Bo Persson <bo@bo-persson.se>: Feb 17 10:24AM +0100 On 2023-02-16 at 21:54, Mr Flibble wrote: > Some say nobody cares that I think making std::list::size() O(1) is a > mistake but I am sure others agree with me: the whole point of using > std::list::splice is the performance benefit of manipulating linked lists. Yes, we know that. Where were you 15 years ago when this was standardized? Consistency won over usefulness, and it is a bit late to reverse that now. Making the size unsigned was also a mistake, but not going to change either. |
| Malcolm McLean <malcolm.arthur.mclean@gmail.com>: Feb 17 02:45AM -0800 On Friday, 17 February 2023 at 09:25:06 UTC, Bo Persson wrote: > Where were you 15 years ago when this was standardized? Consistency won > over usefulness, and it is a bit late to reverse that now. > Making the size unsigned was also a mistake, but not going to change either. It hardly matters because on modern hardware std::list is almost useless. Even on tasks which are heavy on inserts / deletes, an std::list is often beaten by an std::vector, because of a cache issues. |
| "Öö Tiib" <ootiib@hot.ee>: Feb 17 04:01AM -0800 On Friday, 17 February 2023 at 12:46:02 UTC+2, Malcolm McLean wrote: > It hardly matters because on modern hardware std::list is almost useless. Even on > tasks which are heavy on inserts / deletes, an std::list is often beaten by an std::vector, > because of a cache issues. The std::list that contains large elements is performant for certain usage patterns and even elegantly so when the algorithm needs its operations that other containers lack ... like splice, merge, reverse or unique. But in my experience when std::list is doing well and that matters then boost::intrusive::list is doing even better. |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 17 01:11PM +0100 Am 16.02.2023 um 21:54 schrieb Mr Flibble: > Hi! > Making std::list::size() O(1) is a mistake as it breaks std::list::splice; > ... You often need list::size() and making it O(N) would hurt more than counting the items of a splice-operation since this is needed less frequent. |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 17 01:15PM +0100 Am 17.02.2023 um 11:45 schrieb Malcolm McLean: > It hardly matters because on modern hardware std::list is almost useless. > Even on tasks which are heavy on inserts / deletes, an std::list is often > beaten by an std::vector, because of a cache issues. std::list makes sense only if you have appends and deletes at the list's ends and you need to save memory and this is more immportant than the memory blend of the vector due to its amortized constant overhead inser- tion propery. |
| Paavo Helde <eesnimi@osa.pri.ee>: Feb 17 02:27PM +0200 17.02.2023 12:45 Malcolm McLean kirjutas: > It hardly matters because on modern hardware std::list is almost useless. Even on > tasks which are heavy on inserts / deletes, an std::list is often beaten by an std::vector, > because of a cache issues. There are few cases for std::list which I know. One is for holding alive large entity objects which should not be moved in memory, and another is for the algorithms which need splice. For the first usage the complexity of list::size() does not matter, and for the second usage the current O(1) is counter-productive. In retrospect, they should have renamed list size() to count() and leave it O(N). Too late now. |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 17 01:41PM +0100 Am 17.02.2023 um 13:27 schrieb Paavo Helde: > In retrospect, they should have renamed list size() to count() and leave > it O(N). Too late now. No, absolutely not. size() should be O(1) since it is more commonly used as you might splice. |
| "Öö Tiib" <ootiib@hot.ee>: Feb 17 04:42AM -0800 On Friday, 17 February 2023 at 14:40:02 UTC+2, Bonita Montero wrote: > > it O(N). Too late now. > No, absolutely not. size() should be O(1) since it is more commonly used > as you might splice. Why you repeat same bullshit over? You have zero knowledge what others use and how frequently and therefore it is not even a lie. For lying you need at least to think that you know the actual truth. |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 17 08:05PM +0100 Am 17.02.2023 um 13:42 schrieb Öö Tiib: >> as you might splice. > Why you repeat same bullshit over? You have zero knowledge what > others use and how frequently and therefore it is not even a lie. ... Idiot. |
| Chris Vine <vine24683579@gmail.com>: Feb 17 11:31AM -0800 On Friday, 17 February 2023 at 10:46:02 UTC, Malcolm McLean wrote: [snip] > It hardly matters because on modern hardware std::list is almost useless. Even on > tasks which are heavy on inserts / deletes, an std::list is often beaten by an std::vector, > because of a cache issues. Not in the case of queues which might be accessed under thread contention. std::list and its splice_end() and unsplice_beginning() functions can achieve as close to lock-free performance as you are going to get with the standard containers, because new nodes can be constructed outside the queue mutex and all that is done under the mutex is to swap a few pointers by way of splice and unsplice. Happily splice_end() and unsplice_beginning() have O(1) complexity irrespective of std::list::size()'s complexity. |
| Chris Vine <vine24683579@gmail.com>: Feb 17 02:10PM -0800 On Friday, 17 February 2023 at 19:32:01 UTC, Chris Vine wrote: > can be constructed outside the queue mutex and all that is done under the mutex is to > swap a few pointers by way of splice and unsplice. Happily splice_end() and > unsplice_beginning() have O(1) complexity irrespective of std::list::size()'s complexity. My naming could be confusing: by splice_end() I mean an application of std::list::splice which splices a node into the end of a list, and by unsplice_beginning() I mean an application of std::list::splice which extracts a node from the beginning of a list. |
| Paavo Helde <eesnimi@osa.pri.ee>: Feb 18 12:17AM +0200 17.02.2023 21:31 Chris Vine kirjutas: > can be constructed outside the queue mutex and all that is done under the mutex is to > swap a few pointers by way of splice and unsplice. Happily splice_end() and > unsplice_beginning() have O(1) complexity irrespective of std::list::size()'s complexity. By some reason, google returns 0 hits for unsplice_beginning, and only some non-C++ hits for 'std::list splice_end'. Anyway, it depends. In std::list each element would be allocated and released dynamically, which might a bit more expensive than e.g. with std::deque. Even though std::deque does not support splicing, the elements can be moved or swapped into it, and the whole std::deque can be moved or swapped away by the/a consumer thread. These are also fast operations. So to me it looks not so guaranteed std::list is definitely a winner for inter-thread queues. In some cases it might be. |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Feb 17 02:21PM -0800 On 2/17/2023 2:10 PM, Chris Vine wrote: > My naming could be confusing: by splice_end() I mean an application of std::list::splice > which splices a node into the end of a list, and by unsplice_beginning() I mean an application > of std::list::splice which extracts a node from the beginning of a list. are you familiar with the following challenge? RCU works nicely. A proxy collector can work as well. https://youtu.be/Qxduz-CRnDw When you get some free time to burn, give it a watch! :^) |
| Chris Vine <vine24683579@gmail.com>: Feb 17 02:42PM -0800 On Friday, 17 February 2023 at 22:17:55 UTC, Paavo Helde wrote: > swapped away by the/a consumer thread. These are also fast operations. > So to me it looks not so guaranteed std::list is definitely a winner for > inter-thread queues. In some cases it might be. On the first point, yes I was using rather unhelpful shorthand which I have since clarified, taken from some code I use specifically for this purpose,. On the second point, it is certainly not guaranteed. Cases where a lock-free queue implemented via CAS work well are the cases where (if you want to use the standard containers instead) splicing std::list is likely to work well also. For queue elements which are scalars or which have move operators which don't allocate or deallocate, and enough memory has been reserved, std::deque or std::vector might be better. The important point where contention is likely is to try and ensure that allocation and deallocation occur outside the container's mutex. The argument I refute for this particular case is that "on modern hardware std::list is almost useless". |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 17 04:16AM +0100 > Plus the standard C sockets API is fairly simple so why you'd > need it wrapped up in that outdated library is anyones guess. Boost.ASIO is usually more performant than manual socket calls and easier to use. |
| legalize+jeeves@mail.xmission.com (Richard): Feb 17 05:40AM [Please do not mail me a copy of your followup] Muttley@dastardlyhq.com spake the secret code >[a bunch of hand-waiving statements that are not informed by >the current reality of network programming in C++ or the current >state of the ISO C++ standard] Troll much? Neither C++17, C++20 nor C++23 has any standard library support for networking. C++ Weekly Episode 345: No Networking in C++20 or C++23 <https://www.youtube.com/watch?v=v6m70HyI0XE> Standard library support for serial ports has never been proposed AFAIK. Writing a network aware application is much, much more than just saying "give me a socket" (despite what the show "24" may have led you to believe). A socket is just providing the transport mechanism and that's just the start of your troubles. From there you have to implement some sort of protocol on top of the transport. On top of that protocol you have to implement some meaningful application semantics. Utah C++ Programmers has already given presentations on other networking libraries for implementing a REST API on top of application data structures. You can view those presentations on our Network Programming playlist: <https://www.youtube.com/playlist?list=PLJDO7P5jAoXzQvuy7UjFoDSdSy_FLqfOf> But hey, spend 5 years coding up something similar on raw sockets with a C API if you like. Nobody is *making* you use a higher-level library. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| Muttley@dastardlyhq.com: Feb 17 09:33AM On Fri, 17 Feb 2023 04:16:30 +0100 >> Plus the standard C sockets API is fairly simple so why you'd >> need it wrapped up in that outdated library is anyones guess. >Boost.ASIO is usually more performant than manual socket calls Who knows in Windows, but on *nix it'll simply be using the socket API under the hood for networking so that will not be the case. >and easier to use. Unlikely. The main parts of the sockets API are well designed and can be used by dummies. The only awkward bits are the rather arcane types and structures IMO. |
| Muttley@dastardlyhq.com: Feb 17 09:38AM On Fri, 17 Feb 2023 05:40:39 -0000 (UTC) >>[a bunch of hand-waiving statements that are not informed by >>the current reality of network programming in C++ or the current >>state of the ISO C++ standard] Where did I write that? >Troll much? I think that might be you. >Neither C++17, C++20 nor C++23 has any standard library support for >networking. I'm quite well aware of that. >Standard library support for serial ports has never been proposed AFAIK. Wow, thanks for the heads up there. >Writing a network aware application is much, much more than just >saying "give me a socket" (despite what the show "24" may have led you >to believe). A socket is just providing the transport mechanism and Wtf are you babbling about? Wtf is "24"? >that's just the start of your troubles. From there you have to implement >some sort of protocol on top of the transport. On top of that >protocol you have to implement some meaningful application semantics. No shit. Do you expect ethernet cards to be able to speak HTTP? >Utah C++ Programmers has already given presentations on other networking >libraries for implementing a REST API on top of application data structures. Oh fuck off with your REST web shit. It has no place in the sockets API which is to write all that low level code web script kiddies take for granted. >You can view those presentations on our Network Programming playlist: ><https://www.youtube.com/playlist?list=PLJDO7P5jAoXzQvuy7UjFoDSdSy_FLqfOf> No thanks. >But hey, spend 5 years coding up something similar on raw sockets with >a C API if you like. Nobody is *making* you use a higher-level library. Someone has to write the low level code or do you think it writes itself? Also do you know what raw sockets are used for? No, didn't think so. Hint - they're not the same as TCP, UDP or SCTP sockets. |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 17 11:17AM +0100 > Unlikely. ... You've never used it. Socket-Classes are always easier to use. |
| red floyd <no.spam.here@its.invalid>: Feb 17 11:40AM -0800 >> saying "give me a socket" (despite what the show "24" may have led you >> to believe). A socket is just providing the transport mechanism and > Wtf are you babbling about? Wtf is "24"? TV show starring Kiefer Sutherland. Anytime they needed to do something computer related on that show, they had someone "open a socket". |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Feb 17 12:31PM -0800 On 2/16/2023 7:16 PM, Bonita Montero wrote: >> need it wrapped up in that outdated library is anyones guess. > Boost.ASIO is usually more performant than manual socket calls > and easier to use. Never used it. However I am guessing that it uses IOCP on windows, which I have used quite a bit back in the day. Also on Linux it must be using aio? |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Feb 17 12:35PM -0800 On 2/17/2023 11:40 AM, red floyd wrote: > > Wtf are you babbling about? Wtf is "24"? > TV show starring Kiefer Sutherland. Anytime they needed to do something > computer related on that show, they had someone "open a socket". lol. |
| legalize+jeeves@mail.xmission.com (Richard): Feb 17 09:38PM [Please do not mail me a copy of your followup] Welcome to my KILL file. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Feb 17 12:58PM -0800 On 2/10/2023 5:02 PM, Richard Damon wrote: > something like a pipe to the GUI. > If a computation process hangs, you can then just kill it and restart, > maybe letting the user know things are running slow. Humm... I think there is a timer in windows that might "stop" a shader program after some time... |
| Andrey Tarasevich <andreytarasevich@hotmail.com>: Feb 16 10:28PM -0800 On 02/16/23 7:34 AM, Joseph Hesse wrote: > If a non-const argument is given for a copy constructor, with a > non-empty body, does the code in the body execute first or is the > initialization first? Member and base initialization is always carried out first. > In the following example the code in the body > executes first. Where did you get this strange idea? > X x2(x1); > std::cout << x2.getx() << '\n'; // g++ and clang++ output 7 > } Aaand? '7' is the expected output. What made you conclude that "body executes first" here? -- Best regards, Andrey |
| 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