This seems totally misguided and inflammatory. The points made boil down to:
1. Overflow checking adds about a 2x overhead to "+" in a loop
2. Using "reduce" rather than a loop also has ~2x overhead
Neither is really surprising, and hardly seems to warrant the final tangent that "I do not think it is universally a good thing that software should crash when an overflow occurs" since "a mission-critical application could crash because an unimportant function in a secondary routine overflows".
What about the mission-critical bugs, especially security bugs, that are caused by overflows?
Swift's default behavior, of aggressively checking for overflows, is at least arguable, and there's a school of thought in software engineering that says "don't nail your code to the wall", i.e. don't try to keep it running at all costs when something goes wrong. Let it crash and restart it. Obviously that approach works well in some scenarios and less well in others. The creators of Swift reckon it's a good default for most programmers and I reckon they're onto something.
The fact that the overhead is only 2x for a tight inner loop should be a cause for celebration, not dire warnings. And as the author himself shows, it's very easy to disable overflow checking on a per-operation basis when you want to.
> The fact that the overhead is only 2x for a tight inner loop should be a cause for celebration, not dire warnings. And as the author himself shows, it's very easy to disable overflow checking on a per-operation basis when you want to.
Agreed. This smells like premature optimization... on a problem that can be solved in O(1) time.
Agreed that it's misguided, inflammatory and presented in the most flame-baity terms. I would have expected this from some random blogger dealing with an unfamiliar programming language, but from a supposed professor of computer science?
Does he really expect sympathy when he considers something as trivial as array.reduce(0,+) "obfuscated"? I've never written a single line of Swift in my life and I -- being familiar with FP idioms -- immediately understand what it means.
The premise that many abstractions and safety checks come at a cost is reasonable. Unfortunately the rest of his post isn't.
How is it inflammatory? If you don't like his opinions or writing style then fine but it's in no way inflammatory. He takes a stab at functional programming fashion, that's all there is to it. He also shows significant performance penalty in the default language construct. If anything it's an informative, if a bit opinionated, post.
It's inflammatory because his main point -- that abstractions come at a cost -- is buried in digs at FP, mock surprise, and claiming really simple things are difficult to understand, when they are not (and I know they aren't difficult to him either, so it's also mock ignorance).
I don't see any deep insight. The performance loss may very well be caused by an immature Swift compiler, and not ultimately tied to the abstraction, but he mentions nothing of this. I expect this lack of understanding from a novice, not from a CS professor.
What he wrote isn't even a "case study", contradicting even the title of his blog.
> It's inflammatory because his main point -- that abstractions come at a cost
It's also not always correct. See the Rust benchmarks posted here.
Someone seeing this article might think it is correct, though, and thusly misinformed, they might avoid "functional-style" programming in the future when in fact many languages manage to provide FP idioms with no performance penalty.
It's irresponsible, really. If he wants to state his opinions on FP, that's all well and good, but he should make it clear that they are his opinions and that the performance penalty he saw in the fold case is Swift-specific.
Given that the title is "Don’t assume that safety comes for free: a Swift case study", I don't think he's being particularly misleading. "Don't assume" usually just means that one should not take something for granted, not that it is never true. And doesn't appending "a Swift case study" makes it fairly clear that he is talking specifically about this case in Swift?
Also, he does point out in this paragraph that there is nothing inherently slower about the functional approach: "All these functions achieve nearly the same best performance if you disable safety checks at build time (swift build --configuration release -Xswiftc -Ounchecked). This means, in particular, that we get the fancy abstraction (the reduce approach) for free, as long as we disable safety checks. That makes performance a lot easier to understand."
Someone who hasn't used simple "functional idioms" (map, fold, ...) in half a dozen different programming languages could easily come away from this post with some idea that they are slow and/or "unsafe", when in fact they don't have to be slow and they don't really have anything to do with safety. This guy has a theory that this slowness without `-Ounchecked` is just a bug: https://news.ycombinator.com/item?id=13118405
It's been my experience that people who have used just a couple of programming languages tend to project what they "know" about those languages onto programming languages in general. Oh, and the snarky comments suggesting that a trivial functional idiom is gee-whiz "obfuscated" code that's good for impressing interviewers doesn't help.
I mean, I've read worse things on the internet. But I think his conclusions about the performance and safety of the fold abstraction require some clarification.
I work with the author regularly, and am inclined to a more charitable reading. I was serious when I suggested that he'd love to receive your Rust benchmark showing that it has no slowdown, and would happily include a note about them.
I'm not sure of the the purpose of the "obfuscation" comments. I'd guess that they were intended as jokes, but missed the target. Rather than mocking the use of reduce, I think his goal was probably to defend the utility of the humble for loop. On a larger level, both he and I have a concern that people often assume "a sufficiently clever compiler" without checking to see that they actually have one.
Here's the sort of thing I've been working on him with: https://arxiv.org/abs/1611.07612. It's shows how to count number of set bits with SIMD in a way that is faster than the using the builtin POPCNT instruction. This is a different level of optimization than concerns most programmers, but if you are trying to get that last 50% of maximum performance out of an implementation, it's likely that (at this point) Swift shouldn't be your top choice.
To me his jokes read as very unprofessional, unworthy of a CS professor. I understand his post was informal and not a peer-reviewed paper, but still: if you want to be taken seriously, maybe try not to irritate your audience with sarcastic quips unrelated to your main point?
> people often assume "a sufficiently clever compiler" without checking to see that they actually have one.
In many situations this is a reasonable assumption. Of course, checking is always warranted if you actually have a performance problem. In this particular case there's obviously something wrong going on with Swift. This is genuinely interesting -- though I think it doesn't merit being called a "case study" -- and could have been presented in a less confrontational way.
edit: I've read some more of Lemire's blog and I tend to find it interesting and reasonably written. I'm willing to think in this case he just misjudged the tone :)
Exactly. This is what Ada and annotation-based verification do. Usually, there's bad input at one of the interface points (esp function calls or I/O) where some conditional checks can catch it. Not always but most cases.
I'm puzzled by how many people want their programs to just keep on trucking and try their best after something unexpected occurs.
Crashing is not the worst thing your program can do. In fact, I'd argue that it's the second-best thing your program can do, right behind working correctly. Losing data is much worse than crashing, and corrupting data is worse still. Both are strong possibilities once your program's state is something unexpected.
I agree and disagree. What the author says is true, if a thoroughly irrelevant part of your program (let's say a drawing routine for UI somewhere) hits an overflow and crashes your app in the middle of taking a payment, or in the middle of surgery -- while that much more critical element continued to work perfectly -- that's not ideal.
Not all parts of your app make sense to fail-fast. By enforcing this behavior even on peripheral parts of your app, you're taking away the decision making ability about what's important and what isn't from the system designer.
I understand that position, though I still think on the whole explicitness is right. Being able to explicitly disable the check when you know what you want is the right balance, whether it's &+ in Swift or (better, imo) .wrapping_add() in Rust.
Displaying corrupt data in the UI can be just as bad as saving it to disk, if the user actually reads and uses the data you display (and if not, why are you displaying it?).
And since the UI almost certainly shares data with the rest of the program, bugs in the UI can corrupt the underlying data.
Separation of concerns is great, but if you really want different parts of your system to have different reliability constraints, then you need to truly separate them, for example by running them in different processes. Running them in the same process but having some of the code be more lax about state because it's less important is just begging for horrible bugs.
> Separation of concerns is great, but if you really want different parts of your system to have different reliability constraints, then you need to truly separate them, for example by running them in different processes. Running them in the same process but having some of the code be more lax about state because it's less important is just begging for horrible bugs.
Indeed, and you might even want to run them on entirely different and independent systems (connected by some type of network/bus) depending on exactly what bits are critical vs. non-critical.
Why can't it be opt-in instead of opt-out? Or can we have more granular control overall? On an application, module, class, function, and block level? That way my super tight hit loop that I can prove does not overflow gets a 2x speed up, while the rest of the code is safe. Oh and I can always recompile it to be always safe and analyze crashes in the real world, no t just my silly unit tests that amount to 2 + 2 == 4.
One issue is that failures are not necessarily contained. An error in a less important area could still corrupt the state of something more important.
The most convincing take on this I've seen is Erlang/Elixir. You generally fail fast there, but each program is composed of many different, isolated processes. No matter how a single process fails, it won't affect any other independent processes. A stopped process only takes down those processes that depend on it, everything else continues. And Supervisors can restart the failed processes from a known good state again.
> Being able to explicitly disable the check when you know
> what you want is the right balance, whether it's &+ in
> Swift or (better, imo) .wrapping_add() in Rust.
To clarify, Rust does disable the overflow check in release mode (and the benchmarks shown in this post are exactly why, to much heated debate), wrapping instead. `.wrapping_add()` in Rust is just what you use in order to guarantee wrapping behavior in debug mode as well (and also to guard against future changes to the language specification, which currently allows implementations to choose to either panic or wrap on overflow). In order to get the behavior of Swift's basic `+` in Rust, you'd use `.checked_add().unwrap()`.
Of course, you're right -- which is a behavior I'm even more in favor of, wherein your debug builds fail fast all the time but your release builds don't.
If a language is going to have a default behavior, then it can't be a design choice that balances other considerations, because it has no idea what context it might be used in. The best option then is to default to safety, and allow the programmer to choose other behaviors if they need them.
I think it's up to the end developers to decide that the behaviors are. You/I don't know that the best option is to default to "safety" - because we lack the information necessary to make that decision.
And yet again - this is UB because the original writers of the C language knew that the behavior of the hardware would be known to assembly programmers of the time.
You either have to pick a default, or you have to forbid developers from writing a + operation unless they first choose an overflow behavior. I can see arguments for the latter, but it's not a common choice.
It comes from mistakenly architecting systems as monolithic entities. No one would run a major website serving millions of users on a single piece of hardware. Why do applications stuff everything into a single process? Applications can and should be broken up into multiple pieces. The Web Browser is a great example - run each tab in its own process. Run WebGL in yet another process. Our tools could make this a lot easier.
FTIW Swift may not necessarily need to bring down the entire process anyway. When it gets a concurrency story where the compiler can enforce thread boundaries at compile time it could be paired with separate heaps per thread to allow a single thread to abort without aborting the entire process. That would be ideal for the server case.
I totally agree. The most pernicious defect I ever fixed was a result of a subtle overflow during part of a larger calculation. The erroneous result could cause problems months after the overflow occurred and took me days to track down.
The fact that Swift defaults to checking for overflow should be treated as good news.
I had a nasty bug like that once as well. It was in some FPGA logic written in VHDL with an overflow on a FIR filter. Recreating the problem was very difficult since it only happened near max signal power with a noisy input. The correct solution there was to saturate, not wrap, which is almost always the case in DSP code.
One uses a loop, one uses fold with a closure, one uses point-free style. On my machine, summing a vector of a million fives gives
running 3 tests
test sum_fold ... bench: 147,129 ns/iter (+/- 9,101)
test sum_loop ... bench: 148,016 ns/iter (+/- 10,294)
test sum_pointfree ... bench: 146,230 ns/iter (+/- 9,114)
(there is some variance here between runs, sometimes the +/- for each changes a bit.)
Cargo's bench profile doesn't use debug assertions, and hence, no overflow checks by default. Let's turn them on:
running 3 tests
test sum_fold ... bench: 147,638 ns/iter (+/- 12,654)
test sum_loop ... bench: 143,485 ns/iter (+/- 7,255)
test sum_pointfree ... bench: 143,050 ns/iter (+/- 7,549)
Looks like they're being eliminated by LLVM anyway.
Using godbolt, both the loop and the fold versions (I didn't bother to look at pointfree) are both getting vectorized, and while they're not _exactly_ identical, they're quite similar.
(disclaimer: YMMV, I might have made a mistake, always inspect assembly for your situation, etc)
Good point! You're right, it is a little surprising that reduce() adds any overhead at all in this trivial example.
It's interesting that Swift can't seem to fully eliminate that abstraction overhead when runtime checks are enabled -- maybe there's something other than overflow checks that's getting in the way?
The author hints that the abstraction cost does vanish when checks are disabled, but doesn't bother showing any numbers.
Looking at the generated code, we have a couple issues that prevent full optimization. One of them I already knew about (https://bugs.swift.org/browse/SR-2926) -- as a debugging aid, we guard every trap we emit with the equivalent of an `asm volatile("")` barrier, because LLVM will otherwise happily fold all the traps together into one trap. We really want every trap to have a distinct address so that the debugger can map that trap back to the source code that emitted it, but the asm barrier prevents other optimizations as well. As for `reduce`, it looks like the compiler does inline away the closure and turn the inner loop into what you would expect, but for some reason there's more pre-matter validation of the array than there is with a for loop. That's a bug; by all means, reduce is intended to optimize the same.
> Using "reduce" rather than a loop also has ~2x overhead ... Neither is really surprising
I disagree. It all depends on where you're coming from, and what your expectations are. In C++, using reduce (std::accumulate) with a lambda is normally as fast as using a loop, because the compiler will inline the lambda into accumulate, and then accumulate into the calling function, producing the same exact loop.
It's a little bit surprising that using a fold rather than a simple loop has such a high overhead. I was already pretty sure of the result, but I went ahead and wrote a quick benchmark in Rust, and there is no overhead to using a fold rather than a loop (each iteration is addition of a million values of the stated numeric type):
test tests::bench_fold_f64 ... bench: 984,829 ns/iter (+/- 30,827)
test tests::bench_fold_i32 ... bench: 84,497 ns/iter (+/- 16,109)
test tests::bench_loop_f64 ... bench: 993,406 ns/iter (+/- 45,791)
test tests::bench_loop_i32 ... bench: 81,306 ns/iter (+/- 17,815)
That this isn't true in Swift is way more interesting to me than the fact that overflow checking has overhead (duh). It's not difficult to come up with some theories as to why this might be the case, but still, if using these "functional" constructs in Swift has such a high overhead, programmers should probably be questioning whether it's worth using them at all.
edit: I see that I've been beaten to the punch posting a Rust benchmark :)
Rust has overflow checking in debug mode, but release mode does not have any overflow checking. The thinking here is that you'll hopefully catch most of your overflows while testing the app, but get no performance penalty in production use.
If you want to overflow there are special types that you can use.
In Swift, you have total control over this. If you want checks, use +. If you don't want checks, use &+.
In Rust, the operators check in debug builds, and wrap in release builds. Calls are provided so you can always have them check, or always have them wrap, if you need it.
Note that C has some really ugly behavior here. Signed overflow is undefined behavior, which means that the compiler doesn't need to check for it, but also that it can assume it never happens and optimized based on that. Many programmers don't realize this, or don't notice that they've accidentally written code that depends on overflow behavior, which can lead to many entertaining bugs: https://lwn.net/Articles/511259/
>Note that C has some really ugly behavior here. Signed overflow is undefined behavior, which means that the compiler doesn't need to check for it, but also that it can assume it never happens and optimized based on that. Many programmers don't realize this, or don't notice that they've accidentally written code that depends on overflow behavior, which can lead to many entertaining bugs: https://lwn.net/Articles/511259/
That's because different CPUs behave differently. To avoid undefined behavior, you have to have an "if" at every +.
You would also be hard pressed to find a modern architecture that doesn't use twos complement for signed integers.
That said, rolling over on a signed integer is almost always an error, although luckily it is usually one of the easier ones to detect in the debugger. Big negative numbers are a dead giveaway.
&+ isn't quite the same as + in C though. It's defined to perform wrapping overflow everytime, so more like integer + in Java. I don't think there's an addition operator in Swift that means "not only don't do overflow checking, but also consider overflow impossible and optimize accordingly".
Not entirely clear that such an operator is ever what you really want, I suppose...
I believe you can get that behavior by using + in a file that you compile with -Ounchecked. I don't believe there's any built-in way to do it at an individual call site, short of writing a wrapper that you compile with -Ounchecked and then calling the wrapper where you want that behavior.
To elaborate slightly on what my sibling commentors have said:
Rust has a feature called "debug assertions". This is a compile-time option to configure, well, debug assertions.
Rust-the-language says that when debug assertions are turned on, overflow checks must be in place, and will panic. When debug assertions are not on, overflow is considered a "program error", and while implementations are not required to do the check, they may. if they do not, they must implement two's compliment wrapping.
rustc currently does not check when debug assertions are off.
Cargo has the concept of "build profiles", and there are a number of different ones. By default, "cargo build" executes a "debug profile" build, which, by default, has debug assertions on. "cargo build --release" executes a "release profile" build, which, by default, as debug assertions off.
> How do languages which aim to replace C (such as Rust) deal with this issue?
Just like languages older than C did, by providing the option to explicitly request to disable safety checks.
For example in ESPOL and NEWP (1961), running unsafe modules requires admin permission, user code cannot make use of unsafe. Something like setuid in UNIX.
You don't need 100% unsafe code, rather write it in a safe way, profile it, and then only on the sections that really matter you might turn those checks off, after trying everything else to optimize it.
> That’s because I do not think it is universally a good thing that software should crash when an overflow occurs. Think about the software that runs in your brain. Sometimes you experience bugs. For example, an optical illusion is a fault in your vision software. Would you want to fall dead whenever you encounter an optical illusion? That does not sound entirely reasonable, does it? Moreover, would you want this “fall dead” switch to make all of your brain run at half its best speed?
If you lived in a world where hackers crafted optical illusions that made you send all your money to them when you viewed them, you would probably want to go blind or some such when you encountered such an illusion.
A bit of a tangent here, but anyone intrigued by the notion of hacking the brain using optical illusions should read "comp.basilisk FAQ": http://ansible.uk/writing/c-b-faq.html
I see a number of posts that proudly claim (in different forms) "fail early and fast" like it's a good thing to simply do a run-time crash always, and even that the article author is "misguided and inflammatory."
I don't agree with both claims.
Regarding the first, as an example where the crash is definitely not the solution, see the planteen's post:
Or consider that once you use the computers to calculate the real life stuff (like the movement of your car, or even the spaceship 50 million kilometers away) the worst thing you can do is introduce the "fatal discontinuities" in the processing.
Regarding the second, allow me to just roll my eyes. The politics is not allowed this week on HN, but the political approaches start to be used automatically. Please just write which his claim is wrong. Labeling is destructive.
A crash is never the right solution. It is, however, likely to be a better solution than whatever random default behavior you might get.
Regarding the linked comment, if the default had been to crash on overflow (or whatever the FPGA equivalent might be, if there is such a thing) then the problem would have been apparent the first time it happened, and they wouldn't be describing it as "a nasty bug" in the first place. A crash would not have been the best solution there, but it would have been miles better than the wrap that they actually got.
As far as real life stuff, my understanding is that it's pretty common to fail fast and design the system to restart quickly so it can get back to work. If your needs are more sophisticated then you'd need to actually analyze the problem and come up with ways to handle unexpected data gracefully, not just hope that default behavior from the compiler ends up doing something sensible for your problem.
If 1-2 ms is too much to recover from a crash, you better have three or four backup systems written in different languages and running on different hardware. Yet there is no guarantee you will have 100% uptime. And in such a system, having data corruption would probably be far worse then a crash.
One application where I think crashes are bad are computer games, for example if you are fighting a boss, it's better to get a few glitches then having the game crash.
I'm not sure it's even true of computer games, since you might end up corrupting the player's save and destroying all of their progress. The argument for crashing is at least a bit weaker there, though.
> If your needs are more sophisticated then you'd need to actually analyze the problem and come up with ways to handle unexpected data gracefully
The case I've linked to provided exactly that kind of example: "The correct solution there was to saturate, not wrap, which is almost always the case in DSP code."
I have an impression you've written your whole answer without reading it.
Note that something like that is necessary only for the very performance critical code using integers, as today's FPU are also very fast and allow the representation of much bigger range of values: more than the number of the atoms in the observable universe can be fit in the FP number.
Also note "Saturation arithmetic operations are available on many modern platforms, and in particular was one of the extensions made by the Intel MMX platform, specifically for such signal processing applications. This functionality is also available in wider versions in the SSE2 and AVX2 integer instruction sets."
"the IEEE floating-point standard, the most popular abstraction for dealing with approximate real numbers, uses a form of saturation."
All of this is a common knowledge by the professionals, and it's completely different from "just make an exception" approach that is so popular here. I claim that there's much bigger possibility that the author of the article knows about that than the commenters here that are responding (and voting) with the "just fail fast" mantra (or even claim that those who don't agree with their (probably poorly founded, as far as I see that) understanding are "inflammatory."
I read it and understood it. I think we're talking past each other.
You're saying, crashing is bad, it's better to figure out a correct response to overflow.
I'm saying, choosing some default overflow behavior without any analysis is bad, it's better to crash.
In some cases, you want to wrap. In others, you want to saturate. In others, you'll want to signal a failure. In still others, you'll want to fall back to bignums. There's no universal correct answer.
But the discussion here is about what the language should do about overflow. The language has to pick some default behavior for the + operator, and it can only pick one. Some people are arguing that wrapping by default is the best choice, because it at least gives the program a chance of continuing to operate.
I am arguing that the best default behavior is to crash, because continuing on when the programmer hasn't explicitly chosen the appropriate behavior is potentially disastrous.
Of course the person who posted that comment didn't want their stuff to crash. But if the default behavior had been to crash (ignoring the likely impossibility of that in the context of an FPGA), their bug would have been a simple fix instead of something so nasty they still remember it. Sure, if the default had been to saturate then they would have avoided the bug, but only by coincidence, and this would just cause bugs elsewhere when people needed wrapping instead.
The fourth word of your quote is key: "The correct solution there...." That was the correct solution in that spot, but it would not be the correct choice for default behavior for the + operator in a language.
If you are discussing the semantic of the "integer + operator" then I have also completely another opinion:
"it would not be the correct choice for default behavior for the + operator in a language."
No. Except if you're doing crypto, the wrap alone is never the desired mode. The wrap with the accessibility to the carry flag can be (just in implementing arithmetic with more bits). What the HL languages should actually do is not even allow the "easy" expressions in the integer domain, exactly because of all that. Moreover, missing accessibility of the carry flag in the HLL is also a problem. The instruction sets of ASM instructions are much more reasonable than the poor implementations of all the HL languages I know. "Exception on carry" instead of enforcing the code to be precise is the way to the many more accidents waiting to happen.
The current practice of the HL languages is more of the lazy repetition of some old decision than the proper safety-preserving approach.
If you're arguing that there shouldn't be any default behavior, and the programmer should always be forced to choose, I could get behind that.
I've also argued for degradation to bignums as the best default. This way the result is always correct. Of course, that means a performance hit on all arithmetic code unless you opt out of that, and you could make the case that this is also an unacceptable default.
In any case, consider the "crashing is the best default choice" to be qualified with "if you're going to have some default choice for fixed-size integers."
> I've also argued for degradation to bignums as the best default.
It has sense for Python and Perl code but not for the code produced by something that would be better C than the current C. If the performance is critical (as to have to effectively no slowdown compared to what the CPU can achieve), the CPU machine code instructions already do "the right thing" and it's the HL languages that abstract the carry or the saturation away to make the wrong plain "+".
C with the CPU-specific extensions can "do the right thing." It's the "standard" "language lawyers" that are once again wrong.
I see a number of posts that proudly claim [...] that the article author is "misguided and inflammatory."
I wrote that. I definitely don't mean to attack the author personally, just the content of this one article!
I did try to choose those words carefully, though. I went back and forth a few times before deciding that, yes, the article is pushing what I think is a very counterproductive line, so the "totally misguided" seemed strong but fair. And it draws rather grand (and I think incorrect) conclusions from very thin data, hence "inflammatory". But it's hard to stay civil while also saying what you really mean; maybe I was a little too harsh.
once you use the computers to calculate the real life stuff (like the movement of your car, or even the spaceship 50 million kilometers away) the worst thing you can do is introduce the "fatal discontinuities" in the processing
I definitely agree with that, but silent overflows are just as likely to kill you in that scenario as a crash (and hopefully fast reboot) in a submodule. Imagine if the calculated brake pressure in your car wraps around from +MAX to 0, for example. And there's a story (apocryphal, I think) about a fighter jet that would roll 180 degrees if you flew into the southern hemisphere (negative latitude).
A submodule crash is at least something you can plan for and test -- that's standard practice in large Erlang programs, for example.
For safety-critical stuff, extremely careful and painstaking specification, coding and testing is the only solution. There's no silver bullet. Runtime overflow checks won't save you, but turning them off won't save you either.
Now that more languages are checking for integer overflow, it's time for integer overflow exceptions to re-appear in hardware. DEC VAX machines had this, but C didn't use them. With the hardware doing the checking in parallel, there's no performance penalty.
If you want wrap-around arithmetic (which is rare) you should have to write something like
unsigned short i,j;
i = (i + j) % 65536;
which the compiler should optimize into a no-check add. This gets you the same answer on all platforms.
After chasing strange bugs when using dynamic languages like PHP and JavaScript that keep running by default when minor errors happen (PHP warnings, or undefined variables in JavaScript), I think its good that Swift priorizes safety rather than speed.
"Moreover, would you want this “fall dead” switch to make all of your brain run at half its best speed?"
...because this is actually how our brains work! We are much slower to process and respond to all sorts of stimuli (visual, auditory, conceptual [reading]) when it is contradictory. Think of the feeling you get looking at an Escher sketch.
Most costly software bug I've ever witnessed was caused by an integer overflow. Thankfully, it wasn't caused by me, but if I had been auditing the code, I probably wouldn't have found the bug.
The system was billing customers credit cards depending on how long they had used the service. Time was measured in milliseconds (uh-oh!) for no apparent reason. Usage could have been measured in seconds or even days but someone thought it was good to be extra precise. And System.currentTimeMillis() returns milliseconds.
The default charging period was 14 days which worked well. So the maximum number of milliseconds that could be charged (for someone who used the system the whole month) was 1,209,600,000. Then the company decided to change the period to every two months (60 days) instead to save money as there was a fixed cost added to every credit card transfer.
Guess what 60 * 24 * 3600 * 1000 is? It's a number a bit bigger than 2^31 - 1 which is the most positive primitive integer value in Java. And the "totalDuration" variable had type "int". :)
So totalDuration wrapped around which caused the system to retry the transaction over and over and debit customers hundreds of times more than what they really owed. The resulting fallout from that debacle was one of the reasons the company went bankrupt. Integer overflow checking could have saved them.
I thought it might be interesting to see how this effect changes with the size of the array being summed. How do the relative speeds change when operating out of L1, L3, and memory? Does the lower speed of memory access overwhelm the overhead of the overflow checking?
Code is from https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/... with modification to loop over the different array lengths. Numbers are for Skylake at 3.4 GHz with swift-3.0.1-RELEASE-ubuntu16.04. Count is the number of 8B ints in the array being summed. Results shown were truncated by hand --- I wasn't sure how to specify precision from within Swift. The execution with "cset proc -s nohz" was to reduce jitter between runs, but doesn't significantly affect total run time. The anomalously fast result for the L3 sized 'unsafe' 'unchecked' is consistent.
"That’s because I do not think it is universally a good thing that software should crash when an overflow occurs. Think about the software that runs in your brain. Sometimes you experience bugs. For example, an optical illusion is a fault in your vision software. Would you want to fall dead whenever you encounter an optical illusion? That does not sound entirely reasonable, does it? Moreover, would you want this “fall dead” switch to make all of your brain run at half its best speed? In software terms, this means that a mission-critical application could crash because an unimportant function in a secondary routine overflows."
That is a ridiculous analogy. What if we replace "optical illusion" with "hallucination"?
More importantly, what if there were some sort of middle ground between continuing on as if nothing happened on an error and crashing completely?
80 comments
[ 1.9 ms ] story [ 148 ms ] threadEDIT: It's back up
1. Overflow checking adds about a 2x overhead to "+" in a loop
2. Using "reduce" rather than a loop also has ~2x overhead
Neither is really surprising, and hardly seems to warrant the final tangent that "I do not think it is universally a good thing that software should crash when an overflow occurs" since "a mission-critical application could crash because an unimportant function in a secondary routine overflows".
What about the mission-critical bugs, especially security bugs, that are caused by overflows?
Swift's default behavior, of aggressively checking for overflows, is at least arguable, and there's a school of thought in software engineering that says "don't nail your code to the wall", i.e. don't try to keep it running at all costs when something goes wrong. Let it crash and restart it. Obviously that approach works well in some scenarios and less well in others. The creators of Swift reckon it's a good default for most programmers and I reckon they're onto something.
The fact that the overhead is only 2x for a tight inner loop should be a cause for celebration, not dire warnings. And as the author himself shows, it's very easy to disable overflow checking on a per-operation basis when you want to.
Agreed. This smells like premature optimization... on a problem that can be solved in O(1) time.
Does he really expect sympathy when he considers something as trivial as array.reduce(0,+) "obfuscated"? I've never written a single line of Swift in my life and I -- being familiar with FP idioms -- immediately understand what it means.
The premise that many abstractions and safety checks come at a cost is reasonable. Unfortunately the rest of his post isn't.
I don't see any deep insight. The performance loss may very well be caused by an immature Swift compiler, and not ultimately tied to the abstraction, but he mentions nothing of this. I expect this lack of understanding from a novice, not from a CS professor.
What he wrote isn't even a "case study", contradicting even the title of his blog.
It's also not always correct. See the Rust benchmarks posted here.
Someone seeing this article might think it is correct, though, and thusly misinformed, they might avoid "functional-style" programming in the future when in fact many languages manage to provide FP idioms with no performance penalty.
It's irresponsible, really. If he wants to state his opinions on FP, that's all well and good, but he should make it clear that they are his opinions and that the performance penalty he saw in the fold case is Swift-specific.
Also, he does point out in this paragraph that there is nothing inherently slower about the functional approach: "All these functions achieve nearly the same best performance if you disable safety checks at build time (swift build --configuration release -Xswiftc -Ounchecked). This means, in particular, that we get the fancy abstraction (the reduce approach) for free, as long as we disable safety checks. That makes performance a lot easier to understand."
See the Rust benchmarks posted here.
Send him a pull request, and I'd bet he'd be happy to include them for comparison and mention them in an addendum: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...
It's been my experience that people who have used just a couple of programming languages tend to project what they "know" about those languages onto programming languages in general. Oh, and the snarky comments suggesting that a trivial functional idiom is gee-whiz "obfuscated" code that's good for impressing interviewers doesn't help.
I mean, I've read worse things on the internet. But I think his conclusions about the performance and safety of the fold abstraction require some clarification.
I'm not sure of the the purpose of the "obfuscation" comments. I'd guess that they were intended as jokes, but missed the target. Rather than mocking the use of reduce, I think his goal was probably to defend the utility of the humble for loop. On a larger level, both he and I have a concern that people often assume "a sufficiently clever compiler" without checking to see that they actually have one.
Here's the sort of thing I've been working on him with: https://arxiv.org/abs/1611.07612. It's shows how to count number of set bits with SIMD in a way that is faster than the using the builtin POPCNT instruction. This is a different level of optimization than concerns most programmers, but if you are trying to get that last 50% of maximum performance out of an implementation, it's likely that (at this point) Swift shouldn't be your top choice.
> people often assume "a sufficiently clever compiler" without checking to see that they actually have one.
In many situations this is a reasonable assumption. Of course, checking is always warranted if you actually have a performance problem. In this particular case there's obviously something wrong going on with Swift. This is genuinely interesting -- though I think it doesn't merit being called a "case study" -- and could have been presented in a less confrontational way.
edit: I've read some more of Lemire's blog and I tend to find it interesting and reasonably written. I'm willing to think in this case he just misjudged the tone :)
If you're going to take the overhead of range checking for a value, it may as well be a more appropriate range, not just for overflow conditions...
Thinking it would be nice to be able to specify this as part of the type...
Crashing is not the worst thing your program can do. In fact, I'd argue that it's the second-best thing your program can do, right behind working correctly. Losing data is much worse than crashing, and corrupting data is worse still. Both are strong possibilities once your program's state is something unexpected.
Not all parts of your app make sense to fail-fast. By enforcing this behavior even on peripheral parts of your app, you're taking away the decision making ability about what's important and what isn't from the system designer.
I understand that position, though I still think on the whole explicitness is right. Being able to explicitly disable the check when you know what you want is the right balance, whether it's &+ in Swift or (better, imo) .wrapping_add() in Rust.
And since the UI almost certainly shares data with the rest of the program, bugs in the UI can corrupt the underlying data.
Separation of concerns is great, but if you really want different parts of your system to have different reliability constraints, then you need to truly separate them, for example by running them in different processes. Running them in the same process but having some of the code be more lax about state because it's less important is just begging for horrible bugs.
Indeed, and you might even want to run them on entirely different and independent systems (connected by some type of network/bus) depending on exactly what bits are critical vs. non-critical.
The most convincing take on this I've seen is Erlang/Elixir. You generally fail fast there, but each program is composed of many different, isolated processes. No matter how a single process fails, it won't affect any other independent processes. A stopped process only takes down those processes that depend on it, everything else continues. And Supervisors can restart the failed processes from a known good state again.
The decision between "keep on trucking" and crashing is a design choice, and will have to be balanced against other considerations.
And yet again - this is UB because the original writers of the C language knew that the behavior of the hardware would be known to assembly programmers of the time.
FTIW Swift may not necessarily need to bring down the entire process anyway. When it gets a concurrency story where the compiler can enforce thread boundaries at compile time it could be paired with separate heaps per thread to allow a single thread to abort without aborting the entire process. That would be ideal for the server case.
The fact that Swift defaults to checking for overflow should be treated as good news.
It depends! Consider these three functions, in Rust: https://gist.github.com/steveklabnik/da82b51f9dbedd532192492...
One uses a loop, one uses fold with a closure, one uses point-free style. On my machine, summing a vector of a million fives gives
(there is some variance here between runs, sometimes the +/- for each changes a bit.)Cargo's bench profile doesn't use debug assertions, and hence, no overflow checks by default. Let's turn them on:
Looks like they're being eliminated by LLVM anyway.Using godbolt, both the loop and the fold versions (I didn't bother to look at pointfree) are both getting vectorized, and while they're not _exactly_ identical, they're quite similar.
(disclaimer: YMMV, I might have made a mistake, always inspect assembly for your situation, etc)
It's interesting that Swift can't seem to fully eliminate that abstraction overhead when runtime checks are enabled -- maybe there's something other than overflow checks that's getting in the way?
The author hints that the abstraction cost does vanish when checks are disabled, but doesn't bother showing any numbers.
I disagree. It all depends on where you're coming from, and what your expectations are. In C++, using reduce (std::accumulate) with a lambda is normally as fast as using a loop, because the compiler will inline the lambda into accumulate, and then accumulate into the calling function, producing the same exact loop.
edit: I see that I've been beaten to the punch posting a Rust benchmark :)
Now I agree, your average webapp won't see any benefit by removing checks and will see security features by keeping them in, so I'm all for it.
But in OSs (or browsers), speed does matter. And there's no way to optimize it (every + or array operation involves an if).
Is this just one of the "costs of doing business"?
You figure out if you need to optimize by testing and benchmarking.
If you want to overflow there are special types that you can use.
In Rust, the operators check in debug builds, and wrap in release builds. Calls are provided so you can always have them check, or always have them wrap, if you need it.
Note that C has some really ugly behavior here. Signed overflow is undefined behavior, which means that the compiler doesn't need to check for it, but also that it can assume it never happens and optimized based on that. Many programmers don't realize this, or don't notice that they've accidentally written code that depends on overflow behavior, which can lead to many entertaining bugs: https://lwn.net/Articles/511259/
That's because different CPUs behave differently. To avoid undefined behavior, you have to have an "if" at every +.
That said, rolling over on a signed integer is almost always an error, although luckily it is usually one of the easier ones to detect in the debugger. Big negative numbers are a dead giveaway.
The danger is
signed int x; cin>>x; if(x+1<x){return OVERFLOW;}
will, in modern optimizing compilers, never return OVERFLOW
There were quite a few security holes introduced by the compiler with that.
-----
The only problem is to make a standard, one has to define that MAX_INT+1 = 0 or something. Then, whenever one does
signed int x;
cin>> x;
signed int y = x+1;
really turns into
signed int = 0;
if ( x < MAX_INT)
y= x+1
else
y = 1;
( bangs head with ball-peen hammer; rends garment )
Not entirely clear that such an operator is ever what you really want, I suppose...
Rust has a feature called "debug assertions". This is a compile-time option to configure, well, debug assertions.
Rust-the-language says that when debug assertions are turned on, overflow checks must be in place, and will panic. When debug assertions are not on, overflow is considered a "program error", and while implementations are not required to do the check, they may. if they do not, they must implement two's compliment wrapping.
rustc currently does not check when debug assertions are off.
Cargo has the concept of "build profiles", and there are a number of different ones. By default, "cargo build" executes a "debug profile" build, which, by default, has debug assertions on. "cargo build --release" executes a "release profile" build, which, by default, as debug assertions off.
If you want wrapping behavior, use https://doc.rust-lang.org/stable/std/num/struct.Wrapping.htm...
Just like languages older than C did, by providing the option to explicitly request to disable safety checks.
For example in ESPOL and NEWP (1961), running unsafe modules requires admin permission, user code cannot make use of unsafe. Something like setuid in UNIX.
You don't need 100% unsafe code, rather write it in a safe way, profile it, and then only on the sections that really matter you might turn those checks off, after trying everything else to optimize it.
If you lived in a world where hackers crafted optical illusions that made you send all your money to them when you viewed them, you would probably want to go blind or some such when you encountered such an illusion.
I don't agree with both claims.
Regarding the first, as an example where the crash is definitely not the solution, see the planteen's post:
https://news.ycombinator.com/item?id=13117170
Or consider that once you use the computers to calculate the real life stuff (like the movement of your car, or even the spaceship 50 million kilometers away) the worst thing you can do is introduce the "fatal discontinuities" in the processing.
Regarding the second, allow me to just roll my eyes. The politics is not allowed this week on HN, but the political approaches start to be used automatically. Please just write which his claim is wrong. Labeling is destructive.
Regarding the linked comment, if the default had been to crash on overflow (or whatever the FPGA equivalent might be, if there is such a thing) then the problem would have been apparent the first time it happened, and they wouldn't be describing it as "a nasty bug" in the first place. A crash would not have been the best solution there, but it would have been miles better than the wrap that they actually got.
As far as real life stuff, my understanding is that it's pretty common to fail fast and design the system to restart quickly so it can get back to work. If your needs are more sophisticated then you'd need to actually analyze the problem and come up with ways to handle unexpected data gracefully, not just hope that default behavior from the compiler ends up doing something sensible for your problem.
One application where I think crashes are bad are computer games, for example if you are fighting a boss, it's better to get a few glitches then having the game crash.
The case I've linked to provided exactly that kind of example: "The correct solution there was to saturate, not wrap, which is almost always the case in DSP code."
I have an impression you've written your whole answer without reading it.
And if you don't know what that means:
https://en.wikipedia.org/wiki/Saturation_arithmetic
Note that something like that is necessary only for the very performance critical code using integers, as today's FPU are also very fast and allow the representation of much bigger range of values: more than the number of the atoms in the observable universe can be fit in the FP number.
Also note "Saturation arithmetic operations are available on many modern platforms, and in particular was one of the extensions made by the Intel MMX platform, specifically for such signal processing applications. This functionality is also available in wider versions in the SSE2 and AVX2 integer instruction sets."
Not to mention the DSP processors.
https://www.arm.com/products/processors/technologies/dsp-sim...
"Zero overhead saturation extension support"
Moreover,
"the IEEE floating-point standard, the most popular abstraction for dealing with approximate real numbers, uses a form of saturation."
All of this is a common knowledge by the professionals, and it's completely different from "just make an exception" approach that is so popular here. I claim that there's much bigger possibility that the author of the article knows about that than the commenters here that are responding (and voting) with the "just fail fast" mantra (or even claim that those who don't agree with their (probably poorly founded, as far as I see that) understanding are "inflammatory."
You're saying, crashing is bad, it's better to figure out a correct response to overflow.
I'm saying, choosing some default overflow behavior without any analysis is bad, it's better to crash.
In some cases, you want to wrap. In others, you want to saturate. In others, you'll want to signal a failure. In still others, you'll want to fall back to bignums. There's no universal correct answer.
But the discussion here is about what the language should do about overflow. The language has to pick some default behavior for the + operator, and it can only pick one. Some people are arguing that wrapping by default is the best choice, because it at least gives the program a chance of continuing to operate.
I am arguing that the best default behavior is to crash, because continuing on when the programmer hasn't explicitly chosen the appropriate behavior is potentially disastrous.
Of course the person who posted that comment didn't want their stuff to crash. But if the default behavior had been to crash (ignoring the likely impossibility of that in the context of an FPGA), their bug would have been a simple fix instead of something so nasty they still remember it. Sure, if the default had been to saturate then they would have avoided the bug, but only by coincidence, and this would just cause bugs elsewhere when people needed wrapping instead.
The fourth word of your quote is key: "The correct solution there...." That was the correct solution in that spot, but it would not be the correct choice for default behavior for the + operator in a language.
"it would not be the correct choice for default behavior for the + operator in a language."
No. Except if you're doing crypto, the wrap alone is never the desired mode. The wrap with the accessibility to the carry flag can be (just in implementing arithmetic with more bits). What the HL languages should actually do is not even allow the "easy" expressions in the integer domain, exactly because of all that. Moreover, missing accessibility of the carry flag in the HLL is also a problem. The instruction sets of ASM instructions are much more reasonable than the poor implementations of all the HL languages I know. "Exception on carry" instead of enforcing the code to be precise is the way to the many more accidents waiting to happen.
The current practice of the HL languages is more of the lazy repetition of some old decision than the proper safety-preserving approach.
I've also argued for degradation to bignums as the best default. This way the result is always correct. Of course, that means a performance hit on all arithmetic code unless you opt out of that, and you could make the case that this is also an unacceptable default.
In any case, consider the "crashing is the best default choice" to be qualified with "if you're going to have some default choice for fixed-size integers."
It has sense for Python and Perl code but not for the code produced by something that would be better C than the current C. If the performance is critical (as to have to effectively no slowdown compared to what the CPU can achieve), the CPU machine code instructions already do "the right thing" and it's the HL languages that abstract the carry or the saturation away to make the wrong plain "+".
C with the CPU-specific extensions can "do the right thing." It's the "standard" "language lawyers" that are once again wrong.
I wrote that. I definitely don't mean to attack the author personally, just the content of this one article!
I did try to choose those words carefully, though. I went back and forth a few times before deciding that, yes, the article is pushing what I think is a very counterproductive line, so the "totally misguided" seemed strong but fair. And it draws rather grand (and I think incorrect) conclusions from very thin data, hence "inflammatory". But it's hard to stay civil while also saying what you really mean; maybe I was a little too harsh.
once you use the computers to calculate the real life stuff (like the movement of your car, or even the spaceship 50 million kilometers away) the worst thing you can do is introduce the "fatal discontinuities" in the processing
I definitely agree with that, but silent overflows are just as likely to kill you in that scenario as a crash (and hopefully fast reboot) in a submodule. Imagine if the calculated brake pressure in your car wraps around from +MAX to 0, for example. And there's a story (apocryphal, I think) about a fighter jet that would roll 180 degrees if you flew into the southern hemisphere (negative latitude).
A submodule crash is at least something you can plan for and test -- that's standard practice in large Erlang programs, for example.
For safety-critical stuff, extremely careful and painstaking specification, coding and testing is the only solution. There's no silver bullet. Runtime overflow checks won't save you, but turning them off won't save you either.
If you want wrap-around arithmetic (which is rare) you should have to write something like
which the compiler should optimize into a no-check add. This gets you the same answer on all platforms."Moreover, would you want this “fall dead” switch to make all of your brain run at half its best speed?"
...because this is actually how our brains work! We are much slower to process and respond to all sorts of stimuli (visual, auditory, conceptual [reading]) when it is contradictory. Think of the feeling you get looking at an Escher sketch.
The system was billing customers credit cards depending on how long they had used the service. Time was measured in milliseconds (uh-oh!) for no apparent reason. Usage could have been measured in seconds or even days but someone thought it was good to be extra precise. And System.currentTimeMillis() returns milliseconds.
The default charging period was 14 days which worked well. So the maximum number of milliseconds that could be charged (for someone who used the system the whole month) was 1,209,600,000. Then the company decided to change the period to every two months (60 days) instead to save money as there was a fixed cost added to every credit card transfer.
Guess what 60 * 24 * 3600 * 1000 is? It's a number a bit bigger than 2^31 - 1 which is the most positive primitive integer value in Java. And the "totalDuration" variable had type "int". :)
So totalDuration wrapped around which caused the system to retry the transaction over and over and debit customers hundreds of times more than what they really owed. The resulting fallout from that debacle was one of the reasons the company went bankrupt. Integer overflow checking could have saved them.
That is a ridiculous analogy. What if we replace "optical illusion" with "hallucination"?
More importantly, what if there were some sort of middle ground between continuing on as if nothing happened on an error and crashing completely?