6 ms·
Haskell type inference is EXPTIME, O(2^p(n)), yet it works fine in practice. This reminds me of the quote by Rob Pike on algorithms completely: >>Rule 3. Fancy
by frankreyes 4y ago
Haskell type inference is EXPTIME, O(2^p(n)), yet it works fine in practice. This reminds me of the quote by Rob Pike on algorithms completely:
>>Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don’t get fancy.
https://en.m.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#cite_note-5 https://en.m.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_...
- Sesse__ 4y agoThat rule, while sensible at the time, has aged pretty poorly. n used to be small in the 70s, but now people have terabytes of data and run UNIX tools over them.
- taeric 4y agoSorta. What we consider a small N has also gotten surprisingly large.
- frankreyes 4y agoLatest epyc CPU have 768MB of L3 cache. You can run Linux entirely on L3 memory. https://www.amd.com/en/press-releases/2022-03-21-3rd-gen-amd-epyc-processors-amd-3d-v-cache-technology-deliver-outstanding https://www.amd.com/en/press-releases/2022-03-21-3rd-gen-amd...
- meatmanek 4y ago> You can run Linux entirely on L3 memory. Is that a theoretical possibility based on the fact that Linux can run in a memory footprint < 768MB, or has someone actually demonstrated it? Can you boot one of these processors without any RAM installed?
- frankreyes 4y agoIt's my wild unfounded guess, I guess ^_^ Any modern CPU needs RAM, specially to get things to cache, I don't think there's any way around it. What I was trying to say is that having a large L3 means that it never has to wait for RAM access, and that should be fast.
- Sesse__ 4y agoCoreboot sets up cache as RAM through memory mapping tricks, to have something a normal C compiler can work with. (DRAM needs to be trained and set up properly before you have any RAM; before that, you have only registers, which is pretty painful.)
- frankreyes 4y agoCPU cache have gotten larger. For example, Latest epyc CPU have 768MB of L3 cache. You can run Linux entirely on L3 memory... https://www.amd.com/en/press-releases/2022-03-21-3rd-gen-amd-epyc-processors-amd-3d-v-cache-technology-deliver-outstanding https://www.amd.com/en/press-releases/2022-03-21-3rd-gen-amd...
- SnowflakeOnIce 4y agoThis reasoning works okay until you have to deal with machine-generated inputs, at which point your app freezes when it gets sent down a quadratic or worse complexity path.
- frankreyes 4y agoOh yeah I've seen autogenerated source code ... It freezes my browser trying to syntax highlighting it. Raw works fine.