3 ms·
Thanks for the link on sorting -- that looks really interesting! I think it's fair to say that the expression is no slower than the lookup table. Even if miss
by chubot 10y ago
Thanks for the link on sorting -- that looks really interesting!
I think it's fair to say that the expression is no slower than the lookup table. Even if missing the cache is rare, the penalty is large, so the average case will be significantly worse.
I freely admit the problem is contrived, but I think most people would agree it is actually an optimization! If you really want to nitpick, you might want to count the "opportunity cost" of some other 221 bytes not being in L1 cache.
- nightcracker 10y agoI haven't read about the rest of your problem much, but I usually think in terms of _cache pressure_. A lookup table can be very fast, but adds to the cache pressure. A large implementation with many special smart cases can also be very fast, but also adds to the cache pressure (instructions also need to be loaded from memory). Another thing I don't believe you mention is that not every n-instruction solution is equal (even if we only use single cycle instructions as possibilities). This is because of instruction-level parallelism. (a _ b) _ (c _ d) only takes two cycles to evaluate on a modern CPU. a _ (b _ (c _ d)) takes three.
- smcl 10y agoWhat are the underscore operators here? I'm curious, this may be an established convention but I have not seen it before
- stygiansonic 10y agoI presume they are placeholders to represent any binary operator, i.e. +, -, etc. The operator should be the same in all the placeholders or have the same precedence for the two expressions to be equivalent.
- deleted 10y ago[deleted]
- nightcracker 10y agoThey are just arbitrary placeholders for any operator.