Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

For algorithms, a little memory outweighs a lot of time

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 144 posts

Re: For algorithms, a little memory outweighs a lot of time

#31

Post by LPisGood »

LegionMammal978 wrote: post #28
frollogaston wrote: post #23

Earlier quoted context omitted.

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.

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.)

Multitape TMs are pretty well studied

Re: For algorithms, a little memory outweighs a lot of time

#33

Post by jvanderbot »

frollogaston wrote: post #30
cperciva wrote: post #25

Earlier quoted context omitted.

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.)

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.

Spatial position has nothing (ok only a little) to do with topology of connections.

Re: For algorithms, a little memory outweighs a lot of time

#35

Post by mpoteat »

cperciva wrote: post #25
frollogaston wrote: post #23

Earlier quoted context omitted.

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.

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.)

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)

Re: For algorithms, a little memory outweighs a lot of time

#36

Post by crmd »

whatever1 wrote: post #16

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.

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.

Re: For algorithms, a little memory outweighs a lot of time

#37

Post by mncharity »

whatever1 wrote: post #16

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.

> 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.

Re: For algorithms, a little memory outweighs a lot of time

#38

Post by ww520 »

crmd wrote: post #36
whatever1 wrote: post #16

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.

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.

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.

Re: For algorithms, a little memory outweighs a lot of time

#40

Post by valenterry »

ww520 wrote: post #38
crmd wrote: post #36

Earlier quoted context omitted.

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.

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.

Except that there are collisions...
Post reply on HN