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…
Not to mention that the fixed version now has branches as well…
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
func does_query -> loop transforms
If you have
func does_query -> func maps_results
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
(defn factorial [n]
(reduce * (range 1 (inc n))))
def factorial(n):
result = 1
for i in range(2,n+1):
result *= i
return result
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.
congruence_classes m l = map (\x -> ((x ==) . (`mod` m)) l) [0..m-1]
def congruence_classes(m, l):
sets = []
for i in range(m):
sets += [[]]
for v in l:
sets[v % m] += [v]
return sets
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)))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
[ v | v <- l, v `mod` m == x ]
(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.
map(lambda x: do_some_things(x, another_param), filter(lambda x: filter_things(x), lst))
map(lambda x: do_some_things(x, filter(lambda y: filter_things(x, y), another_list)), range(m))
retval = []
for x in lst:
if not filter_things(x):
continue
retval.append(do_some_things(x))
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))
> 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.
def congruent_sets(m, l):
return [[v for v in l if v % m == i] for i in range(m)]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]
def congruent_sets(m, l):
categorize_into_list(l, m, lambda v: v % m)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
for element in elements:
for (i = 0 , i < len(elements), i++) { element = elements[i] ...
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.
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.
It's the ostrich approach: if you don't see the branches they don't matter.
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!
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.
> 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?
It prints 1000.0 kB.