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

151–160 of 419 posts

Re: It Can Happen to You

#151

Post by ThatGeoGuy »

Tyr42 wrote: post #54
jbluepolarbear wrote: post #4

Earlier quoted context omitted.

Looped algorithms generally outperform recursive algorithms.

Goto based algorithms generally outperform looped algorithms. (They're just more general, you can always implement a loop based algorithm using gotos, but not the other way around)

Not exactly. This is more an artefact of language design.

If you convert everything to continuation passing style, then every function call, tail call, recursion, etc. is just as expensive (and expressive) as a GOTO. This is, incidentally, the main "trick" or lightbulb moment in the classic Cheney on the MTA paper by Henry Baker [1].

Now if we're talking specifically in C, then absolutely! But while this intuition holds for C, it's not always true and doesn't have to be always true.

[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...

Re: It Can Happen to You

#152

Post by Xorlev »

sicariusnoctis wrote: post #149
_kst_ wrote: post #127

There's a bigger potential problem with the *scanf() functions than performance. They are inherently unsafe for reading numeric input. For example, if you do something like this: int n; sscanf("9999999999999999999999999", "%d", &n); the behavior is undefined. As the C standard says: > ... the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not a…

> Remember that in C "undefined behavior" [...] means that a conforming implementation can do literally anything. In the worst case, it will do what what you expect until it fails at the most inconvenient possible moment. Actually, the worst case possibility is that your program will become Skynet, enslave humanity for 10000 years, collapse all stars in the universe into black holes, and significantly accelerate proc…

There's probably an npm package for that. :)

Re: It Can Happen to You

#153

Post by ajkjk »

_kst_ wrote: post #127

There's a bigger potential problem with the *scanf() functions than performance. They are inherently unsafe for reading numeric input. For example, if you do something like this: int n; sscanf("9999999999999999999999999", "%d", &n); the behavior is undefined. As the C standard says: > ... the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not a…

Obligatory: it is flabbergasting that this is a quality of language that is still in active use.

Re: It Can Happen to You

#154

Post by ajkjk »

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.

But you'll lose so much time doing that! Realizing there's a bug and investigating it is a huge amount of work compared to never writing it in the first place.

Re: It Can Happen to You

#155

Post by rahimiali »

wruza wrote: post #122
mkl wrote: post #102

Earlier quoted context omitted.

I think your code would be pretty much the same, sscanf, strlen and all. The main differences would be the standard library's implementations of strlen and whatever function you use to read the file into a string in the first place.

str_t json = loadfile(); size_t offset = random(); sscanf(“%d”, ?); With opaque str_t you can’t just json[offset]. Should sscanf take offset with every string (sscanf(fmt, s, off))? Should we copy a slice of json and parse it? Should str_t have zerocopy mirroring ability (s2 = strmirror(s, off, len))? How many of these three are just a snakeoil that changes nothing? It’s only pretty much the same until you try to wri…

You can offset your str_t by creating a new str_t that subtracts offs from the length and adds offs to the pchar. There is no need to keep track of the offset separately.

Re: It Can Happen to You

#156

Post by progre »

loeg wrote: post #129
ironmagma wrote: post #70

Earlier quoted context omitted.

Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ord…

No, that's complete nonsense. Here's the latest revision of the standard: https://www.iso.org/standard/74528.html C has had a well-defined memory model since C11, I believe (re: "ordering of statements").

There is a standard, sure. But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions.

Re: It Can Happen to You

#157

Post by adrianN »

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…

If you replaced the recursion with loops but implemented the same algorithm you'd just have to manage a stack on the heap. I don't think that would be faster.

Re: It Can Happen to You

#158

Post by johnfn »

xconverge wrote: post #110
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.

Agreed, also hey bud, hope you are doing well

Hey, there’s a username I recognize! Long time no see! Same to you :)

Re: It Can Happen to You

#159

Post by ymosy »

telotortium wrote: post #150
chihuahua wrote: post #88

Earlier quoted context omitted.

In principle, that sounds good. But then it can happen that you profiled when N=1000 and it seems fine. Then a few years later (like in GTA), N has grown to 63,000 and it's no longer fine. It seems unlikely the developer will go back and profile it again. Also, I think the original Windows Update algorithm for figuring out which updates you needed to download started out fine, but 20 years later it turns out it's qua…

Do you have a link for the Windows Update algorithm being quadratic?

I believe this is what the parent was referring to: https://arstechnica.com/information-technology/2013/12/expon...
Post reply on HN