[HN Gopher] Safety vs. Performance. A case study of C, C++ and R...
___________________________________________________________________
Safety vs. Performance. A case study of C, C++ and Rust sort
implementations
Author : bubblehack3r
Score : 146 points
Date : 2023-10-05 17:44 UTC (5 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| voxl wrote:
| This work is significant enough that it should be published in an
| academic venue.
| insanitybit wrote:
| What would the purpose of that be? Genuinely wondering as a
| very non-academic person. Surely academics can just read this
| document?
| davrosthedalek wrote:
| Discoverability. They will not find this document. If it's in
| a journal (or maybe only on the arXiv), it's much much easier
| to find.
| insanitybit wrote:
| Ah, got it, thanks.
| dgb23 wrote:
| Interesting work!
|
| I haven't ever even thought about the issues laid out here in
| such detail.
|
| At first I was scratching my head, but the strength of a sorting
| guarantee actually might matter a lot more than I first thought.
|
| Assuming that something is sorted can have quite substantial
| effects on code. It's a very strong assumption in a sense.
| fluoridation wrote:
| >To me the Results across all tested implementations is
| indicative of a pervasive mindset in the C and C++ world, that
| argues it's the users responsibility to be careful, even if that
| has been proven impossible at scale.
|
| I mean, even if the sort function is implemented in such a way
| that it's impossible to use it incorrectly, the user is still
| programming in C/++. Yes, all else being equal, the harder it is
| to introduce bugs the better, but if the user is not careful they
| will shoot themselves in the foot one way or another.
| prosqlinjector wrote:
| > that argues it's the users responsibility to be careful,
|
| If you try to sort with a function that's not a valid
| comparison operator, I don't know what to tell you. What should
| it do?
|
| Semantics cannot be validated at compile time. The best that
| can be done is to annotate the function as "yes this should
| have the right semantics" as is done in Rust and C++ concepts,
| but that's still not a guarantee.
| jeffbee wrote:
| In C++ your relational operators can return
| std::partial_ordering etc which is a bit more semantically
| meaningful, for the reader and the compiler.
| fluoridation wrote:
| There are still ways for a sort function to not work properly
| with the comparer, even if the criterion is correct. As
| mentioned in the article, the comparer might have internal
| state that the sorter duplicates during intermediate steps,
| thus breaking assumptions made by the caller. The example the
| article gives is a comparer that increments a variable each
| time it's called, to count the number of comparisons.
| Depending on how this is done and how the sorter is
| implemented, copying the comparer may break this behavior.
| itishappy wrote:
| > What should it do?
|
| If I'm reading the article correctly, the user can be
| informed at runtime with little to no performance impact.
| That certainly sounds preferable to returning an unsorted
| list (that may not even match the input).
|
| Almost every Rust sort does this, but no C/C++ sorts do. That
| appears to support that author's conclusion that this is a
| cultural thing.
| jithesh wrote:
| What is @stjepang (author of Rust's unstable sort, and many other
| contributions) doing now?
| gpderetta wrote:
| It is an interesting comparison, but it would be nice to compare
| the same algorithms to understand the cost of each language
| (genericity of c++ over C, safety of rust over C++).
| devit wrote:
| "Unspecified order" seems a poor guarantee.
|
| I think a sort implementation should return elements in an order
| consistent with a subset of the comparison calls it makes, and
| that subset should be such that it fully determines the order.
|
| An even better guarantee is that the subset should be the whole
| set of comparison calls.
| Guvante wrote:
| This isn't just <= vs <.
|
| It is absolutely possible to write a comparator that evaluates
| things in a circle e.g. 1<2 && 2<3 && 3<1.
|
| At that point it is impossible to "do your best" there is no
| correct answers only wrong ones. (You have to violate a
| comparison here)
| [deleted]
| wffurr wrote:
| Is there any existing sort implementation that does this? The
| closest I can think of is stable sorts which aren't quite what
| you described.
| tedunangst wrote:
| Who's going to write the specification for how a sort algorithm
| behaves when the comparator lies?
| xeonmc wrote:
| Zig comptime will yield the fastest result ;P
| j-pb wrote:
| But will it be correct and not encounter a compiler bug? ;P
| littlestymaar wrote:
| _compiler miscompiles and outputs a noop_
|
| Fastest program ever.
| 1980phipsi wrote:
| That would only work for data known at compile-time...
| wredue wrote:
| Any language that reifies types at compile time should have
| reasonably similar performance characteristics given similar
| code. Zig, though, should still end up being easier to make
| faster simply because it's not RAII heavy, and doesn't push
| you over in to dynamic dispatch whenever it feels like it.
|
| The reason I responded to you though, is because comptime is
| not strictly for performing business logic at comptime. Most
| comptime uses are for the reification of code.
| insanitybit wrote:
| What is the connection between RAII and dynamic dispatch?
| [deleted]
| Voultapher wrote:
| Author here, I've spent the last 1.5ish years researching sort
| implementations. While developing a test suite and understanding
| prior art, I've accumulated a list of results and properties I
| thought would be insightful to share. Feel free to ask me
| questions.
| mgaunard wrote:
| Why didn't you consider bitonic sort? It's also a comparison
| sort, and it's typically the fastest one.
| Voultapher wrote:
| Adding onto what the other commenter said, these sort
| implementations are practically all hybrids, containing
| multiple sort algorithms. In fact ipnsort uses optimal
| sorting networks as part of its small-sort
| https://github.com/Voultapher/sort-research-
| rs/blob/bf90e294.... And for example vqsort benchmarked in
| another one of my writeups uses a bitonic merge network to
| combine smaller blocks created from optimal sorting networks.
| kelthan wrote:
| Bitonic sort has a couple of properties that make it poor fit
| for a generic sorting algorithm:
|
| * The number of items being sorted must be a power of 2
| (2^n).
|
| * The number of comparisons it makes is larger than other
| sorting algorithms like merge sort, which will make it slower
| in non-parallel environments in many cases.
|
| Bitonic sort has the advantage that it can be implemented to
| run in highly parallel environments (hardware, FPGAs, etc.),
| where the cost of comparisons is offset by them operating in
| parallel, so the sort completes faster even though more
| comparisons are occurring.
| SleepyMyroslav wrote:
| Two notes from C++ user in gamedev. Please, make realistic
| ValWithPtr implementation for C++. Please, implement comparison
| inlining in C and C++ where algorithm API allows it.
| gabereiser wrote:
| I'm sure the author would accept pull requests if you've got
| the time to show ValWithPtr safety.
| Voultapher wrote:
| The C and C++ code pulls in all thirdparty code as header
| only, making for one single translation unit, and the
| compiler is able to do comparison inlining for the C++
| implementations. I've written a bit about this previously
| [here](https://github.com/Voultapher/sort-research-
| rs/blob/main/wri...).
|
| Regarding `ValWithPtr` my goal was to make it as close
| semantically as I could to the Rust code while keeping the
| example to a minimum to avoid distracting from the main
| point. If you have a concrete idea how `ValWithPtr` could
| have been modeled better given these criteria, please let me
| know.
| SleepyMyroslav wrote:
| C and C++ are often used to achieve max performance. For
| max performance devs have to guarantee inlining. Which
| means programmers intentionally choose bigger code size and
| instantiation of sort algorithm code for every type and
| comparison combination. Function pointers to comparison
| operators are not relevant for max performance part of the
| community.
|
| For ValWithPtr to make sense it needs its semantics
| defined. Correct C++ types can be deep copying, move only,
| reference counted, singleton instance etc. For example
| typed deep copy version without attempting any verification
| (link to compiler explorer):
| https://godbolt.org/z/3sesYY8of
|
| If it is not helpful for you please feel free to ignore all
| of the above.
| akhosravian wrote:
| I'll allow that I'm entirely misunderstanding the goal, but
| why is it important to stick close to the semantic meaning
| of rust code?
|
| How does this differ from implementing GC in C++ then
| showing how much better Java does?
| teunispeters wrote:
| Glad to C doing so well at what it's best at - efficiency and
| size. I worked in embedded space for years. Rust does not suit
| that environment.
|
| Different tools for different needs!
|
| I appreciate this, as looking for better tools in embedded
| space is welcome. Just pity that so many of them come with so
| many dependencies and large library sizes.
| m00x wrote:
| It actually does. You can modify Rust to run without stdlib,
| reducing its size significantly. There are also tons of
| tricks to make this work really well so it's very close to C
| performance.
|
| https://esp-rs.github.io/book/ https://github.com/avr-
| rust/ruduino
| saagarjha wrote:
| C of course generally does not require as many of these
| tricks, which is why people reach for it first.
| Voultapher wrote:
| There are many situations where C libraries are amazingly
| small. This however is not one of those cases. ipnsort is
| aggressively optimized for binary-size. A sort instantiation
| for u64 is ~4.5k while crumsort was ~53k last time I
| measured.
|
| I know several easy ways to boost ipnsort's performance by
| 10% but don't because they don't align with my binary-size
| and compile-time goals.
| morning-coffee wrote:
| > I worked in embedded space for years. Rust does not suit
| that environment.
|
| It seems to be getting better though. For example...
| https://tweedegolf.nl/en/blog/65/async-rust-vs-rtos-showdown
| AlotOfReading wrote:
| Honestly, Rust is a lot closer to ready in the embedded space
| than you probably think. It's perfectly adequate to replace
| most of the embedded C++ out there today and coexist with the
| remaining C.
| uxp100 wrote:
| I kept hearing rust was ready for embedded pretty early on
| (like 2018), and I fooled with it for a bit in 2021 and it
| definitely was not, on the platform I chose at least.
| Updating compiler version (minor update) broke existing
| code, I was relying on one guys hobby to support the
| relatively popular (though fading) mcu I pulled out of my
| parts bin.
|
| What about rust today makes it suitable for replacing some
| code but not all of it? What's better, what still isn't
| there yet?
|
| I guess from my limited experience register fiddling
| ergonomics in rust were miserable, but I was blessed with
| working with an extremely safe and ergonomic set of c
| macros at work (you could do something like rmw(i2s,
| clockconfig, enable, set) and know if it compiled that such
| a value corresponded to a valid value in a field that
| existed in such a register in such a peripheral) and I know
| some vendors provided c "pac" equivalents that were pretty
| sloppy and error prone, if still nicer than all the
| punctuation needed to set a bit in a register in rust. How
| is HAL quality for popular platforms? How much does that
| matter? The stm provided c HAL is extremely limiting in my
| experience, anything fancy requires bypassing it, and I
| worked places without touching the vendor provided
| libraries ever but I guess having it as an option for
| popular platforms is important.
| estebank wrote:
| > Updating compiler version (minor update) broke existing
| code
|
| Could you elaborate on that? That's not something that's
| supposed to happen and if it has, I would like to make
| sure we register it in our issue tracker.
| deciduously wrote:
| Wow, you really are vigilant and omnipresent. Thank you
| for the DX!
| AlotOfReading wrote:
| I'm definitely not the best person to answer this, but
| honestly it's not bad. Here's an example of a moderately
| complex peripheral, the cortex-m MPU, and how one rust OS
| handles it:
|
| https://github.com/tock/tock/blob/3a0527d586702b8ae8cb242
| 391...
|
| Reads and writes turn into volatile reads, so everything
| works out under the hood. You get the benefits of
| everything having good names, declared sizes, and proper
| typing on your register accesses. You can extend that to
| bit accesses as well.
|
| Rust still has a few areas it isn't competitive in, like
| your hyper limited or obscure chips (e.g. 8051s, XAP),
| mature tooling around formal methods, and a certification
| story for safety critical code. People are working on
| these latter two issues (e.g. ferrocene) and supposedly
| very close to public delivery, but you know how slow the
| industry is to adopt new things even then.
| dahfizz wrote:
| TLDR: C is fastest, Rust is safest.
| Ar-Curunir wrote:
| Literally the second paragraph :
|
| " Overall no correlation between performance and safety could
| be found, nor whether safe or unsafe internal abstractions are
| used."
| kobalsky wrote:
| You could replace Rust for almost any language in that
| assertion and it would be true, so it would be good to clarify
| that Rust does not trail of behind C much, and it's even faster
| than C on 4 out of 14 tests.
| queuebert wrote:
| I feel like these tests are really testing the ability of the
| language to give hints to the compiler in its attempt to
| generate efficient machine code.
| ape4 wrote:
| "As seen in the benchmarks, the current Rust standard library
| unstable sort implementation outperforms the C++ standard
| library counterparts. "
| xeonmc wrote:
| and C++ would be easiest?
| huhtenberg wrote:
| Is the plussest.
| morning-coffee wrote:
| easiest to blow your foot off with, yes.
| belter wrote:
| easier to blow your whole leg off according to Bjarne
| Stroustrup
| Voultapher wrote:
| I'm kind of sad that's your takeaway :(
| verdagon wrote:
| I don't think the article made that conclusion? I see this in
| there:
|
| > As seen in the benchmarks, the current Rust standard library
| unstable sort implementation outperforms the C++ standard
| library counterparts
|
| And I can't find any generalizations like that from the author,
| though I may have missed it.
| hawski wrote:
| You're talking about C++, he is talking about C.
| dralley wrote:
| The comparison involved different and not completely
| overlapping sort algorithms. If you want to say this you have
| to first prove it's not just the algorithm.
| verdagon wrote:
| > Often safety and performance are characterized as a set of zero
| sum tradeoffs, yet often it's possible to find better tradeoffs
| who's holistic properties improve upon a previously seen "either
| or".
|
| There is truth in this, but I'm not sure whether the reader
| can/should extrapolate this to larger situations (not that the
| author implied we should, but it was my first interpretation).
|
| We know that in certain situations, borrow checking works really
| well and allows us to guarantee safety with minimal friction and
| no overhead.
|
| But there are other cases where safety and performance _are_ in
| contention, and we must choose one or the other. Anyone who has
| been forced to satisfy the borrow checker by using a .clone(),
| using Rc, or refactoring objects into a hash map and referred to
| them by an ID (that must be hashed to exchange with a reference),
| has felt this contention. In https://verdagon.dev/blog/myth-zero-
| overhead-memory-safety, I concluded that there's no general
| approach that always has zero overhead, at least not yet.
|
| So perhaps the best interpretation from this study is that often,
| for small enough programs/areas, there is no conflict between
| safety and performance.
|
| For larger programs with more complex requirements and data
| interrelationships, the question becomes much more interesting.
|
| > I see no reason why a straight port from Rust to C++ wouldn't
| have been possible while satisfying their requirements.
|
| Like the author, I also don't see a reason for this, but I've
| never tried myself. I've always thought that with the restrict
| keyword, one could make any C++ as performant as any Rust code.
| Perhaps something else got in the way there.
| wredue wrote:
| Sorry, but you are just assuming that the borrow checker is an
| authority of safety, when, even stated by rust lang developers,
| it is not.
|
| The borrow checker is known to be far in to "overly cautious"
| territory.
| verdagon wrote:
| I made no assumption like that, though do let me know if I've
| said something that could be interpreted that way.
|
| Rather, I think that the static analysis we see in today's
| languages just isn't powerful/flexible enough to reason about
| safety in a lot of the patterns that we know are safe. I'm
| also uncertain if it can _ever_ catch up to what we know to
| be safe, but I wouldn't be surprised if we get there in a few
| hundred years.
|
| For example, borrow checking is a step forward and can
| guarantee safety, but does nothing about the other half of
| correctness, specifically liveness. [0]
|
| Linear types (like in Austral [1] and Vale's higher RAII [2])
| can help guarantee liveness, but we still have further to go.
|
| Both are based on single-ownership (in the C++ sense) like
| Rust, which introduces errors that e.g. Haskell would not.
|
| But even Haskell (and LiquidHaskell which has linear types)
| don't go far enough; Coq goes even further.
|
| So yes, like you say, we have a long way to go w.r.t.
| correctness, even past the borrow checker though it is a big
| step forward.
|
| To my original point though, even all of these tools put
| together will put restrictions on a program such that it
| sometimes won't be allowed to take the most optimal approach.
| Perhaps someday we'll get there!
|
| [0]
| https://en.wikipedia.org/wiki/Safety_and_liveness_properties
|
| [1] https://austral-lang.org/linear-types
|
| [2] https://verdagon.dev/blog/higher-raii-7drl
| wredue wrote:
| > But there are other cases where safety and performance
| _are_ in contention, and we must choose one or the other.
| Anyone who has been forced to satisfy the borrow checker by
| using a .clone(), using Rc, or refactoring objects into a
| hash map and referred to them by an ID (that must be hashed
| to exchange with a reference), has felt this contention.
|
| Yes. You literally did assume that the borrow checker is an
| authority, as seen here.
|
| To be frank with you, given that zig is 95% of the way
| there, I feel that you are "diving off the deep end" when
| stating things like "Haskell doesn't go far enough".
| Haskell typing system is a nice experiment, but I don't
| believe to be good in any capacity, let alone "not going
| far enough".
|
| Haskell, in my opinion, a great case of "solving a problem
| before even asking what the problem really is".
| Veserv wrote:
| They obviously meant safety in the sense of "knowing the
| operation is safe because it is checked". You can tell
| that was the intention because they say "forced to
| satisfy" which indicates the stated operation is
| unnecessary, but needed to appease a overly cautious
| checker. In addition, in the previous sentence they say
| "allows us to guarantee safety with minimal friction" to
| indicate they are talking about automatic safety
| guarantees, not the abstract concept of safety.
| _a_a_a_ wrote:
| So what problem do you think Haskell thinks it's solving?
| wredue wrote:
| I haven't the foggiest clue what problem Haskell is
| solving, because as far as I can tell, it doesn't solve
| any problem particularly well. Hence "solving the problem
| before even asking what their problem actually is".
| _a_a_a_ wrote:
| "Designed for teaching, research, and industrial
| applications" - from wikipedia (2nd sentence)
|
| Seems to have done pretty damn well IMO. Not that I've
| used it for 25 years, but I liked it and it introduced me
| to FP which totally changed how I thought of programming.
| I guess we have to differ on this.
| wredue wrote:
| Yes. It changed how you thought about programming *for
| the worse*.
|
| Whereas I believe that concepts are tools for programmers
| to reach for when appropriate, functional programmers
| believe concepts are rules and reaching for them should
| be mandatory, no matter how much bullshit they force you
| to add for no reason other than you accepted from the get
| go that, for example, immutability should be mandatory.
|
| This is a massive fundamental problem with Haskell and
| all language that take hardline stances on things that
| are better left to the users. In this regard, I'd say
| it's a complete failure. It's horrible for teaching. You
| need to know more than you need to know for Java just to
| use it. It's horrible for research. It has hardline
| fundamental stances that rejects exploration, and
| therefor is research averse. It is horrible for
| industrial applications as there are massive ranges of
| industry that simply cannot give to the whims of Haskell
| for one reason or another, but probably multiple reasons
| cause Haskell is terrible.
| _a_a_a_ wrote:
| I'm pretty sure you don't have a clue or any significant
| experience, and too much arrogance to stop and question
| your own assumptions which you've just imposed on others
| including me, but carry on anyway.
| borlanco wrote:
| > "This is a massive fundamental problem with Haskell and
| all language that take hardline stances on things that
| are better left to the users".
|
| Thank you. This is completely and utterly true.
| [deleted]
| Guvante wrote:
| Honestly I think unsafe Rust is the solve here. Often you have
| an isolated data structure that is relatively simple that needs
| to break the borrow checker rules (without invoking UB such as
| multiple mutable references). An often times a safe API can be
| written on top of that.
|
| However the current state of this is absolutely terrible. A lot
| of work needs to be done to improve the development experience
| with this model if it is to be used effectively in this way.
| thaliaarchi wrote:
| I'm surprised to see that the author's ipnsort is not published
| on crates.io, even though it performs at first or second place on
| most of the benchmarks for unstable sorts and it passes all the
| safety and correctness criteria, all while also being able to
| deterministically panic to inform the user of a logic bug in
| their comparison function.
|
| https://github.com/Voultapher/sort-research-rs/tree/main/ipn...
| Voultapher wrote:
| It's designed as the new `slice::sort_unstable` stay tuned.
| kibwen wrote:
| Is there a PR or internals discussion that we can follow?
| natsucks wrote:
| can we just move on from C/C++ already
| jimbob45 wrote:
| We can't even move past FORTRAN and Cobol, let alone C/++.
| bee_rider wrote:
| Fortran added the most important OO feature, methods bound to
| types, around 2003. Therefore, it is a more modern object
| oriented language than C++, in the sense that the object
| oriented features were Frankensteind on more recently. So
| maybe we could move past C++ to it.
| petschge wrote:
| Why would we want to move away from them? Fortran is VERY
| good at what it is intended for (implementing formulas in
| code).
| Guvante wrote:
| You don't just "move on" from a multi million line code base.
|
| Hell everything only works by interoping with those languages
| given the OS is written in one of them.
| mgaunard wrote:
| why? is there a real alternative? (no there isn't)
| LAC-Tech wrote:
| Zig is getting there. Very ergonomic at doing the kind of bit
| bashing stuff people might reach to C for. It's about as easy
| to use C libraries in Zig as it is in C++.
| omgmajk wrote:
| Zig is the future, Zig and C as a combination is amazing
| and in my opinion will change everything.
| FpUser wrote:
| What is holding you? And if you mean the rest of us - live and
| let live.
| natsucks wrote:
| What's holding me? People writing software who are choosing
| C/C++ for legacy reasons only.
| FpUser wrote:
| I do not use C++ just for legacy reasons. And frankly I do
| not give a flying fuck about holding people like yourself.
| You are free to do as you please, do not expect others to
| provide for you.
| [deleted]
| prosqlinjector wrote:
| Currently employed writing new C++ btw.
| omgmajk wrote:
| Currently employed writing new C btw. It's not holding me
| back one bit.
| JohnFen wrote:
| When I use C or C++, it's certainly not for legacy reasons.
| And my use of it doesn't prevent you from using a different
| language.
| Conscat wrote:
| Other languages need tooling and featurefulness that is
| overall on par with C++ first. So far no low level language
| has profilers and debuggers that are as good, none have
| nearly as many compiler hints, and most are far harder to
| write zero overhead abstractions in. Not all developers
| need these tools all the time, but their availability is
| what keeps C++ attractive.
| ActorNightly wrote:
| C no. Linux is C, and it works well.
|
| C++ yes, there is no real reason to use C++ anymore outside of
| big libraries that require it.
| jltsiren wrote:
| There is no real reason to use C++ anymore, except that it's
| often the only language you can practically use. Or, in other
| words, you end up using C++ because there are too many people
| designing new programming languages and too few people
| writing libraries for the existing languages.
| geertj wrote:
| > C++ yes, there is no real reason to use C++ anymore outside
| of big libraries that require it.
|
| Some of us like C++ because it gives us a the freedom to work
| at the lowest level when we need to, while also giving us
| plenty of higher level APIs for most day to day situations,
| while having great compatibility with tons of software that
| is already out there. It seems we are at peak Rust fanboyism
| these days. I have nothing against Rust but the idea that
| Rust has already replaced C++, or will certainly do so in the
| future, is ludicrous. C++ has a ton of activity in the
| standards committee and has very interesting developments
| like cppfront. It is a vibrant community that continues to
| reinvent itself and in all likelihood is a lot larger than
| the Rust community.
___________________________________________________________________
(page generated 2023-10-05 23:01 UTC)