Michał did a good job of explaining why I'm not much of a fan of this either. I 
think when it makes sense at all, it is best to have the big-O information in 
module/function docs, where they can be contextualized with their intended 
usage, or at least sit alongside a warning that says something like "always 
benchmark your use case".

Paul

On Thu, Jul 18, 2019, at 6:38 PM, Michał Muskała wrote:
> I'd like to actually argue against this addition. 
> 
> For one — it adds complexity to the documentation - you have to know what the 
> big-O notation means in the first place — I'd argue it will make the 
> documentation less approachable for people without formal CS education. It 
> only becomes worse with some of the more complex data structures that feature 
> "amortised" or "expected" big-O performance. To give just one example - all 
> operations on maps implemented as HAMT are rather complex to express in this 
> notation and would probably need a paragraph if not more to explain.
> 
> Secondly, it might prove problematic in a way that it bounds the standard 
> library not to change those in the future. Changing an implementation where 
> it would affect the complexity of the function could be considered a breaking 
> change. I believe that for that reason, for example, the Rust standard 
> library does not feature such documentation in general.
> 
> But there's also a much bigger issue and that's if this is actually useful in 
> real programs beyond most simple divagations. Modern computers with 
> out-of-order CPU execution, expensive and complex caching mechanisms and 
> other such features mean that the classical notion of big-O notation rarely 
> directly reflects on real-world performance. Even worse if the function at 
> hand allocates - should it also consider the potential impact it could have 
> on garbage collection? There are numerous algorithms that theoretically 
> should be worse, but are much better in practice. I fear that adding such 
> information would lead to people deciding which potential implementation is 
> better just by looking at that documentation instead of benchmarking for 
> their own use case, which is the only reliable method of testing for 
> performance.
> 
> To summarise - I think this will only add additional, superfluous information 
> to the documentation that is of questionable usefulness but that might prove 
> problematic in the future.
> 
> Michał.
> On 19 Jul 2019, 00:01 +0200, José Valim <jose.va...@plataformatec.com.br>, 
> wrote:
> 
>> I like that. Maybe time_complexity / space_complexity for clarity.
>> 
>> 
>> 
>> 
>> *José Valim*
>> 
>> www.plataformatec.com.br
>> Skype: jv.ptec
>> Founder and Director of R&D
>> 
>> 
>> On Thu, Jul 18, 2019 at 11:49 PM Mário Guimarães 
>> <mario.luis.guimar...@gmail.com> wrote:
>>> I would suggest then to have 
>>> 
>>> ``
>>> `@doc time: "O(n)"`
>>> 
>>> and
>>> 
>>> ``
>>> `@doc space: "O(n^2)"`
>>> 
>>> 
>>> to clearly refer to time and space complexity of the function.
>>> 
>>> Mário
>>> 
>>> 
>>> quinta-feira, 18 de Julho de 2019 às 17:36:04 UTC+1, Mário Guimarães 
>>> escreveu:
>>>> Hi, 
>>>> 
>>>> I find this can be useful in selecting the collections and their 
>>>> manipulating functions to be used in our code.
>>>> 
>>>> The case is that in an immutable language it may not be evident what is 
>>>> the O(...) of the insert, read, update, delete and sort, in our 
>>>> collections.
>>>> 
>>>> For example, what is the complexity of sorting an immutable enumerable via 
>>>> `Enum.sort`? I really do not know.
>>>> 
>>>> This could be documented with a table at the start of the documentation 
>>>> for the collection.
>>>> 
>>>> This effort could be decomposed in as many issues as the number of 
>>>> collections to document.
>>>> 
>>>> Experienced people may know many of these Big-O details, but for 
>>>> newcommers to Elixir (and Erlang) it could be very helpful.
>>>> 
>>>> Thanks
>>>> Mário
>>> 

>>> --
>>>  You received this message because you are subscribed to the Google Groups 
>>> "elixir-lang-core" group.
>>>  To unsubscribe from this group and stop receiving emails from it, send an 
>>> email to elixir-lang-core+unsubscr...@googlegroups.com.
>>>  To view this discussion on the web visit 
>>> https://groups.google.com/d/msgid/elixir-lang-core/7e570c16-9cbc-44af-a42b-18b4f39f2742%40googlegroups.com
>>>  
>>> <https://groups.google.com/d/msgid/elixir-lang-core/7e570c16-9cbc-44af-a42b-18b4f39f2742%40googlegroups.com?utm_medium=email&utm_source=footer>.
>>>  For more options, visit https://groups.google.com/d/optout.
>> 

>> --
>>  You received this message because you are subscribed to the Google Groups 
>> "elixir-lang-core" group.
>>  To unsubscribe from this group and stop receiving emails from it, send an 
>> email to elixir-lang-core+unsubscr...@googlegroups.com.
>>  To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4%2BX2LWZ2Z4xDxa67ovo8rtWOJjVqc_8oy5ukWoE-kiZCg%40mail.gmail.com
>>  
>> <https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4%2BX2LWZ2Z4xDxa67ovo8rtWOJjVqc_8oy5ukWoE-kiZCg%40mail.gmail.com?utm_medium=email&utm_source=footer>.
>>  For more options, visit https://groups.google.com/d/optout.
> 

> --
>  You received this message because you are subscribed to the Google Groups 
> "elixir-lang-core" group.
>  To unsubscribe from this group and stop receiving emails from it, send an 
> email to elixir-lang-core+unsubscr...@googlegroups.com.
>  To view this discussion on the web visit 
> https://groups.google.com/d/msgid/elixir-lang-core/70b115b3-2d8b-4e61-a837-0a7a224b4ef8%40Spark
>  
> <https://groups.google.com/d/msgid/elixir-lang-core/70b115b3-2d8b-4e61-a837-0a7a224b4ef8%40Spark?utm_medium=email&utm_source=footer>.
>  For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to elixir-lang-core+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/elixir-lang-core/9cb4596a-7b83-42de-b75c-ddefcff5dbe6%40www.fastmail.com.

Reply via email to