How do you think about time complexity while working with Elixir and other Declarative languages?

With SQL, it is mostly about having the right indexes. You can see what the database does by running it with explain, analyse, etc selected. You can paste the results into sites like this to get a "better” view. Edit: a resource on SQL indexes

In Elixir, I tend to think in terms of data structures and the most efficient way to transform/run an algorithm over them. There is an efficiency guide for Erlang.

Thanks for the insight. I will read the guide.

I think it’s fine to think procedurally in Elixir. “Functional” programming is more about the declarative style and the focus on data structures to me, but otherwise any language is procedural in the end. There is only one instruction executed at a time, that inherits the environment and variables of the instructions executed before.

That is, in a single process. Mutiple process problems are rather about correct concurrency patterns and less about time complexity.

I agree we can always think procedurally. But won’t it be great to have a language to talk about time complexity Functionally. A system of that is derived purely from Lambda Calculus where we don’t have to worry about steps of execution.

I’m not sure, it seems to me that lambda calculus has infinite CPU speed and infinite memory, but I’m not really sure what you are looking for besides the traditional big O.

But I hope someone else, more versed into those kind of things, will chime in

The irony is that those languages are declarative, too, if we’re being pedantic. You’re not telling the computer what steps to follow, you’re telling the compiler what effects you want to have on the C/C++ abstract machine which is very much different from what the CPU will execute (mainly by the “as-if” rule).

C++ defines a program’s observable behavior as its interactions with volatile and library I/O functions, allowing any optimization that does not change those interactions (including their order). The compiler is thus free to rewrite your Bubble sort as a Merge sort if it were to somehow recognize that pattern, and for simple patterns (e.g. something that looks like a memcpy or memset) it often does. In fact there have been many security issues arising from the fact that the compiler has optimized away a memset that lacked an observable effect as defined by the standard, necessitating functions like explicit_bzero to get around that.

In any language, including C and C++, you need to have a model of execution to reason about time complexity. I grant that the model is generally simpler for procedural languages, especially given how the transformations usually don’t affect more than constant-factor operations, but you can apply largely the same to functional languages by reasoning about unavoidable work.

e.g. to sum all the elements in a list, every element must be visited and therefore the operation is O(N). To retrieve an item from a :gb_sets, you have to traverse a binary-tree structure and therefore the operation is O(log N). And so on.

Elixir is also simpler than other functional programming languages in that it’s based on Erlang, which defines every function everywhere as side-effecting because of tracing, which precludes all optimizations that would be visible when tracing is enabled (e.g. you cannot remove a function call that provably does “nothing,” because it would disappear from the trace), so @lud is quite right in that you can “reason procedurally” about time complexity in Elixir.

That’s interesting, TIL. Where can I read more about that?

The Erlang run-time system exposes several trace points that allow users to be notified when they are triggered. Trace points are things such as function calls, message sending and receiving, garbage collection, and process scheduling.

The compiler respects all trace points that it has control over, and as such cannot perform even the simplest of optimizations that would affect tracing, like removing a redundant function call, unused parameters, ignored return values, and so on^[1].

1. Technically we could try to maintain the illusion when tracing is enabled for the specific function that was opitimized away, but the maintainability trade-off is the epitome of “not worth it.” It’s far more involved than it first appears. ↩︎

What problem are you solving?

For context: I came to Elixir for two reasons:

1. Seamless and low-effort and correct parallelism;
2. Not having to think of how will the work be done, I want to say what I want done. A classic example is Enum.map; the stdlib / compiler decide how it’s going to be done, you only are saying “I want each element of this list be transformed”.

That was my reason to start using the language. If not for those I could have just easily stayed with Java and Go and then learned Rust as it gained momentum (which I still did).

Reading your comment, I cannot intuit your intent. Do you want to write a competing compiler? Are you suffering from optimisation paralysis and are convinced all Elixir code is slow? Do you want to have better tracing / flame graphs?

Perhaps you’re thinking about (lazy evaluation)[ Lazy evaluation - Wikipedia ], where time complexity can sometimes be difficult to ascertain. This is true in any programming language that has “lazy” features (for example streams in Elixir), but is a particularly well known problem in Haskell (which is entirely lazy-evaluated by default).

SQL implementations are not lazy-evaluated per se, but their declarative nature can hide the procedural steps that will happen when you fire off the query, and for sophisticated query optimizers in RDMSs like Postgres, it’s sometimes hard to reason about what steps will be taken. You can use the EXPLAIN to see how the query planner will run the query.

In my experience, unless you’re using streams, everything is explicit in Elixir. You know exactly which lines are going to run when, sequentially, even when using recursion. However it’s true that it is a much more declarative style than python or C for example, and this can lead to some confusion because it doesn’t “feel” like you’re giving explicit steps, even though you really are. Procedural feels much more recipe-like, like you’ve got your hands in the mixture, whereas functional programming can feel more like you’re doing something abstract without steps, even though this is not the case.

There are some further nuances, obviously, linked to concurrency (which can rapidly boggle the mind when multiple things are going on, and especially in shared_memory languages like Python or C), but Elixir helps a lot with this thanks to the message passing architecture which makes concurrency a lot more easy to reason about. But I digress..

I think it’s quite easy to confuse the more declarative style of Elixir (and SQL), with the idea of laziness. Yet these are separate concepts.