- Efficiency of standard containers - 1 Update
- Efficiency of standard containers - 1 Update
- Qucksort for Linked List - 2 Updates
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 21 12:16AM +0100 On 20.12.2016 23:37, Stefan Ram wrote: > explains how they made facebook much faster by replacing > ::std::string with their fbstring, which uses a very > efficient small-string representation. For a long while Facebook had Andrei Alexandrescu to do C++ stuff for them. As I understand it he's now devoting his time to D language development. But during this long period Facebook had the luxury of having a superb C++ designer, so they could afford the DIY approach, while with most any other company it would have ended in tears. That said, I mostly agree with the sentiment that one can do much better than the standard library, both in terms of efficiency, code clarity and readability, and convenience. This is especially so for strings and formatting. But in the high circles that lead opinions, this stuff is highly politicized, possibly about what arguments have been forwarded to make changes in the standard, and irrational excuses are put forward. E.g., on SO there was ¹a question whether C++11 disallowed the copy-on-write optimization for `std::string`. The real answer to that is yes, because C++ requires indexing to be constant time always, i.e. unsharing of a buffer can't be put off till indexing time. I provided that answer and it got 2 downvotes and no upvotes. But the politically correct answer, accepted on SO with lots of upvotes, is that correct COW is impossible (that's incorrect) because "calling non-const operator[] would require making a copy (and invalidating references), which is disallowed". That answer is a self-contradiction – because in a correct implementation there are no references to be invalidated at the time of a buffer unsharing, it's unshared precisely because the possibility of a reference looms on the horizon – but in spite of being obvious bollocks, just a self-contradiction, it's upvoted 86 times. Cheers!, - Alf ¹ <url: http://stackoverflow.com/questions/12199710/legality-of-cow-stdstring-implementation-in-c11> |
| ram@zedat.fu-berlin.de (Stefan Ram): Dec 20 10:37PM The new C++ primer says that the new library containers are faster than ever and perform as well or better than everything one can hope to write oneself. Chandler Carruth used to say in 2014 that all the ::std:: containers have such hindering requirements that one can use only ::std::vector when one cares for efficiency, but in 2016 he says that because of the impossibility of the small-size optimization even ::std::vector is unusable when one wants efficient code. He than describes clang's fast "SmallVector" implementation, while someone from Facebook explains how they made facebook much faster by replacing ::std::string with their fbstring, which uses a very efficient small-string representation. |
| Juha Nieminen <nospam@thanks.invalid>: Dec 20 07:18AM > So qsort is 40% slower than merge sort on a linked list eh Gareth > matey?. So I was correct. 40. %. slower. Your problem is that you don't understand what asymptotic complexity and the big-O notation mean. Your claim was about the asymptotic complexity of quicksort on linked lists, not on absolute speed (ie. in practice the constant factor in terms of computational complexity). In addition to that, you weren't comparing quicksort on linked lists to merge sort on linked lists. You were comparing quicksort on linked lists to quicksort on random access arrays (and claiming that the former is worse in terms of asymptotic complexity). It's useless to now cling onto those quicksort vs mergesort numbers, because that wasn't your original claim, nor what people objected to. |
| leigh.v.johnston@googlemail.com: Dec 20 04:31AM -0800 Mr Flibble fully understands asymptotic complexity and Big-O notation. Mr Flibble claimed that the worst case complexity was more likely due to poor pivot choice. Again Mr Flibble didn't claim the former was worse in asymptotic complexity just that worst case complexity was more likely. |
| 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