25 ms·
What’s wrong with a simple loop (like the one near the top)? Why does it have to branchless? Wouldn’t the IO take longer than missed branches/pipeline flushes?
by colejohnson66 5y ago
What’s wrong with a simple loop (like the one near the top)? Why does it have to branchless? Wouldn’t the IO take longer than missed branches/pipeline flushes?
Not to mention that the fixed version now has branches as well…
- MauranKilom 5y agoThe irony is that a single log computation is going to take longer than the loop. (No idea if implementing a log approximation involves loops either.)
- deleted 5y ago[deleted]
- kortex 5y agoWaiting for someone to post some fast-inverse-sqrt-esque hack to compute the logarithm. Although in Java that's probably not likely to be faster. I wonder how fast it'd be to convert to string and count digits.
- Gibbon1 5y ago> I wonder how fast it'd be to convert to string and count digits. When you convert the number to a string you're really transforming it to a decimal format. Which is the domain where you should be solving the problem. Otherwise you're doing some sort transformation in the binary domain and then hopping to pull the answer out of a hat when you do the final convertion to decimal.
- bottled_poe 5y agoSounds like textbook example of when theory is misaligned with reality.
- slavik81 5y agohttps://code.woboq.org/userspace/glibc/sysdeps/ieee754/dbl-64/e_log.c.html https://code.woboq.org/userspace/glibc/sysdeps/ieee754/dbl-6... I don't see any loops, but there are a number of branches. The code could probably be generalized using loops to support arbitrary precision, but I think any optimized implementation for a specific precision will have unrolled them.
- tzs 5y agoMany architectures include a logarithm instruction. Does Java use that if available? Would it make a difference?
- usr1106 5y agoMany architectures? What would they be? Regardless whether they contain a logarithm instruction or not, how may architectures are there these days. Outside of truly embedded computing I can only come up with 2: Intel and ARM. Counting POWER and RISCV is probably a bit of a stretch already.
- tzs 5y agox86 has two logarithm instructions, FYL2X and FYL2XP1. FYL2X takes two arguments, Y and X, and computes Y log2(X). FYL2XP1 takes two arguments, Y and X, and computes Y log2(X+1). As you note, x86 and ARM are by far the most used, and I'd guess that when it comes to Java you are more likely to be running on x86 than ARM, so I figured it was arguable to say "many" when the only one I was sure had a logarithm instruction was x86.
- colejohnson66 5y agoThose x86 instructions are “legacy floating point” instructions. As in, the x87 FPU. Benchmarks I’ve seen seem to indicate that the x87 “coprocessor” is slow compared to the SSE/AVX FPUs, and only exists for backwards compatibility. I don’t think SSE/AVX has a logarithm instruction, sadly, but there are intrinsics for them: `_mm256_log_pd` for example. Considering that intrinsic generates a “sequence” instead of a single instruction, I’d be curious how it compares to x87.
- xxpor 5y agothe original version had branches too, in fact a majority of the lines had them! ? is just shorthand for if.
- enedil 5y agoThis isn't true, this form of conditionals can be compiled into cmov type of instructions, which is faster than regular jump if condition.
- ncann 5y agoIf the if/else is simple the compiler should be able to optimize that anyway.
- dataflow 5y ago> This isn't true, this form of conditionals can be compiled into cmov type of instructions, which is faster than regular jump if condition. IIRC cmov is actually quite slow. It's just faster than an unpredictable branch. Most branches have predictability so you generally don't want a cmov. Speaking of which, a couple questions regarding this for anyone who might know: 1. Can you disable cmov on x64 on any compiler? How? 2. Why is cmov so slow? Does it kill register renaming or something like that?
- dgrunwald 5y agocmov itself isn't slow, it has a latency of 2 cycles on Intel; and only 1 cycle on AMD (same speed as an add). However, cmov has to wait until all three inputs (condition flag, old value of target register, value of source register) are available, even though one of those inputs ends up going unused. A correctly predicted branch allows the subsequent computation (using of the result of the ?: operator) to start speculatively after waiting only for the relevant input value, without having to wait for the condition or the value on the unused branch. This could sometimes save hundreds of cycles if an unused input is slow due to a cache miss.
- 5y ago
- rkagerer 5y agoNot sure why some programmers these days have aversion to simple loops and other boring - but readable - code. Instead we have overused lambdas and other tricks that started out clever but become a nightmare when wielded without prudence. In this article, the author even points out why not to use his code: Note that this started out as a challenge to avoid loops and excessive branching. After ironing out all corner cases the code is even less readable than the original version. Personally I would not copy this snippet into production code.
- chousuke 5y agoVery often processes are naturally modelled as a series of transformations. In those cases, writing manual loops is tedious, error-prone, harder to understand, less composable and potentially less efficient (depending on language and available tools) than using some combination of map, filter and reduce.
- xelxebar 5y agoI can't comment on the social phenomenon here, but there is indeed a decent technical argument for avoiding for loops when possible. In a nutshell, it's kind of like "prinicple of least priviledge" applied to loops. Maps are weaker than Folds which are weaker than For loops, meaning that the stronger ones can implement the weaker ones but not vice-versa. So it makes sense to choose the weakest version. More specifically, maps can be trivially parallelized; same for folds, but to a lesser degree, if the reducing operation is associative; and for-loops are hard. In a way, the APL/J/K family takes this idea and explores it in fine detail. IMHO, for loops are "boring and readable" but only in isolation; when you look at the system as a whole lots of for loops make reasoning about the global behaviour of your code a lot harder for the simple reasone that for-loops are too "strong", giving them unweildy algebraic properties.
- qayxc 5y agoWhile these are all valid and well thought out arguments, in this particular example, a whole class of problems and bugs were introduced specifically by avoiding simple loops. Not to mention the performance implications. Parallelisation, composability and system thinking are sometimes overkill and lead to overengineering.
- nn3 5y agoBesides log()'s implementation is certainly not branch-less. It's the ostrich approach: if you don't see the branches they don't matter.
- xfer 5y agoThe real question is why is it a bug to report 1 mB instead of 999.9 kB for human readable output? It seems like a nice excursion to FP related pitfalls, but i don't think this is a problem to get entangled in that.
- Groxx 5y agoBecause it doesn't print 999.9 kB or 1 mB. It prints 1000.0 kB.
- xfer 5y agoI still wouldn't consider it a bug since we are throwing lots of lsbs anyways. It matters even less when we are talking about Peta/Exa bytes.
- cellularmitosis 5y agoI guarantee a design team would take one look at 1000.0kB and kick it back as a bug
- kruczek 5y agoExactly. As the article itself mentions: > Granted it’s not very readable and log / pow probably makes it less efficient So, the "improved" solution is both less readable and probably less efficient... where is the improvement then?
- ceronman 5y agoSimplicity FTW. The simple loop version is very easy to understand. It's probably really fast, as it's just a loop over seven items. And more importantly it's more correct. It doesn't use floating point arithmetic, so you don't have to worry about precision issues. The logarithmic approach is harder to reason about, prone to bugs (as proven by this post). I'm baffled at the fact that tons of people considered it a more elegant solution! It's completely the opposite!
- sixothree 5y agoIf it were me in my programming language, I would just use Humanizr and be freaking done with it.