[OT] parsing with sscanf is accidentally quadratic due to strlen

[Simen Kjærås]

On Wednesday, 3 March 2021 at 11:09:04 UTC, Patrick Schluter 
wrote:
> On Wednesday, 3 March 2021 at 09:12:19 UTC, Kagamin wrote:
>> Parsers based on sscanf choke on big strings: 
>> https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/
>> Source: 
>> https://github.com/chakra-core/ChakraCore/blob/master/pal/src/safecrt/sscanf.c#L47
>
> Yes, sscanf() calls strlen(). I got bitten by it also some 
> years ago when I memory mapped some log files to parse and had 
> the my program hog the CPU when I went in production. On my 
> test files that were not that big, memory mapping and changing 
> fscanf() to sscanf() was a no brainer. When it went in 
> production and started to map megabytes or gigabyte sized 
> files, I rediscovered what a O(n²) algorithm looked like...

Dawson’s first law of computing: O(n^2) is the sweet spot of 
badly scaling algorithms: fast enough to make it into production, 
but slow enough to make things fall down once it gets there.

(https://twitter.com/BruceDawson0xB/status/1120381406700429312)

--
   Simen