There might be an opportunity somewhere around this area to combine the versioning, continuous improvement, and dependency management of package repositories with the Q&A format of StackOverflow.
Something like "cherry pick this answer, with attribution, and notifications when flaws and/or improvements are found".
Maybe that's a terrible idea (there's definitely risk involved, and the potential to spread and create bad software), but equally I don't know why it would be significantly worse than unattributed code snippets and trends towards single-function libraries.
NodeJS did something a lot like this by having packages that are just short snippets, but half the ecosystem flipped out when someone messed up `leftpad`.
Sadly updates don't just remove bugs, but sometimes also add them. Silently adding a bug to previously working code is a lot more bad than silently fixing a bug you didn't know you had is good, so I wouldn't want to have a load of self-updating code snippets in my codebase.
This! If I had to choose between the two snippets I would have taken the loop based one without a second though, because of its simplicity.
The second snippet is what usually happens when people try to write "clever" code.
The loop by itself isn't entirely clear on what it's doing. Stuff like the direction of the > comparison and what to do vs. >= and the byteCount / magnitudes[i] at the end really do require you to pause & do mental analysis to check correctness. I think the real solution here is to define an integer log (ilog()?) function based on division and use that in the same manner as the log(). That way you only do do the analysis the first time you write that function, and after that you just call the function knowing that it's correct.
I was reading this and thought it sounded familiar. A few months ago I needed a human readable bytes format, ended up on that stack overflow article and, plot twist, copied the while loop one.
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…
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.
> 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.
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.
x86 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.
Those 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.
cmov 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.
I wonder if there's anyone on earth who needs nicely formatted human readable file sizes that's worried about the difference between one or two cpu cycle branching instructions?
There might be a few guys at FAANG who have a planet-scale use case for human readable file sizes. But surely "performance optimising" this is _purely_ code golf geekiness?
(Which is a perfectly valid reason to do it, but I'm gonna choose the most obvious to the next progerammer reading it version over one that 50% or 500% or 5000% fast in almost any use case I can think I'm like to need this... I mean, it's only looking for 6 prefixes "KMGTPE" a six line case statement would work for most people?)
Actually, I just realised. This is (probably a small part of) why "calculate all sizes" in Mac finder windows is so slow. I already mentioned Apple in FAANG, but I guess someone at Microsoft and people who work on Linux file brokers care too. And whoever maintains the -h flag codepaths in all the Unix-like utils that support it?
CMOV is slow because x86 processors will not speculate past a CMOV instruction. They do speculate past conditional jumps, so those are more performant.
Out-of-order just means it can rearrange the decoded uops in a way to keep the execution units at full capacity. So, if an instruction needs the ALU, but it’s busy, and the next one needs the AGU (address generation unit) and doesn’t depend on the results of the ALU one, it can “dispatch” the AGU one while the ALU one waits for the pipeline to move.
Speculative execution refers more towards the decoder/uop generation side of the processor (the “in-order” side). A normal “in-order” processor, upon encountering a conditional jump, would wait until the pipeline is finished to check if it should jump or not. It does it by inserting “bubbles” into the pipeline - essentially doing nothing but waiting.
Speculative execution (or branch prediction) would say, “I think the branch will be taken based on X, Y, Z,” and then keep the pipeline full in the process. If the prediction was right, congratulations! You just saved dozens of clock cycles that otherwise would’ve been wasted. If it was wrong, no worries. The pipeline is then flushed; all the speculated instructions’ results are tossed (before they’re “written back”). Then the processor resumes operation on the correct branch.
Speculative execution doesn’t necessitate an out-of-order architecture, and visa-versa. Just a pipelined one. It’s perfectly possible to have an out-of-order architecture that doesn’t speculate, or a speculative one that is completely “in-order”, but they work hand-in-hand, and it makes sense to have both if you have one.
Is it safe to say speculation is about what to do with instructions following conditionals, and OoO is about what to do with instructions following non-conditionals?
My understanding of out-of-order (and pipelined) CPUs is limited, but it’s interesting that CMOV isn’t interpreted as a “Jcc over MOV” by the decoder. That would allow using the branch predictor. Would it be too complex or does the microarchitecture not even allow it?
Both ?: and if-else have cases where they can be compiled into cmov type instructions and where they cannot. Given int max(int a, int b) { if (a > b) return a; else return b; }, a decent compiler for X86 will avoid conditional branches even though ?: wasn't used. Given int f(int x) { return x ? g() : h(); }, avoiding conditional branches is more costly than just using them, even though ?: was used.
Not 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.
I 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.
While 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.
Loops are easier to read. With functions like reduce you have to solve a puzzle every time to understand what the code is doing (this is also true for functional style of programming in general).
> 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 typical Javascript code reduce operation will not be parallelized. It actually can be slower than a loop because of overhead for creating and calling a function on every iteration.
> when you look at the system as a whole lots of for loops
A code with lot of loops is still more readable than a code with lots of nested reduces.
>Loops are easier to read. With functions like reduce you have to solve a puzzle every time to understand what the code is doing
I think that is a function of familiarity, if you use reduce a lot it will be as easy to read as a loop - perhaps easier because more compact - there is a downside to reading more lines for some people, at some point verbosity becomes its own source of illegibility (although any loop that can easily be turned into a reduce probably won't be excessively verbose anyway)
Of course all that is just on the personal level, you , by using and reading more code with reduce in it will stop finding reduce less easy to understand than loops - but the next programmer without lots of reduce experience will be in your same boat.
loops are harder to read. What does it do, map, reduce, send emails to grandma?
In JavaScript, the reduce callback is created once and called repeatedly. For loops are pretty much always the fastest possible way because they use mutable state. They are also a really good way of creating unreadable spaghetti that does things you don't want them to.
I'm not sure what you mean by nested reduces. Chained reduce functions are easy to follow
The point was that in map and reduce it's clear what's being done and what's being returned, especially in a typed language. Ideally you're also in an environment that doesn't allow for side effects, in which case, grandma gets no emails from map or reduce
It is not visible what is returned or what is input im case of chaining. Because return and input parameters are not directly visible and you have to read all previous calls to figure that out.
I disagree quite strongly, in that this is simply a function of familiarity. Reduce is no more or less readable than for (especially the C style for — imagine trying to work out what the three not-really-arguments represent!)
> So it makes sense to choose the weakest version.
Only if it's actually more readable. The principle of least privilege does not give you any benefit when talking about loop implementations.
> More specifically, maps can be trivially parallelized;
This argument is repeated time and time again but I've never actually seen it work. Maps that can be trivially parallelized aren't worthy to parallelize most of the time. In the rare case it's both trivial and worthy, it's because the map function (and therefore the loop body) are side-effect free, and for those rare cases you don't care too much about the slightly extra effort of extracting the loop body into a function.
> 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 reason that for-loops are too "strong"
Code is too strong in general. Reasoning about the global behavior of code is difficult if the code itself is complex. Nested maps and reduces will be equally difficult to comprehend. The fact that a map() function tells you that you're converting elements of lists does not save you from understanding what is that conversion doing and why.
Sometimes loops will be better for readability, sometimes it will be map/reduce. Saying that for loops always make it harder to reason about the code does not make too much sense in my opinion.
I agree with the no silver bullet thing - and written on another reply I don't even know if I agree with the example in the article.
> The fact that a map() function tells you that you're converting elements of lists does not save you from understanding what is that conversion doing and why.
It can actually, say you have a query that comes in, this calls a function that fetches records from the database, it's not a basic query, it has joins, perhaps a subquery, etc.
Then you have another function that transforms the results into whatever presentational format, decorates, wtv, those results, and it's also more than a few basic couple lines of logic.
And now you have a bug report come in, that not all expected results are being shown.
If you have
func does_query -> loop transforms
You have 3 possibilities, the problem is on the storage layer, the problem is on the query, the problem is on the loop.
You read the query, because the bug is subtle, it seems ok, so now you move to the loop. It's a bit complex but seems to be correct too. Now you start debugging what's happening.
If you have
func does_query -> func maps_results
You know it's either underlying storage or the query. Since the probability of the storage being broken is less plausible, you know it must be the query. In the end it's a synch problem with something else, and everything is right, but now you only spent time on reproducing the query and being sure that it works as expected.
I'm not against using for loops when what you need is an actual loop.
The thing is most of the times, previously, for loops where actually doing something for which there are concepts that express exactly what was being done - though not in all languages.
For instance, map - I know that it will return a new collection of exactly the same number of items the iterable being iterated has. When used correctly it shouldn't produce any side-effects outside the mapping of each element.
In some languages now you have for x in y which in my opinion is quite ok as well, but still to change the collection it has to mutate it, and it's not immediate what it will do.
If I see a reduce I know it will iterate again a definite number of times, and that it will return something else than the original iterable (usually), reducing a given collection into something else.
On the other hand forEach should tell me that we're only interested in side-effects.
When these things are used with their semantic context in mind, it becomes slightly easier to grasp immediately what is the scope of what they're doing.
On the other hand, with a for (especially the common, old school one) loop you really never know.
I also don't understand what is complex about the functional counterparts -
for (initialise_var, condition, post/pre action) can only be simpler in my mind due to familiarity as it can have a lot of small nuances that impact how the iteration goes - although to be honest, most of the times it isn't complex either - but does seem slightly more complex and with less contextual information about the intent behind the code.
For me, code with reduce is less readable than a loop. With loop everything is obvious, but with reduce you need to know what arguments in a callback mean (I don't remember), and then think how the data are transformed. It's an awful choice in my opinion. Good old loop is so much better.
def factorial(n):
result = 1
for i in range(2,n+1):
result *= i
return result
I mean in this case the name kinda makes it obvious anyway :)
If the operation is conceptually accumulating something over the whole collection and if it's idiomatic in the language I'm using - I will use reduce. Same with map-y and filter-y operations.
But if I have to do some mental gymnastics to make the operation fit reduce - for loop it is. Or generator expression in case of python.
I disagree entirely. In most imperative programming languages, you can shove any sort of logic inside a loop, more loops, more branches, creating new objects, its all fair game.
Fold and map in functional languages are often much more restrictive in a sense. For example, with lists, you reduce down a collection [a]->a to a single object, or produce another collection with a map [a]->[a]. So map and fold etc are much more restrictive. That's what makes it clearer.
It can definitively happen, but I think more times than not the others are more readable.
To be honest this seems to be a familiarity thing
> but with reduce you need to know what arguments in a callback mean
If I didn't know for it would be mind boggling what those 3 things, separated by semicolons, are doing It doesn't look like anything in the usual language(s) they're implemented. It's the same with switch.
The only thing both of them have, for and switch, and helps, is that languages that offer it and aren't FP usually use the same *C* form across all, whereas reduce's args and the callback args vary a bit more between languages, and specially between mutable and immutable langs.
I still prefer most of the time the functional specific counterparts.
congruence_classes m l = map (\x -> ((x ==) . (`mod` m)) l) [0..m-1]
than
def congruence_classes(m, l):
sets = []
for i in range(m):
sets += [[]]
for v in l:
sets[v % m] += [v]
return sets
For-in is very neat and nice but it still takes two loops and mutation to get there. Simple things are sometimes better as one-line maps. Provability is higher on functional maps too.
Same one-liner in (slightly uglier) Python:
def congruent_sets(m, l):
return list(map(lambda x: list(filter(lambda v: v % m == x, l)), range(m)))
The one liner is far less readable and under the hood it actually is worse: for each value in [0, m] you're iterating l and filtering it, so it's a O(n^2) code now instead of O(n). That mistake would be far easier to notice if you had written the exact same algorithm with loops: one would see a loop inside a loop and O(n^2) alarms should be ringing already.
Ironically, it's a great example of why readability is so much more important than conciseness and one liners.
I agree and despite beeing a fan (kind of a convert from OO) of FP I am often wondering about readability of FP code.
One idea I have is, that often FP code is not modularized and violates the SOLID principle in doing several things in one line.
there are seldom named subfunctions where the name describe the purpose of the functions- take lamdas as an example: I have to parse the lamda code to learn what it does.
Even simple filtering might be improved (kinda C#):
var e = l.Filter(e => e.StartsWith("Comment"));
vs.
var e = l.Filter(ElementIsAComment);
or even using an extension method:
var e = l.FindComments();
sorry I could not come up with a better example- I hope you get my point...
True, it is computationally worse, though it's O(nm) so applying m at compile time to form a practical use as I used it will turn it into to O(n) in practice.
But that much is immediately obvious since it's mapping a filter, that is, has a loop within a loop.
I did consider the second one to also take quadratic time though. I forgot that in python getting list elements by index is O(1) instead of O(n) which is what I'm personally used to with lists.
It's also true that you can replace the filter with
[ v | v <- l, v `mod` m == x ]
but that's not as much fun as
(x ==) . (`mod` m)
I just love how it looks and it doesn't personally seem any less clear to me, maybe a bit more verbose.
> Have you considered that maybe this is a sign you're too deep into using impractical programming languages?
“Languages that use ‘list’ for linked lists and have different names for other integer-indexable ordered collections” aren’t necessarily “impractical”.
> True, it is computationally worse, though it's O(nm) so applying m at compile time to form a practical use as I used it will turn it into to O(n) in practice.
Even applying it at compile time, it's still O(nm). You have to compute 'v mod m' for each possible value of v and m.
> But that much is immediately obvious since it's mapping a filter, that is, has a loop within a loop.
It's not immediately obvious because you have to parse the calls and see exactly where is the filter and the map.
retval = []
for x in lst:
if not filter_things(x):
continue
retval.append(do_some_things(x))
and
for x in lst:
filtered = []
for y in in another_list:
if filter_things(x, y):
filtered.append(y)
retval.append(do_some_things(x, filtered))
In the first case, you have to parse the parenthesis and arguments to see where exactly are the map and filter cals. In the second, you see a for with a second level of indentation.
> I just love how it looks and it doesn't personally seem any less clear to me, maybe a bit more verbose.
It doesn't seem any less clear to you because you're used to it. But think about the things you need to know apart from what a loop, map, filters and lambdas are:
- What is (x ==). Is it a function that returns whether the argument is equal to x?
- What is '.'. Function composition? Filter?
- Same thing with `mod` m. What are the backticks for?
Compare that with the amount of things you need to know with the Python code with for loops. For that complexity to pay off you need some benefits, and in this case you're only getting disadvantages.
That's the whole point of this discussion. Production code needs to work, have enough performance for its purpose and be maintainable, those are the metrics that matter. Being smart, beautiful or concise are completely secondary, and focusing on them will make for worse code, and it's exactly what happened in this toy example.
Yes, but that's the case with all the functional approaches proposed.
If Python were focused on functional programming it would have a utility function for this similar to itertools.groupby (but with indices in an array instead of keys in a dictionary).
> If Python were focused on functional programming it would have a utility function for this similar to itertools.groupby (but with indices in an array instead of keys in a dictionary).
itertools.groupby doesn’t return a dictionary, it returns an iterator of (key, (iterator that produces values)) tuples. It sounds, though, like you want something like:
from itertools import groupby
def categorize_into_list(source, _range, key):
first = lambda x: x[0]
sublist_dict = {
k: list(v[1] for v in vs)
for k, vs in groupby(sorted(((key(v), v) for v in source), key=first), first))
}
return [sublist_dict.get(i, []) for i in _range]
Then you could do this with something like:
def congruent_sets(m, l):
categorize_into_list(l, m, lambda v: v % m)
When used correctly it shouldn't produce any side-effects outside the mapping of each element.
But that's just a social convention. There's nothing stopping you from doing other things during your map or reduce.
In practice, the only difference between Map, Reduce and a For loop is that the first two return things. So depending on whether you want to end up with an array containing one item for each pass through the loop, "something else", or nothing, you'll use Map, Reduce or forEach.
You can still increment your global counters, launch the missiles or cause any side effects you like. "using it correctly" and not doing that is just a convention that you happen to prefer.
That is true (less so in FP languages though), but the for loop doesn't either - indeed I do prefer it most of the times, I think its a reasonable expectation to provide the most intention revealing constructs when possible, it's also easier to spot "code smells" when using those.
The exceptions I make is when there's significant speed concerns/gains, when what you're doing is an actual loop, when the readability by using a loop is improved.
(and I haven't read the article so not even sure I agree with the example there, this was more in general terms)
Very 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.
Yes, my code is not that complicated and I use languages that are rather high level (Python, Golang, JS with Vue) so I needed the index I think once when I had to remove an element from an array in JS and for some reason I was not using lodash.
But yes, there are of course cases where the index could be needed, I was merely commenting on the aversion part for generic developers.
> Not sure why some programmers these days have aversion to simple loops and other boring - but readable - code.
Like goto, basic loops are powerful, simple constructs that tell you nothing at all about what the code is doing. For…in loops in many languages are a little better, but map, reduce, or comprehensions are much more expressive as to what the code is doing, but mostly address common cases of for loops.
While loops are weakly expressive (about equal to for…in), but except where they are used as a way (in language without C-style for loops) but there is less often a convenient replacement.
The 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.
Simplicity 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!
seems that most comments here missed the end of the article , where he points to the "production ready" version of the solution, that is indeed very close to the original one, including a while loop.
> ..."production ready" version of the solution, that is indeed very close to the original one, including a while loop.
What's missing still is a comprehensive set of test cases to check against.
If such cases were spec'ed to go along with the original code, fthen at least one could have seen the applicability range and perhaps other people would have added some challenging corner cases (just as mentioned in the OP).
It is possible within the limits of available memory on the computer. Rather than the usual limit of a fixed number of bits.
I've ironically found that big integer libraries sometimes optimize math routines more than string conversion. This was quite annoying for me when I optimized the factorial function in Ruby, and found that generating the string was my bottleneck. I then optimized that as well. :-)
> Sebastian then reached out to me to straighten it out, which I did: I had not yet started at Oracle when that commit was merged, and I did not contribute that patch. Jokes on Oracle. Shortly after, an issue was filed and the code was removed.
Good thing it wasn't a range check function. I hear those are expensive.
Something about this comes off as amateurish. The obsession with minimization. Just use a switch statement. Now where is the bug going to hide? The solution doesn't need to generalize, there is only a small handful of different solutions. Just break them all out. It's more maintainable and readable and requires less thinking.
I don't know why you are being downvoted. The best solution here is for the author to admit using log was a bad idea and rewrite an entirely different version.
I must admit I smiled at seeing that I edited the question, back in the day. :) Can't say I remember the question, and didn't know it has that epic feature of being the most-copied. Cool!
> I wrote almost a decade ago was found to be the most copied snippet on Stack Overflow. Ironically it happens to be buggy.
I don’t find it ironic, I find it quite normal that even small snippets of code contains bugs (given the daily review requests I receive).
I think when copying code literally from StackOverflow what’s more important is understanding what the code does, and why , rather than copying it ad-verbatim by copy & pasting it into your production code.
I also often find on StackExchange et al that quite often the most upvoted is the one that ‘fixes it’ for ‘most people’ yet the correct answer is down at number 3 or 4. Again, understanding the answer and why it applies, helps give you the context to understand if this is actually the solution to your problem or just treats the symptom.
One of the best tips I have gotten from the internet is to never copy and paste code you have not written yourself. Even rewriting it verbatim makes you think about what it is you are actually copying.
It's also good legal advice. It's now legally possible for you to copy and paste code directly from stack overflow because they made an effort to assert a compatible license over works published on their site. However, the same can't be said for most other code snippets flying around out there.
Ladislav Vagner, a legendary programming tutor at FIT CTU, is a known proponent of being extremely cautious when copying code, even your own. He gives programming proseminars where students guide him as he codes the solution to some problem, e.g. mathjax-like typesetting in C++. It is a common theme in the proseminars that a bug is introduced by copying code. Probably on purpose, like many of the other bugs that students are supposed to point out.
I think that’s true if you’re trying to learn a new tool or technology. You probably won’t learn as much following the Rails or Django tutorials if you’re just pasting all the code. But if you’re just looking for some esoteric workaround for some very specific tool and use case, I think it’s fine to paste. And the latter makes up the overwhelming majority of my Stack Overflow visits.
> I also often find on StackExchange et al that quite often the most upvoted is the one that ‘fixes it’ for ‘most people’
And also first, or at least early, and subject to a reinforcing cycle of 'sufficiently good' or 'fixed it enough' that it achieves stratospherically more votes than an 'even more good' or 'fixes it properly' answer that came in too late for the same traction.
Ha, well even if there's an argument for that, it quite often leads to (and is even more reinforced by in terms of votes) the original asker 'accepting' the solution; then the answer that 'fixed it for them, first' is forever ranked highest, even if it rarely works for others and something else is more up-voted.
What I realized years ago is that the upvote on Stack Overflow don't mean "I tried this and it works for me" or "I'm an expert and this is the answer". No, the upvotes on Stack Overflow are along the line of the upvotes/likes one would find on Reddit or HN. More like "you sound confident" or "I was looking for this but I haven't tried it yet"
> No, the upvotes on Stack Overflow are along the line of the upvotes/likes one would find on Reddit or HN. More like "you sound confident"
I think you're right that online scoring systems tend to incentivise false confidence. This happens with blog posts too, where a student of some topic writes a confident and subtly incorrect blog post, and it then ends up on the HN front-page. Only someone with a relatively deep knowledge of the topic can then call out the errors. Ideally it should always be made clear upfront that the author is new to the material.
Somewhat related: Stack Overflow's unfortunate norm of calling out mistakes in answers in a way that goes beyond confidence and strays into condescension and borderline hostility. For a lot of people it seems it's not enough to be seen to be right, they also feel the need to paint someone else as clueless, while just about passing as acceptably polite by keeping the aggression passive. If challenged, they'll brush it off as 'directness'.
> Our sites are all intended to be a sort of representative democracy. Moderator elections are an important part of that plan, but voting on questions and answers is the primary mechanism through which the community governs the site on a day to day basis.
And it can fall to all the errors and issues of democracy too - especially the “pseudo-expert” one. At least you can leave a comment on the answer if there’s an issue.
It's a user experience issue and it's hard to solve. You can't possibly expect people to come back to one of their SO tabs AFTER they get code to work.
Meh, I'm usually there looking for how to do something, and if a response helps me do whatever I was looking to acomplish, or at least on the right track, it was helpful and worth an upvote. I've never upvoted just because someone sounded confident.... at least not on SO.
The number of times I've seen the only correct answer being a terse explanation with a short code snippet and having zero upvotes astounds me.
They may not have been the attention seekers like other posters. But they provided exactly what was asked for. And when I come across their post years later I upvote.
This works better when the problem does not 100% match the issue you are tackling. It makes you think about how you can reshape what you found into something useful.
I have successfully avoided FP code for most of my career. At this point, I consider the domain sophisticated enough to be an independent skill on someone's resume.
There are libraries that offer more appropriate ways of dealing with it, but last time I ran into a FP-related bug (something to do with parsing xlsx into MySQL) I fixed it quickly by converting everything to strings and doing some unholy procedure on them. It worked but it wasn’t my proudest moment as a programmer.
Well, manually floating the point in a string is sure to bite again and again too, but way more frequently than in binary.
There is actually no better way, if you try to calculate over the reals (with computers or whatever you want), you are prone to be bitten. Once in a while there's an article about intervalar algebra on HN, those are a great opportunity to just nod positively and remember all of the flaws of intervalar algebra I got to learn on my school's physics labs. (And yeah, those flaws do fit some problems better than FP, but not all.)
Pity the rational numbers (fractions) did not catch on. Of course it has flaws too but bit easier to grasp. And it handles important cases like 1/3 or 1/10 exactly.
As long as you're using it to represent what could be physical measurements of real-valued quantities, it's nearly impossible to go wrong. Problems happen when you want stupendous precision or human readability.
Numerically unstable algorithms are a problem too but again, intuitively so if you think of the numbers as physical measurements.
So you have problems if you want a precise answer, you want to display your answer, or if you want to use any of a large number of useful algorithms? That sounds like it’s quite easy to go wrong.
You can't want a precise answer from physical measurements unless you don't know how to measure things. Display should be done with libraries, and numerical instability makes algorithms basically useless, so you pretty much have to be inventing it yourself.
I do a lot of floating point math at work and constantly run into problems either from someone else's misunderstanding, my own misunderstanding, or we just moved to a new microarchitecture and CPU dispatch hits a little different manifesting itself as rounding error to write off (public safety industry).
If you expect bit-for-bit reproducible results, then yea, you'd have to know about the nitty-gritty details. The values should usually still correspond to the same thing in common real world precision though.
I am regularly reminded of William Kahan's (the godfather of IEEE-754 floating point) admonition: A floating-point calculation should usually carry twice as many bits in intermediate results as the input and output deserve. He makes this observation on the basis of having seen many real world numerical bugs which are corrupt in half of the carried digits.
These bugs are so subtle and so pervasive that its almost always cheaper to throw more hardware at the problem than it is to hire a numerical analyst. Chances are that you aren't clever enough to unit test your way out of them, either.
Notably, this is only true of 64-bit floats. Sticking to 32-bit floats saves memory and sometimes are faster to compute with, but you can absolutely run into precision problems with them. When tracking time, you'll only have millisecond precision for under 5 hours. When representing spacial coordinates, positions on the Earth will only be precise to a handful of meters.
Yep, floating point numbers are intended for scientific computation on measured values; however many gotchas they hsve when used as intended, there are even MORE if you start using them for numbers that are NOT that. money or any kind of "count" rather than measurement (like, say, a number of bytes).
The trouble is that people end up using them for any non-integer ("real") numbers. It turns out that in modern times scientific calculations with measured values are not necessarily the bulk of calculations in actually written software.
In the 21st century, i don't think there's any good reason for literals like `21.2` to represent IEEE floats instead of a non-integer data representation that works more how people expect for 'exact' numbers (ie, based on decimal instead of binary arithmetic; supporting more significant digits than an IEEE float; so-called "BigDecimal"), at the cost of some performance that you can usually afford.
And yet, in every language I know, even newer ones, a decimal literal represents a float! It's just asking for trouble. IEEE float should be the 'special case' requiring special syntax or instantiation, a literal like `98.3` should get you a BigDecimal!
IEEE floats are a really clever algorithm for a time when memory was much more constrained and scientific computing was a larger portion of the universe of software. But now they ought to be a specialty tool, not the go-to for representing non-integer numbers.
I think you are significantly underestimate the prevalence of floating point calculations, there is a reason why Intel and AMD created all the special simd instructions. Multimedia is a big user for example. You also seriously underestimate the performance cost of using decimal types, we are talking orders of magnitude.
There are still a lot of people doing a lot of work in which they hardly ever want a floating point number but end up using it because it's the "obvious" one that happens when you just write `4.2`, and the BigDecimal is cumbersome to use.
Not sure if there's a mistake in that expression, since if they're similar, you're already going to get some ridiculously large magnitude (unphysical) result. Maybe you mean calculating the error between two values or convergence testing? In that case, it hardly matters if whether you do
quantity2/quantity1 - 1
or
(quantity2 - quantity1) / quantity1
with double precision and physically reasonable values.
Just this week I watched someone discover that computing summary statistics in 32-bit on a large dataset is a bad idea. The computer science curricula needs to incorporate more computational science. It's a shame to charge someone tens of thousands of USD and to not warn them that floating point has some obvious footcanons.
> Just this week I watched someone discover that computing summary statistics in 32-bit on a large dataset is a bad idea. The computer science curricula needs to incorporate more computational science.
Sadly, I suspect too many "computer science" courses have turned into "vocational coding" courses, and now those people are computing summary statistics on large datasets in Javascript...
not OP, but the hint is in “computing summary statistics in 32-bit on a large dataset”.
A large dataset means lots of values, maybe we can assume the number of values is way bigger than any individual value. Perhaps think of McDonalds purchases nation-wide: billions of values but each value is probably less than $10.
The simplest summary statistic would be a grand total (sum). If you have a good mental model of floats, you immediately see the problem!
The mental model of floats which I use is 1) floats are not numbers, they are buckets, and 2) as you get further away from zero, the buckets get bigger.
So let’s say you are calculating the sum, and it is already at 1 billion, and the next purchase is $3.57. You take 1 billion, you add 3.57 to it, and you get... 1 billion. And this happens for all of the rest of the purchases as well.
Remember: 1 billion is not a number, it is a bucket, and it turns out that when you are that far away from zero, the size of the bucket is 64. So 3.57 is simply not big enough to reach the next bucket.
Well explained! All of the later contributions to the sum are effectively ignored or their contributions severely damaged in 32-bit because the "buckets" are big.
It was precisely this problem. The individual had done all data preparation/normalization in 32-bit because the model training used 32-bit on the GPU. It's a very reasonable mistake if one hasn't been exposed to floating point woes. I was pleased to see that the individual ultimately caught it when observing that 2 libraries disagreed about the mean.
Computing a 64-bit mean was enough. Compensated (i.e. Kahan) summation would have worked too.
The thing that jumped out at me, as I've seen the same kind of thing on the job, is the assumption that, eg, log(1000)/log(10) is exactly 3. Does the standard guarantee that the rounded approximation of one transcendental number by the rounded approximation of a related transcendental number will give 3.0 and not 2.999999999?
Floating point math is IEEE 754 in pretty much all cases, so you should see this result in most languages. `math.log(1000, 10)` gives the same result because it's implemented using natural logs internally as it is in most languages.
In this case, there's only about six boundary cases to consider so you can just manually verify it works as expected.
I wonder whether the author is suggesting that (potentially) nine branches is a small number, or they overlooked ternary expressions and function calls and are just counting the if statement.
So it's not flawed (it does compute the correct result).
The author just thinks a completely unreadable (but supposedly faster) variant using logarithms is "better" than the simple loop used in the original snippet?
Write your code for junior devs in their first week at your company, not for academic journals.
His code snippet had rounding errors on the boundaries towards the next unit.
However he notes:
> FWIW, all 22 answers posted, including the ones using Apache Commons and Android libraries, had this bug (or a variation of it) at the time of writing this article.
You should almost _always_ focus on code readability and simplicity over inventiveness and cleverness.
Very few people I have encountered have complained about code being 'too simple' or 'too readable', but the opposite happens on a near daily/weekly basis.
Write comments, use a for loop, avoid global state, keep your nesting limited to 2-3 levels, be kind to your junior devs.
Sibling commenters have already pointed out that you seem to have misread the post, but tbh I found it quite confusing to follow myslf, so here's a summary:
- the first answer posted on SO was a simple loop
- the author posted a 2nd (supposedly faster but less readable) answer. The author didn't think this answer was better than the loop, but it seems the community did and it became accepted (and extremely popular). THIS is the version that was buggy.
The author later went back and fixed their own buggy version.
So yes there's an argument to be made that the very first simple loop was better, but that's orthogonal to the point of the story.
> Write your code for junior devs in their first week at your company, not for academic journals.
Hard and fast rules about coding style are silly. There's a time and place for clever code, and there's a time and place for verbose and straightforward code.
I write performance-critical code. Juniors shouldn't be mucking about there, because it's performance critical. I also write non-performance-critical code with some effort. I write that stuff for the juniors.
When writing for academic journals, it looks like the stuff I write for juniors. I'll drop a hint here or there so experts can reproduce less-obvious optimizations.
This is a bit of a tangent, but while it may be conventional to round to the value with the smallest difference, is that convention good? In a case such as this where it's fine for the prescision to vary with magnitude, then I'd argue it makes sense to round to the value with the smallest ratio.
Floating point is really really hard to get right, especially if you want the numbers to be stable. Which begs the question, why the heck does JavaScript, the most used language in the world, not have an integer type? Sure, there's BigInt but that's quite clunky to use. I know it's virtually impossible to add by now, but I'd love a integer type for all my bit twiddling, byte munching needs.
I just feel if you have bit twiddling, byte munching needs JavaScript shouldn't be the language of choice. Doing that is a rather rare edge case and if you're doing it for performance reasons, working in Javascript is the much bigger performance problem.
That may be true but another case where floating point should be avoided is with money. Now think about all the times a web developer innocuously used a JS number to represent a price. I wouldn’t be surprised if floating point errors affected billions of dollars of transactions.
If you're already using JavaScript for some other reasons but occasionally have bit twiddling, byte munching needs, then trying to do that in JavaScript makes perfect sense. Is it the fastest option? No. But according to https://benchmarksgame-team.pages.debian.net/benchmarksgame/... it is generally within a factor of 4-5 of C++.
For an application area where this applies, consider a web-based game. Using JavaScript keeps you from shipping another application. But occasionally you may have bit twiddling and/or byte munching needs. Which you need to do in JavaScript.
My point wasn't to say you should never do byte manipulation in Javascript, but that for these rare edge cases the existing capabilities without a native int are fine and if you would really need the native int rather than some equivalent work around (which I assume is most likely due to performance considerations) a faster language is the better approach. A webgame might be able to use wasm for that.
Why are you writing code? The question was for a static method in Apache Commons, not your "I'm so clever" implementation. Think the reading comprehension is flawed.
(Of course, this static method exists in Apache Commons, going back at least 20 years. But the fellow "code golfers" of the author voted someone to the first answer who similarly had the irresistible urge to try to be very clever. It's a scourge on StackOverflow.)
I think that the answer is what I would expect based on the question title (which doesn’t mention Apache Commons, only Java), if I was another user searching for the solution to this problem. Maybe the question should have been renamed to indicate this, but as it stands, I do think a library-agnostic solution is more helpful to people finding the question than an answer which only works for Apache Commons.
Say what you want about the stability of the npm ecosystem, but if this were JS, a new SemVer patch release could be cut, and it would be fixed in thousands of code bases essentially instantly.
You have to be a terrible programmer to even consider using a base 10 logarithm for this.
Their proposed improvement is also terrible, since it divides multiple times unnecessary, and checks for negativity multiple times unnecessarily.
The proper simple solution is of course a handwritten binary search with if-else blocks that starts with the most likely range, annotated with "likely" annotations, and a single division.
If this is the main task of the program for a while, and thus a large fraction of the cache can be dedicated to it, then solutions with large lookup tables are worth trying (obviously optimizing string formatting is also essential in this case).
This is why software is so often broken, there's a lot of incompetent people programming.
"You have to be a terrible programmer to even consider using a base 10 logarithm for this."
That's not a fair statement.
Good programmers are programmers who deliver value - who build robust, maintainable features in reasonable time that address user needs.
Whether or not you would quickly find the correct approach to this specific problem is a miniscule, pedantic detail in a giant ocean of programming skills and experiences.
About the "terrible" aspect of it, to quote: "Granted it’s not very readable and log / pow probably makes it less efficient than other solutions. But there were no loops and almost no branching which I thought was pretty neat." No need to insult the author over it.
About your "proper simple solution": I don't think that's a good idea either. Based on your next paragraph, the version you suggest with the handwritten binary search and "likely" annotations is for the case where the code isn't performance critical: for where the code is performance critical, you suggest a different solution. If the code isn't performance critical, please do not turn it into an unreadable mess over what would become a negligible overall performance gain. Write it in a simple, obviously correct way, keep it boring, and you'll keep it stable; you can use the time you save on fixing bugs in your super optimised version on improving more critical parts of your program.
Wait. I always use logarithm for this kind of tasks, how exactly does it make me incompetent and terrible? This is literally what logarithm represents?
> The most copied StackOverflow snippet of all time
Maybe, but sounds like it's merely the Java snippet from SO found most often on github. Not sure why blog author didn't include the word "Java" in his title or the first paragraph:
> an answer I wrote almost a decade ago was found to be the most copied snippet on Stack Overflow
There is no evidence for this claim in the blog post, just that it's the "most copied Java snippet". And it's just based on occurrences in github. Maybe the most-copied snippet is an AWK or ffmpeg one-liner? Something that wouldn't find its way into a github repo. Or maybe something undetectably vanilla, like answers to "How do you write loops in language X?" Is there a way of finding out what actually is the most-copied snippet?
The question was how to build a URL, not how to send off a request to it. The answer sends off a request and then inspects the response to see what URL was used. If you wanted to send off the request, inspecting the URL on the result is probably not useful. If you didn't want to send off the request, doing it this was is wasteful or even harmful.
Yes, but unless the answer was edited before the link to HN was posted, the user specifically said you should only do it if you _really_ intend to make a request, not just generate a url. It is conceivable you'd want to log the request or something and hence reference the url after the request call. Yeah, it is a bad answer to the question as stated, but it has a logic to it considering what might be the real motivation behind the question.
EDIT: Apparently the answer was edited by another user just recently making the clarification.
Your parent poster makes the mistake that is rife among Python programmers, which is to assume that in a delightfully simple[0] language like Python, it's "obvious" what a given piece of code does even without explanation. Among people who don't delight in the poor taste of Python's design and have limited exposure to its standard library, of course, it's not always obvious what a given piece of code is doing despite the belief to the contrary, so there are plenty of people who aren't going to pick up on the fact that requests.get doesn't just construct a GET request for the caller, but instead constructs such a request and then goes out and performs it, too.
Shame about the hostile reaction from others towards your question. Keep asking questions (especially things that are presented without comment), and don't be afraid that doing so will make you look stupid or that you should feel like you should be punished for it.
> Shame about the hostile reaction from others towards your question.
I agree that your parent is a good question that should have been well received, but, as far as I can tell, it was. Where do you see a hostile reaction? In fact the only hostility I see in this thread is what you directed at Python, which, in this context, seems unmotivated; it is surely true that one can write code in any language whose full import isn't immediately apparent. At the moment, the only other response to your parent is from hvdijk, saying (https://news.ycombinator.com/item?id=27534803):
> The question was how to build a URL, not how to send off a request to it. The answer sends off a request and then inspects the response to see what URL was used. If you wanted to send off the request, inspecting the URL on the result is probably not useful. If you didn't want to send off the request, doing it this was is wasteful or even harmful.
This seems like a response that takes the question seriously and addresses it clearly, just as it should.
At the time I wrote the comment it was clearly not well-received, and the oblique opening remark from the person you're quoting is not the kind of response that addresses the question as it should.
That comment is, just like the downvotes the question received, precisely the sort of thing that discourages asking honest questions rather than welcoming them. Note that by the way it is written it, too, assumes that it is both obvious and understood that Python's request.get will "send off a request"—instead of merely building a request and returning it to you. Rather than just straightforwardly answering the question (by explaining what this part of the Python' standard library is actually doing—which is the relevant missing piece here, and which no one should be expected to know) the quoted comment ("The question was how to build a URL, not how to send off a request to it") pins the misunderstanding on the questioner by tacitly implying the questioner isn't paying attention to something else entirely different.
The comment, when considered in full and in context, actually has the effect of subtly discouraging/admonishing the questioner (and likeminded people with the same question) for failing to recognize something that is, to the sophomoric Python crowd, obvious and worthy of ridicule—which is what maest's thread was all about, by the way (and almost certainly why it got moderated).
Ew. Yikes. Wow, that's a special kind of special. The mind truly boggles. It had a score of 4 when I first checked it, but it looks like it got slashdotted by this thread/link and now it's -1 and probably still falling.
You'd think that is so completely wrong that no competent programmer would ever do it...
Except the java.net.URL.equals and java.net.URL.hashcode methods do almost the same thing: they issue DNS requests (!)
"Two hosts are considered equivalent if both host names can be resolved into the same IP addresses; else if either host name can't be resolved, the host names must be equal without regard to case; or both host names equal to null."
There is a bug raised[1], but it can't be fixed for backwards compatibility reasons.
I'll never forget this now, after debugging a very horrible and severe and very intermittent performance issue in some code over 20 years ago. A (slow) DNS resolver occasionally caused 1000x performance degradation on remote sites. That was horrible to work out.
350 comments
[ 3.5 ms ] story [ 284 ms ] threadSomething like "cherry pick this answer, with attribution, and notifications when flaws and/or improvements are found".
Maybe that's a terrible idea (there's definitely risk involved, and the potential to spread and create bad software), but equally I don't know why it would be significantly worse than unattributed code snippets and trends towards single-function libraries.
Mostly but not entirely because NPM handled things poorly in various ways.
Seems like the loop based code wasn't so bad after all...
Not to mention that the fixed version now has branches as well…
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.
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.
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.
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.
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?
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.
There might be a few guys at FAANG who have a planet-scale use case for human readable file sizes. But surely "performance optimising" this is _purely_ code golf geekiness?
(Which is a perfectly valid reason to do it, but I'm gonna choose the most obvious to the next progerammer reading it version over one that 50% or 500% or 5000% fast in almost any use case I can think I'm like to need this... I mean, it's only looking for 6 prefixes "KMGTPE" a six line case statement would work for most people?)
This same property makes CMOV useful in Spectre mitigation, see https://llvm.org/docs/SpeculativeLoadHardening.html
Keeping CMOV slow is now an important security feature.
Speculative execution refers more towards the decoder/uop generation side of the processor (the “in-order” side). A normal “in-order” processor, upon encountering a conditional jump, would wait until the pipeline is finished to check if it should jump or not. It does it by inserting “bubbles” into the pipeline - essentially doing nothing but waiting.
Speculative execution (or branch prediction) would say, “I think the branch will be taken based on X, Y, Z,” and then keep the pipeline full in the process. If the prediction was right, congratulations! You just saved dozens of clock cycles that otherwise would’ve been wasted. If it was wrong, no worries. The pipeline is then flushed; all the speculated instructions’ results are tossed (before they’re “written back”). Then the processor resumes operation on the correct branch.
Speculative execution doesn’t necessitate an out-of-order architecture, and visa-versa. Just a pipelined one. It’s perfectly possible to have an out-of-order architecture that doesn’t speculate, or a speculative one that is completely “in-order”, but they work hand-in-hand, and it makes sense to have both if you have one.
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.
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.
Not to mention the performance implications. Parallelisation, composability and system thinking are sometimes overkill and lead to overengineering.
> 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 typical Javascript code reduce operation will not be parallelized. It actually can be slower than a loop because of overhead for creating and calling a function on every iteration.
> when you look at the system as a whole lots of for loops
A code with lot of loops is still more readable than a code with lots of nested reduces.
I think that is a function of familiarity, if you use reduce a lot it will be as easy to read as a loop - perhaps easier because more compact - there is a downside to reading more lines for some people, at some point verbosity becomes its own source of illegibility (although any loop that can easily be turned into a reduce probably won't be excessively verbose anyway)
Of course all that is just on the personal level, you , by using and reading more code with reduce in it will stop finding reduce less easy to understand than loops - but the next programmer without lots of reduce experience will be in your same boat.
In JavaScript, the reduce callback is created once and called repeatedly. For loops are pretty much always the fastest possible way because they use mutable state. They are also a really good way of creating unreadable spaghetti that does things you don't want them to.
I'm not sure what you mean by nested reduces. Chained reduce functions are easy to follow
And they both trivially allow for side effects.
Only if it's actually more readable. The principle of least privilege does not give you any benefit when talking about loop implementations.
> More specifically, maps can be trivially parallelized;
This argument is repeated time and time again but I've never actually seen it work. Maps that can be trivially parallelized aren't worthy to parallelize most of the time. In the rare case it's both trivial and worthy, it's because the map function (and therefore the loop body) are side-effect free, and for those rare cases you don't care too much about the slightly extra effort of extracting the loop body into a function.
> 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 reason that for-loops are too "strong"
Code is too strong in general. Reasoning about the global behavior of code is difficult if the code itself is complex. Nested maps and reduces will be equally difficult to comprehend. The fact that a map() function tells you that you're converting elements of lists does not save you from understanding what is that conversion doing and why.
Sometimes loops will be better for readability, sometimes it will be map/reduce. Saying that for loops always make it harder to reason about the code does not make too much sense in my opinion.
> The fact that a map() function tells you that you're converting elements of lists does not save you from understanding what is that conversion doing and why.
It can actually, say you have a query that comes in, this calls a function that fetches records from the database, it's not a basic query, it has joins, perhaps a subquery, etc. Then you have another function that transforms the results into whatever presentational format, decorates, wtv, those results, and it's also more than a few basic couple lines of logic.
And now you have a bug report come in, that not all expected results are being shown.
If you have
You have 3 possibilities, the problem is on the storage layer, the problem is on the query, the problem is on the loop. You read the query, because the bug is subtle, it seems ok, so now you move to the loop. It's a bit complex but seems to be correct too. Now you start debugging what's happening.If you have
You know it's either underlying storage or the query. Since the probability of the storage being broken is less plausible, you know it must be the query. In the end it's a synch problem with something else, and everything is right, but now you only spent time on reproducing the query and being sure that it works as expected.For instance, map - I know that it will return a new collection of exactly the same number of items the iterable being iterated has. When used correctly it shouldn't produce any side-effects outside the mapping of each element.
In some languages now you have for x in y which in my opinion is quite ok as well, but still to change the collection it has to mutate it, and it's not immediate what it will do.
If I see a reduce I know it will iterate again a definite number of times, and that it will return something else than the original iterable (usually), reducing a given collection into something else.
On the other hand forEach should tell me that we're only interested in side-effects.
When these things are used with their semantic context in mind, it becomes slightly easier to grasp immediately what is the scope of what they're doing.
On the other hand, with a for (especially the common, old school one) loop you really never know.
I also don't understand what is complex about the functional counterparts - for (initialise_var, condition, post/pre action) can only be simpler in my mind due to familiarity as it can have a lot of small nuances that impact how the iteration goes - although to be honest, most of the times it isn't complex either - but does seem slightly more complex and with less contextual information about the intent behind the code.
But in a for loop anything can happen- from a map to a reduce to a mix, to whatever convoluted logic the dev comes up with.
But yes - for me
is slightly more readable than I mean in this case the name kinda makes it obvious anyway :)If the operation is conceptually accumulating something over the whole collection and if it's idiomatic in the language I'm using - I will use reduce. Same with map-y and filter-y operations.
But if I have to do some mental gymnastics to make the operation fit reduce - for loop it is. Or generator expression in case of python.
Fold and map in functional languages are often much more restrictive in a sense. For example, with lists, you reduce down a collection [a]->a to a single object, or produce another collection with a map [a]->[a]. So map and fold etc are much more restrictive. That's what makes it clearer.
To be honest this seems to be a familiarity thing > but with reduce you need to know what arguments in a callback mean
If I didn't know for it would be mind boggling what those 3 things, separated by semicolons, are doing It doesn't look like anything in the usual language(s) they're implemented. It's the same with switch.
The only thing both of them have, for and switch, and helps, is that languages that offer it and aren't FP usually use the same *C* form across all, whereas reduce's args and the callback args vary a bit more between languages, and specially between mutable and immutable langs.
I still prefer most of the time the functional specific counterparts.
Same one-liner in (slightly uglier) Python:
Ironically, it's a great example of why readability is so much more important than conciseness and one liners.
One idea I have is, that often FP code is not modularized and violates the SOLID principle in doing several things in one line.
there are seldom named subfunctions where the name describe the purpose of the functions- take lamdas as an example: I have to parse the lamda code to learn what it does. Even simple filtering might be improved (kinda C#):
var e = l.Filter(e => e.StartsWith("Comment"));
vs.
var e = l.Filter(ElementIsAComment);
or even using an extension method:
var e = l.FindComments();
sorry I could not come up with a better example- I hope you get my point...
But that much is immediately obvious since it's mapping a filter, that is, has a loop within a loop.
I did consider the second one to also take quadratic time though. I forgot that in python getting list elements by index is O(1) instead of O(n) which is what I'm personally used to with lists.
It's also true that you can replace the filter with
but that's not as much fun as(x ==) . (`mod` m)
I just love how it looks and it doesn't personally seem any less clear to me, maybe a bit more verbose.
Have you considered that maybe this is a sign you're too deep into using impractical programming languages?
Cleanness for immutable data structures aside, linked list are a very poor way to store data given the way computer architectures are designed.
“Languages that use ‘list’ for linked lists and have different names for other integer-indexable ordered collections” aren’t necessarily “impractical”.
Even applying it at compile time, it's still O(nm). You have to compute 'v mod m' for each possible value of v and m.
> But that much is immediately obvious since it's mapping a filter, that is, has a loop within a loop.
It's not immediately obvious because you have to parse the calls and see exactly where is the filter and the map.
versus and In the first case, you have to parse the parenthesis and arguments to see where exactly are the map and filter cals. In the second, you see a for with a second level of indentation.> I just love how it looks and it doesn't personally seem any less clear to me, maybe a bit more verbose.
It doesn't seem any less clear to you because you're used to it. But think about the things you need to know apart from what a loop, map, filters and lambdas are:
- What is (x ==). Is it a function that returns whether the argument is equal to x? - What is '.'. Function composition? Filter? - Same thing with `mod` m. What are the backticks for?
Compare that with the amount of things you need to know with the Python code with for loops. For that complexity to pay off you need some benefits, and in this case you're only getting disadvantages.
That's the whole point of this discussion. Production code needs to work, have enough performance for its purpose and be maintainable, those are the metrics that matter. Being smart, beautiful or concise are completely secondary, and focusing on them will make for worse code, and it's exactly what happened in this toy example.
If Python were focused on functional programming it would have a utility function for this similar to itertools.groupby (but with indices in an array instead of keys in a dictionary).
itertools.groupby doesn’t return a dictionary, it returns an iterator of (key, (iterator that produces values)) tuples. It sounds, though, like you want something like:
Then you could do this with something like:Unless you're using Perl - "Each element of LIST may produce zero, one, or more elements in the generated list".
But that's just a social convention. There's nothing stopping you from doing other things during your map or reduce.
In practice, the only difference between Map, Reduce and a For loop is that the first two return things. So depending on whether you want to end up with an array containing one item for each pass through the loop, "something else", or nothing, you'll use Map, Reduce or forEach.
You can still increment your global counters, launch the missiles or cause any side effects you like. "using it correctly" and not doing that is just a convention that you happen to prefer.
(and I haven't read the article so not even sure I agree with the example there, this was more in general terms)
a loop that iterates over indices when I want elements is not readable, e.g. I prefer
rather than This is maybe where this aversion comes from, people usually [citation needed] want to iterate over elements, rather than indices.But yes, there are of course cases where the index could be needed, I was merely commenting on the aversion part for generic developers.
Like goto, basic loops are powerful, simple constructs that tell you nothing at all about what the code is doing. For…in loops in many languages are a little better, but map, reduce, or comprehensions are much more expressive as to what the code is doing, but mostly address common cases of for loops.
While loops are weakly expressive (about equal to for…in), but except where they are used as a way (in language without C-style for loops) but there is less often a convenient replacement.
It's the ostrich approach: if you don't see the branches they don't matter.
It prints 1000.0 kB.
> 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?
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!
What's missing still is a comprehensive set of test cases to check against.
If such cases were spec'ed to go along with the original code, fthen at least one could have seen the applicability range and perhaps other people would have added some challenging corner cases (just as mentioned in the OP).
A real number type could be bounded by the amount of RAM you have.
I've ironically found that big integer libraries sometimes optimize math routines more than string conversion. This was quite annoying for me when I optimized the factorial function in Ruby, and found that generating the string was my bottleneck. I then optimized that as well. :-)
A quick Google says there's an estimate of 10^78 to 10^82 atoms in the universe. That number would be able to be stored in well under 300 bits.
Lots of problems suffer from 'combinatorial explosion' [1].
I recently learned about the Archimedes's cattle problem, the solution is of order 10^206544 [2]
[1] https://en.wikipedia.org/wiki/Combinatorial_explosion
[2] https://en.wikipedia.org/wiki/Archimedes%27s_cattle_problem
Good thing it wasn't a range check function. I hear those are expensive.
I don’t find it ironic, I find it quite normal that even small snippets of code contains bugs (given the daily review requests I receive).
I think when copying code literally from StackOverflow what’s more important is understanding what the code does, and why , rather than copying it ad-verbatim by copy & pasting it into your production code.
I also often find on StackExchange et al that quite often the most upvoted is the one that ‘fixes it’ for ‘most people’ yet the correct answer is down at number 3 or 4. Again, understanding the answer and why it applies, helps give you the context to understand if this is actually the solution to your problem or just treats the symptom.
It's a pretty neat rule to have in mind.
I didn't really grok Test Driven Development until I worked thru the book, line-by-line, experiencing the workflow.
Knowledge vs experience.
And also first, or at least early, and subject to a reinforcing cycle of 'sufficiently good' or 'fixed it enough' that it achieves stratospherically more votes than an 'even more good' or 'fixes it properly' answer that came in too late for the same traction.
So exactly the solution most project managers are after? /s
I think you're right that online scoring systems tend to incentivise false confidence. This happens with blog posts too, where a student of some topic writes a confident and subtly incorrect blog post, and it then ends up on the HN front-page. Only someone with a relatively deep knowledge of the topic can then call out the errors. Ideally it should always be made clear upfront that the author is new to the material.
Somewhat related: Stack Overflow's unfortunate norm of calling out mistakes in answers in a way that goes beyond confidence and strays into condescension and borderline hostility. For a lot of people it seems it's not enough to be seen to be right, they also feel the need to paint someone else as clueless, while just about passing as acceptably polite by keeping the aggression passive. If challenged, they'll brush it off as 'directness'.
> Our sites are all intended to be a sort of representative democracy. Moderator elections are an important part of that plan, but voting on questions and answers is the primary mechanism through which the community governs the site on a day to day basis.
https://stackoverflow.com/help/why-vote
Meh, I'm usually there looking for how to do something, and if a response helps me do whatever I was looking to acomplish, or at least on the right track, it was helpful and worth an upvote. I've never upvoted just because someone sounded confident.... at least not on SO.
They may not have been the attention seekers like other posters. But they provided exactly what was asked for. And when I come across their post years later I upvote.
> [...]
> Floating-point arithmetic is hard.
I have successfully avoided FP code for most of my career. At this point, I consider the domain sophisticated enough to be an independent skill on someone's resume.
There is actually no better way, if you try to calculate over the reals (with computers or whatever you want), you are prone to be bitten. Once in a while there's an article about intervalar algebra on HN, those are a great opportunity to just nod positively and remember all of the flaws of intervalar algebra I got to learn on my school's physics labs. (And yeah, those flaws do fit some problems better than FP, but not all.)
It's been a whole field with its own patron saint for a quite a while, take a look at
https://en.wikipedia.org/wiki/William_Kahan
Numerically unstable algorithms are a problem too but again, intuitively so if you think of the numbers as physical measurements.
These bugs are so subtle and so pervasive that its almost always cheaper to throw more hardware at the problem than it is to hire a numerical analyst. Chances are that you aren't clever enough to unit test your way out of them, either.
It's a matter of time if one doesn't know to look for numerically stable algorithms. Or if one thinks performance merits dropping stability.
https://github.com/RhysU/ar/issues/3 was an old saga in that vein.
The trouble is that people end up using them for any non-integer ("real") numbers. It turns out that in modern times scientific calculations with measured values are not necessarily the bulk of calculations in actually written software.
In the 21st century, i don't think there's any good reason for literals like `21.2` to represent IEEE floats instead of a non-integer data representation that works more how people expect for 'exact' numbers (ie, based on decimal instead of binary arithmetic; supporting more significant digits than an IEEE float; so-called "BigDecimal"), at the cost of some performance that you can usually afford.
And yet, in every language I know, even newer ones, a decimal literal represents a float! It's just asking for trouble. IEEE float should be the 'special case' requiring special syntax or instantiation, a literal like `98.3` should get you a BigDecimal!
IEEE floats are a really clever algorithm for a time when memory was much more constrained and scientific computing was a larger portion of the universe of software. But now they ought to be a specialty tool, not the go-to for representing non-integer numbers.
There are still a lot of people doing a lot of work in which they hardly ever want a floating point number but end up using it because it's the "obvious" one that happens when you just write `4.2`, and the BigDecimal is cumbersome to use.
1 - quantity2 / (quantity1 - quantity2)
... or some such thing. If quantity1 and 2 are similar, ouch!
quantity2/quantity1 - 1
or
(quantity2 - quantity1) / quantity1
with double precision and physically reasonable values.
Sadly, I suspect too many "computer science" courses have turned into "vocational coding" courses, and now those people are computing summary statistics on large datasets in Javascript...
A large dataset means lots of values, maybe we can assume the number of values is way bigger than any individual value. Perhaps think of McDonalds purchases nation-wide: billions of values but each value is probably less than $10.
The simplest summary statistic would be a grand total (sum). If you have a good mental model of floats, you immediately see the problem!
The mental model of floats which I use is 1) floats are not numbers, they are buckets, and 2) as you get further away from zero, the buckets get bigger.
So let’s say you are calculating the sum, and it is already at 1 billion, and the next purchase is $3.57. You take 1 billion, you add 3.57 to it, and you get... 1 billion. And this happens for all of the rest of the purchases as well.
Remember: 1 billion is not a number, it is a bucket, and it turns out that when you are that far away from zero, the size of the bucket is 64. So 3.57 is simply not big enough to reach the next bucket.
It was precisely this problem. The individual had done all data preparation/normalization in 32-bit because the model training used 32-bit on the GPU. It's a very reasonable mistake if one hasn't been exposed to floating point woes. I was pleased to see that the individual ultimately caught it when observing that 2 libraries disagreed about the mean.
Computing a 64-bit mean was enough. Compensated (i.e. Kahan) summation would have worked too.
In this case, there's only about six boundary cases to consider so you can just manually verify it works as expected.
I wonder whether the author is suggesting that (potentially) nine branches is a small number, or they overlooked ternary expressions and function calls and are just counting the if statement.
The author just thinks a completely unreadable (but supposedly faster) variant using logarithms is "better" than the simple loop used in the original snippet?
Write your code for junior devs in their first week at your company, not for academic journals.
However he notes:
> FWIW, all 22 answers posted, including the ones using Apache Commons and Android libraries, had this bug (or a variation of it) at the time of writing this article.
Very few people I have encountered have complained about code being 'too simple' or 'too readable', but the opposite happens on a near daily/weekly basis.
Write comments, use a for loop, avoid global state, keep your nesting limited to 2-3 levels, be kind to your junior devs.
He isn't trying to get people to use the log version.
The log approach _is_ the most copied snippet.
- the first answer posted on SO was a simple loop
- the author posted a 2nd (supposedly faster but less readable) answer. The author didn't think this answer was better than the loop, but it seems the community did and it became accepted (and extremely popular). THIS is the version that was buggy.
The author later went back and fixed their own buggy version.
So yes there's an argument to be made that the very first simple loop was better, but that's orthogonal to the point of the story.
Hard and fast rules about coding style are silly. There's a time and place for clever code, and there's a time and place for verbose and straightforward code.
I write performance-critical code. Juniors shouldn't be mucking about there, because it's performance critical. I also write non-performance-critical code with some effort. I write that stuff for the juniors.
When writing for academic journals, it looks like the stuff I write for juniors. I'll drop a hint here or there so experts can reproduce less-obvious optimizations.
For an application area where this applies, consider a web-based game. Using JavaScript keeps you from shipping another application. But occasionally you may have bit twiddling and/or byte munching needs. Which you need to do in JavaScript.
The question being answered clearly wanted base2 engineering prefix units, rather than the standard base10 engineering prefix units.
suffixes = [ "EB", "PB", "TB", "GB", "MB", "KB", "B" ]
magnitudes = [ 2^60, 2^50, 2^40, 2^30, 2^20, 2^10, 2^0 ] // Pseudocode, also 64 bit integers required. (Compilers might assume unsigned 32 for int)
The author's code gives an option for the units:
int unit = si ? 1000 : 1024;
(Of course, this static method exists in Apache Commons, going back at least 20 years. But the fellow "code golfers" of the author voted someone to the first answer who similarly had the irresistible urge to try to be very clever. It's a scourge on StackOverflow.)
Their proposed improvement is also terrible, since it divides multiple times unnecessary, and checks for negativity multiple times unnecessarily.
The proper simple solution is of course a handwritten binary search with if-else blocks that starts with the most likely range, annotated with "likely" annotations, and a single division.
If this is the main task of the program for a while, and thus a large fraction of the cache can be dedicated to it, then solutions with large lookup tables are worth trying (obviously optimizing string formatting is also essential in this case).
This is why software is so often broken, there's a lot of incompetent people programming.
That's not a fair statement.
Good programmers are programmers who deliver value - who build robust, maintainable features in reasonable time that address user needs.
Whether or not you would quickly find the correct approach to this specific problem is a miniscule, pedantic detail in a giant ocean of programming skills and experiences.
About your "proper simple solution": I don't think that's a good idea either. Based on your next paragraph, the version you suggest with the handwritten binary search and "likely" annotations is for the case where the code isn't performance critical: for where the code is performance critical, you suggest a different solution. If the code isn't performance critical, please do not turn it into an unreadable mess over what would become a negligible overall performance gain. Write it in a simple, obviously correct way, keep it boring, and you'll keep it stable; you can use the time you save on fixing bugs in your super optimised version on improving more critical parts of your program.
Maybe, but sounds like it's merely the Java snippet from SO found most often on github. Not sure why blog author didn't include the word "Java" in his title or the first paragraph:
> an answer I wrote almost a decade ago was found to be the most copied snippet on Stack Overflow
There is no evidence for this claim in the blog post, just that it's the "most copied Java snippet". And it's just based on occurrences in github. Maybe the most-copied snippet is an AWK or ffmpeg one-liner? Something that wouldn't find its way into a github repo. Or maybe something undetectably vanilla, like answers to "How do you write loops in language X?" Is there a way of finding out what actually is the most-copied snippet?
https://stackoverflow.com/a/40429822/864112
It boggles the mind that anyone could ever suggest this as a solution.
etc
EDIT: Apparently the answer was edited by another user just recently making the clarification.
Shame about the hostile reaction from others towards your question. Keep asking questions (especially things that are presented without comment), and don't be afraid that doing so will make you look stupid or that you should feel like you should be punished for it.
0. https://blog.imgur.com/wp-content/uploads/2017/06/mocking.jp...
I agree that your parent is a good question that should have been well received, but, as far as I can tell, it was. Where do you see a hostile reaction? In fact the only hostility I see in this thread is what you directed at Python, which, in this context, seems unmotivated; it is surely true that one can write code in any language whose full import isn't immediately apparent. At the moment, the only other response to your parent is from hvdijk, saying (https://news.ycombinator.com/item?id=27534803):
> The question was how to build a URL, not how to send off a request to it. The answer sends off a request and then inspects the response to see what URL was used. If you wanted to send off the request, inspecting the URL on the result is probably not useful. If you didn't want to send off the request, doing it this was is wasteful or even harmful.
This seems like a response that takes the question seriously and addresses it clearly, just as it should.
That comment is, just like the downvotes the question received, precisely the sort of thing that discourages asking honest questions rather than welcoming them. Note that by the way it is written it, too, assumes that it is both obvious and understood that Python's request.get will "send off a request"—instead of merely building a request and returning it to you. Rather than just straightforwardly answering the question (by explaining what this part of the Python' standard library is actually doing—which is the relevant missing piece here, and which no one should be expected to know) the quoted comment ("The question was how to build a URL, not how to send off a request to it") pins the misunderstanding on the questioner by tacitly implying the questioner isn't paying attention to something else entirely different.
The comment, when considered in full and in context, actually has the effect of subtly discouraging/admonishing the questioner (and likeminded people with the same question) for failing to recognize something that is, to the sophomoric Python crowd, obvious and worthy of ridicule—which is what maest's thread was all about, by the way (and almost certainly why it got moderated).
Good.
> This is akin to answering "how do I bake a cake?" with "open up a bakery, walk inside, and ask for a cake"
Only it's more like answering "how much does this cake cost" by purchasing the cake and looking at the receipt.
Or should I say... analogies are like Uber, but for metaphors. No. I should stop before writing that.
Except the java.net.URL.equals and java.net.URL.hashcode methods do almost the same thing: they issue DNS requests (!)
"Two hosts are considered equivalent if both host names can be resolved into the same IP addresses; else if either host name can't be resolved, the host names must be equal without regard to case; or both host names equal to null."
See https://docs.oracle.com/en/java/javase/11/docs/api/java.base...
There is a bug raised[1], but it can't be fixed for backwards compatibility reasons.
I'll never forget this now, after debugging a very horrible and severe and very intermittent performance issue in some code over 20 years ago. A (slow) DNS resolver occasionally caused 1000x performance degradation on remote sites. That was horrible to work out.
[1] https://bugs.java.com/bugdatabase/view_bug.do?bug_id=4434494