Archive for December 9, 2016

Friday, December 9, 2016

Accidentally Quadratic Rust Hash Tables

Accidentally Quadratic:

I enjoy this bug for at least two reasons: One, it’s fun technically, allowing us to take a brief deep dive into hash-table implementation – something most of us are normally able to treat as a solved problem – and two, it’s a great example of subtle quadratic behavior in a system specifically designed by smart and well-informed developers to avoid the possibility of accidental quadratic behavior!


Robin Hood hashing improves on linear probing with a simple trick: When you’re scanning forward from H%N, look at each element you encounter. If the inserting element is further from its “natural” bucket than the element in the bucket you’re considering, then swap the new element and the element in that bucket, and continue scanning with the other element.


Rust’s problem arises when you iterate over one table and insert the resulting entries into another table. The problem occurs because iteration over a hash table [proceeds] by walking the backing array of the hash table directly. This results in yielding entries approximately in hash order, which turns out to be fatal when combined with the other elements of Rust’s [implementation].

Via Alexis Beingessner:

Meanwhile Swift’s Dictionary is just plain old First Come First Serve with Java-style hash codes. Lots of work to do there!

Previously: Exploring Swift Dictionary’s Implementation, Exposing NSDictionary.

Update (2018-04-03): See also: SR-3268.

How to Unit Test Private Methods in Swift

Bart Jacobs:

While access control is a very welcome addition with many benefits, it can complicate unit testing, especially if you are new to unit testing. You probably know that you can apply the testable attribute to an import statement in a test target to gain access to entities that are declared as internal.

While this is a convenient addition, it doesn’t give you access to private entities in a test target.


The key takeaway of this article is that private entities don’t need to be unit tested. Unit testing is a form of black-box testing. This means that we don’t test the implementation of the AccountViewViewModel struct, we test its specification.

This doesn’t mean that we are not interested in the implementation, though. We need to make sure the suite of unit tests covers every code path of the entity we are testing. Code coverage reports are invaluable to accomplish this.

I don’t find this very persuasive.

iOS App Rejected for Using Pre-selected RSS Feeds

Mike Rundle:

Now I know what was taking so long. Rejected because I use… public RSS feeds like 100 other apps. Thanks, Apple.

Well, Apple denied my appeal. Interesting (simple news app with pre-selected RSS feeds) is no longer allowed under App Store Guidelines.

Their explanation centered around users needing to add the RSS feed themselves (OK) vs. pre-configured list (Not OK.) Makes no sense.

Update (2016-12-10): The app in question is Interesting.

Federico Viticci:

This App Review rejection is lame and makes no sense. No curated news apps? What’s the harm?

John Gruber:

That’s crazy. Surely there are a slew of RSS readers already in the store with default subscription lists.

Mike Rundle:

I can’t even believe this now. People on the App Review Board have potentially never used an app before.

Apple says that any app that loads content from Reddit must open all URLs externally into Safari. Opening inside the app is forbidden.

Super Mario Run

Andrew Webster:

Now Nintendo is finally moving with them. Next week will see the launch of Super Mario Run on iPhone and iPad (an Android version is coming later), marking the first proper Nintendo-developed game on a mobile device. It’s a very different tactic compared to the “blue ocean strategy.” Instead of creating its own space, Nintendo is diving into one of the most crowded and competitive markets around, going up against the more than 2 million apps available in Apple’s digital marketplace. But with that comes a great opportunity. While Nintendo’s best-selling hardware reached 150 million people, Apple sold its billionth iPhone this summer. It’s a chance to introduce a new generation of players to the company’s characters, just as the original Super Mario Bros. did on the NES more than 30 years ago.


Miyamoto says that Nintendo has been toying with the idea of a one-button Mario game since the days of Wii. “As we were doing those experiments, we thought that that kind of approach would perhaps best be suited to iPhone,” he says. “So that became the basis for Super Mario Run.” But whether it was for Wii or iPhone, the goal behind this streamlined Mario was the same: to bring the distinct flavor of Super Mario to as many people as possible. “Nintendo has been making Mario games for a long time, and the longer you continue to make a series, the more complex the gameplay becomes, and the harder it becomes for new players to be able to get into the series,” Miyamoto says. “We felt that by having this simple tap interaction to make Mario jump, we’d be able to make a game that the broadest audience of people could play.”

Mitchel Broussard:

Shigeru Miyamoto has confirmed that Nintendo’s upcoming iPhone game Super Mario Run will require an always-on internet connection to play, which Miyamoto said is “a requirement that’s been built into the game to support security.” The security element is one of the big reasons why the company decided to launch on iPhone first, Miyamoto said, and it helps the game’s three separate modes function together while always keeping the software secure and safe, preventing piracy in the process (via Mashable).

This is to prevent piracy.

Update (2016-12-10): John Gruber:

But people on planes and subways do play games on their phone.

UPDATE: Another big problem: kids with iPod Touches and old SIM-less iPhones.

Update (2016-12-16): Tim Hardwick:

Undoubtedly many users tapped or clicked the button thinking they would be first to play Nintendo’s debut title on iOS. But the delay between the game’s appearance in the App Store and the actual delivery of notification prompts has left many users skeptical of the feature.

I never received the notification.

See also: Marco Arment on the e-mail notification.

I loved the original Super Mario Bros. but find Super Mario Run rather boring.

John Gruber:

The first-run on-boarding process is clunky though. You have to pick your country, and the United States is way down at the bottom of a long alphabetically sorted list. I’d rather be asked to grant access to my location — my phone knows where I am. And there was some confusing shit about creating a Nintendo account.

Update (2016-12-19): I have been reading that Super Mario Run doesn’t follow the App Store guidelines and ties its in-app purchase to your Nintendo account instead of to your Apple ID. If you don’t have a Nintendo account, you can’t restore your purchase.

Update (2017-01-02): Madeline Farber (via fuckingappstore):

Reviews in Apple's App Store (so far, the game is only available on iPhone) show an average rating of two and half stars out of five. Overall, there have been nearly 50,000 reviews. Its reviews make it among the lowest rated app among those at the top of the download rankings, according to Bloomberg.