Am I reading this wrong, or is std.getopt *really* this stupid?

[Seb]

On Saturday, 24 March 2018 at 05:55:53 UTC, Chris Katko wrote:
> On Saturday, 24 March 2018 at 03:04:41 UTC, Andrei Alexandrescu 
> wrote:
>> On 3/23/18 7:29 PM, H. S. Teoh wrote:
>>> Well, looking at the implementation of std.getopt turned up 
>>> the
>>> disturbing fact that the program's argument list is actually 
>>> scanned
>>> *multiple times*, one for each possible option(!).  Besides 
>>> the bogonity
>>> that whether or not searchPaths will be set prior to finding 
>>> -l depends
>>> on the order of arguments passed to getopt(), this also 
>>> represents an
>>> O(n*m) complexity in scanning program arguments, where n = 
>>> number of
>>> arguments and m = number of possible options.
>>> 
>>> And this is not to mention the fact that getoptImpl is 
>>> *recursive
>>> template*.  Why, oh why?
>>> 
>>> Am I the only one who thinks the current implementation of 
>>> getopt() is
>>> really stupid??  Can somebody please talk some sense into me, 
>>> or point
>>> out something really obvious that I'm missing?
>>
>> Affirmative. The implementation is quadratic (including a 
>> removal of the option from the string). This is intentional, 
>> i.e. understood and acknowledged while I was working on it. 
>> Given that the function is only called once per run and with a 
>> number of arguments at most in the dozens, by the time its 
>> complexity becomes an issue the function is long beyond its 
>> charter.
>>
>> This isn't the only instance of quadratic algorithms in 
>> Phobos. Quicksort uses an insertion sort - a quadratic 
>> algorithm - for 25 elements or fewer. That algorithm may do 
>> 600 comparisons in the worst case, and it's potentially that 
>> many for each group of 25 elements in a large array.
>>
>> Spending time on improving the speed of getopt is 
>> unrecommended. Such work would add no value.
>>
>>
>> Andrei
>
> Is there a possibility of improving this function?
>
>  - While quadratic, for low N, quadratic isn't a big deal. So 
> at what point does quadratic for this function become "a 
> problem"?
>
>  - If it is a problem, what's stopping someone from improving 
> it?
>
> Last question though, is there any kind of list of features, 
> and minor features and fixes that can or need to be done? 
> Perhaps it already exists, but it seems like it'd be great to 
> have a wiki of contribution sites (like this function) that 
> someone could just browse and go "Hey, I know how to do X, 
> maybe I'll take a crack at it." That way, devs who don't have 
> time to improve something "low on the list" could still 
> outsource it in a clear list instead of people who just happen 
> to see it on the forum at the right place right time.

Yes, Bugzilla is full of excellent ideas:

https://issues.dlang.org/buglist.cgi?component=phobos&list_id=220544&product=D&resolution=---

There are even some tags like "bootcamp" for someone who is 
looking to get started:

https://issues.dlang.org/buglist.cgi?component=phobos&keywords=bootcamp%2C%20preapproved&keywords_type=anywords&list_id=220545&product=D&query_format=advanced&resolution=---

We have also recently started to experiment with GitHub's new 
project dashboards. Currently they are tracking projects like 
improving the documentation, @safe-ty, DIP1000 etc.:

https://github.com/dlang/phobos/projects

DMD has a similar set which is based on Walter's recent post [1]

https://github.com/dlang/dmd/projects

Last, but not least there's a "Get involved" guide at the wiki:

https://wiki.dlang.org/Get_involved

As you couldn't find any of these pages, please let us know where 
you looked first, so that maybe we can make it easier for future 
people to find this information ;-)

[1] https://forum.dlang.org/post/p6oibo$1lmi$1@digitalmars.com