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

411–419 of 419 posts

Re: It Can Happen to You

#411

Post by randomswede »

mcguire wrote: post #390
nyanpasu64 wrote: post #137

Earlier quoted context omitted.

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

Something that is amortized complexity: vector.push(x) Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when it runs out of space, it's amortized O(1).

Or triple, or quadruple. Or even (IIRC) "increase by 50%" (but, I would need to sit down and do the actual math on that). But, doubling a number is cheap and more conservative than quadrupling (the next "cheap" multiplier).

Re: It Can Happen to You

#412

Post by randomswede »

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.

P = NP for "P == 0" and/or "N == 1".

Re: It Can Happen to You

#414

Post by layer8 »

hyperpape wrote: post #333
layer8 wrote: post #289

Earlier quoted context omitted.

That would likely break backward compatibility of existing implementation-defined behavior.

Converting sscanf from undefined to implementation defined behavior would, by definition, not break implementation defined behaviors. There are real cases where removing undefined behavior blocks optimizations, but this doesn't feel like one.

Implementations can define behavior for undefined behavior. The difference to implementation-defined behavior is that for the latter implementations MUST define some behavior (from the set of options specified by the standard), whereas for undefined behavior they don’t need to.

If an implementation has defined some behavior for sscanf undefined behavior, and then the standard defines a different behavior, then the existing implementation would become nonconforming, and an updated version of the implementation would be not backwards compatible with the existing one. That’s why such changes to the standard can be problematic.

Re: It Can Happen to You

#415

Post by jl2718 »

Seems to me that the problem is the use of text formats in general. I understand the need for universality, but all it would take to solve this is for major OS vendors to ship with a clean simple HDF5 editor. I would also like to see a binary UI description format become a web3c standard, because, good luck trying to eliminate all the quadratic strlen in web services.

Re: It Can Happen to You

#416

Post by mooreds »

flukus wrote: post #126
mooreds wrote: post #96

Earlier quoted context omitted.

My fav optimization story: A few years back, I was doing some geographic calculations. Basically building a box of lat/lngs and getting all the points within that box. It was slow. Weirdly slow. I made sure the lat and lng of the records were in the index, but it was still slow. More testing revealed that the way I was passing the lat/lng into the query was causing those values to be converted to strings, which were…

At least that was an accidental conversion and an understandable mistake, I've seen the same with dates stored as strings from devs unaware that dates are just integers with a lot of maths to make them meaningful. At once place our end of month billing was getting slower and slower over the course of months, from one hour out to about twelve and it had to baby sit and run in batches in order to not bring the whole da…

Whoa, that's an awesome story. Nuts that the slowdown happened over such a short period, must have been a fair amount of data running through that system. Lots of table scans .

Re: It Can Happen to You

#417

Post by koalahedron »

koalahedron wrote: post #395
ctoth wrote: post #207

Earlier quoted context omitted.

Seriously the most I have laughed in like 6 months. Which probably says a lot more about me than this joke. I know that jokes aren't really welcome on HN, and I generally really like this policy. But just had to mention this was just ... what I needed to read right now.

> I know that jokes aren't really welcome on HN IMO, while I really don't come to HN to find dial-a-joke, or joke-of-the-day, I think some humor is essential in modern life. Since we're talking about Matt Keeter, you will find he has a great sense of humor if you read his website or interact with him. Some of his jokes are ROTFL funny, but subtle.

Even greater is someone understanding my own sardonic sense of humor and putting it to good use.

I did have a nice half round of golf today with my wife. What a beautiful day to spend with such a wonderful person!

I'm out.

Re: It Can Happen to You

#418

Post by thw0rted »

toyg wrote: post #266
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 unlikely the library has this problem Any sufficiently-complex library code likely has plenty of problems, often unavoidably so (e.g. trade-offs between best performance and edge cases). Whether they have been found or not is a function of many, many factors. > Efficient Market Hypothesis I've lived long enough to be very sceptical about that sort of thing. Markets tend to be efficient in aggregate , maybe, bu…

There's a variant / corollary of the Efficient Market Hypothesis here, though.

Let's say the GP's XML library has The GTA Bug, i.e. it uses a quadratic-performance loop when parsing. The bug will go undiscovered until any one consumer of the library a) sees enough performance impact to care, b) has the expertise to profile their application and finds that the library is at fault, and c) reports the problem back to the library owner so that it can be fixed. This combination might be unlikely but since only one consumer has to have all those properties, the probability scales inversely with the number of library users.

Re: It Can Happen to You

#419

Post by IggleSniggle »

Chyzwar wrote: post #408
IggleSniggle wrote: post #349

Earlier quoted context omitted.

I live in js land, and the barrier between “folklore” and “documentation” is extremely thin. Especially since V8 may introduce changes at any time that affect performance characteristics of js. I’d respond with “well if performance matters it shouldn’t be in js” except for all the shite being written in js these days, with js being the hammer that makes everything else look like a nail.

V8 documents these changes very well[1]. You can write very fast JS code. When carefully written it can have Java like performance[2]. It is just very hard in practice where most ecosystem is optimized for developer productivity. When performance matter, write your own code and carefully benchmark everything. You can see this working for Typescript and VSCode[3] [1] https://v8.dev/blog [2] https://benchmarksgame-team…

My understanding is that when written carefully, it can have Go-like performance.
Post reply on HN