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

171–180 of 419 posts

Re: It Can Happen to You

#171

Post by gnyman »

mkeeter wrote: post #27

Blog author here! Thanks to HN for warning me about sscanf at exactly the right time – within a day of me trying to load some ASCII STLs and noticing it was slow... Linked deep in the Twitter replies [1], there's an open glibc issue about this, dating back to 2014: https://sourceware.org/bugzilla/show_bug.cgi?id=17577 C doesn't have any requirements on the complexity of sscanf, so it might not be a bug per se, but it…

Thank you for introducing me to the concept/term Ascetic programming. Not sure how widely used it is, but I find it more fitting for what I try to do than minimalistic or KISS.

Also, it is great to see someone write

  > I noticed that ASCII STL loading was really quite slow.
  > From startup to showing the window, it took over 1.8 seconds!
I always find pleasure seeing projects which highlight just how fast modern computers really are.

Re: It Can Happen to You

#172

Post by protontorpedo »

It's impossible to know all the pitfalls, and the author notes that. Metrics (or - ugh - telemetry if it's client-side), as well as automated testing with expectations around performance can go a long way to prevent these issues. Of course, ideally everyone should think about how their code performs with large input, but everyone messes up every now and then.

Re: It Can Happen to You

#173

Post by virgilp »

lostcolony wrote: post #146
nyanpasu64 wrote: post #137

Earlier quoted context omitted.

Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.

Fair point; I'm confusing my terminology. Analogy and realization still holds.

Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.

Re: It Can Happen to You

#174

Post by est31 »

CGamesPlay wrote: post #72
johnfn wrote: post #32

Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.

And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.

The cppreference page linked by the blog post has been changed since: https://en.cppreference.com/w/cpp/io/c/fscanf#Notes

> Note that some implementations of sscanf involve a call to strlen, which makes their runtime linear on the length of the entire string. This means that if sscanf is called in a loop to repeatedly parse values from the front of a string, your code might run in quadratic time

Re: It Can Happen to You

#175

Post by namibj »

Jyaif wrote: post #147
adrianN wrote: post #128

Earlier quoted context omitted.

There is no general solution to deciding whether a program is O(n^k).[1] So either your static analysis won't know the answer for some programs or report a wrong bound, or report a ridiculous overestimate. [1] https://cstheory.stackexchange.com/questions/5004/are-runtim...

Can you point me towards some source code where a human can't find the algorithmic complexity?

Once you leave primitive recursive functions[0], reasoning quickly becomes very non-trivial.

[0]: https://en.wikipedia.org/wiki/Primitive_recursive_function

Re: It Can Happen to You

#176

Post by loeg »

ncmncm wrote: post #164
ironmagma wrote: post #136

Earlier quoted context omitted.

> ISO-C11 specifies 203 circumstances that cause undefined behaviors. 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation…

A good argument for compiling your debug builds with "-fsanitize=undefined".

Sure, or use Rust! Rust is great! We can criticize C for its faults without making baseless claims.

Re: It Can Happen to You

#177

Post by CamperBob2 »

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.

Everybody in this thread seems to be missing a particularly large elephant in this particular room, which is that sscanf() supports scientific notation while strtod() and strtof() do not.

Or at least, they didn't originally support it.

Has this been fixed in the 20+ years since I noticed it and started using sscanf() everywhere instead?

Re: It Can Happen to You

#178

Post by albertzeyer »

I think I would argue that both in this case and in case of GTA, sscanf is actually to blame. Surely, by profiling, this could have been detected, and workarounds are simple. But sscanf doesn't need to be so slow. A naive implementation of sscanf would not be slow. So I think it is perfectly fine to assume that scanf should only take constant time to parse sth like numbers (obviously not "%s").

Re: It Can Happen to You

#179

Post by smallnamespace »

Jyaif wrote: post #147
adrianN wrote: post #128

Earlier quoted context omitted.

There is no general solution to deciding whether a program is O(n^k).[1] So either your static analysis won't know the answer for some programs or report a wrong bound, or report a ridiculous overestimate. [1] https://cstheory.stackexchange.com/questions/5004/are-runtim...

Can you point me towards some source code where a human can't find the algorithmic complexity?

Humans can't tell you whether this program will run forever on any particular (positive integer) input, or whether all inputs terminate.

  def collatz(n):
      while n != 1:
          print(n)
      if n % 2 == 0:
          n = n // 2 
      else:
          n = n * 3 + 1

      print(1)

Re: It Can Happen to You

#180

Post by iamevn »

desertrider12 wrote: post #140
beaconstudios wrote: post #6

Earlier quoted context omitted.

does that hold for languages/compilers with tail call optimisation?

This isn't really related to your question, but I don't think tail calls could help for Fibonacci since f(n) branches to two calls, f(n-1) and f(n-2). And each of those branches into 2. So it can't be done in a finite stack area with naive recursion. The compiler would either have to memoize, or be extremely clever and start at the base case (0, 1) and then transform the code to use the 2x2 matrix exponentiation. I w…

Wouldn't this be the recursion version with tail calls?

  (define/contract (fib n)
    (-> nonnegative-integer? nonnegative-integer?)
    (let fib-recur ([i 1] [curr 1] [prev 0])
      (cond [(= i n) curr]
            [else (fib-recur (+ i 1) 
                             (+ curr prev) 
                             curr)])))
Post reply on HN