frankmcsherry

Most people perceive structs and fields as an aspect of object-oriented programming, but you probably wouldn't write about them under the heading of "Object-oriented programming".

Maybe change the title to "Functional Language Idioms"?

> In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

from https://en.wikipedia.org/wiki/Functional_programming

I totally agree that neither iterators nor 2/3s of closures are "functional programming". That's fine, though, because I really enjoy the sane way that it all was done.

If you check out

https://doc.rust-lang.org/std/iter/trait.Iterator.html

and search for `FnMut`, you see that most of the iterator methods are side-effectful. That is cool and fun and very useful, but it isn't functional programming.

Edit. The term you are probably looking for (guessing) is "higher-order programming":

https://en.wikipedia.org/wiki/Higher-order_programming

If the data owner is malicious, you are right that there is no guarantee differential privacy is being used. That's a far cry from "there is no such thing as anonymized data"; you could just as easily say "there is no such thing as encrypted data", which I think we agree is wrong?

One can provide differentially private access to web histories that provably mask the presence/absence of individuals in that dataset, even when combined with arbitrary exciting side information, like social networks.

Even with something as simple as differentially private counting, you can pull out correlations between visits, finding statistically interesting "people who visit page X then visit page Y surprisingly often" nuggets, which are exciting to people who don't have their own search logs.

It's totally reasonable to consider doing something like this with differential privacy. The techniques exist, but it would still be pretty brave of them. They are certainly aware of DP.

Example technique: if you treat each record as a (src,dst) pair of (lat,lon) pairs or somesuch, you can then build a 4d grid whose cells you populate with (Laplace) noisy counts. This provides eps-differential privacy when the noise is roughly 1/eps.

Whenever counts are sufficiently large, you can refine the contents of the cell and ask again. If you do the refinement at most k times, you get k*eps-differential privacy. There are smarter ways that work even better.

These provide "trip privacy", meaning they mask the presence/absence of individual trips. Uber presumably has user identifiers, and could group all trips by one user together, and do the same counting where the weight of each trip is scaled down so that they sum to at most one for each user. This would then give "user privacy", meaning it masks the presence/absence of individual users.

I know, right. The full quote is apparently less fun to argue against:

> I’m aware the idea for type-safe unions isn’t unique or original to Rust, but it’s the first language I’ve experimented with that has made them a first-class feature.

The only point of the paper is that the previous publications sold their systems primarily on performance, but their performance arguments had gaping holes.

The C# and Rust implementations have the property that they are easy and you don't need to have any specific skills to write a for-loop the way we did (the only "tricks" we used were large pages and unbuffered io in C#, and mmap in Rust).

The point is absolutely not that these are the final (or any) word in these sorts of computations; if you really care about performance, use FPGAs, ASICs, whatever. There will always be someone else doing it better than you, but we thought it would be nice if that person wasn't a CS 101 undergraduate typing in what would literally be the very first thing they thought of.

> The paper is frankly stupid and a great example of difference between practice and academia. it looks good because they are using a snapshot of Twitter network from 2010.

We used these data and workloads because that was what GraphX used. If you take the graphs any bigger, Spark and GraphX at least couldn't handle it and just failed. They've probably gotten better in the meantime, so take that with a grain of salt.

> Unlike a bunch of out of touch researchers the key concern isn't how "fast" calculations finish, but several others such as ability to reuse, fault tolerance, multi user support etc.

The paper says these exact things. You have to keep reading, and it's hard I know, but for example the last paragraph of section 5 says pretty much exactly this.

And, if you read the paper even more carefully, it is pretty clearly not about whether you should use these systems or not, but how you should not evaluate them (i.e. only on tasks at a scale that a laptop could do better).

It's mentioned in the article: RAPPOR.

Do you have a quote for the first point? It doesn't sound (i) correct, or (ii) like something Cynthia would say.

In which case, one shouldn't write

> Instead of taking the easy way out and just correcting the single word in the page proof, we asked the publisher to put our paper on hold

I'm personally inclined to support the climate change folks, being a scientist and stuff, but it's a bit crap to claim that it was a one word typo when the original text apparently read:

> For predictor selection, both proxy climate and instrumental data were linearly detrended over the 1921–1990 period to avoid inflating the correlation coefficient due to the presence of the global warming signal present in the observed temperature record. Only records that were significantly ([pre]p<0.05[/pre]) correlated with the detrended instrumental target over the 1921–1990 period were selected for analysis.

That isn't a typo, it is just being wrong. I'm glad they re-did the work to confirm it was still true, but it's hard to argue with folks who didn't think the claim was supported by the data.

Here is a version (https://is.gd/bFCpMq) that might be instructive. It is based on a simple ref count cycle of structs like:

    pub struct ListNode<T> {
        data: T,
        prev: Weak<RefCell<ListNode<T>>>,
        next: Rc<RefCell<ListNode<T>>>,
    }

The code linked above probably has bugs (for sure with singleton lists), but I hope you get the idea. It allows you to splice lists in and out in constant time.

Also, the code doesn't use `unsafe`. Now, you would need to use `unsafe` somewhere to actually create a list, in order to initialize the fields (or you could change the type of `next` to be `Option<...>`). However, the use of `unsafe` would be limited to that method. This tries to get at the difference between (i) occasionally using `unsafe` and (ii) having no safety guarantees at all.

There are probably lots of other pain points that you can bring up, and I'm not trying to say this should be good enough, but I thought it might help explain what is possible.

> Even a trivial tree is hard to implement in Rust, and the implementation will be severely limited: https://github.com/SimonSapin/rust-forest

I mean, you haven't actually pointed at a trivial tree implementation. The requirement that children be able to navigate to siblings is the issue here (complicating unique ownership by parents).

You could totally do a "trivial tree" as

    struct Tree<T> {
      payload: T,
      children: Vec<Tree<T>>,
    }

which your link even says. You would need a handle to the parent to surf around through siblings, is the limitation.

It's not really clear (to me) that the rctree is really all that complicated; the Rc stuff is there to clarify ownership: for how long should allocated memory stick around. It might just read weirdly due to familiarity, in the same way that D might weird me out.

> Secondly, why would the UK end up with a Norway or Switzerland deal, when the UK is the 5th largest economy in the world?

Well, 6th now. Sorry about that. France said "bonjour" as you passed.

And, just to be clear, in their paper it not the presence of noise that kills people, it is their treatment of noisy measurements as high-confidence measurements that kills them. When you get low confidence reads from data you should use them as such; the authors just act on them no matter how strong (or weak) the confidence and report what happens.

It's roughly analogous to a doc saying "should I deviate from the baseline treatment?" and when the data say "dunno" the doc prescribes a totally random medicine rather than the baseline, because that is what "dunno" means.

> The database still has to exist on Apple's servers.

It doesn't, which is part of the reason Apple wants to do this. You can still do differential privacy without collecting all the data, you just get less accurate results. See page 232 in [1], re "The Local Model".

[1]: http://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

Edit: the article even says this down when it talks about RAPPOR.

Sorry, I see what you are saying, and I wasn't (intentionally) complaining that 1/4 isn't 1/2 or so. Rather, that the stat only tells us that when you look at toxic employees you find toxic players, rather than vice-versa.

Yeah, given that the CPU load for the C lines are listed as

    100% 95% 95% 95%

on a quadcore, I'm going to say "not one thread".

Edit: to be helpful, rather than just obnoxious, (<3) the C version uses open mp pragmas, so it looks single-threaded.

We only have that P[B|A] = 1/4; we don't know anything about P[A|B] without more info.

It could totally be that all non-fired employees are toxic, and viciously went after their weaker colleagues by having them fired! I guess that would make them toxic, but whatever.

"... a quarter of all fired employees had been unpleasant players. Toxic players tended to be toxic employees, even if the reverse wasn't always true."

Isn't this saying the opposite?

Or it is faster than C (http://benchmarksgame.alioth.debian.org/u64q/performance.php...). Depends which link you click on.

Not my experience, fwiw. Rust does a great job of handling the mental overhead (am I allowed to mutate this? who owns this? what is the contract for that?) for me.

It looks like they are comparing (in the chart) throughput on each of their file formats in bytes, rather than records. So, they are slower than HDF5, but eat up more resources doing so (which I think is meant to suggest they are leaving less to waste).

If you put the omitted "..." back in to the quote, it makes it clearer that the "for their own ends" is about appropriating credit rather than testing alternate hypotheses.

More importantly, the full paragraph starts "A second concern held by some is that...", signaling that this characterization is a not-universal opinion about what might be bad about data sharing. The very next paragraph argues that it doesn't have to be this way, which is the whole (missed?) point of the text.

It's almost like the posts here are trying to make the authors' case about the hazards of data sharing for them.

I don't want to speak for all of dataflow-dom, but the main differences that I see (and exploit) are that data-parallel dataflow languages isolate control flow into small independent regions, making the larger computation data-driven. This does mean things are eager rather than lazy, but it also makes things much easier to parallelize (because of the independence) and much easier to incrementalize.[0]

[0]: https://github.com/frankmcsherry/differential-dataflow

It's a good question. I'm punting for the moment because it isn't clear that there is one true solution that makes everyone happy. So, let's say MPI then. :)

I think the more optimistic version is probably that the signals Timely Dataflow (the model) gives should make tasteful fault-tolerance logic easier to write. Michael Isard did some work here just before leaving MSR. Realistically, errors haven't been a big problem yet (thanks Rust!) and it's a research prototype for understanding efficient data-parallel compute, so not too bothered yet.

The MR/Spark approach comes with lots of hidden costs in the programming model; I'm not clear on when these costs make sense. Using lots more resources so that you survive being killed because you were using too many resources seems like a not-best solution.

Some of the layers on top have better fault-tolerance properties. For example, differential dataflow operators are functional and have append-only logs as their internal state; I could see that stack ending up with more transparent fault-tolerance properties, though not yet.

The cost of writing to some number of unrelated locations is mostly determined by the level of cache where your working set can stay resident. You'll be doing random access to that level of cache, but it can exchange data with the next level cache in larger contiguous blocks.

In this case, 256 cache lines fit in the L1 cache, so while it does look like "random access" to the L1, this can end up looking more like "sequential access" to main memory. There are addition complications, like the L1 data cache being only 8-way associative, a quite small TLB cache sitting in front of the L2 and up, etc. So in practice this ends up somewhere between random access to L1 and random access to L3, with sequential access to main memory, I think.

There is this cool related work [0] that I wanted to talk about, but couldn't get to show an improvement on my laptop, which uses software write combining to mitigate cache limitations. In particular, they are worried about the fact that 8-way associative L1 doesn't like to hold 256 specific cache lines, so they manually buffer writes into 16k (= 256 cache lines) contiguous bytes, using a non-temporal write when a cache line is full. They report hitting 88% of their system's peak memory bandwidth.

You could do the same thing (I think) to avoid TLB limitations, manually staging everything in a contiguous 2MB of memory (backed by one large page, say), in order to keep the radix high and do fewer full scans. If you are hitting memory bandwidth, your performance should be determined by the number of scans you end up doing.

All of this is "caveat: I just read other people's work and haven't done this myself, because I haven't figured out inline asm in Rust yet". If you have more details on engineering radix sort, I'd love to read up! :D

[0]: http://arxiv.org/abs/1008.2849

By way of comparison, the single-threaded numbers for PageRank on the `twitter_rv` graph on my laptop are 1.5B edges in 5s, which is about 300M edges per second per core.

PageRank isn't doing much other than a load, a few += operations, and a store. The main reason it is slow is because memory is far away, but if you lay out the edges intelligently your rank data is usually in the L3 and then computers go fast.

> "Rust can leak memory" is an overgeneralization of the issue and misrepresents it.

I thought it was the exactly correct response to a comment that says Rust's main feature is that it doesn't let you leak memory. =/