6 ms·

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

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.

chowells 1y ago
Oh, that's not a problem. Just cache the retrieval lookups too.
- michaelhoney 1y ago
  it's pointers all the way down
  - drob518 1y ago
    Just add one more level of indirection, I always say.
    - EGreg 1y 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.
crmd 1y 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 1y 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!
- ww520 1y 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 1y ago
    Except that there are collisions...
    - datameta 1y 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?
      - ruined 1y 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.
        RetroTechie 1y ago
        > 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?
mncharity 1y ago
> 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 1y ago
  Community scale cache, sounds like a library (the bricks and mortar kind)
EGreg 1y 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
- walterbell 1y ago
  > 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?
  - EGreg 1y ago
    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?
jsnider3 1y 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.
handsclean 1y ago
https://conwaylife.com/wiki/HashLife 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?
- RetroTechie 1y ago
  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).
  - handsclean 1y ago
    I don’t fully understand the algorithm, but no, to my understanding it’s much more general than that. In each tick a cell’s state is solely determined by its immediate neighbors, which means the simulation has a “speed of light” of 1 cell/second: to look N ticks into the future, you need only consider cells within N cells of the area you’re computing, no matter what’s outside that. So, for example, if you want to skip a 10x10 area 100 ticks into the future, you consider a 210x210 area centered on your 10x10, compute it once, then in the future use that 210x210 area as a lookup key for the 10x10 100 ticks into the future. I think HashLife is also somehow doing this on multiple scales at once, and some other tricks.

chowells 1y ago

Oh, that's not a problem. Just cache the retrieval lookups too.

michaelhoney 1y ago
it's pointers all the way down
- drob518 1y ago
  Just add one more level of indirection, I always say.
  - EGreg 1y 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.

crmd 1y 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 1y 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!
ww520 1y 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 1y ago
  Except that there are collisions...
  - datameta 1y 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?
    - ruined 1y 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.
      - RetroTechie 1y ago
        > 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?

mncharity 1y ago

> 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 1y ago
Community scale cache, sounds like a library (the bricks and mortar kind)

EGreg 1y 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

walterbell 1y ago
> 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?
- EGreg 1y ago
  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?

jsnider3 1y 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.

handsclean 1y ago

https://conwaylife.com/wiki/HashLife 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?

RetroTechie 1y ago
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).
- handsclean 1y ago
  I don’t fully understand the algorithm, but no, to my understanding it’s much more general than that. In each tick a cell’s state is solely determined by its immediate neighbors, which means the simulation has a “speed of light” of 1 cell/second: to look N ticks into the future, you need only consider cells within N cells of the area you’re computing, no matter what’s outside that. So, for example, if you want to skip a 10x10 area 100 ticks into the future, you consider a 210x210 area centered on your 10x10, compute it once, then in the future use that 210x210 area as a lookup key for the 10x10 100 ticks into the future. I think HashLife is also somehow doing this on multiple scales at once, and some other tricks.