frankmcsherry

1. Your skepticism for using Rust cites [26], the PLOS paper from the same people who did [27]. They've essentially recanted, in that their PLOS talk was right after Niko's keynote, and he then talked them through how interior mutability works in Rust. Other than [26], are there other lingering concerns? I could imagine so, but it would be great to take stock.

2. You don't seem to page to disk, and do OOM shootdowns instead. If you did enable disk paging, how comically bad an idea does a tracing GC become? :D Naively, I could imagine RC-GC being less horrible, but perhaps that's my built-in (and absolutely for real) bias.

    https://eurosys2017.github.io/assets/data/posters/poster21-Lattuada.pdf

The DD and Adapton approaches may be a bit tricky to hybridize. Much incremental compute works by moving through a sequence of valid configurations, and DD's main departure is generalizing this to partial orders. So, maybe you could borrow ideas, but it would probably be original research to do so.

Email is great, as it is def no longer about skiplang.

https://github.com/frankmcsherry/differential-dataflow

   https://github.com/frankmcsherry/abomonation

http://www.cs.virginia.edu/%7Ecs415/reading/bacon-garbage.pd...

If you have only a probability distribution defined by a product space where all distinguishable events have probability p^i, for some finite i, then any subset of the distinguishable events accumulate to a probability r * p^i for some integral r. If your goal is a probability that is not an integral multiple of p^i, you are out of luck with a finite number of samples.

The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their DFS implementation retains state; not sure what to make of it, and not a Python reader:

> Depth-First should be a bit kinder to system memory, though it'll still chew up quite a bit remembering which game states we've seen before.

Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".

> One note about the results for kdb+: The ingestion scripts I used for kdb+ partition/index the data on the year and passenger_count columns. This may give it a somewhat unfair advantage over ClickHouse and LocustDB on all queries that group or filter on these columns (queries 2, 3, 4, 5 and 7). I was going to figure out how to remove that partitioning and report those results as well, but didn’t manage before my self-imposed deadline.

http://yellowstone.cs.ucla.edu/~yang/paper/sigmod2016-p958.p...

I wouldn't hold your breath on it getting faster.

Edit: and if you are interested in state-of-the-art stuff, here is a thread to start you out on the papers currently being presented at SIGMOD2018:

https://twitter.com/frankmcsherry/status/1002812204075364353

> Databricks made a few modifications to the original benchmark, all of which are explained in their own post: > Removing Redis from step 5 > Generating data in memory for Flink and Spark; generating data via Spark and writing it to Kafka for Kafka Streams > Writing data out to Kafka instead of to Redis

I think the authors know that the benchmark is weak. The blog post isn't (to my reading) claiming that it is proof that SABER is great so much as that the distributed stream processors need better evidence that they should exist (vs the Databricks Structured Streaming SIGMOD 2018 paper, in which the YSB benchmark is (I think) the only quantitative evaluation they do).

I suspect the point of disagreement is

> Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver".

which I don't think is correct. A Datalog solver with the property that it can run faster on certain classes of input is great; it is not "no longer a Datalog solver".

The engine supports negation in the standard way: stratification. You can call 'from_antijoin' with a static relation for its second argument but not a variable. It is not discussed in the post because it is a bit of a diversion from the intended message (and because antijoin is computationally not much different from a filter).

If you would like a more general compute model with non-monotonic iteration, I recommend differential dataflow!

http://erikdemaine.org/papers/BufferTrees_STOC2002/paper.pdf

The rough gist is that if the only thing you need to be able to do is insert and pop-min, then you can buffer up roughly a page's worth of incomplete work for each page, getting amortized performance that tracks the optimal number of cache transfers at each level of the cache.

Further, in the paper above you are introduced (in the related work) to the citation:

"A. LaMarca and R. E. Ladner. The influence of caches on the performance of heaps. Journal of Experimental Algorithmics, 1, 1996."

which describes the author's "B-Heap" (at least, it describes a b-ary heap where you pick b to match your cache line/page size).

I'm guessing the problem isn't that academics don't understand these things so much that practicing programmers don't always read very much.

Let X be a set of iid samples drawn from a distribution D, let M be a model trained with eps-DP on the set X, and let x' be a fresh sample from D.

Let's think about the random variable M(x'), which represents your test loss or whatever. Differential privacy says that the density of this random variable is pointwise within a factor of exp(eps) of M'(x') where M' is the random model resulting from training on X \cup { x' }. But M'(x') is distributed per a random x', random X, and M' trained on both just like your training loss or whatever.

You can push linearity of expectations through all of this to show that your expected loss on test and training should vary by at most a factor of exp(eps), but I'm not aware of a pointwise test for a specific model (and it may not make sense, as DP isn't a property of specific models, but rather distributions of them).

Edit: you can read a bit more about a special case of this at https://windowsontheory.org/2014/02/04/differential-privacy-...

I think this gets at Wirth's law a bit. Yes compilers perform lots of optimizations now, but in Rust's case it is at least partly because they need to in order to claw back the performance that the Rust gives up with its abstraction (as seen in debug builds).

I do much prefer Rust's safe abstractions to writing more direct code and hoping I get it right. I hope (and do believe) that the MIR effort will somewhat rein in the burden shunted over to LLVM, as it is super painful for some of us.

Rust does have the opportunity to do more, and I suspect they are hoping to do more with MIR, but at the moment they rely on LLVM to optimize out all of the zero-cost abstractions that they introduce.

I still don't see why customers want this. I would rather a company struggle to spend its ad budget effectively, and then conclude that it could better spend its resources investing in making a better product (or its employees, or its infrastructure, ..).

I don't have an econ background, so feel free to clear up what's wrong here.

tl;dr: the C and Rust versions had signed integers rather than unsigned like the ATS version, and if you make that change they end up more similar.

[0]: https://users.soe.ucsc.edu/~sbrandt/papers/NIPS02.pdf

I can write that using various maps, folds, flat_maps, and reduces, but no one else would understand what is going on in the code. Maybe someone will post the right idiomatic functional way to do that, but nothing elegant comes to mind.