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

91–100 of 144 posts

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

#91

Post by auto »

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 loosen your adherence to that last idea a bit, where a lookup table can change slightly over time, you can get a ton of mileage out of a comparatively small amount of memory compared to wasting cycles every frame.

As for the right tool for the job, I've read tons of dev logs and research papers over the years about moving work to the GPU, but this last few months stint of ripping my game inside out has really made me see the light. It's not just lookup tables built at compile or early runtime, but lookup tables modified slightly over time, and sent to the GPU as textures and used there.

Follow this train of thought long enough, and now we're just calling memory writes and reads "lookup tables" when they aren't really that anymore, but whos to say where the barrier really lies?

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

#92

Post by RetroTechie »

ruined wrote: post #58
datameta wrote: post #44

Earlier quoted context omitted.

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?

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.

> hashes by definition are not reversible.

Sure they are. You could generate every possible input, compute hash & compare with a given one.

Ok it might take infinite amount of compute (time/energy). But that's just a technicality, right?

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

#93

Post by benchloftbrunch »

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 other problem is that (if we take literally the absurd proposal of computing "every possible block" up front) you're not actually saving any space by doing this, since your "pointers" would be the same size as the blocks they point to.

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

#94

Post by dagw »

RetroTechie wrote: post #92
ruined wrote: post #58

Earlier quoted context omitted.

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.

> hashes by definition are not reversible. Sure they are. You could generate every possible input, compute hash & compare with a given one. Ok it might take infinite amount of compute (time/energy). But that's just a technicality, right?

Sure they are. You could generate every possible input

Depends entirely on what you mean by reversible. For every hash value, there are an infinite number of inputs that give that value. So while it is certainly possible to find some input that hashes to a given value, you cannot know which input I originally hashed to get that that value.

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

#95

Post by senfiaj »

I always thought that the "reverse" relationship between the time and the space requirements is explained by the simple fact that when you have a set of algorithms with certain time and space requirements and you constrain one of these parameters, the other parameter will not be necessarily (in practice oftentimes not) the most optimal. But it doesn't necessarily mean that the faster algorithm will require less memory or vice versa.

This "reverse" relationship works with other parameters. Such as in sorting algorithms, where besides time and space requirements you have stability requirement. If you constrain the sorting algorithms by stability, you won't have any advantage (will likely to have some disadvantage) in performance over non constrained algorithms. And wee see that the known stable sorting algorithms are either slower or require more memory. Nobody has yet invented a stable sorting algorithm that has comparable performance (both time and space) to non stable sorting algorithms. That's it.

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

#96

Post by withinboredom »

Almondsetat wrote: post #12
LPisGood wrote: post #9

Earlier quoted context omitted.

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.

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

This is pretty easy to refute:

> If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.[sic]

This is clearly refuted by all software running today. Programs (especially games) clearly use more memory than there are instructions in the program.

> If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).

Memory bombs use an incredible amount of memory and do it incredibly quickly.

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

#97

Post by benchloftbrunch »

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…

As I understand it, this is the essential insight behind dynamic programming algorithms; the whole idea is to exploit the redundancies in a recursive task by memoizing the partial results of lower order stages.

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

#98

Post by hinkley »

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.

The Camel book was written when Moore’s Law was trucking along. These days you can’t buy much more time but you used to be able to just fine. Now it’s horizontal scaling. Which is still more time.

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

#99

Post by RetroTechie »

handsclean wrote: post #69
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.

https://conwaylife.com/wiki/HashLife is an algorithm for doing basically this in Conway’s Game of Life, which is Turing complete. I remember my first impression being complete confusion: here’s a tick-by-tick simulation too varied and complex to encapsulate in a formula, and you’re telling me I can just skip way into its future?

If I read that page correctly, it does this for areas with empty space between them?

Makes sense. Say you have a pattern (surrounded by empty space) that 'flickers': A-B-A-B-A... etc. Then as long as nothing intrudes, nth generation is the same pattern as in n+1000,000th generation. Similar for patterns that do a 3-cycle, 4-cycle etc.

All you'd need is a) a way to detect repeating patterns, and b) do some kind of collision detection between areas/patterns (there's a thing called 'lightspeed' in Life, that helps).

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

#100

Post by schmorptron »

As an aside, I really enjoy a lot of the quanta magazine articles! They manage to write articles that both appeal to compsci people as well as interested "outsiders". The birds-eye view and informal how and why they pack into their explanation style often gives me new perspectives and things to think about!
Post reply on HN