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.