6 ms·
I suppose that you could just use C with std::vector and std::unique_ptr from C++, and you’d be much better off. The you could still write "C" code but not worr
by petters 10y ago
I suppose that you could just use C with std::vector and std::unique_ptr from C++, and you’d be much better off. The you could still write "C" code but not worry about memory leaks.
Of course, you also need std::sort because it is much faster than qsort. Thinking about it, you probably want to implement all time-critical algorithms with generics.
... never mind, this quickly becomes a stone soup.
- bluecalm 10y agoI keep hearing that std::sort is faster than qsort yet when I benchmarked it with GCC it was the exact same performance which makes sense as modern compiles are either to optimize function calls through pointers. Anyway, both are significantly slower than macro based library based on removing function calls altogether (not the one in comparator but the recursive qsort calls). For things I would like to use C for std::vector is not very useful either as it grows in some generic way which is likely wasteful for specific applications. If an algorithm is time-critical then almost by definition the generic implementation in standard library won't be enough.
- userbinator 10y agoOn the other hand, "inline" too much code which is faster when benchmarked in isolation, and thanks to cache effects you may end up with worse performance as now less code fits in the cache.
- gpderetta 10y agoOn the gripping hand, dead code elimination after constant and range propagation, might make the dynamic cache footprint the inline ed code smaller.
- pjmlp 10y agoThe thing is, there isn't one std::sort, neither one C++ implementation. Try that with ICC instead, for example.
- rleigh 10y agoSo for std::vector you avoid the "generic way" and specify the size up front or when needed with reserve. Just as efficient as a realloc in C. Many things can be inefficient or wasteful, but vector allocation and resizing isn't one of them if you care to use it effectively.
- gpderetta 10y ago> removing function calls altogether (not the one in comparator but the recursive qsort calls). That's an impressive feat as quick sort is not tail recursive. Edit: you can of course maintain the recursion stack by hand but that's not normally a win.
- bluecalm 10y agoI am not sure why you think it's not normally a win. It is quite a big win in qsort implementation at least.
- petters 10y agostd::sort was about twice as fast (!!) last time I ran my benchmark. I don't think std::sort would be slower than a macro based liberty. Obviously, you can reserve memory in a vector in the beginning. > If an algorithm is time-critical then almost by definition the generic implementation in standard library won't be enough. I'm afraid I'll have to disagree here as well.
- petters 10y agoReran the std::sort vs. qsort benchmark: Visual Studio 2015: 1.79x WSL gcc 6.2: 1.92x WSL clang 3.8.0: 2.08x Ubuntu 16.10 VM gcc 6.2: 1.68x Ubuntu 16.10 VM clang 3.8.1: 1.89x All in favor of std::sort.
- ArkyBeagle 10y agoExactly - it quickly becomes a stone soup. The main use case of a code base that is of value to me is: Can someone quickly determine that they have added a defect when doing maintenance? There are a lot of solutions to that.