5

This question is not meant to be a critique of functional programming, but more hoping for resources and opinions.

I am refactoring some historically messy code so that it follows functional programming a bit more, and I've arrived at something like this.

readJson('./data/member.json')
  .map(unmarshallData)
  .map(getCachedData(newBioIdToUrlNameMap))
  .map(getTransformedFields)
  .map(getVoteData(changedFiles))

I've abstracted away business logic and encapsulated portions into functions with appropriate names. I aimed for pure functions, and any parts that are impure I've contained in their own functions (I'm probably not fully living up to the tenets of functional programming here, but maybe another refactor can take it to the next level). Now that I've gotten to this more readable and understandable place, I feel very warm and fuzzy inside.

I am looking at my old code. It was one giant for loop:

const rawData = readJson('./data/member.json')

for (const rawDatum of rawData) {
  ...
  ...
}

This loop had multiple responsibilities and performed many side effects. It felt very messy and increasingly unmaintainable -- but it was doing everything in a single loop.

"Pipelines" in functional programming are mn time complexity, where m is the length of segments in a pipeline. In my particular case, my "imperative" code was 1n while my fp refactor is 4n.

I've read somewhere that the coefficient before n is not really important in time complexity, at least not nearly as important as going from O(n) to O(n log n) or O(n^2). But still -- wouldn't there be some real world scenarios where a team might want to take the 1n solution over the 4n solution?

My questions about this are:

  • How important is the coefficient before the n in Big O notation? Is there some consensus in the Big O community about its level of importance?

  • Are there any languages or tools that "optimize" fp code like this, taking multiple loops and then compiling them down to less loops and adding in side effects in the process? This kind of code is undesirable as a human, but the computer doesn't care. Maybe this is ludicrous, but I'm just wondering if this exists.

12
  • 2
    Yes it is bad, but I think every 'respectable' fp language has a solution to this, the main solution I've seen is to basically make your maps not actually perform the operation and instead just register the operation to be performed and then when you want to evaluate your chain of maps, they all get rolled into one. See docs.scala-lang.org/overviews/collections/views.html for more details (you don't need to know scala to understand the example). re your first question, there's no 'Big O community' that I know of, but the coefficient is crucially important in real life. Commented Jun 2 at 16:19
  • wow! I sort of figured I was going out on a limb by asking this. This is awesome. Thanks.
    – rpivovar
    Commented Jun 2 at 16:30
  • @rpivovar please add a language tag. I assumed Java like streams are in use and could not find the complexity increase.
    – Basilevs
    Commented Jun 2 at 17:48
  • 7
    This questions messes up some of the complexity terms. In fact, when you are asking about "n operations" vs. "4n operations", you are not asking about "time complexity", you are asking about the actual performance. When we speak of complexity, the complexity class O(N) is identical to O(4N), or O(m x N), where m is a constant greater zero. Still, as you have already noted, your functional code does not process 4n of the former n operations, so the whole question seems to be based on a wrong premise.
    – Doc Brown
    Commented Jun 2 at 21:17
  • 1
    While "pipelines" should not affect complexity, it may have a slightly higher overhead. In the majority of cases the difference should be negligible, but you may want to be careful if you are processing a huge number of items, like image or video processing. But always profile/benchmark before you try to optimize anything.
    – JonasH
    Commented Jun 3 at 9:53

3 Answers 3

6

The 4 in 4n isn't usually considered important, because the n doesnt take into account the amount of work you are doing in each iteration. Its assumed to be non reducable.

However, here although you run the loop 4 times, each time only does 1/4 of the work you previously did in one loop.

Additionally its only 4n due to the way map works, not due to the "functionalness" of your programming. You could use a different method of function chaining to get back down to 1n ie.

readJson('./data/member.json').map(getVoteData(changedFiles(getTransformedFields(getCachedData(newBioIdToUrlNameMap(unmarshallData))))))

This isnt any less functional, it's just ugly. but map isn't the only way to prettify your functional code. check these out : https://dev.to/sundarbadagala081/javascript-chaining-3h6g

1
  • 1
    "However, here although you run the loop 4 times, each time only does 1/4 of the work you previously did in one loop." Yeah, there is a logical fallacy in my line of thinking here.
    – rpivovar
    Commented Jun 2 at 17:44
3

Javascipt's built-in map uses O(N) memory and does full traversal in O(N), in other words, the asymptotic complexity of your functional approach is exactly the same as imperative one. Yes, there are a few additional allocations and some unnecessary data transfer, but that's negligible on a large dataset.

You can completely avoid the regression in performance by using actual functional trasformations. Consider using lodash map chain or equivalent.

In that sense, this particular slowdown has nothing to do with functional programming. Please provide a different example (preferably in another question).

9
  • +1 for pointing out that "yes, there is some extra iteration-related overhead, but its fairly negligible". It really connected all the dots for me. Commented Jun 3 at 16:09
  • "there are a few additional allocations and some unnecessary data transfer, but that's negligible on a large dataset." I'm not very familiar with how JS does things under the hood here. Does each map step require allocating a list (or similar structure) with the same cardinality of the original set? That would be my (perhaps naive) assumption?
    – JimmyJames
    Commented Jun 4 at 15:43
  • @JimmyJames I've left JS 10 years ago, but yes.
    – Basilevs
    Commented Jun 4 at 17:20
  • 1
    @Basilevs If that's the case then it seems to me that those allocations are not negligible on a large dataset. I think it would be the opposite. Allocation of large structures (especially contiguous ones) tend to create more performance challenges that many small, short-lived ones, in my experience with memory-managed runtimes
    – JimmyJames
    Commented Jun 4 at 17:28
  • @Jimmy, one ore two allocations is unavoidable to hold the original data and the final result (unless you implement a streaming API for file reading and JSON parsing). Allocation of a large array is a very efficient operation. Either you run out of contiguous memory or it will be blazing fast (c). JS is notorious for GC lagging with large object count, there is no such problem with object large in size. In other words, it seems like we have different experience :)
    – Basilevs
    Commented Jun 4 at 21:03
2

In software development you don’t care about time complexity but execution time. (Of course execution time is affected by time complexity, but in the end execution time counts).

It’s uncommon that time complexity is affected. Exception is when you look for the first item that meets some condition, and it’s the n-th of m items, and your pipelines take 3m + n steps instead of 4n, and n is always small.

Separate pipelines may add overhead. On the other hand, your pipelines might each consist of highly optimised code that runs faster than your own unoptimised code. So measure. If it’s too fast to measure then obviously it doesn’t matter.

2
  • +1 Oops, forgot about measurement recommendation. I wonder what effect branch prediction has on JS.
    – Basilevs
    Commented Jun 4 at 17:24
  • Apple’s browser has one interpreter and three different compilers to run JavaScript, the last one is the full Clang compiler. So branch prediction would be affected as with any compiled code.
    – gnasher729
    Commented Jun 5 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.