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

[Andrei Alexandrescu]

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