Lockless algorithms for mere mortals

Posted Jul 29, 2020 23:47 UTC (Wed) by ras (subscriber, #33059)
In reply to: Lockless algorithms for mere mortals by NYKevin
Parent article: Lockless algorithms for mere mortals

> If you want to reuse the memory for something else, won't it have to be erased at some point? Or is the whole idea to minimize erasure, so that you only erase things that actually need to be erased?

As it turns out this has been explored, at least partially. Theoretically the destruction of information takes energy and heat has always been a problem in computers. (I don't understand the mechanism. Perhaps because information can't actually be destroyed it's turned into heat, which then has to be carted away.) In any case, one solution that was proposed was to make a memory cell using two capacitors rather than one. One is always charged, the other discharged, and changing value is just a transfer or charge from one to the other. I don't know that it every made it off the back of a napkin, mostly because the power lost by discharging the DRAM capacitors is the least of the power problems.

The more general solution has already been deployed, not by physicists or hardware engineers, but by us - the software people. It's log structured storage. From the perspective of the question you posed, the answer we developed is "don't do free()'s". Interestingly, as this conversation is about the connection between time and information, we use a technique that does not destroy information because there are places we have to roll back time in order to keep our data structures consistent.

Lockless algorithms for mere mortals

Posted Oct 13, 2020 15:28 UTC (Tue) by immibis (subscriber, #105511) [Link]

I'll try to give an intuitive explanation for why erasing data must cost energy. Premise: we know that the universe is reversible. If state A goes to state B, then state reverse(B) must go to state reverse(A).

Therefore you can't have states A and B which both go to C, because a universe in state reverse(C) wouldn't know whether to go to reverse(A) or reverse(B). Information cannot be deleted.

So how do computers delete information, then? Well, the universe is full of states we don't care about, so we just cheat and move the information to one of those. For example, writing 1 releases energy from a different point in the chip than writing 0, which causes a different vibration in the silicon lattice, which transfers to the plastic packaging, which causes an air molecule to bounce off the chip differently.

That means if there are 1 zillion different ways the air molecules would've bounced (if the chip was turned off), now there are 2 zillion, because all the bounces after 0 is written are different from all the bounces after 1 is written. Obviously air can bounce a lot of ways - but the problem is that all of the 1-zillion input states map to 1-zillion output states already. There's no way to get more output states than input states without giving the molecule more energy - which allows it to be in states it couldn't be in with its previous amount of energy. Therefore the chip must have transferred a bit of energy to the air molecule. There is no other way it could work.

All of this applies *on average*, by the way.

Or here's a different explanation: If you consider a computer that's known to be in 1 of 1000 states, and the air in the room that's in 1 of 1 zillion states, there are 1000 zillion states in total (the cartesian product). If the computer is in 1 of 500 states in the next timestep, there still must be 1000 zillion states for the computer+air system, because the universe is reversible. Therefore the air must be in 1 of 2 zillion states. This doesn't apply to reversible computers, because reversible computers *don't* decrease their number of states in any time step.