8 ms·
What a terrible article. It starts with the comparison of a general-purpose hash table with specifically-tailored one. Then it throws in a switch from a compa
by bluescarni 8y ago
What a terrible article.
It starts with the comparison of a general-purpose hash table with specifically-tailored one.
Then it throws in a switch from a comparison-based sort to a radix-based one.
Then, the stunning discovery that std::vector value-initialises its elements (fixable with 3 lines of a custom allocator, if you don't want that behaviour).
In the middle, it preaches about portability while at the same time advocating the use of __builtin functions vs standard functions, and type-punning floats to int and back (undefined behaviour in C++).
And all of this for a 572ms -> 320ms performance improvement?
- gpderetta 8y agoIn the grand tradition of HN i haven't read the article (but in my defense it is blocked by work's firewall). Still, if he claims that unordered_map has issues he is not alone. It is well known that the standard requirements preclude a more efficient implementation. And the issue with vector value initializing it's elements is also well known and programmers have been asking for a solution (more user friendly than a custom allocator) for a long time.
- jcelerier 8y agoI don't understand the problems. Want a better hash map ? Use whatever makes your day here : https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... ; they are all header-only just like the standard library's. Want a vector that does not initialize its elements ? Ask and thou shalt receive: https://github.com/aguinet/pector https://github.com/aguinet/pector The whole point of C++ is to make it easy for people to write generic libraries beyond de standard base provided by the stdlib. So why won't you use those ?
- gpderetta 8y agoOh, I'm in violent agreement. The single biggest contribution of the STL is its set of concepts more than the actual implementations. If you do not like the specific tradeoffs for a container or algo implementation, you can swap it for a different implementation often without code changes. I.e. you do not need to remove abstraction, you just swap it for a different one. Still it is fair to critique the specific tradeoff done by the standard library.
- stochastic_monk 8y agoIt’s the linear chaining effectively required by the standard. I had an application years ago which was 10x as fast after dropping in khash over unordered_map.
- gpderetta 8y agoIIRC that's because of the iterator and address invalidation requirements that effectively require an node based implementation. But if your code does not rely on these guarantees then, as you suggest, you can swap it with a different implementation with the same interface. You do not have to pay for what you do not use.
- deleted 8y ago[deleted]
- bluescarni 8y agoI wonder what the reaction would have been if he/she had written a blog post explaining how moving from list to numpy.array for storing numerical data in Python resulted in massive performance benefits. You gotta admit the situation is kinda similar. What is unfriendly about custom allocators? Note that in this specific case you don't need to write any allocation function, you just have to re-implement the construct() function with something that does not value-initialises if no construction arguments are provided.
- twtw 8y ago> You gotta admit the situation is kinda similar. I disagree. 1. Everybody knows Python is a scripting language, and trying to do heavy computation without handing it off to a library is going to be slow. 2. A vector is the de facto data structure for this in c++. In Python, numpy is effectively the de facto approach for math.
- bluescarni 8y agoSorry but I think this is still an apt analogy. 1. "Everybody" knows that unordered sets/maps in C++ must de-facto use chaining due to the requirements imposed by the standard. 2. numpy.array is not part of the Python standard library. It is an extra component you still need to install separately. As someone who deals regularly with novice Python users (often coming from Matlab & the likes), one of the very first points of pain/confusion is the fact that I need to teach/convince them not to use the facilities of the core language to represent "vectors".
- gpderetta 8y agoChanging the allocator changes the type of the vector, which has ABI/API implications, especially if the vector type is not under your control. Also, IMHO tying allocation with initialization in the allocator concept is not one of C++ brightest moments. There have been continuous talks about adding an unsafe_push_back and an unsafe resize for these and other reasons.
- stochastic_monk 8y ago
- CoolGuySteve 8y agoIf you're rapidly removing and adding, a simple fix for unordered_map is to add your own stack allocator. That way the memory you touch for it's lists is nearly always hot. The same technique vastly improves map and set too.
- twtw 8y ago> advocating the use of __builtin functions vs standard functions It wouldn't say it "advocates" for the use of builtins. The author demonstrates a problem they had (including math.h made their compile times 2x slower in c++17 mode) and shows their solution, and advocates changing libc++ so that c headers don't pull in c++ stuff. In any case, the snippet you object to uses the builtins if they are available, or falls back to math.h. It's a hack to avoid math.h when it's slow to compile, but stills seems pretty portable?
- dajonker 8y agoMaybe the title of the article is bit unlucky, if it was named "how I made my library faster and more compatible", would that change your opinion? And yes, it's only a 252 ms improvement, but that's a whopping 44% time saved. If you need to do lots and lots of mesh optimizing, that might be very well worth it.
- MauranKilom 8y agoYeah, but moving towards C is not where those 44% came from.
- _prototype_ 8y agoA 44% performance improvement does not sound good to you?
- MauranKilom 8y agoOf course it sounds good. But you could get basically the same improvement while staying fully within C++ idioms. The correct title would be "Is my library fast without performance tuning?".
- stcredzero 8y agoWhat a terrible article. I thought it was ok. Asking "Is C++ fast?" is a little like asking if internal combustion engines are fast. The actual answer is, "It depends." The content is ok for this site, which also has people who are just starting out with optimization or who might not be that familiar with C++. "Is [lang] fast?" is a typical clickbait tactic which works by nibbling at a programmer's pride. Here's the thing. Either one is a bit naive, the pride is hurt and the clickbait works, because one isn't seasoned enough to know that optimization is a complex subject within a complex world of tradeoffs or you're so invested in making things fast (possibly so good at it) that you can't resist taking it apart. And all of this for a 572ms -> 320ms performance improvement? 78%? "Not tea bag!" as AvE would say.
- johndubchak 8y ago"Value-semantics is the way to optimal performance!", said no one, ever.
- bitkarma 8y agoI never did figure why the author insisted on reporting the runtime statistics for the debug build.
- scott_s 8y agoFrom the post: >One number that we haven’t moved substantially yet is the time it takes to run this code in debug using MSVC. While it’s natural to expect unoptimized builds to be slower than optimized, they have to be fast enough. Sometimes you want to debug your problem on a non-trivial input dataset. Sometimes you want to run the debug build with full checks through your tests to make sure they don’t trigger any bugs that could disappear in release. Sometimes you are trying to debug a different part of the program, but you still need to run the rest of it. The library, by the author, is https://github.com/zeux/meshoptimizer https://github.com/zeux/meshoptimizer. I presume it will be used in graphics pipelines. Debug builds working at a speed that allow graphics to be tolerable by humans sounds like a good goal to have.
- sctb 8y agoCould you please nudge the criticism a bit towards information and away from theatrical dismissal? It's not wrong to react that way to the article, but when we post here we want to focus on what we can learn.
- dan-robertson 8y agoI would interpret the article as one with the following abstract: C++ has a lot of generic programming solutions like std::vector and algorithms, [and we think of these things as being fast even though they are generic because of templates and “zero cost abstractions”] but we show that we still pay for their being generic (because they must support operations which make everything else expensive, or are doing more work than we need done), and so [for situations like this] we prefer the trade-off of implementing specialised functions that may be similar to other functions elsewhere to gain runtime and compile-time performance improvements. We demonstrate this thesis with a case study of a mash simplification algorithm. I think this is a reasonable topic to write about, and I think the article does an ok job of it. I think it is silly to get hung up on specific cases (e.g. you need to do some magic custom allocator thing to make a c++ thing about as cheap as a c thing that achieves the purposes you have, or that you might want to replace an exact sort with an approximate one (note that in this case, using a full radix sort would have you pay 30ms instead of 10, so 572 -> 340ms which is still a large improvement, and one that will become larger with larger inputs)). I think one should instead treat it as a case study which shows some general ideas like “you often do pay for what you don’t use in c++/stl” or “often one can use a more specialised algorithm with much better performance then a general one so when one is writing performance sensitive code, having generic algorithms to hand may not be useful”
- scott_s 8y ago> And all of this for a 572ms -> 320ms performance improvement? The library is supposed to be part of a graphics pipeline. It will be called many times a second, and it will be part of what the eventual framerate is.