On Thursday, 9 July 2020 01:37:37 PDT Artur Czajkowski via Std-Discussion
wrote:
> Then you should correct Thiago Maciera, he is the one that adamantly and
>
> arrogantly states that:
> > " The standard doesn't
> > care if the algorithms rerquired to implement it are quadratic or cubic or
> > exponential. " [Misspelling original]

Accepting the correction. I meant the compiler algorithms, not the standard
library algorithms, but wasn't clear enough when writing it.

This applies to the linker too. In an application I've had to maintain, the
link time grew to 18 hours because the linker uses an (apparently) quadratic
algorithm to search for symbols ("for each symbol processed, search symbol in
the symbol table" sounds O(nē)). This sounds like it could be trivially fixed
to use a sorted table, reducing the link time to O(n log n), or even a hashing
table that could get us close to O(n). But my point is that there's no
constraint in the algorithm that the developers of the linker choose to use to
write their tool. The standard *can't* require them to implement using a
hashing table.

PS: the misspelling is a result of my laptop keyboard having some keys sticky,
so they sometimes repeat-fire.

-- 
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
   Software Architect - Intel System Software Products