Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

It Can Happen to You

mattkeeter.com

Post reply on HN
Print view View original

11–20 of 419 posts

Re: It Can Happen to You

#11

Post by beaconstudios »

decasia wrote: post #5

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…

personally, I think I wouldn't even bother to check the algorithmic complexity of every external function I call. I'd just use the logical choice (like sscanf) and only consider optimising if things started to slow down and profiling the application highlighted it as a bottleneck.

Re: It Can Happen to You

#13

Post by astrea »

It has been a hot minute since I've touched C, so I'm failing to grok the issue here. Sscanf is reading the data variable for a float-formatted string into a float variable. How is that also getting the size? What is different about strtof? It looks from the docs that it does something similar, just without using the formatting string.

Re: It Can Happen to You

#14

Post by decasia »

beaconstudios wrote: post #11
decasia wrote: post #5

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…

personally, I think I wouldn't even bother to check the algorithmic complexity of every external function I call. I'd just use the logical choice (like sscanf) and only consider optimising if things started to slow down and profiling the application highlighted it as a bottleneck.

Yes, I absolutely think profiling and then only optimizing the actual problems is always a sound choice.

I don't check the docs for every library function I use. I'm just saying, it wouldn't hurt if, when you do read the docs for standard library functions, the algorithmic complexity was mentioned in passing.

Re: It Can Happen to You

#15

Post by tux3 »

The moral of the story, as far as I'm concerned: do NOT parse strings in C! Use a library, prefferably in a higher-level language.

C string handling is a mess of viciously surprising APIs, juggling those particular footguns is almost certainly not your least bad option.

Re: It Can Happen to You

#16

Post by edflsafoiewq »

astrea wrote: post #13

It has been a hot minute since I've touched C, so I'm failing to grok the issue here. Sscanf is reading the data variable for a float-formatted string into a float variable. How is that also getting the size? What is different about strtof? It looks from the docs that it does something similar, just without using the formatting string.

> sscanf() converts the string you pass in to an _IO_FILE* to make the string look like a "file". This is so the same internal _IO_vfscanf() can be used for both a string and a FILE*.

> However, as part of that conversion, done in a _IO_str_init_static_internal() function, it calls __rawmemchr (ptr, '\0'); essentially a strlen() call, on your input string. This conversion is done on every call to sscanf(), and since your input buffer is rather large, it'll spend a fair amount of time calculating the length of the input string.

https://stackoverflow.com/a/23924112

Re: It Can Happen to You

#17

Post by xirbeosbwo1234 »

I don't think anyone sensible would claim they would never have made this mistake. It's not even surprising that it made it to production. What is surprising is that it lead to a massive and easily-diagnosable slowdown that no one bothered to fix for several years.

Re: It Can Happen to You

#18

Post by kazinator »

jchw wrote: post #8

It is a good opportunity to mention that you should not use strtod/strtol either if you can help it, since they are impacted by locale. Exactly what to use instead is a bit of a tough nut to crack; you could extract musl’s floatscan code, or implement the Clinger algorithm yourself. Or, of course, use programming languages that have a more reasonable option in the standard library...

I see you are reiterating this point raised in the previous discussion several days ago, but I don't thing it is particularly well grounded.

ISO C allows strtod and strtol to accept, other than in the "C" locale, additional "subject sequence forms".

This does not affect programming language implementations which extract specific token patterns from an input stream, which either are, or are transformed into the portable forms supported by these functions.

What the requirement means is that the functions cannot be relied on to reject inputs that are outside of their description. Those inputs could accidentally match some locale-dependent representations.

You must do your own rejecting.

So for instance, if an integer token is a sequence of ASCII digits with an optional + or - sign, ensured by your lexical analyzer's regex, you can process that with strtol without worry about locale-dependent behavior.

Basically, rely on the functions only for conversion, and feed them only the portable inputs.

Re: It Can Happen to You

#19

Post by astine »

elseweather wrote: post #12
rectang wrote: post #2

Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.

...which makes it a classic exercise for teaching memoization!

And now your memory usage will grow eye-wateringly large. Instead, convert the algorithm to be iterative or at least tail-recursive and it will be faster than both the naive and memoized versions!

Re: It Can Happen to You

#20

Post by karamazov »

astine wrote: post #19
elseweather wrote: post #12

Earlier quoted context omitted.

...which makes it a classic exercise for teaching memoization!

And now your memory usage will grow eye-wateringly large. Instead, convert the algorithm to be iterative or at least tail-recursive and it will be faster than both the naive and memoized versions!

Or use the closed-form solution.
Post reply on HN