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

111–120 of 144 posts

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

#111

Post by lesuorac »

benchloftbrunch wrote: post #93
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 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.

If you don't do _actually_ every single block then you have Huffman Coding [1].

I imagine if you have a good idea of the data incoming you could probably do a similar encoding scheme where you use 7 bits to point to a ~512 bit blob and the 8th bit means the next 512 couldn't be compressed.

[1]: https://en.wikipedia.org/wiki/Huffman_coding

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

#112

Post by anonymars »

ww520 wrote: post #108
valenterry wrote: post #40

Earlier quoted context omitted.

Except that there are collisions...

Can use cryptographic hashing.

How does that get around the pigeonhole principle?

I think you'd have to compare the data value before purging, and you can only do the deduplication (purge) if the block is actually the same, otherwise you have to keep the block (you can't replace it with the hash because the hash link in the pool points to different data)

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

#113

Post by Nevermark »

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 to address all possible 4098 byte blocks, you need a 4098 byte address. I suppose we would expect the actual number of blocks computed and reused to be a sparse subset.

Alternately, have you considered 8 byte blocks?

If your block pointers are 8-byte addresses, you don't need to count on block sparsity, in fact, you don't even need to have the actual blocks.

A pointer type, that implements self-read and writes, with null allocations and deletes, is easy to implement incredibly efficiently in any decent type system. A true zero-cost abstraction, if I have ever seen one!

(On a more serious note, a memory heap and CPU that cooperated to interpret pointers with the top bit set, as a 63-bit linear-access/write self-storage "pointer", is an interesting thought.

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

#115

Post by vlowther »

mpoteat wrote: post #35
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.)

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)

Just need to make sure all your computation is done in a volume with infinite surface area and zero volume. Encoding problem solved. Now then, how hyperbolic can we make the geometry of spacetime before things get too weird?

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

#116

Post by EGreg »

walterbell wrote: post #77
EGreg wrote: post #41

Earlier quoted context omitted.

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

> Using an LLM and caching eg FAQs can save a lot of token credits Do LLM providers use caches for FAQs, without changing the number of tokens billed to customer?

No, why would they. You are supposed to maintain that cache.

What I really want to know is about caching the large prefixes for prompts. Do they let you manage this somehow? What about llama and deepseek?

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

#117

Post by golly_ned »

catoc wrote: post #61
golly_ned wrote: post #57

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

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.

I wonder how the researchers who supplied the tree evaluation algorithm felt when Williams supplied his proof. Dismay at having not kept their result under wraps for longer so they could claim credit for such an advance themselves? I hope not.

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

#118

Post by LPisGood »

frollogaston wrote: post #106
immibis wrote: post #76

Earlier quoted context omitted.

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.

All algorithms are O(1) in this case

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

#119

Post by godelski »

woolion wrote: post #73

It's unfortunate that Quanta links are so popular, when they include so much pseudo-poetic fluff around the mathematics. Below there's an entire thread to dismiss a misconception introduced by the quanta article. "I think it is very intuitive that more space beats the pants off of more time." (poster is absolutely right) The The article say "Until now, the only known algorithms for accomplishing certain tasks require…

I think they used to be better but really have made a blatant turn. I really thought that wormhole fiasco would have killed them. To go 4 whole months before putting the editor's note is beyond egregious[0]. Mistakes happen, but 4 months kills all credibility. You have to act fast on those things! There were big names raising serious concerns on day 1 and it really shows they didn't do due diligence to get outside verification before running a piece that they knew would be really popular.

All this accomplishes is discrediting science. Trading personal gains for eroding the very thing that they make their money off of. This is a major part of why Americans (and people) have such high distrust for science. News outlets, and in particular science focused news outlets, constantly spew inaccurate information. It really should be no wonder that so many people are confused about so many scientific topics, as unless they actually take the years it takes to become an expert in a field, they are going to have a difficult time distinguishing fact from fiction. And why shouldn't the average person expect to trust a source like Quanta? They're "full of experts", right? smh

[0] This is the earliest archive I see with the note. Press back one day and it should not be there. Article was published on Nov 30 2022, along with a youtube video https://web.archive.org/web/20230329191417/https://www.quant...

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

#120

Post by godelski »

simpaticoder wrote: post #107
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

Quanta targets people who are above average. So I don't think it is too much for them to give a sentence or two stating that. Or even a little graphic could do wonders. I don't think it would take much time or effort to make a graphic like the one on wikipedia[0] and just throw in some equations within the ring. You can easily simplify too, by removing NL and merging EXP. Hell, look at the graphics here[1]. That's much more work.

I don't think Quanta should be afraid of showing math to people. That's really their whole purpose. Even if I think they've made some egregious mistakes that make them untrustable...[2]

[0] https://en.wikipedia.org/wiki/PSPACE#/media/File:Complexity_...

[1] https://www.quantamagazine.org/june-huh-high-school-dropout-...

[2] https://news.ycombinator.com/item?id=44067043

Post reply on HN