From the „Camel Book”, one of my favorite programming books (not because it was enlightening, but because it was entertaining); on the Perl philosophy:
“If you’re running out of memory, you can buy more. But if you’re running out of time, you’re screwed.”
ziofill · 4m ago
At the cost of sounding ridiculous: can there be a notion of "speed of light" in the theory of computation, determining the ultimate limit of memory (space) vs runtime?
whatever1 · 9h ago
Lookup tables with precalculated things for the win!
In fact I don’t think we would need processors anymore if we were centrally storing all of the operations ever done in our processors.
Now fast retrieval is another problem for another thread.
crmd · 6h ago
Reminds me of when I started working on storage systems as a young man and once suggested pre-computing every 4KB block once and just using pointers to the correct block as data is written, until someone pointed out that the number of unique 4KB blocks (2^32768) far exceeds the number of atoms in the universe.
manwe150 · 4h ago
It seems like you weren’t really that far off from implementing it, you just need a 4 KB pointer to point to the right block. And in fact, that is what all storage systems do!
jodrellblank · 4h ago
Reminds me of when I imagined brute-forcing every possible small picture as simply 256 shades of gray for each pixel x (640 x 480 = 307200 pixels) = 78 million possible pictures.
Actually I don't have any intuition for why that's wrong, except that if we catenate the rows into one long row then the picture can be considered as a number 307200 digits long in base 256, and then I see that it could represent 256^307200 possible different values. Which is a lot: https://www.wolframalpha.com/input?i=256%5E307200
deadfoxygrandpa · 16m ago
i think at some point you should have realized that there are obviously more than 78 million possible greyscale 640x480 pictures. theres a lot of intuitive examples but just think of this:
if there were only 78 million possible pictures, how could that portrait be so recongizably one specific person? wouldnt that mean that your entire picture space wouldnt even be able to fit a single portrait of everyone in Germany?
p1necone · 3h ago
78 million is how many pixels would be in 256 different pictures with 307200 pixels each. You're only counting each pixel once for each possible value, but you actually need to count each possible value on each pixel once per possible combinations of all of the other pixels.
The number of possible pictures is indeed 256^307200, which is an unfathomably larger number than 78 million. (256 possible values for the first pixel * 256 possible values for the second pixel * 256 possi...).
makmanalp · 5h ago
In some contexts, dictionary encoding (which is what you're suggesting, approximately) can actually work great. For example common values or null values (which is a common type of common value). It's just less efficient to try to do it with /every/ block. You have to make it "worth it", which is a factor of the frequency of occurrence of the value. Shorter values give you a worse compression ratio on one hand, but on the other hand it's often likelier that you'll find it in the data so it makes up for it, to a point.
There are other similar lightweight encoding schemes like RLE and delta and frame of reference encoding which all are good for different data distributions.
ww520 · 5h ago
The idea is not too far off. You could compute a hash on an existing data block. Store the hash and data block mapping. Now you can use the hash in anywhere that data block resides, i.e. any duplicate data blocks can use the same hash. That's how storage deduplication works in the nutshell.
valenterry · 5h ago
Except that there are collisions...
datameta · 5h ago
This might be completely naive but can a reversible time component be incorporated into distinguishing two hash calculations? Meaning when unpacked/extrapolated it is a unique signifier but when decomposed it folds back into the standard calculation - is this feasible?
shakna · 43m ago
Some hashes do have verification bits, that are used not just to verify intact hash, but one "identical" hash from another. However, they do tend to be slower hashes.
grumbelbart2 · 22m ago
Do you have an example? That just sounds like a hash that is a few bits longer.
shakna · 10m ago
Mostly use of GCM (Galois/Counter Mode). Usually you tag the key, but you can also tag the value to check verification of collisions instead.
But as I said, slow.
ruined · 49m ago
hashes by definition are not reversible. you could store a timestamp together with a hash, and/or you could include a timestamp in the digested content, but the timestamp can’t be part of the hash.
whatever1 · 2h ago
We know for a fact that when we disable the cache of the processors their performance plummets, so the question is how much of computation is brand new computation (never seen before)?
vlovich123 · 33m ago
While true, a small technical nitpick is that the cache also contains data that’s previously been loaded and reused, not just as a result of a previous computation (eg your executable program itself or a file being processed are examples)
nine_k · 2h ago
If some blocks are highly repetitive, this may make sense.
It's basically how deduplication works in ZFS. And that's why it only makes sense when you store a lot of repetitive data, e.g. VM images.
> if we were centrally storing all of the operations
Community-scale caching? That's basically what pre-compiled software distributions are. And one idea for addressing the programming language design balk "that would be a nice feature, but it's not known how to compile it efficiently, so you can't have it", is highly-parallel cloud compilation, paired with a community-scale compiler cache. You might not mind if something takes say a day to resolve, if the community only needs it run once per release.
20after4 · 3h ago
Community scale cache, sounds like a library (the bricks and mortar kind)
chowells · 8h ago
Oh, that's not a problem. Just cache the retrieval lookups too.
michaelhoney · 7h ago
it's pointers all the way down
drob518 · 5h ago
Just add one more level of indirection, I always say.
EGreg · 5h ago
But seriously… the solution is often to cache / shard to a halfway point — the LLM model weights for instance — and then store that to give you a nice approximation of the real problem space! That’s basically what many AI algorithms do, including MCTS and LLMs etc.
jsnider3 · 3h ago
> In fact I don’t think we would need processors anymore if we were centrally storing all of the operations ever done in our processors.
On my way to memoize your search history.
EGreg · 5h ago
You’re not wrong
Using an LLM and caching eg FAQs can save a lot of token credits
AI is basically solving a search problem and the models are just approximations of the data - like linear regression or fourier transforms.
The training is basically your precalculation. The key is that it precalculates a model with billions of parameters, not overfitting with an exact random set of answers hehe
LPisGood · 10h ago
I think it is very intuitive that more space beats the pants off of more time.
In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.
hn_acc1 · 9h ago
My intuition: the value of a cell can represent the result of multiple (many) time units used to compute something. If you cannot store enough intermediate results, you may end up needing to recalculate the same / similar results over and over - at least in some algorithms. So one cell can represent the results of hundreds of time units, and being able to store / load that one value to re-use it later can then replace those same hundreds of time units. In effect, space can be used for "time compression" (like a compressed file) when the time is used to compute similar values multiple times.
If intermediate results are entirely uncorrelated, with no overlap in the work at all, that would not hold - space will not help you. Edit: This kind of problem is very rare. Think of a cache with 0 percent hit rate - almost never happens.
And you can't really do it the other way around (at least not in current computing terms / concepts): you cannot use a single unit of time as a standin / proxy for hundreds of cells, since we don't quite have infinitely-broad SIMD architectures.
slt2021 · 9h ago
I think this theorem applies well for modern LLMs: large language model with pre-computed weights can be used to compute very complex algorithms that approximate human knowledge, that otherwise were impossible or would have required many orders more compute to calculate
frollogaston · 8h ago
Also, the O(1) random memory access assumption makes it easy to take memory for granted. Really it's something like O(n^(1/3)) when you're scaling the computer to the size of the problem, and you can see this in practice in datacenters.
I forget the name of the O(1) access model. Not UMA, something else.
cperciva · 7h ago
O(n^(1/2)) really, since data centers are 2 dimensional, not 3 dimensional.
(Quite aside from the practical "we build on the surface of the earth" consideration, heat dissipation considerations limit you to a 2 dimensional circuit in 3-space.)
mpoteat · 6h ago
More fundamentally O(n^(1/2)) due to the holographic principle which states that the maximal amount of information encodable in a given region of space scales wrt its surface area, rather than its volume.
(Even more aside to your practical heat dissipation constraint)
frollogaston · 45m ago
Hmm, I'll go with that
frollogaston · 6h ago
If you have rows of racks of machines, isn't that 3 dimensions? A machine can be on top of, behind, or next to another that it's directly connected to. And the components inside have their own non-uniform memory access.
Or if you're saying heat dissipation scales with surface area and is 2D, I don't know. Would think that water cooling makes it more about volume, but I'm not an expert on that.
manwe150 · 4h ago
That example would be two dimensions still in the limit computation, since you can keep building outwards (add buildings) but not scale upwards (add floors)
frollogaston · 2h ago
You can add floors though. Some datacenters are 8 stories with cross-floor network fabrics.
jvanderbot · 6h ago
Spatial position has nothing (ok only a little) to do with topology of connections.
LegionMammal978 · 7h ago
On the other hand, actual computers can work in parallel when you scale the hardware, something that the TM formulation doesn't cover. It can be interesting which algorithms work well with lots of computing power subject to data locality. (Brains being the classic example of this.)
LPisGood · 6h ago
Multitape TMs are pretty well studied
thatguysaguy · 10h ago
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
LPisGood · 9h ago
I think that since many people find it intuitive that P != NP, and PSPACE sits way on top of polynomial hierarchy that it is intuitive even if it’s unproven.
porphyra · 8h ago
There's not even a proof that P != EXPTIME haha
EDIT: I am a dumbass and misremembered.
doc_manhat · 8h ago
I think there is right? It's been a long time but I seem to remember it following from the time hierarchy theorem
LPisGood · 7h ago
I thought there was some simple proof of this, but all I can think of is time hierarchy theorem.
dragontamer · 9h ago
The article is about a new proof wherein P == PSPACE.
Something we all intuitively expected but someone finally figured out an obscure way to prove it.
--------
This is a really roundabout article that takes a meandering path to a total bombshell in the field of complexity theory. Sorry for spoiling but uhhh, you'd expect an article about P == PSPACE would get to the point faster....
LPisGood · 9h ago
This article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.
undefuser · 3h ago
I think it really depends on the task at hand, and not that intuitive. At some point accessing the memory might be slower than repeating the computation, especially when the storage is slow.
qbane · 9h ago
But you also spend time on updating cells, so it is not that intuitive.
LPisGood · 9h ago
I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes.
More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.
Almondsetat · 9h ago
If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.
If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).
No comments yet
delusional · 9h ago
This is obviously demonstrably true. A Turing running in O(n) time must halt. The one in O(n) space is free not to.
thaumasiotes · 8h ago
Almondsetat's proof seems more obvious. Given O(n) time, you can only use O(n) space, so you're comparing "O(n) space, any amount of time" with "O(n) space, O(n) time", and it turns out you get more resources the first way.
IvanK_net · 7h ago
I am confused. If a single-tape turing machine receives a digit N in binary, and is supposed to write N ones on the tape, on the right side of the digit N, it performs N steps.
If you expect N ones at the output, how can this machine be simulated in the space smaller than N?
This machine must decrement the digit N at the beginning of the tape, and move to the end of the tape to write "1", so it runs in time O(N^2), not O(N)? (as it takes N "trips" to the end of the tape, and each "trip" takes 1, 2, 3 .. N steps)
Since turing machines can not jump to any place on a tape in constant time (like computers can), does it have any impact on real computers?
cperciva · 7h ago
Multitape Turing machines are far more powerful (in terms of how fast they can run, not computability) than single-tape machines.
But to answer your question: "space" here refers to working space, excluding the input and output.
golly_ned · 1h ago
“ If the problem is solved next week, Williams will be kicking himself. Before he wrote the paper, he spent months trying and failing to extend his result”
What a strange, sad way to think about this. Academia is perverse.
catoc · 38m ago
Nothing necessarily perverse here. I don’t know Williams but don’t image him disliking the other guy or being unhappy with progress in general, but just being someone who truly challenged himself only to find him being trumped a week later; and kicking himself for that.
Either way, the week is not yet over, at least since the quanta article, so maybe no kicking will ensue.
https://arxiv.org/abs/2502.17779
“If you’re running out of memory, you can buy more. But if you’re running out of time, you’re screwed.”
In fact I don’t think we would need processors anymore if we were centrally storing all of the operations ever done in our processors.
Now fast retrieval is another problem for another thread.
Actually I don't have any intuition for why that's wrong, except that if we catenate the rows into one long row then the picture can be considered as a number 307200 digits long in base 256, and then I see that it could represent 256^307200 possible different values. Which is a lot: https://www.wolframalpha.com/input?i=256%5E307200
https://images.lsnglobal.com/ZFSJiK61WTql9okXV1N5XyGtCEc=/fi...
if there were only 78 million possible pictures, how could that portrait be so recongizably one specific person? wouldnt that mean that your entire picture space wouldnt even be able to fit a single portrait of everyone in Germany?
The number of possible pictures is indeed 256^307200, which is an unfathomably larger number than 78 million. (256 possible values for the first pixel * 256 possible values for the second pixel * 256 possi...).
There are other similar lightweight encoding schemes like RLE and delta and frame of reference encoding which all are good for different data distributions.
But as I said, slow.
It's basically how deduplication works in ZFS. And that's why it only makes sense when you store a lot of repetitive data, e.g. VM images.
https://github.com/philipl/pifs
Community-scale caching? That's basically what pre-compiled software distributions are. And one idea for addressing the programming language design balk "that would be a nice feature, but it's not known how to compile it efficiently, so you can't have it", is highly-parallel cloud compilation, paired with a community-scale compiler cache. You might not mind if something takes say a day to resolve, if the community only needs it run once per release.
On my way to memoize your search history.
Using an LLM and caching eg FAQs can save a lot of token credits
AI is basically solving a search problem and the models are just approximations of the data - like linear regression or fourier transforms.
The training is basically your precalculation. The key is that it precalculates a model with billions of parameters, not overfitting with an exact random set of answers hehe
In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.
If intermediate results are entirely uncorrelated, with no overlap in the work at all, that would not hold - space will not help you. Edit: This kind of problem is very rare. Think of a cache with 0 percent hit rate - almost never happens.
And you can't really do it the other way around (at least not in current computing terms / concepts): you cannot use a single unit of time as a standin / proxy for hundreds of cells, since we don't quite have infinitely-broad SIMD architectures.
I forget the name of the O(1) access model. Not UMA, something else.
(Quite aside from the practical "we build on the surface of the earth" consideration, heat dissipation considerations limit you to a 2 dimensional circuit in 3-space.)
(Even more aside to your practical heat dissipation constraint)
Or if you're saying heat dissipation scales with surface area and is 2D, I don't know. Would think that water cooling makes it more about volume, but I'm not an expert on that.
EDIT: I am a dumbass and misremembered.
Something we all intuitively expected but someone finally figured out an obscure way to prove it.
--------
This is a really roundabout article that takes a meandering path to a total bombshell in the field of complexity theory. Sorry for spoiling but uhhh, you'd expect an article about P == PSPACE would get to the point faster....
More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.
If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).
No comments yet
If you expect N ones at the output, how can this machine be simulated in the space smaller than N?
This machine must decrement the digit N at the beginning of the tape, and move to the end of the tape to write "1", so it runs in time O(N^2), not O(N)? (as it takes N "trips" to the end of the tape, and each "trip" takes 1, 2, 3 .. N steps)
Since turing machines can not jump to any place on a tape in constant time (like computers can), does it have any impact on real computers?
But to answer your question: "space" here refers to working space, excluding the input and output.
What a strange, sad way to think about this. Academia is perverse.
Either way, the week is not yet over, at least since the quanta article, so maybe no kicking will ensue.
And paper: https://people.csail.mit.edu/rrw/time-vs-space.pdf