Cool! Who is "we" and where can this code be found?
You say "RCU like this", but AIUI RCU and epoch-based collection like in this article are quite different from each other.
RCU involves no-synchronization reads of a data structure and writers that wait for a "quiescent" state to delete old nodes. It is used for data structures that have pure readers (like a frequently read but infrequently-updated list of things).
Epoch-based GC involves lock-free writes but puts garbage in freelists to be collected at a later time. It is used for data structures that are mostly based around writes (for a stack or queue, both push and pop are mutating operations).
"We" is "infrastructure teams at Google". You apparently work there too, my username is the same.
RCU is an overloaded name; it's both a family of implementations of epochs, and a pattern for using epoch-like systems. The name literally refers to the latter (a read-mostly RWlock setup where we don't bother protecting the read side of a data structure, but _copy_ and atomically update access to the data, using epochs to dispose of the old version safely) but is often used to describe the whole system (tracking quiescence and determining when disposal is safe.) One could easily use the kernel's RCU (our my userspace one) to build a data structure like this.
Could someone explain the big difference between RCU and epoch-based reclamation? It seems that the only difference is that RCU has quiescent periods between reschedules and epoch-based has them when you don't have a Guard struct active. Seems like six of one, half a dozen of the other.
They are very similar; I think of the epoch scheme as a particular way of doing RCU that does not impose the need to find quiescent states yourself (RCU can be employed in userspace as well if your application can provide quiescent states in some way).
I think a key property of RCU as traditionally presented is that writers always wait for global quiescence directly after their write, and then immediately delete the garbage. This approach wouldn't make much sense for data structures like stacks and queues where every operation is a write. I see Epoch based GC as an approach that defers the deletion to make the write path cheaper.
> I think a key property of RCU as traditionally presented is that writers always wait for global quiescence directly after their write, and then immediately delete the garbage.
A rather common, in my opinion, way to use something like rcu is to delay freeing (or reusing) memory to the next grace period, without blocking until then. E.g. in the kernel you can use kfree_rcu(..); instead of synchronize_rcu(); kfree(..); for that. That's basically what the epoch based approach does with a the lists of to-be-freed allocations.
According to the paper, it simply makes everywhere outside of data structure code a quiescent state. This may be a big difference in practice through, because one of the appeals of RCU is being able to interact with data structures with no fear of following dangling pointers.
However, with both RCU and the epoch-based scheme, you can make quiescent states as fine- or coarse-grained as you desire.
"According to the paper, it simply makes everywhere outside of data structure code a quiescent state" -- yes, from a per-thread point of view, but of course all the hard work is in detecting global quiescence.
> In addition to improving privacy and control, this is the only way to make Open Source web apps viable.
What about client-side web apps? Like Chrome apps? I've been working on an open-source web app with the intention of deploying it as a client-side Chrome app that is capable of syncing to many popular services (Dropbox, Google Drive, etc) for cloud storage.
I am particularly interested whether your security model could support the following: I'm working on an accounting app, and want to support letting the app automatically pull transactions from the user's bank accounts, mint.com-style. So the app needs to be able to log into the bank's websites as the user, probably using a real web browser. But I (as the developer) don't want to have access to the user's credentials or have the app capable of phoning home to me.
I also want users to have confidence that they can use third-party contributed, bank-specific plugins for pulling this data, but be guaranteed that these plugins can't steal their data or their money. A slightly difficult problem, given that once you have a bank login, you can probably use it to move money around. But curious if you have an answer to this!
The tight security of the app model is compelling, given how sensitive my users data would be.
> PS. offtopic but can you merge this PR? :D
I totally had a long-ish reply typed out but must have closed my browser before I hit "submit" -- d'oh! Sorry, will get to that now.
Yes, absolutely, that sounds like a perfect fit for Sandstorm's security model. We are still working on some of the details, but the user will be able to ensure that the app can, say, talk to bankofamerica.com but not any other web site. You could also have each "bank connector plugin" be in a separate grain, so only that grain has outside access, and then a security-paranoid user only needs to review the connector code to make sure it doesn't do anything nasty, rather than reviewing the whole app. The core app would only have permission to talk to the connectors.
Of course the next question is: will any user actually understand how to set this up? I think with the powerbox UI, it will actually be quite reasonable. It would look like this:
- User installs the base app, which initially has no permission to talk to the outside world.
- User clicks "add an account", causing the app to make a powerbox request for an object implementing "BankAccountConnector".
- The user doesn't have any of those yet, so Sandstorm would guide the user through finding a matching app on the app market, installing it, and setting it up. It's not hard to imagine a reasonable UI here: You see a list of matches like "Bank of America Connector", "Wells Fargo Connector", etc.
- As part of installing an app, the user will be able to see who the author is, look at reviews, and (if they are so inclined) click through to code.
- Once installed, the connector app prompts for the user's bank credentials and then makes a powerbox request for "access to bankofamerica.com" (or whatever). Sandstorm asks the user if the app may access this site, and the user confirms.
- Everything now resolves and the user is returned to the original app, which now is able to pull data from their bank account.
This is, of course, still very vaporware right now, but that's the vision, and there honestly aren't many open questions about how it will work, just code to write.
Cool -- that's a really compelling story! And I presume the two apps (the main app and the connector app) can send messages to each other?
The only part of this that seems short of ideal to me is: I want the connector to use a real web browser to talk to the bank's website, for several reasons, but chief among them is that if the website asks the user something unexpectedly (like a security question), or something doesn't work, it's easy for the user to see what is going on. That is one aspect of the client-side approach I liked: the browser running the accounting app is the same browser being used to actually fetch the data. Do you have an answer for this?
> And I presume the two apps (the main app and the connector app) can send messages to each other?
Yep. Through Cap'n Proto RPC -- or HTTP layered on top of Cap'n Proto RPC.
> I want the connector to use a real web browser to talk to the bank's website
Interesting. That does add complication, but it seems doable. Perhaps the connector grain could act as a proxy, embedding the bank's UI in an iframe, where the iframe src of course doesn't point directly to the bank but points back to the connector grain in proxy mode.
FWIW, we definitely want grains to be able to embed each other's UIs in iframes (with proper permissions), which might play a part in this.
> Interesting. That does add complication, but it seems doable. Perhaps the connector grain could act as a proxy, embedding the bank's UI in an iframe, where the iframe src of course doesn't point directly to the bank but points back to the connector grain in proxy mode.
You're saying MITM the user's HTTP connection? I can't imagine how that would work with SSL?
This might be too tricky to actually be feasible, just dreaming here! Hopefully it is useful to help you imagine cool scenarios and possible requirements.
> You're saying MITM the user's HTTP connection? I can't imagine how that would work with SSL?
The browser wouldn't think it's talking to bankofamerica.com. The browser would think it's talking to your sandstorm server. The user is willingly letting the grain MITM the connection so that the app can get their data out.
That's a different use case. A client side web app is supposed to mimic the use case for native apps. While sandstorm seem to mimic the use case for Web Apps. If you are the only user I guess you could try to port it as a Chrome App, but Sandstorm seems to be aiming for something available online to be accessed by multiple users.
The laws of physics conserve information in that sense that two initially distinct states will always remain, at least in principle, distinguishable for all times, i.e. two distinguishable states A and B will never evolve into the same state C. This is equivalent to the statement that the laws of physics are time reversible, i.e. if you would end up in state C you could not tell whether the system came from state A or B.
If you, for example, start a pendulum with different initial displacements the pendulum will always end up at rest due to friction but if you could take into account the exact states of all the molecules in the air and the joint and so on you could in principle figure out in which exact positions you started the pendulum.
You could actually just very precisely measure the temperature of a pendulum in a box and infer the initial displacement from that because different initial displacements imply different initial (potential) energies and therefore different final temperatures after all the energy became thermal energy and everything in the box had time to reach the equilibrium temperature. You just couldn't figure out whether the pendulum was started to the left or to the right of the rest position with this method.
Fascinating. Do physicists generally believe this? The idea that both the infinite future and the infinite past are all encoded into any snapshot of the universe is blowing my mind.
My layperson's understanding of QM always gave me the impression that it does the opposite: that it gives non-determinism a place to "hide," so-to-speak. My impression was that religious believers could use QM to argue that their unseen God, for example, does actually have a physically plausible mechanism by which he/it could intervene in the physical world. But if I'm understanding this theory correctly, unless God is a physical thing, there is no way for God or any other supernatural force to affect the physical world without itself being physical.
This theory also would seem to deny the existence of free will.
It is the same for quantum mechanics, in technical terms the time evolution of a quantum system is unitary. It is the uncertainty principle that prevents you from learning the exact state of a system and therefore perfectly predicting its evolution into the future or past. The underlying mathematical structure nonetheless allows you to do exactly this assuming you exactly knew the state of the system at one point in time.
There is of course the infamous collapse of the wave function that seems to turn a quantum state into a classical state during a measurement and this with different probabilities for different outcomes. This collapse of the wave function is not unitary and there are no good reasons to assume that a measurement is in any way special and should violate the laws of quantum mechanics which have otherwise been shown to work with incredible precision.
Therefore the collapse of the wave function is probably not a thing but just an apparent artifact of our ignorance of the details of the measurement apparatus which just is a gigantic quantum mechanical systems with billions and billions of particles.
Another way to think about that are symmetries and conserved quantities. The physical laws are believed to have certain symmetries, for example time and space translation symmetry or rotation symmetry, i.e. a physical experiment should yield the exact same result no matter whether you do it here or five meters to the left, today or in three weeks, with the laser beam pointing north or east.
Space translation symmetry, for example, means that if you change all you initial say x coordinates by the same amount the calculations should nonetheless yield exactly the same result as a calculation with the unchanged coordinates besides that the final state will of course have the same offset in its x coordinates.
If you demand that your laws of physics obey such symmetries and do some math you will find that each such symmetry inevitably gives you a quantity that does not change over time, i.e. that is conserved. That is Noether's theorem and extremely general, i.e. (almost) no matter what laws you imagine, a symmetry will always give you a conserved quantity.
The conserved quantity for space translation symmetry is what we call momentum, for rotation in space it is angular momentum and for time translation it is energy. But now that we have conserved quantities it is now impossible that two states differing in any of the conserved quantities will ever evolve into the same state or have ever been in the same state because that would require the change of a conserved quantity.
So to summarize, very basic assumptions like isotropy and homogeneity of space and time inevitably lead to conserved quantities which in turn prevent certain state evolutions that would violate those conservation laws. I am not sure if those constraints force time reversibility onto you but I assume they do.
Another commenter mentioned T-symmetry, that is that the physical laws remain the same if you reverse the time axis, i.e. multiply the time coordinates by minus one flipping past and future. This is of course not the same as time translation symmetry which is about adding to the time coordinates and it is also different from the reversibility I mentioned before, i.e. the ability to retrodict past states which does not require that the evolution into the past is symmetric with the evolution into the future. T-symmetry is believed to be violated for very good reasons but that has not yet been shown experimentally although it follows from the observed CP-violation and the assumed CPT-symmetry.
And I am not a physicist, so while I believe everything I said is accurate or marked as me not being sure or not knowing it may still contain some - hopefully minor - errors.
QM does away with any notion of conservation of information. Time reversibility (T symmetry) is usually talked about at macro scales where QMs effects are vanishingly small. IANAP
Regarding free will -- rigorously define it for us, without evoking the supernatural, and as distinct from pure randomness and absolute determinism, and it should be easy to tell whether the law of conservation of information allows for it. Before spending too much time in e it, though, note that such a definition is widely considered impossible. IANAP
Time reversibility exists in quantum mechanics because observables are self adjoint operators. Closed systems evolve unitarily. In simpler terms, you can think of it as the requirement that maps preserve distances and are easily invertible. We need this so that the information describing a system (which we can still talk about in terms of traces), remains invariant with time. In the classical sense, the corresponding violation leads to probabilities not summing to 1! We clearly can't have information shrink and for pure systems, dropping distance preserving maps leads to a really awesome universe (I believe this also ends up highly recommending L2). We literally go from a universe that is almost certainly near the bottom end of the Slow Zone of Thought to the Upper Beyond (https://en.wikipedia.org/wiki/A_Fire_Upon_the_Deep#Setting). We gain non-locality, causality violations and powerful computational ability.
In practice, our confusion about a system does increase with time as classical systems become ever more correlated, losing distinguishability, aka decoherence.
To me, a lack of free will would mean that a mind's future state is entirely determined by its current state. "Free will" would mean that its future state can be altered by some nonphysical entity (whether you call that a soul, consciousness, or whatever).
Free will is an obvious idea for a self aware consciousness to adhere to. The purpose of consciousness is to keep its organism viable. It does that by collecting an essence of past and from that predict an essence of the future. This expectation of the immediate future is then corrected according to actual perceptions and transformed into appropriate actions.
The full past is abstracted into an essence state, lots of information is lost to elsewhere, so there is no way to determine what details of the past went into forming the precise state from which the brain makes its actions. Of course it has to feel like at least some of our choices emerges from nowhere. But the only way to know if a brains thoughts are really free is to replay its entire brain state building past in every minute detail and look for alternative actions. An impossible experiment.
When you formulate it so, the problem is the question itself, as, except if we are religious believers, we don't have any reason to consider a "soul" (or a "consciousness") to be a "nonphysical entity." Look at the etymology of the "psyche:" it's "the breath." At the time people explained their environment unscientifically they considered that the existence of "breath" makes the difference between the dead and the living person but also between the conscious and the unconscious bodies. Animals do breathe too. But humans saw themselves as "special" in their religious setup. As a kid would ask "does my dog go to heaven too when he dies?" See, we go deeper and deeper in religious explanations which just postulate something non-existing (once you accept nonphysical soul, it's easier to believe in heaven or reincarnation or whatever). Now go back and ask, if you believe that the only thing we can "see" around us that doesn't have the "physical entity" is the "soul" of humans why do you do so? Are humans by any way "the chosen ones" in the animal world, looking at their physical bodies and the processes in them? The scientific view doesn't see them so. The human "consciousness" is, so observed, more complex than the "consciousness" of the crow on the lawn due to the more complex brain, but both of these can be explained as the function of their physical "hardware" (the body and the brain) and the interaction with the environment. The "consciousness" as a "neurological process by which the animal or the human sees it as special, the center of its attention in order to protect itself" can be seen as a product of evolution. (And now I have a weird feeling of explaining a grown up person that Santa doesn't exist). So it looks that we humans, if we don't destroy ourselves first, will be able to eventually produce a "conscious" computer. (Hal, open the door, please).
> Now go back and ask, if you believe that the only thing we can "see" around us that doesn't have the "physical entity" is the "soul" of humans why do you do so?
I don't think this. I don't think that anything about the consciousness or agency of humans is exceptional to humans.
> The "consciousness" as a "neurological process by which the animal or the human sees it as special, the center of its attention in order to protect itself" can be seen as a product of evolution.
This is an interesting perspective that definitely made me think, but I think it ultimately begs the question. If you're talking about "seeing" or "attention," you're already speaking in concepts that presume the existence of consciousness. I'm not sure this gives us a useful framework to know when any computational process we have created does indeed have "consciousness," or where the line is between animals advanced enough to have it and animals (or even plants) that don't.
> If you're talking about "seeing" or "attention," you're already speaking in concepts that presume the existence of consciousness.
Maybe I wasn't clear enough. The world around us (and animals) is projected in our (and animal's) neurological system as some kind of the model. The question is just if the model is such that favors the representation of the uniqueness of the organism or not. I claim that there's evolutionary advantage in producing a system (hardware and software) where organism cares for itself and where the model is so formed that "me" is in the center, to the level that "me" is "conscious" in the sense, processing the stimuli as much that the dog understands that the paw is "his paw" and that it's dangerous to put the paw in the fire and up to the level of you and me considering "us" "us" and being able to talk about it. Therefore we're not so much different from the rest of the animals.
> I'm not sure this gives us a useful framework to know when any computational process we have created does indeed have "consciousness,"
I'd still like to know how you can define consciousness in a way that it doesn't sound religious. If you can't, then of course we can't progress in our discussion.
Let me give you very "primitive" and "simplified" view of the "free will" subject. I see it as a purely religious construct, based on the following history: initially, gods weren't "almighty and omnipresent." If you've read ancient Greek literature, there are such gems like "Zeus was at that moment in Egypt so he wasn't there when the soldiers he supported lost." If you've read Bible, the oldest myths (I mean, stories in the Bible) are actually based on such concept of god(s). Then the theology "theory" grew more demanding, postulating the "almighty omnipresent" but also the "loving" god. Which made the myths (stories) much absurder than they were as they were written. How can almighty loving god produce the world and then see that it's bad, so that it has to send the flood to destroy it? It's either not almighty or not loving etc. As a rescue, the priests invented the concept of "free will" as in "once god creates humans, they have their own free will (which god can't control!?) and they do what they do so then they get to deserve to suffer, go to hell and all that nice stuff." Most of the "modern" theological concepts are constructed as an attempt to make less absurd the whole "body of work." A kind of "justification by obscurity" which obviously works for believers, giving them easy covertly nonsensical sentences to answer the "hard questions" others would give them.
In reality, we just have what user jonsen formulates here as "the purpose of consciousness is to keep its organism viable. It does that by collecting an essence of past and from that predict an essence of the future."
Now you ask about the "framework to know when any computational process we have created does indeed have "consciousness."" It depends on the definition of he consciousness, but that definition can't involve gods and "nonphysical entities." As soon as that is clear we can measure the "consciousness as what we observe in a dog" or the "consciousness as what we observe in a six months kid," the "consciousness as what we observe in a twenty years old healthy human" and the "consciousness as what we observe in 80 years old human with Alzheimer's disease which progressed this much."
Note that neurologists as the part of their daily routine have to evaluate the level of consciousness in their patients. It's very instructive to read just some examples of he cases they work with.
When we're there, do you think that a human with Alzheimer's disease which progressed so much that he can't remember anybody from his life or what he did just 15 seconds ago has a "soul?" (a lot of healthy animals remember for months different things, or if you talk with the owners of pets, you'll hear that there are animals which have traumas and a lot of the psychological symptoms you'd just associate with humans). So back to the patient, do you consider him "conscious?" If not, at which point did he lost his consciousness which you equate with soul? If yes, where is he different from some good Perl script? There is no "single unique unchangeable" consciousness, there are just different levels of functioning of the model I mention at the start. Of course, when you die, the model completely stops functioning as it needs both the hardware and the software, the brain and the body as the hardware and all these nice electrical impulses and chemical reactions in the living organisms as the software. There's no such thing as the "agency of the nonphysical entity" there.
I think it depends on your perspective. From the perspective of my keyboard, my input is random/unpredictable (it doesn't have perfect entropy, but it doesn't follow rules that make it completely predictable). From the perspective of my body, I have complete control over what I am typing, and there is nothing random about it.
No it doesn't depend on your perspective. If it did the conversation would make no sense. The only perspective worth considering is the global objective perspective. Quantum events are globally, objectively random. Nothing else seems to be, which means, by definition, that everything else is deterministic.
The question I'm trying to get at is: from the perspective of the physical realm (which may be, even likely is, all that exists) is there any possible mechanism by which something nonphysical could influence events in the physical realm?
For example, is there any physical property that is not "locked into place" by the laws we know and the observations we can make? Is there any fundamental impossibity (not practical impossibility) of snapshotting the state of the universe and using that snapshot to determine every past and future state of the universe?
I said without evoking the supernatural. The concept of a soul is supernatural. There's no reason to think consciousness is anything other than physical in nature -- but to the extent that you mean it in some kind of supernatural, extra-physical way, it's not part of this conversation.
By all means go on thinking there might be some supernatural thing called a "free will" if you want. But if it's supernatural, then the utterly natural laws of QM wouldn't have much to say about it.
> There's no reason to think consciousness is anything other than physical in nature
Consciousness is not the same thing as agency. It is possible that we are conscious but do not actually have free will / agency.
> By all means go on thinking there might be some supernatural thing called a "free will" if you want. But if it's supernatural, then the utterly natural laws of QM wouldn't have much to say about it.
I am not sure I agree. If QM implies a strict determinism, to me that rules out free will. For free will to be plausible, there has to be a place for non-determinism to "hide." If QM can rule that out, to me that rules out free will.
Yes there is a principal in on of the "interpretations" (we really need a better word for it) of QM that the information carrier by a wave function cannot be destroyed, this present a problem in certain cases such as black holes.
There's allot of weird stuff going on on the extreme edges of theoretical physics, to the point in which also a though that some areas of theoretical physics have moved into the "Metaphysics" and Philosophy domains and are distancing them selves from certain scientific principals.
That said I like to treat black holes in the GR/SR manner they are simple massive objects not super dense hot balls of entropy, they don't have some universal cosmic powers, they are "black" simply because they red-shift all radiation to the point of invisibility, they can form, grow and break apart, and we never can see anything actually entering a black hole due to time dilation and anything that comes close to it will be red-shifted to a point in which we won't be able to see what or where it is either.
Since nothing from out POV ever enters the black hole and everything is stuck on the event horizon nothing is lost, and since black holes can evaporate (Doesn't require hawking radiation altough it's the most common explanation since Yakov Zeldovich (which Stephen hawking based his work on) and others have proposed similar mechanisms which are more compatible with physics as it is measured and perceived by hmmm reality...), no firewalls or weird mechanism are needed to protect or explain other weirdness that happens around singularities.
Singularities are well covered by GR and SR prevents naked singularities so we are good there too.
All known physical processes only transform information, it's never actually lost (although it may get "transformed" in a way that it's irretrievably scrambled). Black holes are the only known thing that may cause information to disappear from the universe - or not, that's the open question.
The many worlds interpretations. Roughly speaking, if there is a quantum system that is in a superposition of states A and B, and we observe it, we then become entangled with it and are then in a superposition of having observed A and having observed B. No information has been lost from the universe, but there is no way for those of us living in the A state to observe anything about the B state.
Quantum information is actually different from classical information (classical entropy). Quantum information is (believed to be?) a conserved quantity; classical is not (it never decreases). A quantum random number generator is just emitting quantum bits: without having had those qubits in the first place, you can't have computed them ahead-of-time, so they're random.
It seemed to make a pretty strong statement by the end: "The old story of high primary sex ratio — as high as 282 (74 percent male) by some accounts — declining rapidly and then steadily to birth, is gone. Any sex ratio much higher than 108 (52 percent male) at any time during pregnancy is essentially excluded by modern data."
Really curious to hear more explanation of this comment from Patrick: "Printing is pretty incompatible with parallelism though." Is he saying that Servo as a parallel engine won't be able to handle printing?
Patrick refers to parallel layout here: in a text with many paragraphs for example, the contents of each paragraph can be laid out in parallel with other paragraphs. Then you only need to sum up the heights of earlier paragraphs to find the vertical position of each.
When printing though, you don’t know where to start page 10 until you’ve done the layout of earlier pages. There may still be some parallelism opportunity, but less than on screen.
That's not the problem. We could easily run our parallel screen layout and then just use Skia (or the local system)'s PDF backend. The trouble is that this doesn't implement the printing spec. As Simon mentioned above, the problem is the various CSS rules that control pagination.
Using a raster image is a recepie for slowness, especially at common printer resolutions of 300dpi+. It also breaks "Save as PDF" from the print dialog. Far better to communicate with the print driver using GDI, PostScript, PCL, PDF, etc. using vector graphics and embedded fonts.
I'd sort of like to see 'return' explained earlier, rather than used without explanation in the IO monad example. Also it's weird to hear that a monad is a design pattern, and then hear about the monad deciding things; that implies something more concrete than just a design pattern. It's only vaguely clear that "the monad" in that sense is the specific choice of bind/return functions (if that's even correct!). But while it's a bit rough around the edges, I can see this becoming a really good explanation. It explains how the goals of monads relate the implementation, which seems to be the tricky part, in a way that makes sense to me.
> A nice simplification of would be to use the current CPU number as your ID.
I don't think that works unfortunately. The thread could be rescheduled on a different CPU in the middle of the read-side critical section. When the critical section is exited, it will decrement a different counter. Scan() will wait until every counter is zero, but this will never happen unless another critical section is also rescheduled in the reverse order.
Indeed! I think I missed that in the original algorithm it doesn't wait for all slots to be zero, just that each slot go to zero. In that way it is just like waiting for each reader to go through a period of quiescence. This is a lot like the the version of rcu where the writer shuttles itself across cpus to use syscalls returns as a proxy for knowing that a particular cpu is not in any read side critical sections.
If there were a nice way to swap out the counters then summing would work, unfortunately that introduces an even bigger race :-(