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

291–300 of 419 posts

Re: It Can Happen to You

#291

Post by layer8 »

TeMPOraL wrote: post #208
beaconstudios wrote: post #11

Earlier quoted context omitted.

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.

I personally would, if it was listed in documentation. Doing stuff and profiling later is the right general approach to performance optimization. But what's better is not doing stupid mistakes in the first place, if they are trivial to avoid. To achieve that, you need to know the complexity guarantees of functions and data structures - or at least their ballpark (like, "this could be O(n) or perhaps O(n logn), defini…

It might still not help in he case of sscanf. The documentation would specify that it’s O(N) in the size of the input string, just what one would expect without deeper thought. The problem is not O(N), the problem is that N is the complete input string, not just the part being parsed. The documentation would have to include a big fat warning about that.

Re: It Can Happen to You

#292

Post by gnyman »

gnyman wrote: post #171
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 comp…

Re-read my comment and to be clear, the quote and the last paragraph are not related. The last sentence was meant to refer to the Erizo project as a nice single purpose high performing tool, not as a comment to the bug that made it slow.

Re: It Can Happen to You

#293

Post by account42 »

beaconstudios wrote: post #227
ajkjk wrote: post #154

Earlier quoted context omitted.

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.

No, spending time optimising areas of the code that will never become bottlenecks is the waste of time.

This is how you get software where everything is just fast enough to be tolerable but still annoyingly slow.

Re: It Can Happen to You

#294

Post by oblio »

kaba0 wrote: post #219
tdeck wrote: post #10

This just makes me think that null-terminated strings are the bad gift that keeps on giving. If we were to design an OS, language, or standard library in 2021 (or even 1999) we probably wouldn't use them, but we're stuck with this relic of a former era.

The thing is, they are even worse for performance than string implementations that store the length.. that extra few bits of memory is much cheaper than checking the size of a string everywhere. For example, copying a string with known length. Also, c++’s strings even do some clever hacking where they store the text itself for shorter strings in the pointer, barring a pointer lookup. And this is possible only because…

They were designed when an extra byte or so per string cost you a lot of money. Nowadays, when 99% of the systems anyone will program start at 1MB RAM and 90% probably start at 512MB, they're a liability for almost no benefit.

Re: It Can Happen to You

#295

Post by MaxBarraclough »

acqq wrote: post #264
TeMPOraL wrote: post #199

Earlier quoted context omitted.

You're joking, but now I'm thinking about the XML we parse at work and the library we're using to do it. We parse a lot of it, but I've always had this vague feeling that it takes a bit too long (given the codebase is C++). The XML library we use is rather well-known, so if someone found a bug like this there, I'd suspect a general improvement of performance across the board in the entire industry. Efficient Market H…

It's possible. I've personally reduced the time spent for reading huge XML file on the startup of an application at least 10 times in the application I was in charge of, by avoiding the library dependence and writing a custom code. Having a lot of experience in such kinds of code and in the performance issues, it was quite a fast change with no negative effects. The prehistory of that was simple: up to some point the…

I'm reminded of a 2008 article, Why is D/Tango so fast at parsing XML? [0]

One of the main factors seems to be that a lot of XML parser libraries, even the high-profile ones, did a lot of unnecessary copy operations. D's language features made it easy and safe to avoid unnecessary copying.

I wonder what became of that Tango code.

[0] https://web.archive.org/web/20140821164709/http://dotnot.org... , see also reddit discussion where WalterBright makes an appearance, https://old.reddit.com/r/programming/comments/6bt6n/why_is_d...

Re: It Can Happen to You

#296

Post by beaconstudios »

account42 wrote: post #293
beaconstudios wrote: post #227

Earlier quoted context omitted.

No, spending time optimising areas of the code that will never become bottlenecks is the waste of time.

This is how you get software where everything is just fast enough to be tolerable but still annoyingly slow.

No, not paying attention to performance at all is how that happens. Optimising all your code in advance is just being frivolous with your time.

Re: It Can Happen to You

#297

Post by TeMPOraL »

thaumasiotes wrote: post #269
heavenlyblue wrote: post #267

Earlier quoted context omitted.

> Strings are immutable, so in theory it could easily be the case that any two equal Strings must share their machine address, even if you got them from user input. Hey, and now you have two problems: String hashing and finding all strings which are equal to each other in memory

Well, no, the whole point of this discussion is that solving the second problem means the first problem never comes up. And this isn't exactly some exotic approach; how often do you think people write Hashes in Ruby where the keys they use are all symbols? It's so common that there's dedicated syntax for it.

It's as old as Lisp, but there's a reason symbols exist separately from strings - they're used differently. Strings are frequently transformed, symbols almost never are. String are frequently taken from end-user input, symbols very rarely. Strings sometimes are very large, symbol names are almost universally very short.

The problem is, interning is an expensive operation. It means adding to an ever growing database of strings, but first checking if the string isn't already there. You don't want to do that every time you change case or flip a letter in a string, or use it to access a hash table. I'm not saying it can't be done, but I honestly have no idea how to implement sane, generic, automatic interning of strings. I feel more comfortable having a symbol type, and control over turning strings into symbols.

Re: It Can Happen to You

#298

Post by steerablesafe »

TeMPOraL wrote: post #201
thaumasiotes wrote: post #184

Earlier quoted context omitted.

> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.

I'm guessing GP means the complexity guarantee sidesteps the complexity of the hashing function. It probably doesn't matter all that much in typical case - I'm guessing 80-90% of hash map use is with very short strings.

Well-written complexity guarantees specify the operations they count. Otherwise sorting in O(n log(n)) also "sidesteps" the cost of comparison too.

Re: It Can Happen to You

#299

Post by jedimastert »

Quick question: At the top of the parser they define

  const char VERTEX_STR[] = "vertex ";
And a few lines in

  data += strlen(VERTEX_STR);
Would parsers optimize this out? Seems like an easy win to replace that with a "7" (or a constant or something), although I don't know how much of a win it would be.

Re: It Can Happen to You

#300

Post by geon »

perl4ever wrote: post #78
tux3 wrote: post #15

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.

I used to work for people that processed emails and loaded them into databases with perl scripts. One day someone asked me if I could help, because the script they were running on a batch of emails was inexplicably freezing or running out of memory, I forget the exact details. There were maybe a few thousand or tens of thousands of emails, and so, I came to look at the issue with my usual attitude which is that if it…

The other week I optimized some processing in a web app from 3 minutes to 11 seconds.

The customer was ecstatic, but I still think it is 2 orders of magnitude too slow.

Post reply on HN