tag:blogger.com,1999:blog-7101933101966798446.post8333551973094727411..comments2024-03-17T08:14:57.577-07:00Comments on The View from Aristeia: Should you be using something instead of what you should use instead?Scott Meyershttp://www.blogger.com/profile/05280964633768289328noreply@blogger.comBlogger72125tag:blogger.com,1999:blog-7101933101966798446.post-18167888553926128272015-11-14T05:47:57.707-08:002015-11-14T05:47:57.707-08:00Two particular problems with unordered containers ...Two particular problems with unordered containers which I have not seen coming up in performance discussions are construction time and memory footprint. For (many) relatively short-lived objects aggregating such containers, unordered ones are - in my experience - the least favorable choice. The numbers here suggest universal applicability of unordered sets although they come with real and hard disadvantages. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-79534200406147626072015-09-23T08:53:53.290-07:002015-09-23T08:53:53.290-07:00@Ben Craig I understand, but in my modification of...@Ben Craig I understand, but in my modification of Scott's code the lookup value is also a random-length string of up to 1000 chars. I understand that both Clang & GCC use a variation of the murmur hash which operates 4 bytes at a time, so assuming a lookup value 500 chars in length on average, that would be around 125 operations per lookup ignoring collisions. The largest container Scott's code tests is 100,000 elements, so a sorted container should be able to find the right element in about 16 lexicographical comparisons. Assuming the lexicographical comparison stops at say the 4th character on average (assuming keys are sufficiently random), that's about 64 operations. Add to that the fact that sorted container lookup operations are simple operator<() comparisons, while a hash function operation is more complicated.<br /><br />If anything could explain this, it's probably your point that sorted containers have to bring every element to the cache to compare it with the key, while unsorted containers operates solely on the key. That could probably explain why they're more efficient in the case of string keys too.Haitham Gadhttps://www.blogger.com/profile/06179137492849085754noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-8355187080417619432015-09-23T06:21:41.464-07:002015-09-23T06:21:41.464-07:00@Haitham Gad
When doing a lookup in an unordered m...@Haitham Gad<br />When doing a lookup in an unordered map, you only hash the item that is being looked up. That hash directs you to the appropriate bucket. Once you are in the correct bucket, op== is called on each collision. You generally don't hash the target item during a lookup.<br /><br />So for a successful lookup, you end up hashing one string that is likely already in the cache, and then you do one full op== operation on the successful item, with some number of unsuccessful op== operations for the collisions.<br /><br />Also note that for strings that are too long to hit the small string optimization, you are likely to get even more cache misses when looking at the characters in ordered containers.Ben Craighttps://www.blogger.com/profile/01237025391218848306noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-16182918295664914862015-09-23T03:11:24.827-07:002015-09-23T03:11:24.827-07:00@Scott Meyers Exactly, but that's a point in f...@Scott Meyers Exactly, but that's a point in favor of sorted containers (which perform lexicographical comparisons). Hash functions would still have to scan the full string to calculate the hash. Yet, unordered containers are still faster according to the graph.Haitham Gadhttps://www.blogger.com/profile/06179137492849085754noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-35671648264525484972015-09-22T22:07:53.403-07:002015-09-22T22:07:53.403-07:00@Haitham Gad: I didn't check your source code,...@Haitham Gad: I didn't check your source code, but it seems to me that if you chose truly random strings, most would likely differ in the first one or two characters, so a comparison would not have to look at very much of each string. Strings selected by humans (e.g., names) are likely to be much less random than truly random strings of characters, I think. But that's just speculation on my part.Scott Meyershttps://www.blogger.com/profile/05280964633768289328noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-43738816504414375692015-09-22T19:34:34.588-07:002015-09-22T19:34:34.588-07:00@Scott Meyers I had the same thought as @jensa. In...@Scott Meyers I had the same thought as @jensa. Intuitively, running a hash function on two relatively long strings and comparing the hashes should be slower than comparing the two strings lexicographically and looking for the first mismatch. However, it seems this is a wrong intuition. I did a slight modification to your program by changing the keys to be random-length strings of up to 1000 characters with characters drawn randomly from a set of 93 different symbols. The resulting graphs on Clang 3.6, Intel Core 2 Duo looks similar to yours.<br /><br />Gist: https://gist.github.com/hgad/7178e03fcdfaa571f5de<br />Graph: https://www.pinterest.com/pin/317574211202963438/Haitham Gadhttps://www.blogger.com/profile/06179137492849085754noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-82046936330885443002015-09-21T21:51:47.704-07:002015-09-21T21:51:47.704-07:00@Rein Halbersma: Thanks for the suggestion, but I&...@Rein Halbersma: Thanks for the suggestion, but I'll let others tackle that topic. It's an area I haven't looked into very much, sorry.Scott Meyershttps://www.blogger.com/profile/05280964633768289328noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-76983464642648607862015-09-21T14:05:09.842-07:002015-09-21T14:05:09.842-07:00Scott, as a suggestion for a possible sequel to th...Scott, as a suggestion for a possible sequel to this interesting installment on container performance, I'd be interested in your take on various vector optimizations and variations. There's array (C-style or std::), there is Hinnant's short_allocator, Boost/Facebook Folly have small_vector (small string optimization for vector, non-conformant) and static_vector (push_back and other things with fixed array memory capacity), and there's the still zombie-like proposal for dynarray. Rein Halbersmahttps://www.blogger.com/profile/09512938204991225090noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-40956876676558089552015-09-20T09:47:32.066-07:002015-09-20T09:47:32.066-07:00Recent comments on this blog have focused on wheth...Recent comments on this blog have focused on whether I'm qualified to offer advice on C++ programming and, more generally, on what kinds of qualifications somebody offering such advice should have. Those are legitimate topics for discussion, but they're not related to this blog post. I've therefore removed all comments of that nature except for the first few. (I'm retaining the first few so as not to pretend that the discussions didn't occur. I'm not an enthusiast of revisionist history.) To debate who should be giving advice about C++, please find a different forum.<br /><br />I've changed my comment moderation policy so that I must approve new comments before they appear. This means that comments you leave on my blog may not show up for a while. My normal moderation policy is to screen only comments for blog entries that are at least 30 days old. I'll reinstate that policy when this blog entry reaches that point (on October 15).<br /><br />I continue to welcome comments about the substance of any of my blog posts, even if the comments are critical. <br /><br />As for feedback on my decision to remove some comments pertaining to this blog post and to temporarily impose a stricter moderation policy, I will not permit those to be published, regardless of whether they applaud or condemn my decision. To get a comment posted, you'll need to write about something related to the lookup performance of different containers in the Standard Library.Scott Meyershttps://www.blogger.com/profile/05280964633768289328noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-88187756439957571602015-09-20T06:29:34.004-07:002015-09-20T06:29:34.004-07:00This comment has been removed by a blog administrator.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-76744648740319073532015-09-20T06:15:33.504-07:002015-09-20T06:15:33.504-07:00This comment has been removed by a blog administrator.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-67126408224121748172015-09-20T05:53:27.038-07:002015-09-20T05:53:27.038-07:00This comment has been removed by a blog administrator.jensahttps://www.blogger.com/profile/12096756960804348733noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-89814025468161301092015-09-20T05:13:07.944-07:002015-09-20T05:13:07.944-07:00This comment has been removed by a blog administrator.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-89225716593446377162015-09-20T05:08:41.148-07:002015-09-20T05:08:41.148-07:00This comment has been removed by a blog administrator.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-81941941839701192182015-09-20T05:08:00.015-07:002015-09-20T05:08:00.015-07:00This comment has been removed by a blog administrator.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-29741929228738816042015-09-20T04:25:26.529-07:002015-09-20T04:25:26.529-07:00This comment has been removed by a blog administrator.jensahttps://www.blogger.com/profile/12096756960804348733noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-61269107510199253422015-09-20T03:50:06.260-07:002015-09-20T03:50:06.260-07:00This comment has been removed by a blog administrator.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-25347102714569723912015-09-20T02:57:46.370-07:002015-09-20T02:57:46.370-07:00This comment has been removed by the author.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-4132497084612928232015-09-19T20:59:43.254-07:002015-09-19T20:59:43.254-07:00@Unknown: Thanks for your kind words. I'm glad...@Unknown: Thanks for your kind words. I'm glad you've found my work helpful.Scott Meyershttps://www.blogger.com/profile/05280964633768289328noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-88550053527450467302015-09-19T19:10:35.126-07:002015-09-19T19:10:35.126-07:00@Knowing me, knowing you, a-ha: you need to move o...@Knowing me, knowing you, a-ha: you need to move on to something else. Many of us appreciate and learn from the work Scott does. If you have nothing left to learn, or you can get your knowledge elsewhere, great. Scott: I've been a software developer for decades, and have no shame admitting that my career as a C++ developer was given a significant boost (no pun) when I came across your first book in the mid-1990s. I own your books, have been to 3 of your workshops/presentations, and continue to look forward to learning.Anonymoushttps://www.blogger.com/profile/03122556592697269644noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-23860400824981554402015-09-19T04:24:05.784-07:002015-09-19T04:24:05.784-07:00"Your job is to employ C++ as a tool to write..."Your job is to employ C++ as a tool to write useful software. My job is to discover and package the information you need to best apply that tool."<br />First of all, please don't tell me what my job is. Instead let me tell you what really my job is:<br />My real (that meaty and what really matters at the end job) is to write/maintain real programs, and that what you've described as "your" job, I (and most of the *real* programmers) do that so called "your job" during breakfast, lunch and spare free time. You surely are not that arrogant and you surely don't think that real programmers can't think for them - self and don't do their research, don't learn new things and discover new and important things on their own, without your or people like you help? Every real programmer does it. But we do it (that what you called "your" job) as I've just said, in our **free** **spare** time.<br /><br />Now let me tell you what your job is:<br />You've invented job for yourself, job in where you do something for living what real programmers do during their lunch (and other) breaks.<br /><br />Programming is very practical, hands on task profession, and without practical knowledge of that subject you (as you've proven in this article and others), you have really no real/deep knowledge of what you're talking about. Not only that, you give very often incorrect and misleading information. Why? Because the sad true is that you don't have practical knowledge of what you're talking about.<br /> <br />I tell you who you are:<br />An amateur, snake-oil salesman and good people (especially beginning programmers) should be warn against you.<br />I personally have no respect for you as a professional, because you're not a professional.Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-32459364701601202702015-09-18T21:21:57.459-07:002015-09-18T21:21:57.459-07:00Obviously, this analysis completely leaves out ins...Obviously, this analysis completely leaves out insertion speed, deletion speed, and turn-around time, and whether or not these are important depends on your workload.<br /><br />One of the common "use cases" for sets is when you need to process a bunch of things which may have duplicates, but ensure that you only process them once. The turn-around time between insert and lookup is crucial here, so even sorted arrays don't work well in this case.<br /><br />But while I'm the topic, I'd like to point out that every single std::unordered container that I've used in C++ have a performance bottleneck which makes them difficult to use well in some scenarios: the prime hash policy.<br /><br />It seems that a lot of peoples' knowledge about hashing dates from somewhere between the 1970s and the 1990s. Back in the day, the advice was to use a cheap-but-reasonable hash function, then make your hash tables a prime size. On modern pipelined CPUs, this is terrible advice.<br /><br />The performance gap between division and all other arithmetic operations has widened considerably; modern multipliers are fully pipelined and can issue and retire one multiply per cycle. Division, on the other hand, is still a high-latency low-throughput operation. This means that the "divide by a prime" operation can be a bottleneck.<br /><br />And then there's the advent of SIMD instructions. Today, it's almost as cheap to compute two or even four hash functions simultaneously as it is to compute one. This means that hash techniques which use multiple hash functions (e.g. double hashing, cuckoo hashing) are extremely competitive.<br /><br />What I guess I'm trying to say is that if your set implementation is a bottleneck, you probably should prepare yourself for the fact that the standard containers won't help you.<br /><br />Oh, and don't forget Boost's intrusive containers, which certainly help with memory usage.Pseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-75403507527005344552015-09-18T09:49:14.347-07:002015-09-18T09:49:14.347-07:00@Knowing me, knowing you, a-ha: I've been on r...@Knowing me, knowing you, a-ha: I've been on record for many years as not being a professional programmer. For example, in <a href="http://www.artima.com/cppsource/top_cpp_books.html" rel="nofollow">this 2006 article</a>, I wrote:<br /><br /><i><br />I’ll begin with what many of you will find an unredeemably damning confession: I have not written production software in over 20 years, and I have never written production software in C++. Nope, not ever. Furthermore, I’ve never even </i>tried<i> to write production software in C++, so not only am I not a real C++ developer, I’m not even a wannabe. <br /></i><br /><br />A bit later in that article, I write:<br /><br /><i><br />Fundamentally, I study C++ and its application. I gather as much information as I can about the language and its use (from books, magazines, newsgroups, email and face-to-face conversations with developers and members of the standardization committee, experiments with toy programs I write, etc.), organize and analyze what I find, then I package my findings in concentrated form (e.g., books, magazine articles, technical presentations, etc.) for consumption for people like you—people who </i>do<i> use the language. Your job is to employ C++ as a tool to write useful software. My job is to discover and package the information you need to best apply that tool. <br /></i>Scott Meyershttps://www.blogger.com/profile/05280964633768289328noreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-89361439900735572262015-09-18T03:30:29.677-07:002015-09-18T03:30:29.677-07:00I find I prefer sorted containers over unordered c...I find I prefer sorted containers over unordered containers for two reasons:<br /><br />1. you are often able to write more efficient algorithms on sorted data sets.<br />E.g. computing the union or intersection of two sets of elements<br /><br />2. I want output that is both predictable and deterministic.<br />Just changing the size of an internal container or the insertion order of elements should not change a program's output.<br />(obviously less of an issue when used internally)<br /><br />For larger datasets where memory is tight the load factor is a performance killer.<br />However, there has been some work on producing minimal perfect hashes in O(n log n) or slightly better which would be very useful for applications that are construct once and lookup many times.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7101933101966798446.post-52763362083785406842015-09-18T02:33:52.256-07:002015-09-18T02:33:52.256-07:00@Scott Meyers
Sorry about that, fair enough.
But ...@Scott Meyers<br />Sorry about that, fair enough. <br />But please could you answer:<br />Would you consider yourself a *professional* programmer?Knowing me, knowing you, a-hahttps://www.blogger.com/profile/17285302826361363533noreply@blogger.com