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

101–110 of 144 posts

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

#101

Post by ThomasBHickey »

jodrellblank wrote: post #89
deadfoxygrandpa wrote: post #65

Earlier quoted context omitted.

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: 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 would…

"At some point" I do realise it. What I don't have is an intuitive feel for why a number can be three digits 000 to 999 and each place has ten choices, but it's not 10 x 3 possibles. I tried to ask ChatGPT to give me an intuition for it, but all it does is go into an explanation of combinations. I know it's 10 x 10 x 10 meaning 10^3 I don't need that explanation again, what I'm looking for is an intuition for why it…

Try starting with a 2x2, then 3x3, etc. image and manually list all the possibilities.

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

#102

Post by ChrisMarshallNY »

auto wrote: post #91
ChrisMarshallNY wrote: post #81

Interesting. It's one of those things that I’ve always “just assumed,” without thinking about it. I did a lot of raster graphics programming, in my career, and graphics work makes heavy use of lookup tables. Yesterday, I posted a rather simple tool I wrote[0]: a server that “frontloads” a set of polygons into a database, and then uses them, at query time. It’s fairly fast (but I’m sure it could be a lot faster). I wr…

I'm in the depths of optimization on a game right now, and it's interesting how the gains I'm making currently all seem to be a matter of scaling the concept of lookup tables, and using the right tool for the job. What I mean is that traditionally I think peoples' ideas of lookup tables are things like statically baked arrays setup at compile time, or even first thing at runtime, and they never change. But if you loo…

Without getting too much into detail (because the people I worked for were really paranoid, and I don't want to give them agita), we used to build lookup tables "on the fly," sometimes, deep inside iterators.

For example, each block of pixels might have some calculated characteristics that were accessed by a hash into a LUT, but the characteristics would change, as we went through the image.

We'd do a "triage" run, where we'd build the LUT, then a "detailed" run, where we'd apply the LUT to the pixels.

It could get pretty hairy.

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

#103

Post by const_cast »

immibis wrote: post #75
xlii wrote: post #68

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

This can work both ways. If the program needs more memory than the computer has, it can't run until you buy more. But if it takes twice as long, at least it runs at all.

Modern computers have so much memory it feels like it doesn't matter. Spending that memory on arrays for algorithms or things like a Garbage Collector just make sense. And, extra memory is worthless. You WANT the summation of all your programs to use all your memory. The processor, on the other hand, can context switch and do everything in it's power to make sure it stays busy.

The CPU is like an engine and memory is your gas tank. Idling the engine is bad, but leaving gas in the tank doesn't hurt, but it doesn't help either. I'm not gonna get to my destination faster because I have a full tank.

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

#104

Post by RetroTechie »

hn_acc1 wrote: post #14
LPisGood wrote: post #4

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.

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 replac…

There's many algorithms with a space vs time tradeoff. But what works best, depends a lot on the time/energy cost of re-computing something, vs the storage/bandwidth cost of caching results.

Expensive calculation, cheap storage → caching results helps.

Limited bandwidth / 'expensive' storage, simple calculation (see: today's hyper-fast CPU+L1 cache combo's) → better to re-compute some things on the fly as needed.

I suspect there's a lot of existing software (components) out there designed along the "save CPU cycles, burn storage" path, where in modern reality a "save storage, CPU cycles are cheap" would be more effective. CPU speeds have grown way way faster than main memory bandwidth (or even size?) over the last decades.

For a datacenter, supercomputer, embedded system, PC or some end-user's phone, the metrics will be different. But same principle applies.

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

#105

Post by ziofill »

awanderingmind wrote: post #70
ziofill wrote: post #67

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?

You mean something like this https://en.wikipedia.org/wiki/Bremermann%27s_limit or this https://en.wikipedia.org/wiki/Quantum_speed_limit ?

Oh wait, I just realized what I said was probably very stupid: I was thinking of some computational complexity theorem that links memory and runtime complexity classes in the same way that the "speed of light" sets an ultimate bound on the relation between actual space and actual time.

But the speed of light is the maximum space in the smallest time, which computationally would correspond to filling the largest amount of memory in the shortest time :facepalm: (and thanks for the links!)

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

#106

Post by frollogaston »

immibis wrote: post #76
frollogaston wrote: post #54

Earlier quoted context omitted.

You can add floors though. Some datacenters are 8 stories with cross-floor network fabrics.

When you get to, say, 100000 stories, you can't build more stories. At this point your computer costs more than the Earth's GDP for a century, so talking about theoretical scaling laws is irrelevant. Eventually you run out of the sun's power output so you build a Dyson sphere and eventually use all of that power, anyway.

Oh right, so the height is practically a constant. Square root for sure then.

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

#107

Post by simpaticoder »

alkyon wrote: post #82

It's kind of insulting to the reader that they explain P complexity class without using the word polynomial ("all problems that can be solved in a reasonable amount of time")

Be generous - it saves a lot of time. Once you say "polynomial" readers will think, "like, ANY polynomial, even like n^100?!" and you'll have to explain, yes, but that's STILL better than exponential, etc. They avoided all of that

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

#108

Post by ww520 »

valenterry wrote: post #40
ww520 wrote: post #38

Earlier quoted context omitted.

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

Can use cryptographic hashing.

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

#109

Post by amelius »

JohnKemeny wrote: post #88
amelius wrote: post #85

> Williams’ proof established a mathematical procedure for transforming any algorithm — no matter what it does — into a form that uses much less space. Ok, but space is cheap, and we usually want to trade processing time for space. I.e., the opposite.

Ryan made a dent (a tiny dent) in one of the most important open problems in mathematics. He's not trying to please programmers.

But what makes an open problem important? ;)

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

#110

Post by mystified5016 »

danwills wrote: post #79
jodrellblank wrote: post #47

Earlier quoted context omitted.

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…

Yeah I had a similar thought back in the 90s and made a program to iterate through all possible images at a fairly low res, I left it running while I was at school and got home after many hours to find it had hardly got past the first row of pixels! This was a huge eye-opener about how big a possibility-space digital images really exist in!

I has the same idea when I first learned about programming as a teenager. I wonder how many young programmers have had this exact same train of thought?
Post reply on HN