Don’t assume that safety comes for free: a Swift case study
lemire.me
lemire.me
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.
try:
#your code goes here
except:
passThe 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.
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
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)
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)
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.
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)
edit: I see that I've been beaten to the punch posting a Rust benchmark :)
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.
If you want wrap-around arithmetic (which is rare) you should have to write something like
unsigned short i,j;
i = (i + j) % 65536;
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.
"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.
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?
$ swift build --configuration release
$ cset proc -s nohz -e .build/release/reduce
# count (basic, reduce, unsafe basic, unsafe reduce)
1000 (0.546, 0.661, 0.197, 0.576)
10000 (0.403, 0.598, 0.169, 0.544)
100000 (0.391, 0.595, 0.194, 0.542)
1000000 (0.477, 0.663, 0.294, 0.582)
10000000 (0.507, 0.655, 0.337, 0.608)
100000000 (0.509, 0.655, 0.339, 0.608)
1000000000(0.511, 0.656, 0.345, 0.611)
$ swift build --configuration release -Xswiftc -Ounchecked
$ cset proc -s nohz -e .build/release/reduce
# count (basic, reduce, unsafe basic, unsafe reduce)
1000 (0.309, 0.253, 0.180, 0.226)
10000 (0.195, 0.170, 0.168, 0.170)
100000 (0.217, 0.203, 0.196, 0.201)
1000000 (0.292, 0.326, 0.299, 0.252)
10000000 (0.334, 0.337, 0.333, 0.337)
100000000 (0.339, 0.339, 0.340, 0.339)
1000000000(0.344, 0.344, 0.344, 0.344)
EDIT: It's back up
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.
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.