psi-squared

That's a really neat solution, and avoids the cognitive overhead of having to remember yet another password (or the security risk of re-using passwords). I particularly like the way you tie the log-in token to a particular browser session so that it can't be hijacked!

Plus by merging all of the log-in paths (registration, 'forgot password', and normal login), you have one thing to design and secure rather than three. That seems like a huge advantage from a security perspective.

It's worth noting that, if you need something which runs on really low power, ARM have their R and M series processors. So even if the A series did become really power-hungry, the other two lines presumably wouldn't.

> I suspect the results in this paper could be improved with more modern gather techniques on newer x86-64 processors.

By that, do you mean the AVX2 'gather' type instructions? If not, I'd be interested to know what those techniques are.

As for AVX2 gathers, I had to look this up recently and it sounds like they're about as fast as manually unpacking the vector and performing scalar loads. That is to say, they're decidedly not fast. On the other hand, it sounds like (as of Skylake) they're bottlenecked on accesses to the L1 cache, so they're about as fast as they reasonably could be.

Source: https://stackoverflow.com/questions/21774454/how-are-the-gat...

Not sure about performance on Zen, but I would imagine it's similar?

If you want exactly zero at the end points, you could do something like the post does, of approximating sin(x) / x(pi+x)(pi-x), or similar. You can still do that with the Remez algorithm.

Also, a while ago I realized that you can tweak the Remez algorithm to minimize relative error (rather than absolute error) for strictly-positive functions - it's not dissimilar to how this blog post does it for Chebyshev polynomials, in fact. I should really write a blog post about it, but it's definitely doable.

So combining those two, you should be able to get a good "relative minimax" approximation for pi, which might be better than the Chebyshev approximation depending on your goals. Of course, you still need to worry about numerical error, and it looks like a lot of the ideas in the original post on how to deal with that would carry over exactly the same.

The paper has a section on this, around the end of page 4, which is really interesting. The short version is: They compared their double-precision results to extremely high-precision Taylor expansions (with theoretical 70+ digit accuracy, and calculated in 100+ digit accuracy), and found that they matched to the accuracy you'd expect.

That doesn't guarantee that the orbits are perfectly periodic, I suppose, but it does suggest that the orbits are stable with respect to rounding errors up to those you get from using doubles.

I am not a security researcher, but I think you could keep the benefits of both compression and security, as long as you're careful on the server side:

Say you have a document structured like [boring data] [secret data] [boring data]. I don't know if any existing compressor lets you do this, but the gzip file format (really the 'deflate' format used inside it) allows you to encode this (schematically) as follows:

[compressed boring data] || [uncompressed secret data] || [compressed boring data]

where each || is i) a chunk boundary (the Huffman compression stage is done per-chunk, so this avoids leaks at that level), and ii) a point where the encoder forgets its history - ie, you simply ban the encoder from referencing across the || symbols.

If you wanted, you could even allow references between different "boring" chunks (since the decoder state never needs resetting), just as long as you make sure not to reference any of the secret data chunks.

Edit to add: Also, if the "boring" parts are static, you can pre-compress just those chunks and splice them together, potentially saving you from having to fully recompress an "almost static" document just because it has some dynamic content.

I had an eye test recently (in the UK, if it's relevant), and they had a device which seemed to do that. You sit down, look into the device and see a blurry image, which sort of "snaps" into focus as it works out the shape of your eyes.

That device was a fairly big thing linked to a desktop, though - no idea if it could be miniaturised or not. In addition, they followed it up with more "traditional" tests, which in my case disagreed with the results from that device. So maybe it's not quite there yet?

This is related to my current favourite algorithm: Because the BWT is closely related to the suffix tree of the original string, there's an algorithm to search for a substring of length 'm' in a BWT-ed string of length 'n' in O(m log n) time!

The one downside is that you have to pre-process the string, which takes O(n) time and between 5n and 9n space depending on exactly how you do it. But after that, you can do as many searches as you want practically "for free".

There's a paper outlining the various algorithms available here: (PDF) http://www.cosc.canterbury.ac.nz/research/reports/HonsReps/2...

There's a really nice article about the Postgres query optimizer, which goes into much more detail about the algorithms used (it's likely that at least the basic ideas are shared with SQL server, though I can't say for sure). I really like the exposition in this:

http://jinchengli.me/post/postgres-query-opt/

Okay, so on reading through that it looks like the answer to my question is "it depends":

* On-disk, the layered approach always saves space, as expected

* In memory, it depends on which storage backend you use: apparently btrfs can't share page cache entries between containers, while aufs/overlayfs/zfs can - I'm not sure if this is due to btrfs or docker's btrfs backend.

From looking at the relevant sources, it looks like (but I could be wrong if I looked in the wrong places) both exec() and dlopen() end up mmap-ing the executable/libraries into the calling process's address space, which should mean they just reuse the page cache entries.

So, if I understand correctly, as long as you pick a filesystem which shares page cache entries between containers, then you do indeed only end up with one copy of (the read-only sections of) executables/libraries in memory, no matter how many containers are running them at once. That's good to know!

(disclaimer: I haven't watched the talk yet, this is just branching off of Animats's comment)

One thing I wonder, and which I don't know enough about containers to answer myself, is:

Let's say I have a bunch of containers which share most of their system packages, but which each have some extra per-container state (possibly packages, possibly just application data). Suppose I decide to build one read-only image for the common data, along with one smaller, read-write overlay per container.

As I understand it, when you run multiple copies of a program on a system not using containers, read-only parts (eg, the .text sections of the executable and of any shared libraries) are only loaded into memory once. Would this behaviour carry over to multiple containers using the above setup?

If so, that seems like it would accomplish most of the memory usage reduction for this case, without needing explicit memory deduplication. Of course, this won't fit all use cases, but is it a viable option?

It looks like the first part of what you want is nearly there - see https://github.com/Yamakaky/rust-bindgen

It converts C headers to a Rust module containing the relevant type/function/etc. definitions. On stable you need to either pregenerate the module (not too bad if you're pinning particular versions of libraries anyway) or add a build script to autogenerate it. On nightly, there's also a compiler plugin that does all the work for you, and looks not-too-dissimilar to what you wanted. The only thing it lacks is the prefix removal stuff.

One of the less-well-known features of Linux is that you can do this! Theres's a thing called the "x32 ABI" (use the option -mx32 with gcc or clang; you'll need all your libraries compiled with it too) where:

* As far as the processor itself is concerned, the code runs in 64-bit mode, so you get the extra (and wider) registers from that.

* But pointers are still 32 bits, so you get the memory savings of 32-bit mode.

In principle, as long as you're using <4GiB of memory, it should be at least as fast as the best of 32-bit or 64-bit mode for any particular program. But I haven't heard of it being used much.

https://en.wikipedia.org/wiki/X32_ABI

(edited to add: Note that superoptimization isn't something you do to a whole program, it's more a thing you do to speed-critical sections of a larger program, ideally on the order of a few dozen instructions at most. That alone makes things a lot more tractable)

(edit 2: I've read the relevant papers now, and have corrected some of the stuff below. Corrections are in italics.)

The paper says that this system is built on top of STOKE, which uses the following verification method:

* Generate a random set of test cases

* Each intermediate code block gets instrumented and run on the host processor

* The intermediate code block are given a cost depending on how different their results are from those of the original block on the current test set, as well as an estimate of the running time

* If we get a code block which is correct on all the current test cases, we ask a theorem prover whether it's equivalent to the original one. If it isn't, the theorem prover spits out a test case which proves they're different, and we add that to the test set for future iterations.

Finally, the fastest few provably-correct results are output, where they can be further tested in a full run of the original program they were taken from.

The main room for error here is in the theorem proving step, which requires knowing the full semantics of the host's machine code. But it feels like that part should be share-able between different projects, as it's pretty much independent of the search method used.

My current workflow has a lot of "Run make -j<lots> to build, followed by parallel -j<lots> to run all the tests", but sometimes I want to compare/test multiple different versions of the code (in a way which, sadly, doesn't work well with incremental builds). In that case it'd be nice to be able to just spin everything up and not have to worry about overloading/under-loading the machine I'm working on.

I know what you mean about the load average limiter - parallel behaves like that too. I think the --delay option to parallel is supposed to solve that (I haven't tried it - will try tomorrow), but I don't know if make has anything similar.

Finally, on further reading, it definitely seems technically possible, even if it hasn't been done so far. The make documentation has a section on the jobserver protocol, which looks complete enough to write both the client and server parts: https://www.gnu.org/software/make/manual/html_node/Job-Slots...

So if nothing exists so far, it's something I might look into writing myself.

If I've read this correctly, the 'sem' mode lets you submit several lots of jobs with an overall limit on the total number of tasks running at a time (rather than one limit per lot of jobs).

That on its own is super useful for what I'm working on right now. But what would make it even more useful, is: can you get GNU make to use 'sem' instead of its own jobserver? That way I could run almost everything I need to under one overall task limit, and that would be really nice to have.

(For this reason, I'm a fan of the idea that every program with its own 'parallel execution' mode should be able to interact with a common jobserver. The 'make' jobserver is, as far as I know, the simplest, and should be pretty easy to support: http://make.mad-scientist.net/papers/jobserver-implementatio... )

This is pretty neat! A couple of thoughts spinning off from this:

In the breadth-first traversal example, it looks like the resulting linked list is completely static. By that I mean that you could pre-compute the traversal order and store it into the linked list of 'p' pointers. Then you can traverse as many times as you want just by following the pointers. In fact, as long as you aren't editing the tree, these traversals should even be reentrant and thread-safe.

I feel like you could do the same sort of thing with depth-first search, or any other scan order really: Do one "expensive" (ie, allocating) traversal to build a linked list, then lots of (comparatively) cheap linked-list-following. Or you could even build the linked list along with the trie, and update both when you add/remove elements (if that's much rarer than traversals). For the latter you'd probably want to use a doubly-linked-list so you don't have to do another search to find the "previous" element.

If you are able to allocate extra memory, or can structure the memory layout appropriately, it might even make sense to (re-)pack the trie nodes in traversal order in memory, so that the memory accesses during a traversal are nice and linear. Again, depends a lot on how you're using the trie and what your constraints are.

It's been mentioned below that differences in temperature matter a lot. But there's also the fact that erasing a flash block inherently damages it, progressively reducing its ability to retain data.

So I wonder if there's a tradeoff between longer data retention when powered off (by using higher write and erase voltages) and longer MTBF (by using lower voltages). I could be completely wrong here, but if there is such a tradeoff it would make sense for consumer and enterprise drives to make different choices.

The two types of "ghosts" here are very different. In both cases, though, they're mathematical artefacts rather than anything "physical", but I'll try to explain them as well as I know. Disclaimer: The most advanced physics I've done was a first course in this stuff, so I might be wrong about some things.

For what they're calling "Higgs ghosts": There are two different ways of describing the electromagnetic and weak forces, and which one is best depends on how much energy the particles you're dealing with have. At really high energies, it makes the most sense to talk about a combined "electroweak force", described in terms of four fields with 2 components each (often called W1, W2, W3 and B), and one 4-component field (the Higgs field).

In contrast, at low energies, it makes more sense to talk about the electromagnetic force, with one 2-component field (y), and the weak force, with three 3-component fields (W+, W-, Z0) and a 1-component field (the Higgs field, again). So, where did the other three components of the Higgs field go? Well, we just rearranged things - if you check, the total number of components stayed the same. There are various names for this rearrangement, and I haven't seen this one before, but I guess they're calling these "missing" components "ghosts".

As for the other type, the Faddeev-Popov ghosts, those are more obviously mathematical artefacts. Normally, you'd start by writing down a "physical" Lagrangian ("physical" here meaning something like "written in terms of actual physical fields").

But it turns out that you can't actually calculate with the physical Lagrangian. So you have to rewrite it in a (mostly) mathematically-equivalent way, which involves extra fields. These fields come along with extra rules which basically say "no state you can actually measure involves the ghost fields in any way". Really, they're just there as a calculational aid and aren't physically "real", and they're called "ghosts" to reflect that.

Hope that's at least vaguely comprehensible, it's difficult to explain this stuff without assuming a lot of background knowledge.

So, let's call the correct value of whatever 'A'. Then "Off by X%" really means that the number you used is (1 + X/100) * A. (note: if you underestimated you need to make X negative for this to work)

When you raise that to the power Y, you get (1 + X/100)^Y * A^Y, when the correct result is just A^Y. So you get (1 + X/100)^Y times what you should've gotten.

You can convert that back into a percentage directly if you want, but if X is small (ie, if the original value is "close enough"), you can use the binomial expansion [1] and just keep the first few terms. If you do that, you eventually end up with:

Percentage the final result is out = Y * X + (1/200) * Y(Y-1) * X^2 + ...

[1]: https://en.wikipedia.org/wiki/Binomial_theorem

There is an exception-like mechanism in Rust, in the form of the "try!" macro. It's a lot more flexible, but somewhat more verbose (Haskell has the same mechanism in a way that looks a lot more like exceptions, so that's not an inherent flaw). The best explanation I've seen is this:

http://www.jonathanturner.org/2015/11/learning-to-try-things...

tl;dr: "Result"s are like exceptions which are caught by default. You can (explicitly) propagate them upwards by using try!(...). This is nice because it means that you can tell what exceptions can occur in a block of code only using "local" information.

As the article points out, every modern OS clears (main) memory before handing it over to a new process. The cost is often mitigated a bit by using spare CPU cycles to zero out free pages, and by keeping a buffer of such pages. You only need to pause to zero pages if you have sustained 100% CPU usage for a long time - and that's pretty rare on most machines. GPUs probable even more so.

GPUs generally have less memory, many fewer (but larger) allocations, and way higher memory bandwidth than CPUs, so it shouldn't be a problem for them to do this.

AIUI, ZFS was explicitly designed to deal with this sort of data corruption - one of the descriptions of the design I've heard is "read() will return either the contents of a previous successful write() or an error". That would (in principle) prevent the file containing "a boo" or "a far" at any point.

It looks like one of the authors cited in this article has written a paper analysing ZFS - though they admittedly don't test its behaviour on crashes. Citation here, in PDF form:

http://pages.cs.wisc.edu/~kadav/zfs/zfsrel.pdf

(edited to add: This only deals with the second part of this article. The first part would still be important even on ZFS)

How much do you cache? Hardware is difficult because you could add/remove/swap it at any time, and software information is already partly cached depending on your OS.

IIRC, Windows a) builds a list of files to pre-load from disk based on your usage, and b) doesn't actually fully shut down by default (it goes to hibernate mode: http://blogs.msdn.com/b/olivnie/archive/2012/12/14/windows-8...). I don't know if any Linux distros do either of those by default, but it is certainly possible.

Also, some BIOSes already have a "quick boot" setting which caches some hardware information, particularly about memory. It usually comes with a warning that you need to disable the setting for at least one boot when installing RAM.